COMMUNICATION
Distributed computing and reliable communication in sensor
networks using multi-agent systems
Stefan Bosse
Florian Pantke
Received: 14 July 2012 / Accepted: 15 October 2012 / Published online: 29 October 2012
Ó German Academic Society for Production Engineering (WGP) 2012
Abstract There is a growing demand for robust distrib-
uted computing and systems in sensor networks. Interac-
tion between nodes is required to manage and distribute
information. One common interaction model is the mobile
agent. An agent approach provides stronger autonomy than
a traditional object or remote-procedure-call based
approach. Agents can decide for themselves, which actions
are performed, and they are capable of flexible behaviour,
reacting on the environment and other agents, providing
some degree of robustness. The focus of the application
scenario lies on sensor networks and low-power, resource-
aware single System-On-Chip designs, i.e., for use in
sensor-equipped technical structures and materials. We
propose and compare two different data processing and
communication architectures for the implementation of
mobile agents in sensor networks consisting of single
microchip low-resource nodes. Furthermore, a reliable
smart communication protocol for incomplete and irregular
networks are introduced. Two case studies show the
suitability of agent-based approaches for distributed
computing.
Keywords Distributed computing Agent Sensor
network Energy management Data fusion
1 Introduction
Trends recently emerging in engineering and micro-system
applications such as the development of sensorial materials
show a growing demand for autonomous networks of
miniaturized smart sensors and actuators embedded in
technical structures [7]. With increasing miniaturization
and sensor-actuator density, decentralized network and
data processing architectures are preferred or required. A
multi-agent system can be used for a decentralized and
self-organizing approach of data processing in a distributed
system like a sensor network, enabling the mapping of
distributed data sets to related information, for example,
required for object manipulation with a robot manipulator.
Simplification and reduction of synchronization constraints
owing to the autonomy of agents is provided by the dis-
tributed programming model of mobile agents [5]. Tradi-
tionally, mobile agents are executed on generic computer
architectures [8, 10], which usually cannot easily be
reduced to single microchip level like they are required,
e.g., in sensorial materials with high sensor node densities.
In the following sections, we propose and compare two
different data processing and communication architectures
suitable for the implementation of mobile agents in sensor
networks consisting of single microchip low-resource
nodes. A reliable communication protocol suitable for
robust communication in agent based systems is introduced
and analysed. Finally, the two agent processing architec-
tures are compared.
S. Bosse (&)
Department of Computer Science, Workgroup Robotics,
University of Bremen, Bremen, Germany
e-mail: sbosse@uni-bremen.de
S. Bosse F. Pantke
ISIS Sensorial Materials Scientific Centre,
University of Bremen, Bremen, Germany
F. Pantke
TZI-Center for Computing and Communication Technologies,
University of Bremen, Bremen, Germany
123
Prod. Eng. Res. Devel. (2013) 7:43–51
DOI 10.1007/s11740-012-0420-8
2 Distributed data processing with state-based agents
Initially, a sensor network is a collection of independent
computing nodes. Interaction between nodes is required to
manage and distribute data and computed information. One
common interaction model is the mobile agent. An agent is
capable of autonomous action in an environment with the
goal to meet its delegated objectives. An agent is a data
processing system, a program executed on a computer
system, that is situated in this environment [11]. A multi-
agent system is a collection of loosely coupled autonomous
agents migrating through the network. Agents can be used
in sensor networks for
Sensor data processing and extraction
Sensor data fusion, filtering, and reduction of sensor
data to information in a region of interest
Sensor data and information distribution and transport
Global energy management, exploration and negotiation
Agents can operate state-based. Such an agent consists
of a state, holding data variables and the control state, and a
reasoning engine, implementing behaviours and actions. In
this proposed data processing and communication archi-
tecture, the state of an agent is completely kept in messages
transferred in the network providing agent mobility. The
functional behaviour of an agent can be easily implemented
statically with a finite-state machine part of the local data
processing system on register-transfer level (RTL), or
dynamically by using a programmable code approach.
Agents record information about the environment state
e2E and history. Let I be the set of all internal states of the
agent. An agent’s decision-making process is based on this
information. The perception function see maps environ-
ment states to perceptions, function next maps an internal
state and percept to an internal state, the action-selection
function action maps internal states to actions (see also
Fig. 1):
see : E ! Per
next : I Per ! I
action : I ! Act
3 Approach I: non-programmable message-based/state
machine agent processing architecture
Figure 2 shows the first proposed non-programmable exe-
cution environment used for the data processing of mobile
agents. This execution environment is preferred for low-
resource implementations of mobile agents with low
algorithm complexity. All nodes must comply with data
structures and message formats specified at design time
required for the cooperation of agents. There is a message
module implementing smart adaptive delta-distance
routing of messages (SLIP, the Scalable Local Intranet
Protocol, explained later), providing some kind of fault-
tolerance regarding interconnect failures, and several finite-
state machines implementing the agent behaviours and
providing virtual machines able to process incoming
agents. All parts are mappable to digital logic on RT level
and single-SoC system architectures, a prerequisite for
miniaturized sensor nodes embedded in structures and
sensorial materials.
The functional agent behaviour is implemented with a
(non-mobile) finite state machine (virtual machine) built in
the sensor node, modelled with a high-level synthesis
approach on an imperative multi-process programming
language level [1]. Inter-agent communication is provided
by shared data structures, available on each sensor node.
Each node is represented by a node agent, too, to ensure
Fig. 1 State-based agents and interaction with environment
AGENT
STATE
M
A-Queue
MESSAGE
POOL
SCHEDULER
M
M-QueueM-Queue
Sensor
SoC
Micro-
chip
Messages
Finite
State
Machine
RTL
DATA PRO.
COMMU.
AGENT VM
AGENT
STATE
A-Queue
AGENT VM
Fig. 2 Sensor node building blocks providing mobility and process-
ing for multi-agent systems: parallel agent virtual machines, agent-
processing scheduler, communication, and data processing. All parts
are mappable to digital logic on RTL and SoC system architecture
44 Prod. Eng. Res. Devel. (2013) 7:43–51
123
interaction and information exchange between mobile
agents and the sensor node. All interacting agents must
comply about the data structures and types, fixed at design
time. A scheduler is responsible to map incoming messages
(M), holding information about the agent class and agent
state, to agent executions frames (A), passed to an agent
virtual machine by using queues. Finally, the scheduler
transforms the state of finished agents ready for migration
to messages and passes them to the communication unit by
using queues, too. The design process is shown in Fig. 3,
and requires the textual specification of the agent on
algorithmic and programming level (left part). This speci-
fication is transformed into an abstract agent finite state
machine (FSM) model, the state memory layout (middle
part), and the message structure. Finally the microchip
implementation on RTL (right part) can be synthesized
from this intermediate representation, creating an applica-
tion specific processing environment for mobile agents.
4 Approach II: programmable multi-agent processing
architecture using code morphing
Multi-agent systems providing migration mobility using
code morphing can help to reduce the communication cost
in a distributed system [3]. The second proposed hardware
architecture and run-time environment is specifically
designed towards the implementation of mobile agents by
using dynamic code morphing under the constraints of low-
power consumption and high component miniaturization.
Code morphing is the ability of a program to modify its
own program code to reflect state changes and embedding
computational results. The advantage of this distributed
computation model using code morphing is the computa-
tional independence of each node and the eliminated
necessity for nodes to comply with previously defined
common data types and structures as well as message
formats. Computing nodes perform local computations by
executing code and cooperate by distributing modified
code (carrying embedded information) to execute a global
task. It uses a modified and extended version of FORTH as
the programming language for agent programs. FORTH is
a stack-based interpreted language whose source code is
extremely compact. Furthermore, FORTH is extensible,
that is new language constructs (called words, zero-oper-
and functions) can be defined on the fly by its users.
A FORTH program contains built-in core instructions
directly executed by the FORTH processing unit and user-
defined high-level word and object definitions that are
added to and looked up from a dictionary data structure.
This dictionary plays a central role in the implementation
of distributed systems and mobile agents. Words can be
added, updated, and removed (forgotten), controlled by the
FORTH program itself. User-defined words are composed
of a sequence of words. The principal system architecture
of one lFORTH processing unit (PU, part of the node
runtime environment) is shown in Fig. 4. A complete run-
time unit consists of a communication system with the
smart routing protocol stack SLIP, one or more lFORTH
processing units with a code morphing engine, resource
management, code relocation and dictionary management,
and a scheduler managing program execution and distri-
bution, that are normally part of an operating system,
which does not exist here. A lFORTH processing unit
initially waits for a frame (a FORTH program) to be exe-
cuted. During program execution, the lFORTH processing
Type Perc = Record
energy : Integer;
links: Connectivity;
End;
Function see(node) : Perc =
Begin
VAR p:Perc;
p.energy:=Node.energy-ET;
p.links:=Node.links;
Return p;
End;
Function next(s,p) : State =
Begin
Case s of
| Explore =>
If p.energy > ET Then
Return Stay;
| ..
End;
Procedure action (s) = ...
Agent Specification
Type Message =
Record
state: State;
energy: Integer;
migration: Bool;
...
End;
Agent Message Structure
Agent Finite State Machine
state
energy
perception
....
Agent State Memory
AGENT
STATE
AGENT VM
A-Queue
COMMUN.
MESSAGE
POOL
SCHEDULER
DATA PRO.
M-Queue
SoC
Microchip
Finite
State
Machine
RTL
System On Chip/RTL
Architecture
S1
S2
S3
Algorithmic &
Programming Level
Fig. 3 Design process for state-machine based agent implementation
Prod. Eng. Res. Devel. (2013) 7:43–51 45
123
unit interacts with the scheduler to perform program
forking, frame propagation, program termination, object
creation (allocation), and object modification. The sched-
uler is the bridge between a set of locally parallel exe-
cuting lFORTH processing units, and the communication
system, a remote procedure call (RPC) interface layered
above SLIP, providing fault-tolerant message-based com-
munication system used to transfer messages (containing
code) between nodes using smart XY delta-distance vector
routing.
The simple FORTH instruction format is an appropriate
starting point for code morphing, i.e., the ability of a pro-
gram to modify itself or make a modified copy, mostly as a
result of a previously performed computation. Calculation
results and a subset of the processing state can be stored
directly in the program code, which changes the program
behaviour. The standard FORTH core instruction set was
extended (see Table 1) and adapted for the implementation
of agent migration in mesh networks with two-dimensional
grid topology. In our system, a lFORTH program is con-
tained in a contiguous memory fragment, called a frame. A
frame can be transferred to and executed on remote nodes
and processing units. The virtual lFORTH machine can
execute most of the core words from the FORTH core
programming language.
All architecture parts of the multiprocessor-FORTH
node, including SLIP communication, lFORTH process-
ing units, scheduler, dictionary and relocation support, are
mapped entirely to hardware multi-RT level and a single
SoC design using the ConPro compiler [1]. The resource
demand depends on the choice of design parameters and is
in the range of 1M–3M equivalent gates (in terms of FPGA
architectures). The entire design is partitioned into 43
concurrently executed sequential processes, communicat-
ing by using 24 queues, 13 mutex, 8 semaphores, 52 RAM
blocks, 59 shared registers, and 11 timers.
5 Robust and reliable communication for mobile agent
systems
Most actual work in communication focusses on wireless
networks [9]. But sensorial materials and highly integrated
robotics systems require basically wired networks [7]. The
Scalable Local Intranet Protocol (SLIP) and a communi-
cation controller design was developed for message based
robust communication in low-resource and low-power
sensor networks [2]. To meet the goal of miniaturization
and low-power capability, the protocol must be capable of
implementation in SoC and RTL designs, and adaptable to
local communication requirements.
5.1 Reliable communication protocol SLIP
SLIP is scalable with respect to network size (address size
class (ASC), ranging from 4 to 16 bit), maximal data
payload (data size class (DSC), ranging from 4 to 16 bit
length) and the network topology dimension size (address
dimension class (ADC), ranging from 1 to 4). Network
nodes are connected using (serial) point-to-point links, and
they are arranged along different metric axes of different
geometrical dimensions: a one-dimensional network
(ADC = 1) implements chains and rings, a two-dimen-
sional network (ADC = 2) can implement mesh grids, a
three-dimensional (ADC = 3) can implement cubes, and so
on. Both incomplete (missing links) and irregular networks
SCHEDULER
CS
PC FRM
μFORTH
PROCESSING UNIT
SS
DS
RS
FRAME
FRAME’
PC’ FRM’
FRAME
ES
DATA
STACK
RETURN
STACK
EXCEPTION
STACK
CODE SEGMENT DATA SEGMENT
DICTIONARY
LUT
OBJ
SLIP / RPC Communication
Fig. 4 Mobile-agent run-time
architecture providing code
morphing, consisting of FORTH
data processing units, shared
memory and objects, dictionary,
scheduler, and communication
(PC Program Counter, FR*M*
Frame Pointer, OBJ Object
Pool, CS Code, LUT Lookup
Table, *S Stack)
46 Prod. Eng. Res. Devel. (2013) 7:43–51
123
(with missing nodes and links) are supported for each
dimension class, shown in Fig. 5.
The main problem in message-based communication is
routing and thus addressing of nodes. Absolute and unique
addressing of nodes in a high-density sensor network is not
suitable. An alternative routing strategy is delta-distance
routing, used by SLIP. A delta-distance vector D specifies
the way from the source to a destination node counting the
number of node hops for each dimension. A message
packet contains a header descriptor specifying the type of
the packet and the scalable parameters ASC, DSC, and
ADC, shown in Table 2. The network adress dimension
ADC and the size class ASC reflect the network topology,
the data size class DSC the data payload. There are two
different main message types: requests and replies. A
packet descriptor follows the header descriptor, contain-
ing:the actual delta-vector D, the original delta-vector D
0
,a
preferred routing direction x, an application layer port p,a
backward-propagation vector C, and the length of the fol-
lowing data part. The total bit length of the packet header
depends on the fASC; DSC; ADCg scalable parameter tuple
setting, which optimises application specific the overhead
and energy efficiency (spatial & temporal). Each time a
packet is forwarded (routed) in some direction, the delta-
vector is decreased (magnitude) in the respective dimen-
sion entry. For example, routing in x-direction results in:
D
1
¼ D
1
1. A message has reached the destination iff
D ¼ 0 and can be delivered to the application port p. There
are different smart routing rules, applied in order showed
below until the packet can be routed (or discarded), shown
in Ex. 5. First the normal XY routing is tried, where the
packet is routed in each direction one after another with the
goal to minimize the delta count of each particular direc-
tion. If this is not possible (due to missing connectivity),
the packet is tried to send to the opposite direction,marked
in the gamma entry C part of the message packet
descriptor. Opposite routing is used to escape small area
traps, backward routing is used to escape large area traps or
to send the packet back to the source node (packet not
deliverable). The routing decision is based on the actual
NODE
1
NODE
2
NODE
3
NODE
4
NODE
5
NODE
6
NODE
9
NODE
10
NODE
11
NODE
12
Y
X
NODE
7
NODE
8
HDT PDT DATA
ADC
TYP
DSC
ASC
1
ΔΔ
Γ
π
LEN
Fig. 5 Message based communication in two-dimensional networks
using delta-distance vector routing. Networks with incomplete
(missing links) and irregular (missing nodes) topologies are supported
by using smart routing routes
Table 1 lForth extensions for code morphing and agent migration support
Word Description
frame c! SETC: Sets frame of shadow environment for code morphing
m1 m2 [[ c COPYC: Switches to morphing state: Transfers code from program frame between two markers m1 and m2 into shadow frame
(including markers)
[c TOC: Copy next word from program frame into shadow frame
n s[c STOC: Pop n data value(s) from stack and store values as word literals in shadow frame
\m[ MARKER: set a marker position anywhere in a program frame
dx dy fork Send contents of shadow frame for execution to node relative to actual node. If dx = 0 and dy = 0, the shadow
frame is executed locally and concurrently on a different FORTH processing unit
Prod. Eng. Res. Devel. (2013) 7:43–51 47
123
message entries fD; C; xg and achieves adaptive routing
reflecting the actual network topology and the path the
message already had travelled, including back-end traps,
resulting in alternative paths by choosing different routing
directions.
A message is only send to a neighbour node using the
particular link iff the connection to the neighbour node was
negotiated and is fully operational concerning the sending
and the receiving of messages to and from the neighbour
node. For this purpose, the communication controller sends
periodically ALIVE messages to all direct surrounding
nodes and waits for ACKNOWLEDGE messages send back
from the neighbour node to check the state of a connection.
Non-existing nodes can be detected this way, too.
The hardware implementation (using Conpro and stan-
dard cell ASIC synthesis) requires about 244k gates, 15k
FF % 2.5 mm
2
assuming ASIC standard cell technology
0.18 lm. The design is partitioned on programming level in
34 processes, communicating by using 16 queues.
5.2 Robustness and stability analysis
A simulation of a sensor network consisting nodes arranged
in a two-dimensional matrix with 10 rows and 10 columns
was performed by using a multi-agent model. Messages and
sensor nodes were modelled with agents. A comparison of
XY and smart routing using the routing rules introduced in
Ex. 1 is shown in Fig. 6. The diagram shows the analysis
results of operational paths depending on the number of link
failures. A path is operational (reachable) iff a node (device
under test), for example node at position (2,2), can deliver a
request message to a destination node at position (x,y) with
x = 2_y = 2, and a reply can be delivered back to the
requesting node. A failure of a specific link and node results
in a broken connection between two nodes. The right image
in Fig. 6 shows an incomplete network with 100 broken
links. With traditional XY routing there is a strong decrease
of operational paths, from a specific node (DUT) to any
other node, if the number of broken links increases. Using
smart routing increases the number of operational paths
significantly, especially for considerable damaged net-
works, up to 50 % compared with XY routing providing
only 5 % reachable paths any more.
Results from stability analysis shown in Fig. 7 point out
unstable behaviour under some particular network topolo-
gies. Though most situations are live lock free, there are
some live locked messages circulating for ever in some
isolated traps, shown for example in the snapshot on the
right side of this figure.
6 Case study I: energy management in sensor networks
Global energy management and distribution in sensor
networks introduces the first application for distributed
computing using agents. Energy management in sensor
network can take place:
LOCALLY
At design time: low-power, application specific
single System-On-Chip design
At run-time: computation on demand, parametriza-
tion of algorithms with cost-feedback analysis,
control of duty-cycle of computation and sleep mode
GLOBALLY
Distribution and collection of energy between nodes
(demonstrated by simulation and experiment in [4])
Energy Management by exploring and exploiting the
neighbourhood of nodes
Table 2 SLIP message format (HDT: header descriptor, PDT: packet
descriptor)
Entry Size [bits] Description
HDT:ADC 2 Address Dimension Class
HDT:ASC 2 Address Size Class
HDT:DSC 2 Data Size Class
HDT:TYP 2 Message type = {Request,
Reply, Alive,
Acknowledge}
PDT:D Num(ADC)*Bits(ASC) Actual delta vector
PDT:D
0
Num(ADC)*Bits(ASC) Original delta vector
PDT:C 2*Num(ADC) Backward propagation vector
PDT:x Bits(ADC) Preferred routing direction
PDT:p Bits(ASC) Application layer port
PDT:LEN Bits(DSC) Length of packet
DATA LEN*Bits(DSC) Data
48 Prod. Eng. Res. Devel. (2013) 7:43–51
123