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
- Firstly, of all modern programming
languages, Java is one of a handful that is statically strongly-typed.
By contrast, C and C++ are not strongly-typed, and SmallTalk is
strongly-typed but not statically. Java thus supports statically
type-safe programming which is now recognized as essential for writing
- Java is compiled to transportable bytecode, not to native code,
the latter being the case with C and C++ for example. This means that
Java programs are portable to any platform to which a Java interpreter
(the so-called Java Virtual Machine or JVM) has been ported. Similarly, for
the sensing needs of the snBench we leverage the Java Media
Framework (JMF) which is a Java based cross platform multimedia API including
- Java also provides several features that ease implementation;
including garbage collection, memory protection, and a rich API of
common functionalities. Although such functionalities can be
implemented in other languages, Java includes these features "out of
- As with any large software
project with many separate modules, it is very helpful (though not
absolutely essential) for maintenance, manageability and future
extensions to adopt the same programming language for the implementation of all components.
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
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
Creation Date: 1/10/06
Last Change: 1/12/06