PARC NEST Project

DISTRIBUTED ADAPTIVE CONSTRAINED OPTIMIZATION

Palo Alto Research Center (PARC) has engaged with the DARPA Network Embedded Software Technology (NEST) project from April 2001 to April 2006. The project has evolved in the direction guided by shifts in the NEST project objectives. For the first 2 years, PARC mostly followed the original Statement of Work (SOW), working on the three areas: 1) complexity analysis of constraint-based systems, 2) adaptive solvers according to the complexity of the problems, and 3) distributed solving that decomposes a complex problem into hierarchies. For the last 3 years, PARC’s focus was on components for sensor networks, in particular, constraint-based routing and self localization, and their component-based architecture for modeling and simulation. In addition, PARC has been leaders on routing and modeling mini-tasks and developed simulation environments for performance comparisons among algorithms developed by NEST groups.

I. Constraint-based Routing 

I.1 Message-initiated Constraint-Based Routing (MCBR)

We proposed MCBR, a general message specification mechanism to explicitly encode the routing destinations, constraints and objectives in messages, so that generic-purpose instead of objective-specific or destination-specific routing strategies can be applied [CCNC04]. The separation of routing specifications and routing strategies makes it possible for exploring meta-routing strategies, allowing quality-of-service (QoS) requirements at the application layer for individual messages. MCBR were implemented and demonstrated in TinyOS.

I.2 Learning-based Meta-routing Strategies

We developed a set of distributed routing strategies based on real-time reinforcement learning.

In particular, three types of meta-strategies are proposed: real-time search, constrained flooding, and adaptive spanning tree [WQoSR04]. All of these use the same reinforcement learning core, which estimates and updates the cost from the current node to the destination. The contribution of this work is twofold: first, the use of MCBR for QoS specification, and second, the introduction of learning-based meta-strategies. The details of these three strategies were presented in various papers:

·        Real-time search  [AAAI04] passes the packet to the “best” neighbor according to the estimates

·        Constrained flooding  [AINA06] decides if and when to rebroadcast the packet according, to the cost estimates

·        Adaptive spanning tree  [CCNC06] forwards the packet to its parent, with parents possibly changing over time due to mobility or node failure.

This approach has a number of attractive properties:

·        Explicit use of destination and QoS specifications for finding optimal routes

·        Automatic adaptation with different routes when network conditions change

·        No need for extra maintenance packets

·        No infinite looping if a path to the destination exists.

In addition to the above meta-strategies, ant-based routing strategies (i.e., based on ant colony optimization mechanisms) [Ant04] were developed  which improved the existing basic ant strategies for network routing. Learning-based routing strategies have also been applied to information-directed routing (IDR) [OptBook06], which demonstrated significant improvements over previous algorithms for this application.

I.3 Radial Coordination and Minimum-time Convergecast

Convergecast is a common communication pattern across many sensor network applications featuring data flows from many different source nodes to a single sink node during a very short time window. Convergecast in wireless ad hoc network requires proper coordination among the nodes to avoid high packet collision rates near the sink node. We developed a coordinated convergecast framework [EmNeTS-I, MilCom05] for achieving high convergecast reliability and studied the effectiveness of packet aggregation and duplication within this framework.

A guarantee on packet delivery and a bound on convergecast latency are highly desirable in mission critical applications, e.g., surveillance and security.  We developed a minimum time TDMA schedule [ICDCS06]. The important contributions of our work include the following:

1.      Distributed convergecast scheduling algorithm for tree networks that requires at most max(3n_k-1, N) timeslots. Here, N represents the number of nodes in the network and n_k represents the maximum number of nodes in any subtree.

2.      Distributed convergecast scheduling algorithm that requires at most 3N timeslots in any network. Simulation results show that the number timeslots required is about 1.5N.

3.      A bound of two on the number of packets that are required to be buffered at a node during convergecast. This result is significant considering the fact that sensor nodes have a limited amount of memory.

4.      A sleep schedule for nodes that conserves at least 50 percent of the energy spent in convergecast. This result is important considering the limited amount of energy available at sensor nodes.

I.4 Comb-Needle: Efficient Query Model

We investigated efficient strategies for supporting on-demand information dissemination and gathering in large-scale wireless sensor networks. In particular, we proposed a “comb-needle” discovery support model [SenSys04] resembling an ancient method: use a comb to help find a needle in sands or a haystack. The model combines push and pull for information dissemination and gathering. The push component features data duplication in a linear neighborhood of each node. The pull component features a dynamic formation of an on-demand routing structure resembling a comb. The comb-needle model enables us to investigate the cost of a spectrum of push and pull combinations for supporting discovery and query in large scale sensor networks. Our result shows that the optimal routing structure depends on the frequency of query occurrence and the spatial-temporal frequency of related events in the network.

I.5 Minimum Power Configuration

Many wireless sensor networks must aggressively conserve energy to operate for extensive periods without wired power sources. We proposed a novel approach called minimum power configuration (MPC) [MobiHoc05], that minimizes the aggregate energy consumption in all power states. In sharp contrast to earlier research that treated topology control, power-aware routing, and sleep management in isolation, MPC provides a unified approach that integrates them as a joint optimization problem in which the power configuration of a network consists of a set of active nodes and the transmission powers of the nodes.

I.6 Routing Modeling Application Simulation Environment (Rmase) and Component-based Routing Architecture

We developed Rmase [INSS06], which consists of a network topology generator, an application scenario generator, and a set of performance metrics. The topology generator is based on a topology model that allows one to create networks with a variety of topologies, from rectangular to triangular grids, from regular to random networks, and networks that are either uniform or have holes. The application generator can create peer-to-peer (one-to-one), multicast (one-to-many), or convergecast (many-to-one) routing application scenarios, and can specify the properties of the source(s)/destinations(s), such as type -- static, dynamic (changing from time to time), or mobile (moving while routing), rate, center, radius, percentage, and speed (for dynamic or mobile source/destination). The performance model generates statistics of various routing metrics, including latency, throughput, success/loss rates, energy consumption and efficiency, as well as network life-time prediction. Rmase also supports a layered routing architecture, which advocates the sharing and reuse of common routing components. Rmase has been successfully used to model existing applications, to develop new routing algorithms and to analyze performance tradeoffs of the existing routing algorithms for given applications and performance requirements.

II. Self-localization Algorithms and System

II.1 MDS-MAP

We developed MDS-MAP [MobiHoc03, TPDS04] for node localization in sensor networks. The heart of the MDS-based localization is multidimensional scaling (MDS), a data analysis technique that transforms proximity information into a geometric embedding. The kernel of the MDS-based localization algorithm MDS-MAP(C) consists of three steps:

1.      Compute the shortest path distance between all pairs of nodes. A distance matrix is obtained where each entry is the shortest estimated distance (path distance) between two points.

2.      The distance matrix is used to approximate the Euclidean distance. Apply MDS to the distance matrix, retaining the first two (or three) largest eigenvalues and eigenvectors to construct a 2-D (or 3-D) relative map.

3.      Transform the relative map to an absolute map using the known positions of anchor nodes if available. One of the advantages of MDS is that it still produces a useful relative map in cases where there are no anchor nodes with known absolute positions.

For uniformly deployed sensor nodes (e.g., a grid deployment), this method works very well. For irregular sensor placement, the distance matrix no longer approximates the Euclidean distance well. MDS-MAP(P) solves this problem by building local maps and patches them to form a global map. MDS-MAP(P) has shown to work very well for irregular types of deployment.  For both MDS-MAP(C) and MDS-MAP(P), a refinement step can be added. The refinement step uses the position estimates of nodes in the MDS solution as an initial solution, then applies the least-squares minimization to improve the match between the measured distance and the distances in the solution.

The advantage of MDS-based localization is that it works well with few anchor nodes (or in the extreme case, without anchor nodes). The disadvantage is that it does not work well for irregular networks with concave connectivity (even with MDS-MAP(P)); the refinement step is generally slow; and the solutions are subject to local minima. 

II.2 Sequential Active Method (SAM)

There has been a lot of work on localization for sensor networks. Most localization schemes assume an already-deployed network. Very little research has been done for active sensor deployment with mobile robots. We developed a distributed sequential localization process [PCAC06] which is tightly integrated with robotic sensor deployment. Being location-aware, sensors can be placed in advantageous locations to avoid big localization errors. In turn, the accurate localization result helps further sensor deployment. We compared our distributed sequential localization scheme with five existing localization algorithms, both through simulations and through repeated runs on a mote testbed. Results show that the distributed sequential localization algorithm produces comparable results to the state-of-the-art centralized localization algorithms.

II.3 Iterative Least Square (ILS)

We developed a novel iterative method for node localization [MobiHoc06]. At each iteration, nodes are localized using a least-squares based method. The computation is lightweight, fast, and any-time. At the core of our iterative localization method is an error control mechanism to control error propagation and accumulation during iterations. We have proposed an error registry to actively select nodes that participate in the localization. Simulation results have shown that the active selection strategy significantly mitigates the effect of error propagation. The proposed approach has also been tested on a small network of Berkeley Mica2 motes with ultrasound time of arrival (TOA) ranging devices. We have compared with more global methods such as MDS-MAP and the SDP-based algorithms in both simulation and real hardware. The proposed iterative localization method has achieved comparable performance in both cases. At the same time, it enjoys good scalability properties since it is fully distributed and uses only local knowledge.

II.4. Radio Interferometric Positioning System (RIPS) Localization Algorithm

RIPS was developed by Vanderbilt University for node localization. The technique relies on a pair of nodes emitting radio waves simultaneously at slightly different frequencies. The relative phase offset of this signal measured at two receivers is a function of the distances between the four nodes involved. The advantage of RIPS is that it does not require any sensors other than the radio used for wireless communications. The disadvantage is that it requires new localization algorithms to solve the localization problem.

We developed a localization algorithm using RIPS inputs. Similar to ILS it is an iterative algorithm with anchor selection. It requires at least three anchors within a quadrilateral, where a quadrilateral is defined to be four nodes with two independent measurements. For each free node, it searches a quadrilateral with “best” three anchors. If it exists, a free node will be localized and becomes the pseudo-anchors. Such computation propagates until all nodes are localized. The advantage of this method is that it is very efficient. The disadvantages are: 1) it needs at least three anchors for 2-D, (more for 3-D), within a quadrilateral, 2) there is the problem of error propagation for large networks even with anchor selection. The algorithm has been tested using two data sets given by Vanderbilt. It worked really well on one but failed localizing the other due to not enough data/connections.

II.5 System of Tracking and mapping (STAM) and Component-based Architecture

A variety of self-localization algorithms have been developed for wireless sensor networks. Each algorithm has its own application scenario, which makes it hard to compare different localization algorithms. STAM  [Wireless04] has been developed for dealing with the challenge of comparing different localization algorithms for sensor networks.  STAM defines a common localization API (extension to Calamari) with different types of inputs. STAM provides a GUI for creating, saving and loading localization data sets, selecting components and algorithms, and showing performance metrics. STAM also supports a three-layer localization architecture for plug-and-play common pre and post localization components. Many data sets have been created in STAM, by drawing and batch generating. It also includes real data from various sources (e.g., acoustic data from UIUC, ultrasound data from PARC). An increasing list of localization algorithms and components has been developed. STAM has been used to develop new localization algorithms, to analyze performance, and to select the best localization algorithm for a given application.

STAM has been created initially as a robotic assisted map building for search and rescue applications. It has been tightly integrated with PARC's ultrasound motes through TinyOS PC/Matlab interface. With that interface, STAM has real-time localization and tracking capabilities using a closed feedback loop between data collection and localization.