\section{Semantic Labeling}
\label{semantic}
\subsection{Background}
A universal requirement of distributed systems is a mechanism to find
components. Systems such as search engines for the World Wide
Web\cite{www} utilize a combination of the semantic mark up of
HTML\cite{html} as well as textual analysis to determine whether a
component (document) matches a query. Many software systems, such as
CORBA\cite{OMG95} utilize a naming service\cite{corbaservices} where
components are mapped 1-to-1 with names. CORBA also utilizes a
``trading service'' which allows lookup by interface (what Hive calls
syntactic lookup).
\par
In a environment where the components are ``things that think'',
neither of the above described approaches work well. While a direct
naming scheme could be used, this primarily defers the problem to one
of creating a directory service so those names may be usefully
associated with descriptions of the services they provide. Hive
utilizes two conceptually distinct ways of locating agents and
shadows: ``syntactic lookup'' and ``semantic lookup''.
\par
Syntactic lookup is the ability to locate components based on their
Java type. In the case of agents, these are completely composed of
{\tt Remote} interfaces, and in the case of shadows, are composed of
the shadow's type and any interfaces it implements. This sort of
lookup is necessary to assure programmatic compatibility. Many very
different devices, however, may have identical interfaces.
\par
A reasonable remote interface example is {\tt Toggleable}, which would
apply to devices such as lamps, door locks, or any other simple output
device. While there is no programmatic distinction between these
devices, their actual role in an application would be substantially
different. This issue could be addressed by the creation of a number
of so-called ``tag interfaces'', such as {\tt Lamp}, which extend {\tt
Toggleable}, but implement no new methods themselves. This approach,
however, has problems in that these tag interfaces cannot be
dynamically extended or modified at run time, and their use creates
substantial clutter in the Java type system.
\subsection{Underlying technologies}
In lieu of extending syntactic lookup this way, Hive implements a
separate semantic lookup system. Associated with each agent or shadow
is a {\tt Description} which describes the object. Hive semantic
descriptions are expressed using the Extensible Markup Language
(XML)\cite{xml} serialization of Resource Description Framework
(RDF)\cite{rdf} model in the same style as those described in the
Composite Capability/Preference Profile (CC/PP)\cite{ccpp} system.
\par
The canonical example for an application of CC/PP is a cell phone.
The ``capabilities'' portion would indicate how much memory the phone
had, if it was analog or digital, and what sort of screen it has. The
``preferences'' portion would indicate that the user wants a
particular ring style, certain numbers on the speed dial, and the
like. This naturally extends to the broader world of things that think.
\subsubsection{XML}
The Extensible Markup Language provides a simple but flexible basis
for sophisticated semantic descriptions. An sample XML document,
shown in figure \ref{xmldoc}
\begin{figure}[hbt]
\begin{Code}
Matthew Gray
mkgray@mit.edu
Infrastructure for an Intelligent Kitchen
\end{Code}
\label{xmldoc}
\caption{Sample XML Document}
\end{figure}
shows the basic form. Through use of SGML Document Type Definitions
(DTD)\cite{sgml} and Document Definition Markup Language
(DDML)\cite{ddml} schemas, the structure and content of document can
be validated.
\subsubsection{RDF}
The Resource Description Framework (RDF) is a framework for
representing a directed labeled graph data structure and specifies a
representation in XML. For example, the above XML document example,
reformulated in RDF (which requires substantially additional syntactic
structure) would produce the graph shown in Figure \ref{rdfthesis}.
\begin{figure}[hbt]
\begin{center}
\mbox{\epsfxsize=3in \epsfbox{rdf.ps}}
\end{center}
\caption{RDF graph of sample document}
\label{rdfthesis}
\end{figure}
RDF is primarily distinguished from generic XML by the fact XML is
considered ``document-centric'' and RDF is ``data-centric''. This
means that two different RDF documents can correspond to the identical
underlying data representation, while in XML, differences in
formatting correspond to differences in the resulting
document. Additionally, RDF has extensive syntactic requirements,
making representations entirely unambiguous, but at the cost of
simplicity and easy human readability. The use of RDF versus plain XML
for semantic labeling is discussed below.
\subsubsection{CC/PP}
The ``Combined Capability/Preferences Profile'' specification, as the
name suggests is a way of representing the capabilities and
preferences that correspond to a device. It provides a standard
structure for representing default values, where those values may
reside in an externally referenced document, rather than requiring all
metadata to be replicated in each description.
\par
The particular kinds of data CC/PP aims to describe are well suited to
the primary purpose of semantic descriptions within Hive. While it is
valuable to be able to include traditional metadata such as the owner
of a resource in Hive, the primary goal for these descriptions is to
describe capabilities and preferences. CC/PP is built on top of RDF.
\subsection{Semantic Descriptions in Hive}
The semantic description lookup scheme for Hive was implemented
utilizing RDF, CC/PP and XML. In a typical configuration, each Hive agent
or shadow would have a description that contained information about
the type of device it represented, its location, a ``nickname'',
configuration data, and any other metadata relevant to potential users
of the service.
\par
This approach has certain similarities with Jini's
attribute\cite{jiniattribute} based lookup, which is compared in
detail in Section \ref{semlabeljini}. Other systems, such as
Ontolingua\cite{ontolingua} and KQML\cite{kqml} have the disadvantage
of substantial complexity, even in comparison to RDF, as they are
targeted more toward knowledge representation problems.
\par
\subsubsection{Description of Descriptions}
A sample RDF description appears in Figure \ref{sampledesc}. It
describes a ``QuickCam'' camera located in room 468 of building E15.
The representation of the RDF structure that this represents is shown
in Figure \ref{samplegraph}.
\begin{figure}[hbt]
\begin{Code}
\end{Code}
\caption{Sample RDF Description}
\label{sampledesc}
\end{figure}
\begin{figure}[hbt]
\begin{center}
\mbox{\epsfxsize=4in \epsfbox{rdf2.ps}}
\end{center}
\caption{RDF Structure of description shown in Figure \ref{sampledesc}}
\label{samplegraph}
\end{figure}
A schema, or particular set of conventions for describing an object, is
needed if multiple agents are going to interact. If one agent calls
the place that something is located its ``place'', which has
parameters of ``latitude'', ``longitude'' and ``elevation'', and
another calls it a ``location'', with a ``building'' and ``room'',
they will have a hard time usefully interacting.
\par
Defining a particular schema is outside of the scope of this work.
Initially, the goal, instead is to provide a sufficiently flexible
description system for exploring different schema, and how those
schema might be constructed. In practical application, a few loose
conventions were applied as a preliminary Hive schema.
\par
Hive does not provide a notion of a unique name for agents; an agent
is used by reference, and need to be discovered by the lookup
mechanism. Part of the reason for this is that it is hard to define
the notion of identity in a mobile distributed objects context. If an
agent moves from one host to another, is it the same agent? If an
agent duplicates itself and both copies move, which is the
``original''? However, it is often useful to be able to refer to an
agent by name, or ask an agent its name so the ``same'' agent can be
found later. To avoid the semantic ambiguity of ``same'', Hive
utilizes the semantic description system to allow an agent to give
itself a name, and it can decide when its identity changes or remains
the same.
\par
Due to the fact that the agents assign themselves these names, there
is no guarantee of uniqueness, and uniqueness may not even be desired.
Consider the case of a ``phone book agent''. If there are multiple
identical instances of this agent, they are all equally good. They
may as well share a common name. If there are multiple instances of a
light bulb agent, however, they should have very different names.
This name is called the ``nickname'' and in the case of the example in
figures \ref{sampledesc} and \ref{samplegraph} is ``Pia Quickcam''.
\par
In the ``Honey, I Shrunk the CDs'' demonstration described in Section
\ref{scenarios}, the central agent locates both the tag reader and the
jukebox by nickname, since it is looking for a particular pair of
agents, the ``Pia Demo Tagreader'' and the ``Pia Jukebox''. Most of
the time, though, agents would be found based on their other
parameters.
\par
In the kitchen demonstration described in Section \ref{netkitchen},
one agent collects references to all of the tag-readers available.
This is accomplished via semantic lookup, without the use of nicknames
or any other individualized identifier. Specifically, the
concentrator agent performs a query for all agents which have as one
of their ``role''s the type ``tag-reader''. The parameter ``role'' is
another piece of the preliminary Hive schema. It allows a device to
have multiple arbitrarily parameterized labels. In the example in
figure
\ref{sampledesc}, the device has the role of ``camera'', and that role
has the parameter ``kind'' which in the example is ``QuickCam''.
\par
Another example of roles, where a single agent may have multiple
roles, is shown in the {\tt AutoWiringAgent}. This agent
finds a pair of two on screen agents to connect together. First, it
locates all agents that have the role of ``screen-widget'' to limit
the selection to screen based agents. Second, it selects an agent
with the role of ``button'', and an agent with the role of
``event-display'', each with appropriate syntactic types and connects
them together.
\par
Lookup based on a combination of parameters is possible as well. An
extension to the kitchen lookup could include restricting the
tag-readers that are selected to those in a particular location (i.e.,
the kitchen). An example of a scenario that uses the location portion
of the preliminary Hive schema for use by wearable computers is
described in Section \ref{wearable}. Further work on defining schemas
and managing their creation is needed, and Hive's semantic labeling
approach provides the necessary flexibility.
\par
Finally, in the example in figures \ref{sampledesc} and
\ref{samplegraph}, there is a portion of the description labeled
``config''. This is configuration information rather than actual
semantic description. This is implemented to use CC/PP style
defaults, to easily allow a number of descriptions to share defaults,
such as having a default location. Further comments on the use of RDF
for configuration appear below in the analysis.
\subsubsection{Description API}
The fundamental unit used in queries is a set of zero or more
descriptions called a {\tt DescSet}. The {\tt DescSet} allows
flexible manipulation of these descriptions to identify the agents or
shadows of interest to a particular application.
\par
The API for querying a {\tt DescSet} is primarily composed of the {\tt
select(String parameter, String value)} method. The effect of this
call is, in each description, to traverse the path on the graph with
the label {\tt parameter} that connects to a node with value {\tt
value}. If {\tt value} is null or absent, it will traverse the path
regardless of the value of the node it leads to.
\begin{figure}[htb]
\begin{center}
\begin{minipage}{5in}
Stage 1: \parbox[c]{\fill}{\epsfxsize=4.5in \epsfbox{query1.ps}}\\
Stage 2: \parbox[c]{\fill}{\epsfxsize=4.5in \epsfbox{query2.ps}}\\
Stage 3: \parbox[c]{\fill}{\epsfxsize=3in \epsfbox{query3.ps}}\\
\end{minipage}
\caption{Progression of a sample query}
\label{queryfig}
\end{center}
\end{figure}
Figure \ref{queryfig} shows the steps in a simple query of a {\tt
DescSet} starting with with 3 descriptions. In this example, the goal
is to select all descriptions that describe an object located in the
city of Cambridge. Unrelated portions of the graph are not shown for
simplicity.
\par
Stage 1 of Figure \ref{queryfig} shows the state of the {\tt DescSet}
before anything is done. A {\tt DescSet} may be reset to this state
by calling {\tt DescSet.noContext()}. A call of {\tt
select("location")} changes the state to that shown in stage 2. A
final call of {\tt select("city", "Cambridge")} changes to what is
shown in stage 3. Note, the third description, which described an
object in Boston, was removed from the set.
\par
In order to obtain a {\tt DescSet} in the first place, an agent calls
the {\tt queryAgents(\ldots)} method on a cell, or constructs it from
a pre-existing list of agents or shadows. A number of other methods
exist on {\tt DescSet} to retrieve matches following a set of {\tt
select}s, count matches, add and remove descriptions, merge with other
{\tt DescSet}s, and reset the graph query. A practical guide to using
RDF descriptions in Hive appears in Appendix \ref{rdfdescdoc}.
\subsubsection{Analysis}
This approach toward semantic labeling has proved flexible, extensible
and useful. The use of RDF has been a bit cumbersome, however. In
the small number of actual applications built so far, it has been
capable of usefully describing all the necessary components. As
larger numbers of components are constructed, and the interaction
increase, better evaluation will become possible.
\par
The system's flexibility and extensibility has been evidenced by two
particular extensions: nicknames and configuration data. In the early
design of Hive, a decision was made not to assign unique names to
objects; all objects would be the result of lookups. As
discussed above, it became clear that allowing agents to name
themselves had utility. Adding a ``nickname'' as part of a
description was easy, but the use of RDF allows for structured
nicknames if so desired. That is, a nickname may have the string
value ``Pia Quickcam'', but it might have a parameter
``assigningAuthority'' of ``Pia'', or any other substructure desired.
Another agent doing a lookup that does not use this structure would
not be interfered with.
\par
During the development of Hive, the need for a method of
doing per agent configuration arose. Adding new per agent
configuration files was considered, but dismissed when it was realized
that the configuration could readily be put into the semantic
description. The configuration information in the semantic
description is automatically translated into JavaBeans\cite{javabeans}
method calls to configure the agent or shadow. Further, more complex
configuration structures can be put into the description and utilized
by the agent on its own terms.
\par
Unfortunately, RDF has evolved into a very complicated specification,
and has become more difficult to use. While this complexity provides
substantial customizability and a strong underlying data model, it is
unclear whether the tradeoff is worth it. Alternative approaches would
include a non-RDF, but still XML based representation, or a more
complex knowledge representation system.
\par
Future work, particularly if RDF is kept as the description
representation, should include implementation of a suite of utilities
to generate, modify, and view these representations. To some extent,
this is motivation to continue to use RDF, as many such tools will be
created for RDF in general, independent of a particular application
domain.
\par
Details of how the semantic labeling system were applied in various
Hive applications are discussed in Sections \ref{netkitchen} and
\ref{scenarios}. User documentation for doing RDF based agent
configuration appears in Appendix \ref{confdocs}.