CS294-11 Project Ideas


Title : Develop system abstractions for in-network statistical modeling
Suggested by : David (davidchu@cs), Guilherme Rocha (gvrocha@stat.berkeley.edu)
Description : The literature has seen many proposals for using statistical models on inside sensor networks. (e.g. for more accurate classification, reducing msg transmissions, etc.). Examples are Carlos Guestrin's distributed junction tree, Guilherme Rocha's work, David's Ken work, and Nestfe multi-target tracking. The solns here are often require substantial custom infrastructure, or simply are centralized (at the base) solutions. Design and implement new system abstractions/APIs that help in quickly and easily deploying new statistical modeling techniques i.e. something that lets statisticians design algorithms and os researchers optimize system code.

Title : A Location Service for Point-to-Point Routing Scheme (with other possible uses)
Suggested by : Rodrigo fonseca (rfonseca@cs) and Jerry zhao (zhao@icsi)
Description : BVR creates a dynamic coordinate system based on topology that allows nodes to send messages to a coordinate, thus enabling point-to-point routing. The problem is that the coordinates change with topology changes, and we need a way to find the current coordinates held by a given node. BVR has a set of nodes, called beacons, which are the bases for the coordinate system. All nodes know how to route packets to the beacons. In the BVR paper we outline a location service that uses consistent hashing and uses the beacons as storage places for the mappings (node id -> coordinate). Each node periodically publishes its coordinates to a beacon, determined by a well know hash function, and another node willing to talk to that node looks it up in the right beacon. The BVR route to coordinates primitive is implemented and has been tested in real testbeds and simulations, with code publicly available. There are several interesting issues to be explored in this problem, including which hash function to use, tradeoffs in replication (if you hash to two beacons, and store at both, you get more resilience and much shorter lookups), how to evenly spread the load among beacons, and even come up with a totaly different scheme for doing the mapping. Of course, I am available to help and to answer any questions, and willing to publish this.

Title : Pairing advanced in-network data operators with traditional operators.
Suggested by : David (davidchu@cs)
Description : For network data collection, there have been proposals for new classes of data operators beyond the standard AVG, Max, Min, Count, Histogram operators. One good example first made widely known by Synopsis diffusion is "approximate AVG" (see synopsis diffusion paper for more). Another is the distributed regression "operator" (a more compact way to do histogram). While well-regarded by the community, these have not seen adoption in a real system. Design and implement these, alongside existing well-known operators. For example, start by looking at how TinyDB implements operators.

Title : Analysis of high-level programming languages
Suggested by : David (davidchu@cs)
Description : Many suggestions exist for wsn high-level programming languages, in TinyOs and otherwise: Mate, Abstract regions and its derivatives, SNACK (click on wsn), tinydb and many more. Yet very few receive wide use. What makes a high-level language successful? What are the common features? What forces users to "resort to" systems programming in nesc? This analysis should also include differentiating between various application domains, if appropriate, e.g. tracking, monitoring, etc.

Title : cross-layer power management
Suggested by : Cheng Tien Ee (ct-ee@eecs), Sukun Kim (binetude@eecs)
Description : Here's something that is sorely needed: the design of a cross-layer power management component. This can be generalized to: the design of an cross-layer arbitrator component. Such a component can handle power management issues, interrupt issues (for instance Sukun turns off interrupts when doing high-frequency sampling, this has to be managed if there are multiple components in the system wanting to fiddle with that knob), etc.

Title : Taking Advantage of the Capture Effect
Suggested by : Kamin Whitehouse (kamin@cs)
Description :
  1. Add a post-amble to all TOS packets (as described in our paper). This would increase packet collision detection rates from ~46% to ~92%.
  2. Add collision detections for preambles, which would increase detection rates from ~92% closer to 100%
  3. In general, the receiver should NACK the transmitter that collided to indicate that there was a collision. This is because a transmitter should be able to perform very different actions in the case of a bad link (change parents) and congestion (stop sending) and collisions (change phase). Disambiguating this information and the ability to send NACKs is only possible through collision detection and recovery.
  4. As a MAC protocol, nodes could go through a learning phase to find which neighbors overpower other neighbors. Then, when node hears a pre-amble from one node (id must be incorporated into preamble), it sends a NACK only to those nodes that would overpower that transmitter. All other neighbors are still free to transmit, allowing increased spatial reuse, and potentially much higher overall bandwidth.
  5. using TDMA schemes such as Barbara Hohlt's FPS, when two nodes fend for the same TDMA slot, the receiver can recover one of the packets, identify the collider, and send an ack to both of them indicating that one actually won the slot and the other should take an alternative slot. This allows both nodes to associate immediately with the receiver even if there is a collision. Alternatively, in the case of collisions, barbara's scheme drops potentially both nodes, which need to wait an entire cycle (potentially minutes, depending on the duty cycle) in order to associate. This scheme could therefore create dramatically reduced latency in association, which is one of the key sources of energy loss in barbara's scheme.