Projects

The projects listed below are given in order of increasing difficulty and time required.

We require that all implementations be in Java, for several good reasons:
1. STEP Type-checker
Implement a Java based type checker to ensure that a specified STEP program (XML file) describes functions chained together such that their type annotation is correct. (For example, a function that produces a String is invalid input to a function expecting an Integer). This may be done leveraging the existing STEP Java parser.

You should produce a Java program that verifies if given a STEP XML file is valid or violates some restriction of STEP. In our current parser we ensure the XML file is valid (we get this for free from any XML parser), and ensure that the elements found in the file are correct. If an element or attribute is incorrect, we provide no information to the caller. Moreover, a STEP file may contain correctly formed elements yet express an invalid STEP program (e.g., with direct cycles, redundant node IDs, etc).

An XSD/DDT is a meta-description of how an XML document may be formatted. It contains the valid syntax for any XML instance document (think a BNF for your XML documents) and can be used to either accept or reject an instance XML document. Unfortunately the rejection is essentially binary without much information as to why the instance document fails. Given the rules of STEP, one could write an XSD for STEP XML documents and also a Java program to use an XML engine to check instance programs and return a “meaningful” error code. You can use XSD for the initial syntax check, and reuse our Java parser to speed development.

You will not be able to perform all type checking of the STEP program with XSD's alone. For example, STEP programs should not have cycles, however one can easily create an XML document that is syntactically legal yet has a cycle. It is trivial to ensure that there are no cycles in the STEP program once the STEP program has been loaded, however we do not do so directly within our parser (and it should be done here). Your task would be to expand the STEP parser to include such checks as well as give some detail to the user where errors occur in the program and to give detail about them.

2. Java applet SXE (or SSD) interfaces
Your group will create Java applet-based interfaces to either the sensor execution environment (SXE) or the service dispatcher/resource monitor (SSD/RM). The interface(s) will obtain XML information via HTTP, parse the XML, and offer an interactive interface that is an alternative to the current web browser interface. For example, show an interactive graphical interface to the STEP program accepted to a sensor rather than a plain text interface.

As snBench components communicate using XML messages sent via HTTP, our current interfaces use XSLT to provide HTML formatted versions of this data to end users (or administrators) as needed. Unfortunately, the use of HTML places some limitations on the type of interface we provide whereas the use of a Java applet can provide a richer interface.

Consider the inspection of the running STEP nodes of a STEP program on a single SXE. Our current text-based interfaces could be replaced with interactive graphical interfaces showing the live execution state of the nodes and their interconnection and offering functionalities beyond those possible via basic XML.

Your project will establish an HTTP connection to the server, obtain the XML and render your own interface based on this data, perhaps a swing or Java2D rendering of the STEP graph. The complete HTTP name-space for the SXE is available in the technical report provided. Similarly, your group may create a Java applet based interface for the Sensorium Service Dispatcher/Resource Manager as well.

Another feature might include a posting interface that allows a user to post new STEP programs to either an SXE or the SSD. A template for implementation is given in the source tree: testsuite/poster.java

3. STEP Programming GUI
Your group will create a graphical programming interface for generating sensor network tasking programs (STEP programs). Your graphical interface should allow the user to specify program execution graphically from an extensible palette of functionalities and save the results as a properly formatted STEP file (XML).

SNAFU is an accessible prototype, functional style programming language that is compiled into STEP. Meanwhile, STEP is human readable and we (developers) are able to compose programs directly in STEP using a regular text editor. As STEP is a direct representation of the abstract syntax tree of a program, one can imagine a more accessible graphical programming interface in which a palette of nodes may be offered to be dropped and wired into a flow of execution that may saved directly into STEP (XML). Ideally, such an interface would prevent the construction of non-sense or illegal STEP programs. The level of complexity of such a tool may vary greatly. For example, including support for opening existing STEP programs implies some degree of XML parsing; preventing non-sense programs implies a more rigorous logic implementation.

A complete list of valid STEP nodes including sample programs are included in the appendix. In addition we provide a complicated STEP program, a graphical representation of that same program, and a mock-up graphical STEP programmer are also included in the appendix.

4. Expanding the Opcode library
Your group will create new sensor opcodes-- functionalities for deployed sensors, implemented in Java, adhering to a specified abstract class and runtime specification. Example opcodes in the image manipulation domain include: image differencing, motion detection, average image intensity, face detection. Example data manipulation opcodes include distributed hash_table_init, hash_table_add(k,v), hash_table_remove(k), hash_table_check(k), hash_table_get(k).

A STEP program graph is comprised of STEP nodes, one type of which is expression nodes (ExpNode) that describe actions to be taken by the individual computing resources. An ExpNode indicates its expression via the “Opcode” attribute. The opcode specifies a specific Java class file that exists on the SXE host. For example, there is a class /sxe/core/math/add.java corresponding to the opcode “sxe.core.math.add” as there is for each opcode known to the SXE. All opcode classes implement the abstract class /step/FunctionWrapper.

When the SXE's STEP evaluator encounters an ExpNode, a custom java class loader attempts to find the corresponding java class, load it, and invokes the class's implementation of the “Call” method. The abstract method Call takes a parameter that is an snArgList and returns an snObject. ValueNodes that are the parameters to your expression are converted to “first class” snObjects by the SXE before handing off to your Call method.

Your task will be to implement some new, interesting opcodes by providing classes for the sxe/core library.  the suggestions given above are just suggestions and you may implement any opcode you are inspired to provide, though do remember the domain and try to come up with useful opcodes.  You are strongly encouraged to discus alternate opcodes with us before proceeding.

For further information on developing opcodes, click here.

5. SXE Modification
Modification of the sensor execution environment (in Java) to change the way in which accepted STEP programs are executed on a sensor. At present, all computations are received and iterated over to check their enabled state (running each computation only when enabled). Ideas include (1) sandbox execution for remotely tasked computation (i.e., start a new Java Virtual Machine for every computation to be run and monitor those JVMs for failure) (2) perhaps creating a new (sleeping) thread for every computation accepted and waking them up as needed when they become enabled

The SXE is a runtime interpreter/evaluator for STEP programs. Each SXE accepts a partial STEP graph and iterates over all nodes. As the STEP graph is directed (computations percolate upward) a STEP node higher in the graph can not be evaluated until the lower nodes have been evaluated. Thus leaves are evaluated first and so on, upward, until a result reaches the root. Some branches of the graph may not need to be evaluated at all (e.g., they are one branch on a conditional) such that checking if a node should be evaluated depends on state of both children and parents (if this nodes' children have produced “fresh” values and if the result of this node is wanted farther up the tree). As our present evaluator iterates over all nodes, we miss out on some possible local optimization, such as using multiple threads to simultaneously execute multiple ready nodes of independent branches. Similarly in a single threaded model, if the computation of a single node diverges it will block the execution of all other nodes. As such scheduling algorithms should ensure that if multiple nodes are eligible for execution they each get a “fair" share of the SXE's cycles.


Michael Ocean (mocean@cs.bu.edu)
Creation Date: 1/10/06
Last Change: 1/12/06