NeTS-NOSS: Semantic Internetworking of Sensor Systems for Efficient In-Network Information Processing
National Science Foundation Grant No. CNS-0435353
Principal Investigators: Thomas DC Little, Thomas H Kunz, Nathan G Phillips,
Venkatesh Saligrama, and Murat Alanyali
Project Summary
Advances in sensor and computing technologies provide impetus for deploying wireless sensor networks. Such networks are envisioned to provide real-time information in diverse applications ranging from environmental and habitat monitoring, power systems, and manufacturing. While successful realization of such systems would lead to a dramatic shift in ways our environment is monitored and understood, the research to date in this area is fragmented and a systematic methodology is yet to emerge. Sensor network operation and lifetime is fundamentally limited by energy, a particular concern in environmental applications, which necessitates long-term deployment.
Intellectual Merit Our research will systematically interface new semantic routing techniques with novel in-network localized distributed inferencing algorithms to realize scalability and massive energy efficiencies in sensor network operation. We will address a challenging ecological application, which is representative of the challenges arising in environmental monitoring. The proposed approach includes:
Semantic Routing: The significance is twofold: (1) by limiting the scope of routing within specific subsets of the SNET there is an opportunity to limit excess energy use otherwise expended on general purpose data routing. In essence, we can limit routing to involve only those nodes relevant for the data flow in the sensing application. (2) The use of attribute-based routing permits the efficient reconciliation of multiple overlaid routing paradigms.
Distributed Information Processing: We propose distributed localized algorithms for inferencing, which can be tailored to a variety of applications, and in general provide substantial energy gains over existing algorithms. These algorithms can exploit statistical relationships between different attributes to either reach a consensus about desirable events or to describe more complex relationships such as spatio-temporal variation.
Broad Impact The proposed research is inherently targeted towards impact in several communities: (1) It has significant societal impact with the potential to stimulate a paradigm shift in the way our environment is monitored and understood. It successful, it will provide a framework for evaluating broad policy questions relevant to society, such as, protecting endangered species and the argoecosystem. (2) The MANET and sensor networks research communities via the development of new techniques and theories to advance the viability of large-scale sensor networks as an engineering challenge. (3) Scientists, educators, students, and like-minded individuals who might apply thes results of the work: the work is intended to enable access to sensor networks by thes groups to achieve widespread and flexible access to scientific inquiry on the universe of network-connected sensors. (4) The proposed interdisciplinary effort bridges the disciplines of biology, geography, and engineering. We expect that this effort will lead to novel, anticipated insights and technologies in each discipline. (5) The PIs have demonstrated prior commitment to providing access to their labs by underrepresented groups such as PATHWAYS at Boston University and will continue to seek out ways of encouraging careers in science and engineering by young people.
This material is based upon work supported by the National Science Foundation under Grant No. CNS-0435353. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.
ParticipantsGraduate students: S. Aeron, A. Agarwal, G. Atia, S. Abu Ayyash, E. Ermis, C. Fan, S. Guo, Z. Gao, W. Ke, O. Savas.
Undergraduate students: S. Chamberlain, J. Chau, B. Neiswander, L. Pham, M. Ryan, D. Slovin, J. Tang, F. Walker.
Major Activities Since Project Inception (January 2005)
Development and Refinement of the Semantic Routing Concept The proposed concept of semantic, attribute-based efficient routing (SABER) is intended to provide energy-efficient data dissemination in a SNET as well as enabling the retasking of the SNET's mission after deployment. In contrast to conventional routing in which dedicated routers are optimized to shuttle large volumes of data quickly without examining their contents, SABER uses the type and class as marked by attributes within the data stream to support routing decisions. This concept is well suited to SNETs in which each node can be required to perform routing functions.
In its basic form, data originating within the SNET are tagged with attributes defined by a global ontology for the class of sensing applications. The attributes along with their associated data can be evaluated at each node during the routing process with decisions being made on next-hop forwarding or data discard. In conjunction with a proposed distributed consensus algorithm that will generate trigger events, SABER is expected to be both useful and efficient in future SNETs.
Research activity related to this topic is described in references [WALB05], [AL06], and [KL06]. The work describes the use of SABER in defining virtual "containment" hierarchies as attributes for routing in a SNET. We show algorithms that support clustering sensors according to these hierarchies and implement clusterhead failure recovery and load balancing among cluster members. We show that the framework has significant bandwidth gains over a flooding-based scheme under the scenario considered using analytical techniques.
We have also been investigation the use of XML-based schemas for attribute-based routing in various application scenarios including ecology, building automation, and vehicular networking as described in [AL06].
Evaluation of Target Environmental Applications for Demonstrating Concepts A significant challenge in our work is to reconcile the (high-level) concepts proposed in SABER with the capability of current off-the-shelf SNET mote technology. An associated equipment grant from Intel has provided five Stargate single-board Linux computers and approximately 20 Crossbow Motes equipped with environmental sensor boards. In collaboration with PIs Kunz (bat ecology) and Phillips (tree forest hydrology) we have been evaluating scenarios that will best demonstrate the SABER concepts. To this end, we are focusing on adapting the equipment to their specific needs and gaining experience with their current field experiments. In this way we, and they, are learning about the capabilities and limitations of the equipment.
In the case of PI Kunz, we have adapted the motes and stargate for the purpose of recording environmental conditions found in two field sites in Texas for his study of the Brazilian Free-Tailed Bat. The intent of the study is to compare the environmental conditions existing in bridge roosting sites vs. cave roosting sites. The motes and stargate have been weatherized and programmed for the sampling required in this setting. Initial experience and data collection in this field trial highlight many problems with successful deployment and the collection of clean data. An additional trial was conducted under more hospitable conditions locally (MA) using a larger set of motes borrowed from an educational lab. This latter deployment involved monitoring temperature, light, and humidity conditions in a barn roost at a site in Paxton MA. Details of this summer 2005 work are described in [LAT05]. We expect to repeat these trials in 2006 to capture cleaner data sets.
We have also deployed the motes to support PI Phillips' work in tree hydrology and the study of carbon intake in the forest as specified in the supplemental REU grant. In this experiment we deployed motes to measure the impact of sun occlusion in a trial at Boston University's Sargent Camp. Details are described in [LAT05].
Investigation of the VANET Scenario for Semantic Routing We have previously investigated vehicular scenario as applicable to the use of mobile ad hoc network (MANET) technologies. Recently, we have explored the SABER concepts in this setting specifically as an enabler (not as an energy conserver) for routing. This work is described in [LA05a], [LA05b] and [AL06]. This work is relevant as represents a concrete example of how attribute-based routing can be significant for future applications.
An important feature of future vehicular networking is to enable the dissemination of traffic and road conditions such as local congestion and surface ice as detected by independently moving vehicles. This activity known as Information Warning Functions is useful for vehicles on the highway and enables early reaction. This problem can be described as the directional propagation of information originating from linearly-distributed mobile nodes on a rectilinear plane. By using limited-range packet radios and attribute-based routing, we are able to isolate vehicular from network traffic and permit directional propagation of messages outward from the point of origin. For example, it is desirable to propagate the occurrence of congestion created by an accident in both the forward and backward directions on a highway.
We assume the use of multi-hop routing in clusters of connected vehicles to achieve a propagation rate that exceeds the speeds of individual carrier vehicles. We characterize the bounds of information propagation under various traffic patterns and describe a new technique and algorithm that can achieve these limits. We also show an implementation of the dissemination algorithm as a routing protocol using a combination of MANET (mobile ad hoc networking) and DTN (delay tolerant networking) methodologies.
Distributed Algorithms for In-network Data Processing with Applications to Distributed Hypothesis Testing We consider the problem of classifying among a set of M different hypotheses via distributed noisy sensors. The sensors can collaborate over a communication network and the task is to arrive at a consensus about the event after exchanging messages. The considered problem is thus a distributed version of the canonical statistical decision making formulation. We apply a variant of belief propagation as a strategy for collaboration to arrive at a solution to the distributed classification problem. We show that the message evolution can be re-formulated as the evolution of a linear dynamical system, which is primarily characterized by network connectivity. We show that a consensus to the centralized MAP estimate can almost always reached by the sensors for any arbitrary network. We then extend these results in several directions. First, we demonstrate that these results continue to hold with quantization of the messages, which is appealing from the point of view of finite bit rates supportable between links. We then demonstrate robustness against packet losses, which implies that optimal decisions can be achieved with asynchronous transmissions as well. With energy-limited sensing applications in mind, we present an account of energy requirements for distributed detection and demonstrate significant improvement over conventional decentralized detection. Finally, extensions to distributed estimation are described. See [AV05].
Token-based Sequential Algorithms for Distributed Computation In this thrust, we are further focusing on energy-limited sensor networks and design, analyze, and verify distributed algorithms that possess favorable message/ time complexity tradeoffs compared to previously studied algorithms in literature. We consider in-network processing via local message passing by networked sensors. There is no designated fusion center; instead sensors exchange messages on the associated communication graph to obtain a global estimate. We propose an asynchronous distributed algorithm based on local fusion between neighboring sensors. The algorithm differs from other related schemes such as gossip algorithms in that after each local fusion one of the associated sensors ceases its activity until it is re-activated by reception of messages from a neighboring sensor. This leads to substantial gains in energy expenditure over existing local ad-hoc messaging algorithms such as gossip and belief propagation algorithms. Our results are general and we focus on some explicit graphs, namely geometric random graphs, which have been successfully used to model wireless networks, and d-dimensional lattice torus with n nodes, which behave exactly like mesh networks asymptotically. We quantify the time, message and energy scaling of the algorithm, where the analysis is built upon the coalescing random walks. In particular, for the planar torus the completion time of the algorithm is $\Theta(n)$ and energy requirement per sensor node is $O((log n)^2)$ and for 3-d torus these quantities are $\Theta(n)$ and $O(log n)$ respectively. The energy requirement of the algorithm is thus scalable, and interestingly there appears little practical incentive to consider higher dimensions. Furthermore, for the planar torus the algorithm exhibits a very favorable tradeoff relative to gossip algorithms whose time and energy requirements are shown here to be $\Omega(n)$. Also, the proposed algorithm can be generalized to robustify against packet losses and permanent node failures without entailing significant energy overhead. These theoretical results are verified via numerical simulations. See [SAV06].
Distributed Target Tracking In contrast to static sensing problems where the sensor network processes a fixed set of measurements, important applications involving tracking entail dynamic measurements. When the communication network is mesh-type and therefore information dissemination is subject to delays associated with the network diameter, the tasks of sensing and message transmission need to be considered in a common time scale. The objective of this thrust is to quantify the impact of delays on tracking performance, and to design distributed algorithms that minimize the attendant degradation. We describe distributed tracking of a linear dynamical system via networked sensors. The networked sensors communicate with each other by means of a multi-hop protocol over a communication network. Minimum Mean Square-optimal solution is Kalman filtering when measurements are available centrally, but new methods are required to account for communication constraints. We derive optimal algorithms to deal with arbitrary network topology and then extend these results to account for communication delays and packet losses. The proposed techniques differ from related techniques proposed in two important aspects: a) there is no designated leader/fusion node and each sensor attempts to optimally track the system trajectory based on its local observations and time-dependent information available from other sensors in the network; b) the message computation at each sensor is structurally identical, where the computed message from each sensor is the innovation in the state conditioned on all the information available up to that time at each sensor. Consequently, the sensor network can be queried at any time and at any node to obtain optimal estimates for the state of the dynamical system. See [VAS05].
Development of a new graduate/undergraduate course The PI has proposed a new course at Boston University to commencing in the fall of 2005. This course, SC 500, "Networking the Physical World" covers concepts and methodologies for network programming with motes. In the spring of 2006 this course has been formally approved as a regular course SC 544 and is be cross-listed with the Department of Manufacturing Engineering and televised in the distance learning format.
SC 500/544 considers the evolution of embedded computing systems with the introduction of network connectivity. Key themes are computing optimized for resource constrained (cost, energy, memory and storage space) computers to interface with the physical world. The course will study current technology for networked embedded network sensors including IEEE 802.15.4 and other evolving standards. A laboratory component of the course introduces students to the unique characteristics of distributed sensor motes including programming, reliable communications, sensing modalities, calibration, and application development.
Training In addition to basic research activities including examination of published literature, students are involved in presenting their semester work in laboratory meetings, on-campus poster sessions open to the campus, and within the Sensor Network Consortium meetings.
The PIs participated in an REU Supplement for the summer of 2005. Two students were involved in varying capacity: Johnathan Tang, an ECE student, and Meghan Ryan of the Geography department at Boston University. These students were involved in three main activities: (1) experiencing a research setting including lab and field work, (2) developing the mote-sensor hardware and system for deployment outdoors including software development, (3) data collection in the field, and (4) data analysis and presentation. Additional details of this REU supplement are described in [LAT05].
The PIs have leveraged assets of the project in undergraduate course development and instruction. In 2005, PIs Alanyali and Venkatesh sponsored a senior thesis with Derek Slovin and Lyndon Pham to implement concepts developed under the grant using the Mica2 mote platform (see [CRO05]). This effort led to an award by Crossbow in their international competition.
In 2005-2006, several more projects of this type were sponsored. A senior design team used motes and an existing concept proposed by Basu and Little [BL04] to implement a wireless parking meter network [LIT06]. The team designed a new sensor board incorporating a magnetometer for the purpose of detecting parking space occupancy. Multiple motes are deployed at parking spots forming mesh network. A gateway interfaced to the network and served to collect data for a database enabled for web services and the use of Google Maps. This project resulted in several interviews including from the Boston Globe and Wired News.
Also in the spring of 2006, motes acquired for the grant were employed by a senior design team implementing wireless trash cans [SASE06], [BAR06]. ECE students developed the sensing hardware and software infrastructure to monitor the state of a network of trash receptacles deployed in public parks. The benefit of the system is the reduction of trips to service non-full cans, and the timely servicing of full ones. This team will complete in an IEEE-sponsored international design competition at the end of June 2006.
Later in 2006 we expect results from a similar project to perform rooftop monitoring of arrays of solar panels.
References and Publications
The following link serves as a dissemination point for project results including publications: http://hulk.bu.edu/projects/snet/summary.html