NEST Challenge Architecture

Version 004 -- Friday, September 13, 2002

 

Homepage:        http://webs.cs.berkeley.edu/tos/api/

Mailing List:       http://mail.millennium.berkeley.edu/mailman/listinfo/nest-challenge

 

 

Table of Contents

Chapter 1: Introduction. 2

Chapter Descriptions. 2

Group and Document Roles. 2

Chapter 2: Demo Description. 4

Game Outline. 4

Demo Implementation. 4

Functional Outline. 4

Chapter 3: Abstract Architecture. 6

Overall Architecture. 6

Methodology. 6

Application Architecture. 6

Prototype Middleware Architecture. 7

Concrete Middleware Architecture. 8

Chapter 4: Formal Architecture. 9

Chapter 5: NesC Architecture. 10

Methodology. 10

Modules

Interfaces

Types

Chapter 6: Graphical Architecture. 11

 


Chapter 1: Introduction

Chapter Descriptions

Chapter 1: Introduction

Chapter Descriptions. Roles of Berkeley, Middleware Groups, and Document.

Chapter 2: Demo Description

Detailed description of the demo scenario, including what entities are present and how they behave.  Also define high-level architecture decisions such as global/local coordinate systems, global/local time, etc.

Chapter 3: Abstract Architecture

Informal, linguistic description of each component, its behavior, and interaction with other components.  Informal description of the overall architecture.

Chapter 4: Formal Architecture

Constraints, parameters, preconditions, and postconditions of each component; and bounds on these parameters.

Chapter 5: NesC Architecture

Define the API for each component and corresponding message structures.  Subdivided into modules, interfaces, and types.

Chapter 6: Graphical Architecture

Diagram of connections between components, interface interaction, composition of overall architecture.

Group and Document Roles

Berkeley's role

·         Manage this NEST Challenge Architecture Document

·         Set revision dates

·         Provide the initial abstract architecture and concrete implementations

·         Review and integrate changes proposed by other groups

·         Web site

·         Mailing list

·         SourceForge facilities / repository

·         Provide the demo kits as well as the final demo test bed

Middleware groups' role

·         Work within the framework of the provided architecture

·         Conform to changes in revisions of the architecture

·         Suggest changes to the architecture

·         Use the collaborative infrastructure and facilities

·         Provide NesC component implementations

·         Provide Formal Architecture for their components

Challenge Architecture Document goals

·         Provide frameworks to allow for Middleware providers to develop individual components in a reasonably independent manner

·         Define a Methodology subject to constraints extracted from the demo description

·         Define Prototypes which form the core abstraction

·         Use those Prototypes create Concrete Implementations in NesC, subject to constraints specified in the Formal Architecture

·         Always work toward abstractions when it makes sense to do so

·         Specify common types / structures used between components


Chapter 2: Demo Description

Game Outline

To start the game, the motes comprising the sensor network are deployed onto the playing field in a sleep state.  An external node broadcasts a begin signal to the sensor network to indicate the start of global time.  The pursuers and evaders then enter the playing field and remain within the field for the duration of the game.  The sensor network provides a variety of services to both pursuers and other sensor motes: time synchronization, localization, critter (moving object: pursuer or evader) estimation, etc.  For the purpose of the game, the sole goal of these services is to produce estimates on the positions, velocity, and identity of critters in the playing field.  This information is time stamped and routed to all pursuers in the playing field.  The pursuers have onboard computation facilities comparable to a laptop computer and may optionally communicate through a separate robust channel to coordinate to capture the evader.  When all evaders are captured (a capture occurs when a pursuer is "close enough" to it), the game ends.  A base station is outside the playing area and provides logging and visualization services.

Demo Implementation

Location

Richmond Field Station

Playing Field

20m x 20m

Coordinate System

Aligned with the GPS coordinate system with origin at the southeast corner of the field

Sensor Network

100-400 motes with sensor boards dropped from helicopter on a grid spacing of 1-2m

Evader

1 Pioneer robot

Pursuer

2-3 Pioneer robots

Functional Outline

Pursuers

1.       Initialize

2.       Listen for updates from the sensor network

3.       Communicate, coordinate with the other pursuers if necessary

4.       Actuate to capture the evader

5.       Debugging/logging output

6.       Go to Step 2 if evader has not been caught

7.       Done

Mote Sensors

1.       Initialize and calibrate

a.       Position and velocity estimates require the sensor motes to have self-localization

b.       ... and time synchronization

c.       Robust routing protocols may require initial network measurements

2.       Estimate the position and velocity of pursuers and evaders

a.       Filtering and sensor data reduction at each mote

3.       Send estimates to pursuers

4.       Debugging/logging output

5.       Go to Step 2 until "Stop"

6.       Done

Evaders

1.       Human controlled

2.       Smart mote evaders get some subset of

a.       Listens to the network traffic

b.       Knows the pursuit algorithms

c.       Knows the pursuer dynamics

3.       Smart evaders maximally exploit any data they gather


Chapter 3: Abstract Architecture

Overall Architecture

The architecture defines a set of components which may implement algorithms and may behave as services.  The architecture further defines the input and output structures and protocols accepted and emitted by components, implicit or explicit constraints and behaviors pertinent to the components, and interrelationships between components.

 

In this chapter, we first define just the subset of the architecture seen from the application layer: the pursuit-evasion game demo.  From there, we iteratively extend that architecture with likely supporting components up-to and including top-level TinyOS components.  As this document evolves, we will keep an eye toward abstraction and generality; ideally creating a refactored specification with broader application than just the game demo.

Methodology

Prototypes

Prototypes are the essence of the architecture.  Prototypes define the minimal interface provided by components.  The goal is to create an architecture in which dissimilar implementations of components are interchangeable if they provide equivalent facilities, while at the same time not imposing unnecessary constraints on the underlying algorithms.

 

These Prototypes formally describe the API that certain classes of components and algorithms must adhere to.  Concrete implementations of these prototypes provide at least the described interfaces, but may include additional interfaces specific to the algorithm at hand, such as Sensor's and Actuator's.  Concrete implementations that wish to be used in the demo must fully specify themselves in the context of this document.  That is, they must clearly define their abstract, formal, NesC, and graphical architectures.  These concrete specifications will be wholly included in the architecture document.

Services

Each service is implemented as a separate component.  We intend a coordination component that provides scheduling of other components and management of shared resources.  Each component is initialized in turn, during which it is responsible for registering itself with the coordination component.  Each component registers how often it should be executed (time-triggered) and which events it should receive (messages, sensor readings, etc).  The coordination component is responsible for meeting these demands of the components.

Filtering and Calibration Interfaces

To filter data or calibrate a sensor or actuator, we intend to create components that both provide and use the interface they are filtering/calibrating. This allows us to chain any number of filters or calibrations transparently.

Application Architecture

These are the components we expect to directly use at the application level for the game demo.

PrototypeCritterListM

Send and receive critter lists between the application layer and the middleware.  The list may contain estimates for only some subset critters detected in the playing field.  A critter list (critterList_t) is a list of estimated critter attributes (critterAttribs_t): identity, position, position error, velocity, velocity error.

PrototypeRobotControlM

Provides low-level control (RobotControl) of the robot by allowing both adjustments to the robot's turning angle and speed.  Current estimates on these physical quantities may also be retrieved.

PrototypePursuitAlgorithmM

Responsible for computing the pursuers' game strategy and carrying it out.  Each pursuer receives the critter estimates (ReceiveCritterListMsg), processes those estimates, develops a game strategy, communicates with other pursuers (SendPursuitMsg and ReceivePursuitMsg), and adjusts its heading and speed (RobotControl) to carry out the strategy.

Prototype Middleware Architecture

Actuator

Set the value of a device that manipulates (actuates) some aspect of the environment.

PrototypeActuatorTransformM

Transform from an Actuator to an Actuator, probably for calibrating from units meaningful for the environment to units meaningful to the actuator.

Sensor

Read the current value from a device that measures (senses) some aspect of the environment.

PrototypeSensorTransformM

Transform from a Sensor to a Sensor, probably for calibration or filtering.

PrototypeLocalizationM

Provide the position (Position) of the current mote using acoustic localization where a series of motes transmit synchronized, stamped radio and audio messages.  The data packet (localization_t) may contain some amount of pertinent information, which is sent (SendLocalizationMsg) and received (ReceiveLocalizationMsg) using appropriate interfaces.  The acoustic measurements interface to the sounder (Actuator) and the microphone (Sensor).  An arbitrary localization service will conform as closely as possible to the interface specified in this sample implementation.

PrototypeTimeSyncM

Provide synchronized global time (Time).  This module implements trivial time synchronization: a beacon mote broadcasts a message declaring global time zero.  The time between physical emission of the sync message and the incoming message timestamp is assumed to be virtually invariant across all motes and all mote states.  All listening motes take the time stamp on the received message (ReceiveStampedMsg) as global time zero.  The beacon mote will not be synchronized.  An arbitrary time synchronization service will conform as closely as possible to the interface specified in this sample implementation.

PrototypePacketRoutingM

Basic routing component.  An incoming packet is processed by the component and either re-sent (with possibly a new immediate destination) or delivered to the local mote.  The intent is that this component can be transparently wired to any component that receives packets.  It uses the basic packet routing interfaces (SendMsg and ReceiveMsg).

PrototypeEstimateCrittersM

Aggregates sensor readings among a group motes and fires a CrittersPosition event for client components in the current mote.  The estimation requires knowing the current mote position in space, sensor readings from the current mote, and an infrastructure for sending and receiving current sensor readings to other motes for aggregation.

Debugger

Sample "debugger" interface for emitting LED state and strings that are useful primarily in a debugging context.  To be disabled, a null debugger interface may be wired in, instead.

Concrete Middleware Architecture

TODO: All concrete implementations (that is, actual middleware components) of the prototype modules must be described in a similar fashion.


Chapter 4: Formal Architecture

PrototypeCritterListM

·         T_period = 1 s; frequency of position estimates

·         T_jitter = 0.1 s; maximum jitter in T_period

 

TODO: Create formal architecture specifications for all prototypes.

 

TODO: All concrete implementations of the prototype modules must also be described in a similar fashion.


Chapter 5: NesC Architecture

Methodology

Resources

By default, we are not providing a resource sharing infrastructure beyond the sharing of the CPU and RF channel via the service coordination component.  That is, we are assuming that in any particular configuration, no more than one component will want to use, say, the sounder.  Creating a configuration in which more than one component needs access to the same resource is considered malformed.  If this becomes a problem in practice, we will work to develop a resource sharing scheme.  We are deferring that solution until we see conflicts arise in practice.   That way, we can develop something well-suited for the problem (instead something ill-suited).

Input/Output Convention

Sensors readings (input) are event driven. Processing dependent on sensor readings are also events, say for filtering data. And, it cascades all the way up; events are fired for both estimating position and initiating the broadcast of those estimates. Actuation (output) is command driven; that includes both movement and outgoing communication.

Send/Receive Structures

We want to abstract from byte-packed messages used for radio communication. Each component that communicates via messages to other components (either on the local mote or remote motes) operates in the context of a structure containing native types. We package all relevant information in a single structure. This reduces the need to redefine interfaces when/if we adjust only the particular data passed between components. This also results in a one-to-one correspondence between message interfaces and message structures.

 

Modules

module PrototypeActuatorTransformM {
    provides {
        interface Actuator;
    } uses {
        interface Actuator as OutgoingActuator;
    }
}
module PrototypeCritterListM {
    provides {
        interface ReceiveCritterListMsg;
    } uses {
        interface ReceiveCritterListMsg;
        interface SendCritterListMsg;
    }
}
module PrototypeEstimateCrittersM {
    provides {
        interface CrittersPosition;
    } uses {
        interface ReceiveEstimateCrittersMsg;
        interface SendEstimateCrittersMsg;
    }
}
module PrototypeLocalizationM {
    provides {
        interface Position;
    } uses {
        interface SendLocalizationMsg;
        interface ReceiveLocalizationMsg;
    }
}
module PrototypePacketRoutingM {
    provides {
        interface ReceiveMsg;
    } uses {
        interface ReceiveMsg as IncomingMsg;
        interface SendMsg;
    }
}
module PrototypePursuitAlgorithmM {
    provides {
        interface StdControl;
    } uses {
        interface ReceiveCritterListMsg;
        interface RobotControl;
        interface SendPursuitMsg;
        interface ReceivePursuitMsg;
    }
}
module PrototypeRobotControlM {
    provides {
        interface RobotControl;
    } uses {
    }
}
module PrototypeSensorTransformM {
    provides {
        interface Sensor;
    } uses {
        interface Sensor as IncomingSensor;
    }
}
module PrototypeTimeSyncM {
    provides {
        interface Time;
    } uses {
        interface ReceiveStampedMsg;
    }
}

Interfaces

interface Actuator {
    command result_t setValue(
        int value
    );
}
interface CrittersPosition {
    event result_t newCrittersPosition(
        critterList_t* list
    );
}
interface Debugger {
    command result_t led_int(
        int value;
    );
    command result_t message(
        char* msg
    );
}
interface Position {
    command result_t getPosition(
        position_t* position
    );
}
interface ReceiveCritterListMsg {
    event result_t receiveCritterList(
        critterList_t* msg
    );
}
interface ReceiveEstimateCrittersMsg {
    event result_t receivePursuitMsg(
        estimateCritters_t* msg
    );
}
interface ReceiveLocalizationMsg {
    event result_t receivePursuitMsg(
        localization_t* msg
    );
}
interface ReceivePursuitMsg {
    event result_t receivePursuitMsg(
        pursuit_t* msg
    );
}
interface ReceiveStampedMsg {
    event result_t receiveStampedMsg(
        TOS_MsgPtr msg,
        time_t* time
    );
}
interface ReceiveTimeSyncMsg {
    event result_t receiveTimeSyncMsg(
        timeSync_t* msg
    );
}
interface RobotControl {
    command result_t setSteeringWheel(
        int value
    );
    command result_t setSpeed(
        int value
    );
    command result_t getSteeringWheel(
        int* value
    );
    command result_t getSpeed(
        int* value
    );
}
interface SendCritterListMsg {
    command result_t sendCritterListMsg(
        critterList_t* msg
    );
    event result_t sendCritterListMsgDone();
}
interface SendEstimateCrittersMsg {
    command result_t sendLocalizationMsg(
        estimateCritters_t* msg
    );
    event result_t sendLocalizationMsgDone();
}
interface SendLocalizationMsg {
    command result_t sendLocalizationMsg(
        localization_t* msg
    );
    event result_t sendLocalizationMsgDone();
}
interface SendPursuitMsg {
    command result_t sendPursuitMsg(
        pursuit_t* msg
    );
    event result_t sendPursuitMsgDone();
}
interface SendTimeSyncMsg {
    command result_t sendTimeSyncMsg(
        timeSync_t* msg
    );
    event result_t sendTimeSyncMsgDone();
}
interface Sensor {
    event result_t sensor (
        sensor_t* value
    );
}
interface StdControl {
    command result_t init();
    command result_t start();
    command result_t stop();
}
interface Time {
    command result_t getTime(
        time_t* time
    );
}

Types

typedef struct {
    int id;
    position_t pos;
    positionError_t posErr;
    velocity_t vel;
    velocityError_t velErr;
} critterAttribs_t;
typedef struct {
    unsigned int length;
    critterAttribs_t* critters;
} critterList_t;
typedef struct {
    /* ... define me ... */
} estimateCritters_t;
typedef struct {
    int moteID;
    /* ... and other pertinent stuff ... */
} localization_t;
typedef triple_t positionError_t;
typedef triple_t position_t;
typedef struct {
    int command;
    int value;
    /* ... maybe other stuff goes in here ... */
} pursuit_t;
typedef struct {
    int srcID;
    int value;
    int valueError;
} sensor_t;
typedef struct {
    /* ... define me ... */
} timeSync_t;
typedef unsigned int time_t;
typedef struct {
    int x;
    int y;
    int z;
} triple_t;
typedef triple_t velocityError_t;
typedef triple_t velocity_t;


Chapter 6: Graphical Architecture

TODO