Wireless Sensor Network Abstraction – IDSQ

In continuing my research into wireless sensor networks, I found another programming abstraction called IDSQ. Information Driven Sensor Query (IDSQ) is a routing protocol in which a node can determine which node it should route data through based on acquiring incremental information that is worth more than the cost of the energy consumed in achieving it. The technique has been used in real world applications with positive results. You can see more at this site.

In a nutshell, IDSQ chooses a node as the “leader” which then takes available information and develops a “belief system.” From this it determines which node might be the next best one to investigate (say a node it believes is closer to the measurement to be made), and then passes its information to that node and declares it to be the new leader. The new node repeats the process. The first node goes back into an idle state.

The key to a robust sensor network is the right tradeoff between performance and scalability. One could take all the data from the network and centralize it, but this would not scale up. One way to handle large networks of nodes is to create groups of nodes and then deal only with those nodes. For object tracking a geographical grouping of nodes makes sense.

The algorithm is as follows:

1. The nodes sit in idle mode but wake up to sense any change in the environment.
2. If a change is detected then a leader node is elected (the one with the best sense of the change detected).
3. The leader node creates a “belief state” which contains the best known information at the time.
4. The leader node creates a group of nodes to collaborate with and disables other nodes from becoming leader.
5. The leader node propagates the belief state to the next best node and passes “leadership” status to it.

Since most nodes sit in an idle state making occasional detections, this state must be energy-efficient for the nodes.

This technique is not without its challenges. Some networks may elect multiple leader nodes as the information propagates throughout the system. Through a series of messages, a leader node can try and suppress other groups from forming.

This technique works well with object tracking because the nature of the application focuses on a subset of the nodes in a group. As the object moves through the network, the “leader” node can pass its information along to other nodes without having to rely on a centralized repository of information.

It’s not clear from the research how efficient this mechanism is or how well it performs in a real-world scenario. In this paper the authors apply statistical models to compensate for common errors in sensor networks using IDSQ techniques. By using probabilistic models, they hope to reduce the amount of data acquisition the network must perform.

Best regards,
Hall T.

Wireless Sensor Networks – Abstract Regions

In today’s post we look at another Wireless Sensor Network programmatic structure called Abstract Regions. You can see more here. Abstract Regions seeks to handle the low-level communication that goes on between neighboring nodes – tracking neighbor lists, sharing attribute values, and analyzing the results. Regions can be defined based on geographic area, radio communication links, or other attribute properties.

Unlike central networks which can perform algorithms across the entire network of nodes, wireless sensor networks decentralize the control and allow each node to communicate only with its neighbors. This decentralized control requires a new set of spatial operators to handle communication, data caching, and data reduction.

The first step in building up this programming abstraction is neighbor discovery. Nodes send out broadcast messages and then build up a neighbor list by capturing the signal strength and direction of neighboring nodes. A “region” of nodes is then declared based on number of hops, geographical positioning, RF signal strength, or some other mechanism. Attributes and their value pairs are then shared among the nodes in the region. Finally, the data is analyzed across the region either by bringing the data to a central node or hub, or propagating the data through a tree-like structure and analyzing at each steps along the tree.

Applications for Abstract Region programming include edge detection, object tracking, environmental monitoring, and more. One advantage of it is that it allows for multiple programs to run on a single set of wireless sensor nodes. In this paper the concept of “scopes” is raised. Scope defines a group of components (i.e. a set of nodes) and limits the visibility of messages sent within groups. Scope can be applied in a descriptive manner, for example defining those nodes that can measure temperature data or in a deployment manner—defining those nodes that are close to each other geographically.

Scoping uses a set of selection rules that define which nodes belong to a group and which do not. This is more complicated than it seems since nodes can be mobile and can drop out of a group based on battery failure or weak signal strength.

One of the major advantages of scoping is that it limits messages to only those nodes relevant to it. Since wireless sensor nodes are resource limited to begin with, limiting their usage is a key consideration.

Abstract regions work well on applications such as object tracking in which one must examine a set of nodes (those near the object) and compare their information. Abstract regions provide a region-based collective communication interface.

In this paper the researchers create a programming model called Kairos which aggregates nodes together into a logical unit. Kairos uses shared memory-based parallel programming models. It provides three programming constructions: shortest path routing, localization, and object tracking. For localization and object-tracking applications, the researchers reported a 2x increase in performance over other wireless sensor networks.

In conclusion, clustering nodes either logically or geographically simplifies the programming challenge in building wireless sensor networks.


Best regards,
Hall T.

Hood – a Neighborhood Abstraction for Wireless Sensor Networks

Another Wireless Sensor Network middleware technique is called “Hood” which is short for Neighborhood. In this paper from Berkeley, the authors describe how Hood can simplify application programming. Instead of using neighborlists, data caches, and messaging protocols, Hood aggregates a cluster of nodes and lets the programmer treat them as one entity. It abstracts away the details of data caches and messaging protocols and lets nodes share and view attributes of neighboring nodes.

The user defines the attributes to be shared and the membership criteria. The Hood software takes over and keeps track of related nodes and their attribute values. This alleviates the user from having to program the search for attribute values and related nodes.

Hood uses a broadcast/filter mechanism for data sharing and neighbor discovery. Receiving nodes filter through the broadcast data to see which neighbors and which of their attributes should be cached. The receiving node or “observing” node determines who is in its neighborhood, rather than the broadcasting or “owner” node. When a node updates its attribute values, this is pushed to the neighbor nodes which can choose to update their data cache or delete it. This provides a “reflective” memory of those nodes’ attribute values. Hood is implemented in nesC on the TinyOS platform.

Efficiency of the network can be tuned based on the “push policy” in so far as how much data and how often it is pushed from one node to its neighbors. For some applications, a low push may be the best in order to conserve memory and battery power. In other applications, a large push more often may be required to provide accurate and up to date information on the network.

Hood faces some challenges. Each “neighborhood” must keep its own data set which can cause problems when neighborhoods overlap. Through the use of parameters, one can distinguish one neighborhood from another. Another challenge is that within a neighborhood, all neighbor values must be kept in memory. This can create an inefficient use of memory and ultimately require large memory capacities. Also, Hood hides the cost of messaging from the user. A user could potentially make requests of the system that weigh it down in terms of memory usage or communications bandwidth and not be aware of the cost of their request.

Hood is ideally suited for object tracking in which locationing, routing, and tracking must be coordinated within groups of nodes (read “neighborhoods”). It may be useful to other wireless sensor network applications in which “neighborhoods” provide a foundation for the application. A search of twenty wireless sensor network applications revealed a large number of them using a neighborhood concept.

Future work in this area focuses on creating neighborhoods with multi-hop rather than one-hop distances. This would create a more robust neighborhood.

Best regards,
Hall T.

Directed Diffusion – A New Paradigm for Communication Networks

Traditional networks are based on an IP-style layout. The end points are labeled with unique addresses and a stacked architecture of software provides the communications services sending data from one end of the network to the other. In wired networks this works well but in wireless sensor networks, this paradigm is expensive and difficult to implement.

In directed diffusion, a series of sensor nodes are named with attribute-value pairs. A node requests data by sending an interest request for a piece of named data. For example, a temperature sensor node could have the named value temperature and the attribute of temperature on the sensor. A request for “temperature” would return the numeric value of the sensor. Nodes that do not have temperature sensors but say have pressure or humidity sensors would not respond to the node request for temperature. Through localized interactions, nodes learn how to route information in the most efficient way. Also, repairs can be made by nodes seeking information through broken links such as a node with a run-down battery.

Directed diffusion consists of interests – a query for a specific piece of information, data messages – the requested information, and gradients – the direction state created in each node that receives an interest. Gradients indicate which of the surrounding nodes requested information. Responses to requests are sent back to the requesting nodes.

Interest propagation is the technique whereby the node requesting information sends out a “broadcast” message to the other nodes. The first objective is to see if any of the nodes can make the measurement (say temperature) and if so, then to setup those nodes to start sending their temperature data back to the requesting node. After the requesting node receives data back, it switches from an exploratory mode to a path establishment mode in which it reinforces the path from the requesting node to the nodes providing data. Each node in the chain keeps a data cache that tracks requests and data transmissions. From the data cache it optimizes the path.

One of the advantages of directed diffusion is the ability of the network to “repair” itself by working around failed nodes. When a node sees reduced activity or no-activity it can send information in another direction. This is quite useful in wireless sensor networks in which batteries can run down and EMI interference can render a node inoperable.

As you can see, directed diffusion is a data-centric network. Nodes make requests based on data. Also, nodes communicate only with its neighbors, unlike traditional networks that communicate from one end of the network to the other using routers.

This paper describes in more detail the details of directed diffusion.


Best regards,
Hall T.