OVERVIEW

Sensor diversity enables a method for determining and reducing sensing uncertainty. Now, since sensing uncertainty arises from limitations associated with physical configuration of sensor network nodes, then physical reconfiguration in the form of articulation, mobility, and the distribution of new sensing assets is required for reducing uncertainty.  However, this then creates the requirements for systems that combine sensor diversity based self-awareness to enable coordinated mobility for measurement of sensing uncertainty and methods for effecting its reduction.

The relocation of sensing assets may be in rapid response to a triggering event that results from physical phenomena directly or model-based analysis of phenomena. This exploits progress in multi-robot operations, however, with the new features of NIMS constrained and precise mobility. This is enabled by reactive coordinated mobility. However, the NIMS system may also proactively probe the sensor network environment to determine the spatio-temporal regions where sensing uncertainty is expected to be large. This forms a proactive coordinated mobility operating regime.

A domain specific application applies to the problem of detection of mobile objects (sources) in natural environments. For example, acoustic sensors may typically be deployed in environments where acoustic propagation is highly variable with source-sensor range, terrain foliage, and meteorological conditions. Yet, it is at the same time required that detection of sources remain effective throughout these variations. Figure 1 illustrates an example where acoustic sensors are able to detect that sources have moved through their area, however, due to obstacles to sensing, these acoustic sensors are not able to support detection of an important large aggregation of sources.  A combination of both event detection and an awareness of sensing uncertainty level produce a trigger for reactive coordinated mobility of mobile sensors and redeployment of nodes. Figure 1 illustrates that coordinated mobility enables a potentially drastic advance in performance by optimizing sensor population and position with both mobile nodes (imaging devices with powerful viewing perspective) and redeployed sensors. In this example, a static node acts as a trigger and the system is able to physically relocate sensing assets to acquire data at higher resolution and diversity at the trigger location.

Examples of proactive coordinated mobility include those where mobile nodes may analyze historical data (obtained via sensor diversity algorithms) and realize that particular areas are mapped with less certainty, causing them to revisit those areas at higher frequency until they are better mapped. Another reason for opportunistic motion is exploration, where in the absence of triggers from the static sensors on the ground, the mobile nodes proactively explore their configuration space, to detect phenomena of interest. For example, it is a general occurrence that in situ sensors may not successfully detect features of interest (i.e. acoustic sensors may not detect sound sources or chemical sensors may not detect compounds for which they are sensitive.) However, of course, it cannot be concluded by the system that the lack of sensor signals means that no sources are present – they may simply be occluded by current environment conditions or be unexpected with respect to initial sensor deployment. Thus, proactive exploration of the sensing space is essential for establishing performance. Here, proactive coordinated mobility provides a constant background probing of system performance and at the same time surveying for unanticipated events and sources. Without this, the distributed sensor system may detect, at best, only those sources that were expected prior to deployment.

The underlying problem in coordinated mobility for any distributed actuated system is the selection of actions at the individual node level such that the entire system performance is optimized, or at least improved. Typically performance is measured using a task-specific objective function. The problem of action selection is known as Task Allocation.

Task Allocation (TA) is the problem of assigning available resources to tasks. There are two major subdivisions: offline and online. The offline TA is the problem of assigning resources to different tasks if certain information (e.g. the distribution of task arrival times, relative task priority) is known a priori. The assignment process proceeds offline. The offline TA problem, in its most general form, is equivalent to the conjunctive planning problem, which is NP-Complete.

Our focus here is on online task allocation. In online TA, all information about the tasks becomes available only upon task arrival. The assignment of resources to tasks must be computed in real time. It has been shown in literature [1] that greedy algorithms provide good approximate solutions to online TA. It has also been shown [1] that in some cases the greedy online TA solution is within a bounded limit of the optimal solution obtained by offline TA. Following the model in [2], we think of task assignment occurring in decision epochs. A decision epoch is a period of time during which only the tasks which have arrived since the end of the previous epoch are considered for assignment. Increasing the decision epoch to infinity converts the online TA into the offline TA problem. We model the NIMS system as an online TA problem, since it is designed for real-life autonomous field applications in dynamic environments.

The proposed system differs from the TA approaches developed previously. Our system relies on a static network, and communication, sensing and computation are distributed. The motivation for this system derives from the need to efficiently sample the entire environmental space. As has been discussed in the Introduction, it is impractical to deploy enough fixed sensors to achieve required sensing fidelity. As will be shown, the system combining fixed and mobile nodes enables efficient sampling. TA becomes the primary driver of efficient data collection in this system, since it allows the user to select a portion of the environment for sampling, as opposed to sampling the entire environment. In addition, TA manages system resources, so that resources are not consumed unless assigned most effectively.

APPROACH

Methodology
The general online TA system functions in the following way. Suppose at a given decision epoch the system maintains a set of resources R = {r1, ..., rn} and tasks T = {t1, ..., tk}. Tasks are prioritized based on a criterion C. C is an application dependent function and can combine such

parameters as task arrival time, task importance, etc. A set of assignments A = (l = min(n,k): {a1, ..., al}) is computed as follows.

where t is the next unassigned task according to C and U(r_j, t) is the j-th resource utility value for accomplishing t. The assigned resource and corresponding task are removed from R and T respectively, before the next assignment. The utility function is chosen to be application and resource dependent. In our model, once assigned, resources cannot be reallocated. After a resource has completed its task it becomes available for a new assignment. In the terminology of [3] we adopt a commitment strategy as opposed to opportunism.

The system consists of a mobile node suspended on a cable and a static sensor network. We assume that the network is predeployed where each node knows its location in a global coordinate system. The network monitors the environment for events of interest (motion, change in light intensity, etc). The problem then is to prioritize the events, and drive the mobile node to a vantage point from which a particular event is better observed. Once the node arrives, the local phenomenon is measured. In TA terminology, a robot is a resource and a detection by a sensor node of an event requiring perusal by a robot is a task.

Figure 2 shows two network topologies that we define - positioned on the ground (the 2D-case) and more generally, in the volume surrounding the transect (the 3D-case). In order for TA system to plan node's motion the goal points should lie in the transect plane. Hence, we project the nodes locations onto the transect plane. As a result we get a set of points on a line l (2D-case,

Figure 2a) or a plane Pi_r (3D-case, Figure 2c), both of which lie in the transect plane. In the 2D-case, l is the line where the transect plane intersects the ground plane. Since, the mobile node cannot move along that line, we translate l to a parallel line l_r on the transect. We define the projection function in the 2D-case PROJ_lr and 3D-case PROJ_Pir.

Based on tasks projected locations TA divides the transect into slices (2D-case, Figure 2b), or generally cells (3D-case, Figure 2d). With every projected node k we associate a cell C_n. Note that a 2D system is sometimes preferred because it is easier to setup in the field and for some applications a 2D perspective is enough. As an example, consider studying sunlight intensity shining through a forest canopy. In this case a sensor network with illumination detectors can be placed on the ground. Suppose node k discovered an interesting reading (say an abnormal light value). The TA system then would guide the robot towards the goal point on l_r computed by PROJ_lr. The mobile node then can study appropriate slice C_k. The general 3D-case system is investigated in this paper.

The Task Allocation System

Our system consists of two algorithms - one running on the robot and another within the network. First we describe the algorithm that runs on every static node. It consists of two parts - Task

Generation and Task Management.

1. Task generation. If node's sensor reading is above a threshold a task is created and a notification message NEW_TASK is broadcasted. The notification message contains the notifying node's ID, location, sensor reading, and time stamp (time when the task was generated).

1. Task management. Each node maintains a set of currently active tasks T_a and non-active tasks T_na. If a node receives NEW_TASK message and the task is new (it is neither in T_a nor in T_na) then T_a is updated and the message is redirected to the network several times. As we discuss later, when the robot fulfills its assigned task it sends a TASK_DONE message containing the id of the node that generated the task and task's time stamp. If the task is in T_a, then it is removed from T_a, added to T_na and the message is redirected to SN several times.

Note that in practice the sizes of T_a and T_na are fixed (20 and 30 in our experiments). Both sets can be overwritten, so where is no overflow problem. At the same time, the size of T_a should be set with care to avoid loss of data about currently active tasks and potentially failing to propagate this data to the rest of the system.

Our system is a special case of the TA methodology described above - with only one resource (mobile node) for task assignment. Consider task assignment Equation 1. Since there is only one mobile node, the next task with highest priority (according to criterion C) is assigned to the mobile node, no matter what the mobile node's utility function might be. The task prioritization criterion selected here is C based on the time stamp associated with every task. The algorithm running on the mobile node is as follows.

All incoming new tasks (specified by NEW_TASK message) are sorted according to the criterion C (tasks with smaller time stamp get priority - a FIFO policy) and stored in a set of currently active tasks T_a. When the mobile node becomes available for reassignment, the task of highest priority is extracted from T_a and assigned to it. Next, based on the task information the mobile node needs to compute a goal point. If the task's position is p then the goal position will be PROJ_lr(p) in 2D-case and PROJ_Pir(p) in 3D-case (see Figure 2). After the robot completes its last task it sends a TASK_DONE message containing the id of the sensor node that generated the task and task's time stamp.

The TA algorithm computes projections of the static network onto the transect and separates the transect into slices (in the 2D-case) or more refined cells (in the 3D-case). This is the cornerstone for Event-Aware Adaptive Sampling Algorithm discussed next.

Event-Aware Adaptive Sampling

The proactive coordinated mobility, or the adaptive sampling approach is designed to capture static phenomena with an adjustable level of accuracy. On the other hand, consider a dynamic scene when the phenomenon to be observed changes spatially and temporally. If this change is faster than the time it takes adaptive sampling to complete, the algorithm would not obtain a correct result - the final ''sensor picture'' will consist of superimposed phenomena.

Methodology

Suppose the task is to observe a dynamic phenomenon P which changes rapidly in time (Figure 3a). Thus, P consists of {p₁, p₂, ... p_n}. One solution is to deploy many high fidelity sensors so that every point of the environment is sampled. This is impractical. Consider a hybrid approach where a large number of static low-fidelity sensors capable of detecting p_i are used in conjunction with the mobile NIMS node which carries the high fidelity sensor. The adaptive sampling algorithm can then focus on a portion of a transect containing p_i that TA system provides. As shown in Figure 3b, the sensor network effectively discretizes the environment, allowing to localize p_i and limit the adaptive sampling to a part of the transect. Note that multiple nodes can detect the same phenomenon p_i For simplicity we assume that only the node with highest sensor reading of the phenomenon detects it. In principle, there are two ways to address that problem. One is to let the mobile node cluster tasks and then create a combined slice of the transect to run the adaptive sampling. Another way is to let the SN locally determine the cluster, and the 'leader' of the cluster will create a combined task.

Event-Aware Adaptive Sampling System

The following describes the Event-Aware Adaptive Sampling (EAAS) Algorithm:

1. TA module monitors the environment for new tasks;
2. If unassigned tasks set T_a ¹ 0, TA assigns the robot to the next task in order, say task t;
3. TA determines the appropriate goal position and a corresponding transect cell as discussed in previous section;
4. TAdelivers the robot to the computed goal position of the cell to sample;
5. TA sends request to the adaptive sampling system with (x, y, z) of the center of the scan and dimensions of the scanning cell;
6. TA system pauses, while monitoring the environment for new events;
7. The adaptive sampling scans designated area, returns to TA (sends AS_DONE_MSG);
8. TA sends TASK_DONE message into SN containing id of the node that generated the task and task's time stamp;
9. TA resumes. Repeat;

In summary, when a node detects a phenomenon (sensor reading reaches a predetermined threshold) it notifies the SN and the mobile node. We say that a task is created. The notification message contains the node ID, its location and the sensor reading. Given this information we can use the TA algorithm to assign robot to the task, navigate the robot to that task and start the adaptive sampling on a limited cell provided by TA. Figure 3c shows nodes that detected phenomena of Figure 3a and created corresponding tasks.

Results for Event-Aware Adaptive Sampling

Both Task Allocation and Event-Aware Adaptive Sampling use a notion of a task. In the following experiments we will compare the cumulative task OnTime across all tasks, over the duration of every experiment. Each task's OnTime is computed as the difference between the time the task was turned off by a Robot (TASK_DONE} message is sent) and the time the task was detected by one of the nodes of the network.

A network of 6 Mica2 Motes was predeployed in a test environment with predetermined coordinates. We use the general 3D topology. Hence, by knowing nodes locations and computing nodes' projections onto the transect plane, the TA algorithm produces a subdivision of the transect similar to Figure 1d.

Task Allocation vs. Raster Scan:

Experiments were conducted comparing Task Allocation(TA) methods with conventional Raster Scan methods. The Raster Scan method scans every point of the transect with a specified resolution. When the Raster Scan reaches the location of an event it clears it by sending TASK_DONE message. Raster Scan method proved to be prohibitively low in performance.In particular, experimental results showed that at the maximum NIMS-LS spatial

resolution of 1 cm, with a sampling dwell time of 1 second at each location, OnTime results were dramatically inferior to TA methods.Raster Scan method was also characterized at reduced spatial resolution of 5cm with a corresponding improvement in response time. This however, is still inferior to TA algorithm described in this paper.

In this experiment an artificial event is first generated on a remote server. Then the server sends an event message to the node designated for task generation and the node proceeds as if this event was detected by the node's sensor. For this experiment, schedules of 3, 5, 7, 10 and 20 events were drawn (in time) from a Uniform distribution to arrive within 600 seconds, with uniformly distributed nodes that detected the event. Note that for actual applications we do not expect to receive/process more than 1 - 10 events in 10 minutes on average. Hence the case of 20 events shows the behavior of the system at the limit.

Figure 4a shows experimental results comparing OnTime performance of TA and Raster Scan. The number of events varies between 3 and 20. Both algorithms were evaluated from 3 different starting positions of the mobile node on the transect (drawn from a Uniform distribution). The results were averaged. As can be seen from the graph, TA performs 9-22 times better on the entire interval of 3-20 events. Note also that TA is stable, as indicated by error bars, and hence is favored for use in this application since it provides reduced bounds on system run time over Raster Scan method.

In addition to response time comparison, it is also important to compare mobility requirements for TA and Raster Scan methods. Specifically, the use of mobility requires energy. Thus, this can be computed and compared for each method. Now, when the density of the events is low, the TA algoritm enables the mobile node syste to remain in a static position for extended periods - ' 'in between events' '. This occurs when it has serviced all events that have arrived and is awaiting new events. Raster Scan, however, forces the robot to move constantly. Hence this method will

consume far greater energy and mobility resources than TA. A measure of energy for mobility is determined for the purposes of comparison by computing the total time of mobile node motion. Figure 4b shows comparison of energy consumption in units of time-in-motion between TA and Raster Scan. As expected, TA outperforms Raster Scan significantly. However as the number of events increases to infinity, the TA should approach Raster Scan energy consumption. Also note, that on interval [5, 20] the slope of the Raster Scan curve is very small and the energy consumption is insensitive to event arrival rate.

Event-Aware Adaptive Sampling
The introduction of Event-Aware Adaptive Sampling produces a potential dramatic improvement in event response time. Thus, in this section the results of measurement of task OnTime is described for the system using the Event-Aware Adaptive Sampling (EAAS) algorithm.

It is important to note that adaptive sampling does not provide an accurate sampling of the scene if the frequency of events is such that events arrive at a rate greater than the time required for adaptive sampling to complete. But if the event frequency will be sufficiently low then on average every task OnTime will be approximately the same. Hence, it suffices to compare the results for OnTime of only one task.

This experimental characterization was performed using light intensity variations to induce events (exactly as occurs in natural environment conditions.). The mobile and fixed nodes form a network. Also, each node is equipped with a light intensity sensor as deployed on the mobile node. Here, a node generates an event when the sensor sampled value exceeds a threshold.

The task OnTime performance of adaptive sampling is 20524 seconds and 577 seconds for EAAS. Hence EAAS significantly outperforms adaptive sampling (with an improvement by a factor greater than 35). This dramatic advantage of EAAS results from its ability to determine the location of the task, deliver the mobile node to the proper location, and then reduce the scan area requirements for the adaptive sampling module by focusing attention on the proper event region.

ACCOMPLISHMENTS

The project accomplishments include:

1. A Task Allocation system is designed for NIMS, which drastically improves the performance of the system.
2. TA also enables study of dynamically changing phenomena.
3. Research papers based on the current work:
   > Maxim A. Batalin, Mohammad Rahimi, Yan Yu, Duo Liu, Aman Kansal, Gaurav S. Sukhatme, William J. Kaiser, Mark Hansen, Gregory J. Pottie, Mani Srivastava, Deborah Estrinl, “Towards Event-Aware Adaptive Sampling Using Static and Mobile Nodes”, CENS Technical Report #38

FUTURE DIRECTIONS

In future work we are going to experiment with application specific utility functions, and research the effects of such functions on system performance.

The other direction of research will be focused on designing TA algorithms for NIMS systems consisting of multiple transects, further improving the overall performance and the applicability of the system.

PEOPLE

Faculty:

Prof. Gaurav S. Sukhatme
Prof. William J. Kaiser

Graduate Students:

Maxim A. Batalin