Overview

As we have gained experience with prototype wireless sensor networks (WSN) in environmental monitoring applications, we have recognized the need for these systems to also serve interactive users in the field. This interactive capability arises at all stages of the system life cycle, from design debugging, to deployment testing, and ongoing system health maintenance, as well as for data visualization and analysis in the field in order to support the collection of and correlation with manual observations. At the same time it is critical to minimize the impact of such interactive use with the ongoing activities with which the system is tasked.

The two system requirements that emerge from this interactive, in-the-field, usage scenario are the need for a data tasking and routing architecture that supports mobile and transient queries, as well as a host of data analysis and visualization tools to assist the scientist. This section describes the design and performance of the system support, and we leave the discussion of data tools to future work. We will use examples from our experiences deploying and using WSNs for environmental monitoring at James Reserve, however we are confident that these techniques have broad applicability. The system, which we call Hyper, has the following features key to supporting mobility: fast neighborhood assessment and efficient tree convergence to offer a mobile user low latency access to a network; multiple collection tree support for concurrent use by several mobile users and a fixed collection microserver; support of lonely mote clouds (when routes intentionally do not exist for long periods until mobile users connect to them). Hyper has also been integrated with DTN for reliability in the face of disconnection.

Approach

For both scientific exploration and basic maintenance an ideal routing scheme for James Reserve would allow new nodes to join a network quickly (so that a user doesn't have to stand and wait), would support multiple independent routing trees simultaneously for networks with concurrent fixed and mobile users. In addition it would allow application scientists to go into the field, get quick access to sensor data services, deploy new sensors and get results from them quickly, and even perform calibration experiments in realtime. And it would do all this while burdening the network as little as possible.

For these reasons we have identified the following WSN usage scenarios:

• Users remain in each location for several minutes. Technicians go to a location to add a new node, add new sensors, or change batteries. Users go to a location to verify data, annotate data, or to directly monitor stimulus/response. These tasks are all short-lived relative to the duty-cycled, latency-insensitive data gathering style of many existing systems. The chief concern in supporting this sort of behavior is in providing a connection to the mote network as quickly as possible.
• Even when moving, users rarely switch transmission domains. Radio links are on the order of 50m. After working with a node a user typically moves to a neighboring node.
• Connectivity is not necessary during periods of mobility. Infield users interact with nodes while seated near those nodes. The only reason for movement is to relocate near other nodes. Disconnections caused by large movements are not problematic or undesirable because sensor data services aren't typically needed during transition. Data that is stuck in-network due to the user moving somewhere else can either be dropped in-network, or be stored until a connection is re-established, depending on the user's tolerance for delay. This aspect of the usage scenario is very different from cellular connectivity or mobile IP, where the technical challenge is in maintaining a connection that provides timely delivery through a series of hand-offs and where disruptions in the connection are always undesirable.
• Disconnected operation of sensor nodes is a common case. Some deployment sites are so remote that it is not cost effective or even possible to construct a multiple-hop routing tree to a permanent microserver-class collection sink. For these lonely cloud deployments, sensor nodes must store the information they collect until a user acting as a data mule can get close enough to them to establish network connectivity and offload that data.

Because mobile users are particularly latency sensitive; thus establishing a connection quickly is important. To connect by mote radio to the WSN, Hyper provides three services designed to set up an efficient and unobtrusive connection with low latency: fast neighborhood evaluation, fast tree formation, and routing support for multiple sinks.

When a mobile sink arrives at a new location, it initiates neighborhood evaluation by sending out a series of link beacon packets, each of which causes one-hop neighbors to respond with a packet. The mobile sink and its one-hop neighbors can estimate the quality of the links that connect them after only a few iterations of this "call and respond."

Once neighborhood connectivity is assessed, the link layer alerts the routing software that the fast link convergence stage has completed. Once neighborhood connectivity is established and evaluated, Hyper builds a collection tree. The time it takes for tree convergence to occur is proportional to the depth of tree desired, but for most trees it takes only about a second. The tree routing algorithm forms a tree with minimum path costs. Path cost is the sum of the individual link costs that make up a path. Thus, an efficient tree can only be constructed if a good estimate of link cost can be established.

For efficiency, the tree formation algorithm defers evaluating a routing control packet for a time proportional to the cost advertised within it. In this manner, useful control packets advertising good routes will be considered before those that advertise bad routes. The consequence is that radio use will be decreased; control packets advertising poorer routes will not propagate.

The sink initiates tree formation by transmitting a tree update message. Tree update messages contain the transmitter's address (to be used as the parent in the routing tree), the address of the root, the path cost, an epoch number to distinguish new updates from old ones), a TTL used to limit the depth of the tree, and a time indicating when to expect the next update. A node that receives a tree update message waits to evaluate it for an amount of time proportional to the cost of the link over which the update came. It sets a "wait timer" for this purpose. If before the wait time expires another update arrives (from a different node, but pertaining to the same sink) then the two are compared in terms of the path qualities they offer; the update message containing the better path is retained. Once the wait timer expires, a node broadcasts its own update message containing its best path cost to the sink. Good paths propagate quickly, while poor paths propagate slowly, or not at all. In the event that no update packets are lost, and each node's link estimates are accurate then the tree that is built will be a minimum spanning tree, and each node will only send out one update message.

Using cost-dependent delays is an optimization made popular by Scalable Reliable Multicast. A tree with the same path qualities could be formed without this optimization, but would be less energy-efficient, as more messages would be transmitted. Without the optimization, a node would receive updates from its neighbors and process them in an order that has little relation to the qualities of the paths they advertise. The control traffic overhead of maintaining a tree is one packet per node per update period. The longer the update period, the smaller will be the impact of control overhead on network lifetime. However, a longer update period also increases the amount of time, on average, it will take to fix a route when a link truly does break (such as when a node fails, moves, or when there are significant and sudden environmental changes)

In Hyper, route formation and maintenance is initiated by the root, path costs are strictly increasing with depth, and each node keeps track only of its parent for each tree to which it belongs. As a result, loops cannot form.

There are potentially multiple simultaneous, independent users that want access to the network; Hyper thus supports multiple concurrent sinks. However the number of sinks is expected to be relatively small compared to the number of data source nodes. In the network, each tree is maintained independently. Therefore, multiple trees is supported by a node by expanding the management state for a single tree into an array of state. It is expected that each node will connect only to a few routing trees, thus limiting the state recorded in a mote's RAM. This increase in state does not consume too significant a portion of the mote's limited RAM.

Each state structure contains the ID of the root node, the next hop along the path to the root (i.e. the parent), and the route cost. The structure also maintains an indication of whether the route is active so as to hide trees from the application that are in the process of forming, the time when the route will next be advertised, and a time after which time tree should be dismantled if no control messages are received in the interim.

Since each tree is managed independently, the update messages for more than one tree are never aggregated into a single packet. Although doing so would reduce routing control overhead, it would complicate tree formation. First, combining messages would interfere with the route construction protocol's reliance on delays. Hyper's timing property that reduces the number of control messages each node sends would no longer hold. For this reason, combining control messages would either lead to building inefficient trees (and hence, spending more energy on collecting data) or potentially could cause nodes to send many more control messages, which again wastes energy. Second, it might lead to routing loops and other persistent incorrect routing state.

Transport over an alternate routing structure such as an any-to-any multicast tree might reduce redundant transmissions when multiple users request the same data. However, we determined that forming this sort of routing structure, determining which data requests are shared, and scheduling multicast transmissions was too complicated and error prone for resource-constrained mote networks with severely limited debugging visibility.

Systems/Experiments

UCLA's Mildred E. Mathias Botanical Gardens collects several different botanical habitats into a relatively small region, combining varying topography with interesting ecology. It sits on over 7 acres of land, and is home to several species of tropical and subtropical plants. Our goal is to try to capture how temperature and humidity vary over the garden. To this end, we've deployed 11 static sensor nodes and two mobile sensor nodes, each equipped with temperature and humidity sensors. The static sensor nodes provide a general overview of the garden. The mobile sensors satisfy two purposes. First, they can be used to zoom in on a particular geographical region in order to capture spatial variability that the static sensors cannot capture. Second, by placing a mobile sensor next to a static sensor it is possible to check how well the one sensors is calibrated with respect to the other, and how much noise the actual sensing hardware is introducing into the sensor readings themselves.

Our sensing system consists of three parts. First are the nodes that are equipped with sensors themselves (both static and mobile). These nodes are connected to temperature and humidity sensors. However, the distance between sensor nodes, combined with the dense foliage of the garden makes communication difficult. The second component of our system is a set of nodes that are devoted to acting as repeaters. They don't do any environmental sensing (although they do report there current battery voltage, which is useful for maintenance planning) but serve only to create a richly connected communication topology. The final piece is a microserver where all the data is collected.

Once we were collecting lots of sensor data reliably, we analyzed the data to try to understand which static sensors were good predictors of other static sensors. We identified two “cliques” of sensor nodes that formed contiguous regions. Using our mobile sensors we were able to collect data from those regions that are near the interface of the two cliques.

Our initial deployment ran into sever communication problems that were unlike any previous habitat monitoring deployments we had done. Poor connectivity necessitated deploying several repeater nodes, but we had only a rough idea of where to place them. In order to limit the time spent in trial-and-error repeater placement we employed two techniques. First, we used a handheld computer to survey various locations in the garden to get an idea of connectivity. Second, we over-deployed repeaters throughout the garden in order to ensure a connected network. At its peak, the garden had 34 nodes. From this we collected route an link statistics and established which repeaters where helping to form a network backbone, and which were largely superfluous. Once the backbone was identified we pruned the number of repeaters. This process was greatly expedited by using tools that support fast convergence of newly deployed nodes.

We've begun to develop statistical models based upon the data collected that predict what the temperature is at a point in the Botanical Garden, in addition to a confidence in the prediction. Using the mobile sensors we will be able to enhance the model by providing data from a greater set of points than our static sensors would otherwise provide. In addition, the mobile sensors allow us to check our predictions in order to validate our model.

Accomplishments

We have designed, constructed, and deployed a novel sensor network routing protocol that in initial testing has proven to be an improvement over it predecessor in ESS. We have futher used that hyper-based system to begin research in developing statistical models for guiding sensor placement for improved data collection in an embedded sensor network.

Future Directions

We will continue to use the hyper routing protocol as a foundation for continued assessment of new statistical model development. It’s performance will also be contrasted with the new centroute routing protocol (described in the adjacent section).

People

Graduate student: Tom Schoellhammer

Faculty: Miodrag Potknojak, Deborah Estrin