=Paper=
{{Paper
|id=Vol-1128/intro14
|storemode=property
|title=(Re-)configuration of Communication Networks in the Context of M2M
|pdfUrl=https://ceur-ws.org/Vol-1128/paper14.pdf
|volume=Vol-1128
|dblpUrl=https://dblp.org/rec/conf/confws/NicaW13
}}
==(Re-)configuration of Communication Networks in the Context of M2M==
https://ceur-ws.org/Vol-1128/paper14.pdf
Iulia Nica, Franz Wotawa 101
(Re-)configuration of Communication Networks in the Context of M2M
Applications
Iulia Nica and Franz Wotawa
Institute for Software Technology
Graz University of Technology, Graz, Austria
{inica,wotawa}@ist.tugraz.at
Abstract gains direct remote access to the interface between the net-
work and customer. This allows for instance turning off con-
Machine-to-machine (M2M) communication is of sumer loads whenever needed in order to prevent for example
increasing importance in industry due to novel ap- from a blackout.
plications, i.e., smart metering or tracking devices M2M communication has been a growing market that
in the logistics domain. These applications pro- causes more and more communication over mobile phone
voke new requirements for mobile phone networks, networks. Hence, mobile phone companies providing the in-
which have to be adapted in order to meet these fu- frastructure have to adapt their networks due to future needs.
ture requirements. Hence, reconfiguration of such Moreover, a M2M application provider has to be ensured
networks depending on M2M application scenarios that the current mobile phone network is capable of provid-
is highly required. In this paper, we discuss model- ing enough resource in order to carry out communication re-
ing for reconfiguration of mobile phone networks in quirements. Within the Simulation and Configuration of Mo-
case of M2M applications and present the founda- bile Networks with M2M Applications (SIMOA) project the
tions behind our tool including the used modeling objective has been to develop a simulation and reconfigura-
language and the reconfiguration algorithm. tion environment for smart metering applications in order (1)
to ensure that current mobile phone networks are capable of
providing enough resources (through simulation), and (2) to
1 Introduction give advice for changing either the smart metering solution
Because of the availability of communication networks al- or the communication network in cases of lack of resources
most everywhere new applications arise. Besides mobile (through reconfiguration). Hence, we first simulate a net-
phones for accessing the internet or simple making phone work configuration, in order to check whether this can sup-
calls, machine-to machine (M2M) communication becomes a port the set of user requirements, and, if the simulation fails
still growing application domain for mobile phone networks. (the requirements can not be fulfilled by the mobile network),
Connecting home appliances like alarm systems or heating a working reconfiguration of the given system has to be de-
installations remotely is one application area. Others are livered.
tracking of goods in the logistics domain and smart metering. In this paper, we focus on the SIMOA approach to recon-
The latter deals with metering of electrical power or water figuration comprising the modeling language SIMOL, which
consumption of homes on a fine granular basis of minutes or is an object-oriented language, and the reconfiguration engine
hours instead of months or even years. In many countries the that makes use of constraint solving and ideas from diagno-
administration enforces the use of smart metering in order to sis in order to compute system changes. The key concept
rise the customer’s awareness of their current consumptions of SIMOL is the definition of basic and hierarchical compo-
in order to reduce the need for electricity, water or other re- nents, which are used to represent the desired system. The
sources. behavior of a component has to be provided as set of equa-
Besides this educational effect, there are other advantages tions. If a component is a subclass of another component, the
of smart metering systems. The overall costs for metering equations of the superclass are taken together with the equa-
might be reduced because the more labor intensive man- tions of the component in order to specify the component’s
ual metering is not longer necessary. The supplier of re- behavior. In SIMOL, it is also possible to assign equations
sources gains more information regarding current consump- to specific behavior modes. Such a mode might represent a
tions, which likely improves prediction of consumptions and potential configuration like stating a component to be active
further allows for improving the stability of the overall sup- or inactive in a certain configuration. Alternatively, a mode
ply network. This is especially important for power networks might represent the range of values assigned to a certain pa-
where electricity has to be generated when needed. Unfor- rameter.
tunately, power plants cannot be turned on or off without Another feature of SIMOL is its ability to model the sys-
a substantial delay. Another advantage is that the supplier tems behavior over time. In this case, SIMOL allows for spec-
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
102 Iulia Nica, Franz Wotawa
ifying state transfer functions. Such a function itself is a set
of equations, that connect values of variables between one 7-13%11+9-
state and its successor state. SIMOL does not allow to deal
with continuous time. Only systems which can be modeled
using discrete time can be represented in SIMOL. The deci-
sion to restrict modeling to discrete time via states is due to
the requirements of the smart metering application domain, 'SQTMPIV
where not the continuous evolution of parameters is impor-
tant, but the their discrete values. Besides the model of the
system, also the system’s requirements can be modeled us-
ing SIMOL. Hence, every information needed for stating a
reconfiguration problem can be formalized using SIMOL.
The reconfiguration algorithm is based on model-based di- 6I'SRJ
agnosis, where the idea is to select one mode for each com-
ponent such that all system’s requirements are fulfilled. This
problem can be easily stated as constraint satisfaction prob- 'SRJMK'SVI
lem. Hence, we make use of an available constraint solver for
computing simulations and reconfigurations. In the follow-
ing, we discuss the whole SIMOA system architecture, the Figure 1: The SIMOA architecture
SIMOL language, and the reconfiguration algorithm in more
detail. A discussion on related research and a summary of the
content conclude this paper.
2 The SIMOA architecture
In Figure 1, we depict the SIMOA system architecture. The
architecture comprises at the highest level two parts: a graph-
ical user interface (SIMOA M2M GUI) and the configuration
core (ConfigCore). The latter is general and can be used in
various applications, whereas the other is application specific
and has to be tailored accordingly to the requirements. The
configuration core itself comprises a compiler that translates
models written in SIMOL into MINION constraints [Jeffer-
son et al., 2012; Gent et al., 2006]. MINION is a constraint
solver coming with its own constraint language, which is not
easily accessible for non-experts in constraint solving. The
reasons for choosing MINION were the easy integration into
the program written in Java and the very good reasoning per- Figure 2: The M2M user interface for the smart metering ap-
formance (being able to solve 8,000 constraints in less than plication
2 seconds). The MINION program is used in the reconfigu-
ration engine ReConf together with the MINION constraint
solver to compute valid reconfigurations, which are given parameters for components. In case of a reconfiguration, the
back as Results. GUI generates a SIMOL program that makes use of the com-
The interface between the graphical user interface and the ponents, their behavior and additional parameters. It is also
configuration core is represented by the SIMOL program and worth noting that also the positions of the components in the
the results obtained from ReConf. The SIMOL program com- map are used. For example, when specifying a base load (that
prises the information necessary to specify the system to be represents all the non-smart-metering traffic) for the mobile
reconfigured and the given pre-specified requirements. The phone network, the concrete assignment to cells is done con-
reconfiguration result is basically nothing else than a set of sidering the distance between the base load and the cell. If
possible component modes, that are necessary to fulfill the a base load is not within reach, there is no effect. If a base
requirements, together with the computed values for the at- load might influence two or more cells, the load is assigned
tributes. The presentation of these results to the user has to be to each cell accordingly to their distance. For example, closer
implemented in the user interface and is application specific. cells will have a larger percentage of the communication base
In Figure 2, the current user interface of the SIMOA M2M load than cells that are more far away.
application is given. This graphical user interface enables the The ConfigCore of the SIMOA architecture is general and
user to specify a smart metering application, by placing the can be used in various reconfiguration applications. In this
meters as well as the cells, which provide access to the mo- respect, we have conducted a series of experiments using,
bile phone network, among other components at the appro- for instance, combinational circuits from the well-known IS-
priate positions. Moreover, the user might specify additional CAS85 benchmark suite. Due to limitations of the ReConf
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Iulia Nica, Franz Wotawa 103
part, we do not handle generative constraints. Hence, build- we decided to adopt the syntax of Java. The program de-
ing systems from scratch using the given constraints is not picted in Figure 3 is a partial model used in our M2M appli-
possible in SIMOA. However, to some extent, configuration cation domain. The program comprises 4 components, which
of systems is possible by providing a model of a larger sys- model a Point-to-Point (P2P) individually addressable smart
tem, where parts can be activated or inactivated. In our ap- meter, a base transceiver station (BTS), the number of serv-
plication domain there is no impact due to restrictions, be- ing frequencies (FPC) and a mobile cell. Every component
cause the network, as well as the M2M application structure, definition starts with declaring the name of the component.
are already known and only small deviations are possible. Within a component, its attributes, constraints, and transitions
Therefore, providing information regarding structural system are defined. The latter is for defining the next state in order to
changes and changes in parameter is sufficient. In the next model discrete time and state machine models.
section, we discuss SIMOL in more detail. Moreover, we in-
troduce a basic algorithm for reconfiguration using SIMOL Syntax: Since SIMOL has a Java-like syntax, most of the
programs. For more information regarding the application defined tokens are Java-like, i.e., identifiers for any type of
domain we refer the interested reader to [Nica et al., 2012]. components and attributes, integers, and boolean literals, sep-
1. kbase GPRSCell; arators, arithmetic and relational operators (+, −, ∗, /, =, <
2. component P2PMeter { , >, <=, >=, ! =), comments and also reserved keywords. In
3. attribute int mdist,codeset,mRate; addition, it is also possible to use physical units like Watt (W),
4. constraints {
5. mdist = {1..3}; or Ampere (A), etc., for a more realistic description. Another
6. codeset = {1..4}; feature of the language is that the domain of the variables val-
7. } ues can be restricted. In Line 15 of the program depicted in
8. } Figure 3 only the values 2, 3, and 4 are allowed for variable
9. component FPC { value.
10. attribute int value;
11. constraints(default) { Every SIMOL program comprises 3 sections: (1) a knowl-
12. value = 1; edge based declaration section (Line 1) for organizing the
13. } files similarly to Java packages, (2) an import declaration sec-
14. constraints(x1) {
15. value = {2..4}; tion where knowledge bases can be loaded, and (3) compo-
16. } nent definitions (Line 2 to 45). The first 2 sections are op-
17. constraints(unknown) { tional, whereas the component definition section is manda-
18. tory. Each component definition starts with the keyword com-
19. }
20. } ponent followed by the name of the component and with an
21. component BTS { optional extends followed by a comma-separated list of com-
22. attribute int fpc; ponent names. If extends is used, we know that the new
23. constraints { component has one or more super components from which
24. FPC fpc1;
25. fpc = fpc1.value; constraints are inherited.
26. } In every component definition, we firstly define the com-
27. } ponent’s attributes after the attribute keyword. For example,
28. component Cell {
29. attribute int neededR, realR; in Line 3 the attributes midst, code set, and mRate are
30. constraints { defined. All these attributes are of type integer (int). Besides
31. BTS b1; attributes, constraints can be defined. There are two ways of
32. P2PMeter s[100];
33. realR=sum([s], mRate)/P2PNo; doing this. Either we use the keyword constraints directly
34. realR>=neededR; followed by a block in surrounding parentheses {}, or we use
35. ..
36. } the same keyword constraints followed by a mode name un-
37. transition { der parentheses () and again a block statement. The first defi-
38. forall ( P2PMeter ) { nition of constraints only allows for specifying a single com-
39. if (mdist=1 and codeset=2 ) ponent behavior. The other definition makes use of modes
40. codeset.next = {2,3};
41. if (mdist=3 and codeset=2 ) that are needed later on for configuration. For example, in
42. codeset.next = {2,1}; Line 11 to 19 three modes for the component FPC are defined.
43. } The default mode sets the value of variable value to 1.
44. } The x1 mode restricts the domain of value, where the con-
45. }
Figure 3: A (partial) SIMOL program straint solver can select one value from the range {2..4} when
computing reconfigurations. The last mode (unknown) does
not specify any value.
3 SIMOL syntax and semantics In the constraint section of a component definition the fol-
As already said, SIMOL is an object-oriented programming lowing types of statements are allowed in SIMOL:
language. Most of the basic features have been already de-
scribed elsewhere [Nica and Wotawa, 2011; 2012b]. How- • an empty statement: ;,
ever, in order to be self-contained, we briefly introduce and • a component instance declaration, with the possibility of
discuss SIMOL’s syntax and semantics. To be more acces- initializing its attributes. See for example Line 24 of the
sible for non-experts in configuration and constraint solving, GPRSCell knowledge base, where a new component
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
104 Iulia Nica, Franz Wotawa
fpc1 is generated as an instance of component FPC.
Using this kind of statements, we define the subcompo-
nent hierarchy in our model, i.e., the partonomy rela- constr(C) = constr0 (C) ∪ constrI (C) ∪ constrV (C)
tions. The cardinality of these relations (i.e., the number where constrI are the constraints inherited from the super
of subcomponents which can be connected to a certain components of C
component) is always finite. [
• an arithmetic or/and boolean expression constrI (C) = constr(C 0 )
C 0 ∈super(C)
• a conditional block starting with the keyword if and op-
tionally followed by an else. constrV are the constraints coming from the components
used in the definition of C (and requiring variable renaming
• special functions like forall, exist, sum, product, min, using the function replace that add a new pre-fix to the vari-
and max, that allow to state constraints over an array of ables used in the components in order to make them unique)
instances or values. For example, in Line 33 we sum the
mRate attribute of all P2PMeter stored in variable s. [
constrV (C) = replace(constr(C 0 ), N )
In addition, models written in SIMOL might be described
(C 0 ,N )∈vd inst(C)
over discrete time. For this purpose SIMOL makes use of
the transition section. Within the transition section the new Each constraint within the constraints { . . . } block con-
values of some, but not necessarily all variables, have to be tributes to constr0 (C) as follows:
defined. In our running example Line 37 to 43 define the next
values of the codeset variables for all P2PMeters. In or- • Cattr val : attribute-equals-value/s constraints, formu-
der to distinguish the new value of a variable in the successor lated with = operator and applied on component at-
state we make use of the keyword next. It is worth noting tributes together with one single integer/boolean value
that in the transition section we can use all statements from or with a set of values;
the constraint section. • Cattr attr : attribute-equals-attr constraints, formulated
with = operator and applied on component attributes;
Semantics: The following informal definition of the se- • Cnum : numeric constraints, formulated with basic rela-
mantics of SIMOL relies on mathematical equations. In par- tional operators over numeric expressions;
ticular the idea behind the semantics is to map all constraints • Ccond : conditional constraints,
that are assigned to one component to a set of equations. This
if (Cx is satisf ied) Cy must be satisf ied else Cz
also requires the combination of equations in case of multi-
must be satisf ied;
ple inheritance and component instances. In the first part of
the definition of the semantics we ignore discrete time. We • Cexist : existence constraints,
discuss this issue later in this section. exist(at least(N R) |at most(N R)|N R, C, AT T R =
For each component C defined in SIMOL we assume a set V ALU E), with the meaning that at most, at least or
of equations constr0 (C), representing the set of constraints exactly NR components of a given type C have
within the constraints(mode) { . . . } blocks. Then each con- AT T R = V ALU E.
straint Cmode within a constraints(mode) { . . . } block con- Note that the forall, sum, . . . constraints are similarly
tributes to constr0 (C), only if mode is active. Hence, we defined.
can define this as a conditional mode constraint Ccondmode :
if (mode is active) Cmode must be satisf ied and therefore How to handle time? Within the transition section we have
constr0 (C) becomes: constraints that define a relationship between the variables of
a state and its successor state. In order to represent states,
[ we introduce an index that is assigned to each variable used
constr0 (C) = constrmode (C) in constr(C). Hence, what we do is to define constraints
mode∈M ODES(C) that hold in each state i ∈ {0, . . . , s}, where s represents the
maximum number of considered states within a reconfigura-
where M ODES(C) is the set of functional modes, de- tion model. These constraints are obtained from constr(C)
fined for component C, and constrmode (C) is the set of con- by adding an index i to the variables. We represent these
ditional mode constraints. constraints using the function constri (C). For example, if
Moreover, the component C also receives equations from value = 1 is element of constr(C), then value 4 = 1
its super components and the instances used in the component is element of constr4 (C). Such constraints are valid within a
definition. Because of the possibility of having more than state and therefore called state constraints.
one instance of a component, we have to rename the vari- In addition to state constraints we require transition con-
ables used in the constraints of an instance. For this purpose, straints. The transition constraints can be easily computed
we assume a function replace that takes constraints M and a from the transition section. In principle we make use of the
name N and changes all variables x in M to N.x. Hence, the same translation as in the constraints block, but also take
set of equations that corresponds to a particular component C care of the next attribute assigned to variables. If a variable
is given by the following definition: v has such an attribute and we consider state i we replace
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Iulia Nica, Franz Wotawa 105
v.next with v i + 1. Variables v without the next attribute Definition 1 (Reconfiguration problem) A recon-
are changed to v i. Hence, we obtain all transition constraints figuration problem can be defined as a tuple
transi (C) for state i and component C. (KB, COM P, M ODES), where KB = SD ∪ REQ
In summary, the constraints for the whole SIMOL program is the knowledge base comprising the model of the system
can now be obtained as follows: SD and the requirements REQ, COM P is a set of system
components, and M ODES is the set of functional modes for
[ [ the elements of COM P .
constr = (constri (C) ∪ transi (C))
i∈{0,...,s} C
The reconfiguration problem consists in searching for an
assignment of modes to each component, such that the knowl-
Hence, the set of the obtained equations represents the be- edge base together with this assignments is satisfiable.
havior of the SIMOL program. It is worth noting that we As already mentioned, all information regarding the recon-
took the semantic definition based on equations from the se- figuration problem can be obtained from SIMOL programs.
mantics of Modelica [Fritzson and Bunus, 2002]. In contrast The program from Figure 3 allows us to derive the knowledge
to Modelica the handling of time is different as well as some base KB, which is the set of equations constr representing
of the functions that can be used within SIMOL. the semantics of the SIMOL program, the set of components
COM P = {P2PMeter, FPC, BTS, Cell}, and the set of
4 Reconfiguration in SIMOA modes M ODES = {def ault, x1, unknown}.
Before stating a configuration algorithm, which is based on Definition 2 (Mode assignment) Given a set of components
the diagnosis algorithm ConDiag [Nica and Wotawa, 2012a], COM P and a set of functional modes M ODES. A mode
we introduce and discuss some basic definitions. We first assignment M is a function M : COM P 7→ M ODES
formalize the reconfiguration problem. The reconfiguration mapping each component to one of its modes, i.e., for all
problem requires information on the current system and the c ∈ COM P : M (c) ∈ modes(c).
new requirements. Note that the current system may fulfill Having now all ingredients we are able to formally state a
the given requirements. In this case no changes of the cur- reconfiguration as follows:
rent system are required. For the information needed of the
current system we follow a component-oriented engineering Definition 3 (Reconfiguration) Given a reconfiguration
approach and assume that the structure as well as the behav- problem (KB, COM P, M ODES). A mode assignment M
ior has to be represented. The behavior of course has to cap- is a valid reconfiguration iff KB ∪ {M (c)|c ∈ COM P } is
ture those aspects relevant for configuration. In particular the satisfiable.
functionality of the system has to be modeled. In reconfiguration we are interested in finding mode as-
In addition we assume that for each component of the sys- signments that do not imply too many changes. Hence, we
tem we know how to reconfigure the component. Here we can use the number of required system changes to indicate
borrow the idea coming from Model-Based Diagnosis (MBD) the optimality of a reconfiguration. The number of changes
[Reiter, 1987; de Kleer and Williams, 1987] and introduce necessary in a mode assignment is the number of used modes
modes for components. Hence, every component has at least that are not equivalent to the def ault mode.
one mode. We assume the def ault mode to be the stan-
dard mode of a component, and all other modes to be po- Definition 4 (Number of changes) Given a reconfiguration
tential reconfigurations of this component. For simplicity, M for a reconfiguration problem (KB, COM P, M ODES).
we introduce a function modes : COM P 7→ M ODES The number of changes (N OC) of M is equivalent to the
mapping components from COM P to their M ODES. At number of modes in M deviating from the def ault modes,
least def ault has to be element of modes(c) for all compo- i.e., N OC(M ) = |{M (c)|c ∈ COM P ∧ M 6= def ault}|.
nents c ∈ COM P . The SIMOL language allows for spec- We say that a reconfiguration M is optimal with respect to
ifying models of systems comprising components and their its N OC if it is minimal, i.e., there exists no other reconfigu-
modes. For example, in lines 2–27 of our running example ration M 0 with N OC(M 0 ) < N OC(M ). This definition of
from Figure 3 the components P2PMeter, FPC and BTS minimality corresponds to cardinality minimality in diagno-
are defined. P2PMeter and BTS only have one mode (i.e., sis, which is different from the usually used subset minimality
the def ault mode), whereas for FPC, 3 modes (def ault, x1, of diagnosis (see [Reiter, 1987]). However, for the purpose of
and unknown) are defined. reconfiguration minimality based on cardinality seems to be
Besides the structure and behavior of the system, we have a better choice.
to define the new system requirements. System requirements After stating the underlying definitions we introduce an al-
in our context are nothing else than constraints, which a sys- gorithm for reconfiguration that is based on ConDiag [Nica
tem has to fulfill. For example, we might say that the mobile and Wotawa, 2012a]. Computing reconfigurations in our con-
phone network has to be capable of servicing 100 smart me- text is nothing else than searching for minimal mode assign-
ters at once in a particular area, given the communication re- ments, i.e., mode assignments that are as close to the original
quirements of the smart meters. In the context of SIMOA this assignments as possible. When assuming that small changes
information again is specified using SIMOL. For example, lead to a satisfiable knowledge base, it would be good to
lines 28–45 of the program from Figure 3 are for specifying start search considering small deviations of mode assign-
exactly those requirements. ments from the def ault mode first. The number of changes
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
106 Iulia Nica, Franz Wotawa
can be increased if no solution is found. Therefore, an itera- 5 Empirical results
tive algorithm seems to be sufficient.
In this section we report on first empirical results obtained
using a SIMOL model of our application domain, i.e., smart
Algorithm 1 reconfig(KB, COM P, M ODES, n) metering. The SIMOL source code has 95 lines of code, de-
scribing a model with one, two, or three cells, where each cell
Input: A reconfiguration problem
contains from 7 up to 100 P2PMeter components. When
(KB, COM P, M ODES) and the maximum N OC
compiling the SIMOL program to its MINION representa-
n
tion, considering at maximum 5 states, we obtain up to 2,387
Output: All minimal reconfigurations (up to the predefined
variables and 7,320 constraints, depending on the the number
cardinality n)
of smart meters considered. In principle, there are many pos-
sibilities of mapping SIMOL to MINION and also for com-
1: for i = 0 to n do puting solutions for a given maximum number of changes
2: CM = {|{M (c)|c ∈ COM P ∧ M 6= def ault}| = i}∪ N OC. In the following, we discuss the encoding of SIMOL
KB modes within MINION and show that the choice of certain
3: S = P (CSolver(CM )) MINION parameters influence the computation of reconfigu-
4: if S 6= ∅ then rations substantially.
5: return S
6: end if The mode encoding in MINION is rather straightforward.
7: end for In principle, a mode of a component can be either active or
8: return ∅ inactive. Therefore, we map each mode modex to a Boolean
variable in MINION, which is 1 (true) if the corresponding
component is in mode modex , or 0 (false) otherwise. In order
to compute a solution for a particular N OC we have some-
Algorithm 1 reconfig takes a reconfiguration problem and how to maximize the number of def ault modes in the solu-
a maximum number of changes and computes all minimal tion. In the first version of our implementation we used the
reconfigurations. Algorithm 1 is an iterative algorithm that M AXIM ISIN G option of MINION for this purpose. In
starts with no changes of modes and continues search if nec- addition, we decided to control the way the solver searches
essary up to the predefined value n. The termination criteria for a solution also by directly specifying the instantiation or-
before reaching n is given in Line 4, where an non-empty der for the MINION variables representing a mode. Hence,
solution obtained from the satisfiability check is returned as we used the MINION variable ordering (V ARORDER) as
result. In case no solution is found the empty set is returned well as the corresponding value ordering (V ALORDER)
(Line 8). The CSolver is a constraint solver taking a set of with the following settings: for all the def ault mode vari-
constraints CM and is expected to return a set of mode as- ables their values should be searched in descending order,
signments if a satisfiable solution can be found. Otherwise, whereas for the other mode variables the searching should
the empty set is returned indicating that no reconfiguration of be done in ascending order. The intuition behind is to prefer
the given size is possible. The function P is assumed to map solutions with more def ault modes to be true over the other
the output of the solver to a set of solutions. solutions.
In the SIMOA prototype implementation we make use For the experiments we made use of a notebook with In-
of the MINION [Jefferson et al., 2012; Gent et al., 2006] tel(R) Core(TM) i7 CPU 1.73 GHz and 4 GB of RAM run-
constraint solver for this purpose, but every other constraint ning under Windows 7. We obtained the results presented in
solver would also be sufficient providing that it is capable of the upper diagram of Figure 4 for models containing a rather
handling the constraints stored in CM . Line 2 of Algorithm 1 small number of P2PMeters ranging from 7 to 50. It is
adds a new constraint to the model stating that we are inter- worth noting that when using the M AXIM ISIN G func-
ested in finding solutions that comprise exactly i modes that tion the measured running times exceeded 300 seconds for
are not equivalent to def ault. more than 100 meters (which is unacceptable in some situ-
Algorithm 1 obviously terminates assuming that CSolver ations). Hence, we decided to use only the V ARORDER
terminates. The complexity is of O(n · k) where k is the com- and V ALORDER and ignore the M AXIM ISIN G func-
plexity of CSolver. In the worst case searching for solutions tion. From the results depicted in the bottom diagram of
for a finite constraint satisfaction problem is exponential in Figure 4 we see a substantial improvement in the mea-
the size of the problem. Therefore, reconfig is also exponen- sured running time. Note that the obtained results without
tial in the worst case. However, in practice solutions can be M AXIM ISIN G were always correct.
found in a much faster way. See for example the results re- From the diagram at the bottom of Figure 4 we can extract
ported in [Nica and Wotawa, 2012a] and more recently [Nica two observations. First, when checking only that a given sys-
et al., 2013]. In these paper search for solutions up to a size of tem fulfills the requirements, the running time even in case of
3 is within seconds even for constraint satisfaction problems 100 P2PMeters is within seconds. Second, even for a NOC
comprising up to 3,800 constraints. Although these results of size 6 the reconfiguration time never exceeds 25 seconds.
are for diagnosis, they also can be applied to configuration Since, for the application domain these running time results
because of the similarity of the algorithms. are sufficient and the proposed approach is feasible.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
Iulia Nica, Franz Wotawa 107
mains is more or less a well developed and researched field,
the application to the M2M domain that requires models from
the application itself and the used communication infrastruc-
ture is to our knowledge new. Moreover, besides the logical
model also spatial information has to be integrated accord-
ingly in order to come up with a correct model. The SIMOA
approach provides a good bases because it allows to specify
constraints dealing with Boolean and Integer values as well
as discrete time. Moreover, also arrays can be used for mod-
eling. Extensions in the direction of handling floats or strings
can be implemented but require to change the underlying rea-
soning engine.
There are of course many languages for simulation like
Modelica [Fritzson and Bunus, 2002] or Simulink [Henson,
2005] used in industry. However, these languages are mainly
optimized towards simulation and therefore can be hardly
used for reconfiguration. In particular such languages do not
allow under-constrained models, which are necessary for our
purpose when searching for appropriate modes that do not
contradict the given requirements while ensuring that the re-
quirements can be fulfilled. There are some similarities be-
tween Modelica and SIMOL but also many differences in-
cluding the tight integration of component modes and the
handling of discrete time.
Our previous papers mainly deal with either the application
domain [Nica et al., 2012] or the SIMOL language [Nica and
Wotawa, 2011; 2012b]. In contrast to the latter paper, we ex-
tend the SIMOL language using the transition block in order
to handle discrete time in the underlying models. Moreover,
Figure 4: Comparing running times for reconfiguration, when we discuss the algorithm for configuration in more detail in
the Integer variable domain is fixed to [0..20,000] and the this paper.
number of solutions is limited to 1.
7 Conclusions
6 Related research
In this paper we discussed the underlying language, defini-
The idea of using constraint solvers for configuration is not tions, and algorithms of the SIMOA approach to reconfig-
new. In [Haselböck and Stumptner, 1991] the authors formal- uration. Although, the approach has been applied to the
ize the configuration and design problem as constraint satis- machine-to-machine communication domain, it is not re-
faction problem. Similarly in [Stumptner and Wotawa, 1998] stricted to this domain. Any reconfiguration problem that
the authors discuss the use of constraint solving for reconfig- can be represented using the underlying modeling language
uration and in particular parameter reconfiguration in detail. SIMOL can also be solved using the proposed SIMOA ap-
The latter also makes use of model-based diagnosis for ob- proach. SIMOL itself is an object-oriented programming
taining reconfigurations. In contrast to these previous papers language where components can be defined. The syntax of
our reconfiguration algorithm although relying on constraint SIMOL is close to Java. The semantics has been mainly
solving is different because we compute configurations di- taken from the modeling language Modelica. Within the de-
rectly without making use of hitting set computation [Reiter, veloped SIMOA prototype SIMOL is converted in MINION
1987; Greiner et al., 1989] or other means for computing di- constraints. Hence, MINION is used as underlying constraint
agnoses [de Kleer and Williams, 1987]. solver. This again does not restrict the approach since chang-
The application of configuration for solving problems in ing constraint solvers is still possible. Only, the conversion of
the engineering domain has a long tradition. In [Stumptner et SIMOL has to be adapted.
al., 1994; Fleischanderl et al., 1998] the authors describe the Besides SIMOL we also discuss the basic definitions of re-
use of generative constraints for configuring large technical configuration and state an algorithm that allows to find min-
systems comprising thousands of components within a rea- imal reconfigurations up to a predefined size. Size in this
sonable amount of time. Other applications include the use of context is defined as number of necessary changes of the sys-
configurations for web services [Felfernig et al., 2002], tech- tem in order to fulfill all constraints. The reconfiguration al-
nical products [John and Geske, 1999; John, 2000], and even gorithm derives solutions directly from the constraints (i.e.,
telecom systems [Emde et al., 1996]. Haag [Haag, 2010] dis- equations coming from SIMOL). This distinguishes this ap-
cussed experiences obtained from product configuration. Al- proach from other similar approaches where search for valid
though, configuration of technical products from various do- configurations is often based on conflicts and conflict resolu-
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria
108 Iulia Nica, Franz Wotawa
tion. First empirical results indicate that computation is suffi- [Henson, 2005] William Henson. Real time Control and
ciently fast and that the results are within expectations. In the Custom Components in the Matlab Environment. Tech-
future it is planned to further evaluate the approach. nical report, 2005.
[Jefferson et al., 2012] Christopher Jefferson, Lars Kotthoff,
Acknowledgement Neil Moore, Peter Nightingale, Karen E. Petrie, and An-
drea Rendl. TheMinion Manual, Minion Version 0.15.
The work presented in this paper has been supported by the http://minion.sourceforge.net/, 2012.
BRIDGE research project Simulation and Configuration of
Mobile networks with M2M Applications (SIMOA),which is [John and Geske, 1999] Ulrich John and Ulrich Geske. Re-
funded by the FFG. configuration of Technical Products Using ConBaCon. In
Proceedings of WS on Configuration at AAAI-99, Orlando,
1999.
References [John, 2000] Ulrich John. Solving large configuration prob-
[de Kleer and Williams, 1987] Johan de Kleer and Brian C. lems efficiently by clustering the ConBaCon model. In
Williams. Diagnosing multiple faults. Artificial Intelli- Proceedings of the 13th international conference on Indus-
gence, 32(1):97–130, 1987. trial and engineering applications of artificial intelligence
and expert systems: Intelligent problem solving: method-
[Emde et al., 1996] Werner Emde, Christian Beilken, Josef
ologies and approaches. Springer-Verlag New York, Inc.,
Bording, Wolfgang Orth, Ulrike Petersen, Jörg Rahmer, 2000.
Michael Spenke, Angi Voss, Stefan Wrobel, and Schlo
Birlinghoven. Configuration of Telecommunication Sys- [Nica and Wotawa, 2011] Iulia D. Nica and Franz Wotawa.
tems in KIKon, 1996. SiMoL- A Modeling Language for Simulation and (Re-
)Configuration. In Workshop on Configuration, pages 40–
[Felfernig et al., 2002] Alexander Felfernig, Gerhard 43, 2011.
Friedrich, Dietmar Jannach, and Markus Zanker. Se-
mantic Configuration Web Services in the CAWICOMS [Nica and Wotawa, 2012a] Iulia D. Nica and Franz Wotawa.
Project. In ISWC ’02 Proceedings of the First Interna- ConDiag – Computing minimal diagnoses using a con-
tional Semantic Web Conference on The Semantic Web, straint solver. In Proc. 23rd International Workshop on
pages 192–205, 2002. Principles of Diagnosis (DX), 2012.
[Nica and Wotawa, 2012b] Iulia D. Nica and Franz Wotawa.
[Fleischanderl et al., 1998] Gerhard Fleischanderl, Ger-
The SiMoL Modeling Language for Simulation and (Re-
hard E. Friedrich, Alois Haselböck, Herwig Schreiner,
) Configuration. In Proc. Conference on Current Trends
and Markus Stumptner. Configuring large systems using
in Theory and Practice of Informatics (SOFSEM), pages
generative constraint satisfaction. In IEEE Intelligent
661–672, 2012.
Systems & their applications, pages 59–68, 1998.
[Nica et al., 2012] I. D. Nica, F. Wotawa, R. Ochenbauer,
[Fritzson and Bunus, 2002] Peter Fritzson and Peter Bunus. C. Schober, H. Hofbauer, and S. Boltek. Model-based sim-
Modelica - a general object-oriented language for contin- ulation and configuration of mobile phone networks - the
uous and discrete-event system modeling and simulation. SIMOA approach. In Proc. of the ECAI 2012 Workshop
In Proceedings 35th Annual Simulation Symposium, pages on Artificial Intelligence for Telecommunications & Sen-
365–380, 2002. sor Networks, pages 12–17, 2012.
[Gent et al., 2006] I. P. Gent, C. Jefferson, and I. Miguel. [Nica et al., 2013] Iulia D. Nica, Ingo Pill, and Thomas
MINION: A Fast, Scalable, Constraint Solver. 17th Eu- Quaritsch Franz Wotawa. The Route to Success - A Per-
ropean Conference on Artificial Intelligence, ECAI-06, formance Comparison of Diagnosis Algorithms. In Proc.
2006. of the International Joint Conference on Artificial Intelli-
[Greiner et al., 1989] Russell Greiner, Barbara A. Smith, and gence (IJCAI), 2013.
Ralph W. Wilkerson. A correction to the algorithm in Re- [Reiter, 1987] Raymond Reiter. A theory of diagnosis from
iter’s theory of diagnosis. Artificial Intelligence, 41(1):79– first principles. Artificial Intelligence, 32(1):57–95, 1987.
88, 1989. [Stumptner and Wotawa, 1998] Markus Stumptner and
[Haag, 2010] Albert Haag. Experiences with Prod- Franz Wotawa. Model-based reconfiguration. In Proceed-
uct Configuration? http://www.minet.uni- ings Artificial Intelligence in Design, Lisbon, Portugal,
jena.de/dbis/lehre/ss2010/konfsem/, 2010. 1998.
[Haselböck and Stumptner, 1991] Alois Haselböck and [Stumptner et al., 1994] Markus Stumptner, Alois
Markus Stumptner. Configuration and design as a con- Haselböck, and Gerhard Friedrich. COCOS - a tool
straint satisfaction task. In Artificial Intelligence in Design for constraint-based, dynamic configuration. In Proceed-
– Proceedings of the Workshop of the 12th International ings of the 10th IEEE Conference on AI Applications
Joint Conference on Artificial Intelligence, Sydney, Aus- (CAIA), San Antonio, March 1994.
tralia, August 1991. Also appeared as Technical Report
DBAI-CSP-TR 91/1.
Michel Aldanondo and Andreas Falkner, Editors
Proceedings of the 15th International Configuration Workshop
August 29-30, 2013, Vienna, Austria