Jorn Lapon

Markulf Kohlweiss

Bart De Decker

Vincent Naessens

Performance Analysis of Accumulator-based Revocation Mechanisms

Keywords: Anonymous Credentials, Revocation, Accumulators

Anonymous credentials are discussed as a privacy friendlier replacement for public key certificates. While such a transition would help to protect the privacy of digital citizens in the emerging information society, the wide scale deployment of anonymous credentials still poses many challenges. One of the open technical issues is the efficient revocation of anonymous credentials. Currently, accumulator based revocation is considered to be the most efficient and most privacy friendly mechanism for revoking anonymous credentials. This paper analyses the performance of three accumulator based credential revocation schemes. It identifies the bottlenecks of those implementations and presents guidelines to improve the efficiency in concrete applications.

Introduction

In an increasing information-driven society, preserving privacy becomes essential. However, anonymity comes with a snag: it facilitates clandestine and illegal actions. Anonymous credentials, such as idemix [START_REF] Camenisch | Design and implementation of the idemix anonymous credential system[END_REF] and U-Prove [START_REF] Brands | A Technical Overview of Digital Credentials[END_REF], promise a solution. They protect the user's privacy, while ensuring accountability. Another emerging trend is the increasing amount of mobile applications and services. People use their mobile device to read mails, access social networks, order tickets, and much more. As these mobiles are easily lost or stolen, effective revocation mechanisms are essential. As anonymous transactions should still remain anonymous, this is not a trivial task. Efficient revocation mechanisms are crucial, especially if anonymous credentials are used in large scale settings such as electronic identity cards and e-passports.

Currently, the most efficient solutions [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF][START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF][START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF], among the privacy friendly ones, use cryptographic accumulators to support revocation. Verifier local revocation [START_REF] Boneh | Group signatures with verifier-local revocation[END_REF] is also efficient for some scenarios, but has other disadvantages. For instance, if a credential is ever revoked, signatures created with that credential before its revocation, become linkable. Accumulators have been used for a variety of applications such as time-stamping [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Sinatures (Extended Abstract)[END_REF], fail-stop signatures [START_REF] Bari | Collision-Free Accumulators and Fail-Stop Signature Schemes Without Trees[END_REF], credential or membership revocation [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF], and broadcast authentication [START_REF] Papamanthou | Authenticated hash tables[END_REF][START_REF] Tartary | Ensuring Authentication of Digital Information Using Cryptographic Accumulators[END_REF].

Contrary to certificate revocation lists (CRL) in public-key infrastructures, that act as a blacklist of revoked certificates, accumulators are primarily used for white-list revocation mechanisms. The accumulator acts as a white-list representing the 'identifiers' of valid credentials. Because of the compact representation and efficient proofs of membership used in such schemes, accumulators are more suitable for white-list revocation than CRL-based mechanisms. Accumulator schemes that could be used for black-list revocation exist in the literature [START_REF] Li | Universal Accumulators with Efficient Nonmembership Proofs[END_REF][START_REF] Damgard | Opoulos: Supporting Non-membership Proofs with Bilinear-map Accumulators[END_REF]. Their non-membership proofs are, however, less efficient.

Our Contribution. This paper evaluates and compares three accumulator schemes for the revocation of anonymous credentials based on white-listing: the scheme proposed by Camenisch and Lysyanskaya CL, [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF]; the scheme due to Nguyen LN [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF]; and the construction due to Camenisch, Kohlweiss and Soriente CKS [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF]. We compare their computational and storage performance and evaluate their suitability for massive deployment (e.g. in a national eID infrastructure). Finally, relevant optimisation guidelines are proposed.

The paper is structured as follows: Section 2 introduces some technologies used in this paper. Section 3 briefly describes the implemented accumulator schemes. Some implementation details and configuration settings are given in Section 4 followed by the results in Section 5. These results are further discussed in Section 6 and finally some conclusions are drawn.

Definitions

Cryptographic Accumulators. A cryptographic accumulator, first introduced by Benaloh and de Mare [START_REF] Benaloh | One-Way Accumulators: A Decentralized Alternative to Digital Sinatures (Extended Abstract)[END_REF], is a construction which allows the accumulation of a number of elements into one value. The size of this value is independent of the number of elements incorporated. For each accumulated element, there is a witness that allows to prove that the element is contained in the accumulator. It must be infeasible, for the adversary, to find a witness for an element that is not included in the accumulator. Camenisch and Lysyanskaya [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF] further extended this notion into dynamic accumulators. In dynamic accumulators adding and removing values and updating individual witnesses can be done dynamically [START_REF] Camenisch | Design and implementation of the idemix anonymous credential system[END_REF].

Anonymous Credentials. Anonymous credential systems [START_REF] Chaum | Security Without Identification: Transaction Systems to Make Big Brother Obsolete[END_REF][START_REF] Camenisch | An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation[END_REF][START_REF] Camenisch | Design and implementation of the idemix anonymous credential system[END_REF][START_REF] Brands | A Technical Overview of Digital Credentials[END_REF] allow for anonymous yet accountable transactions between users and organisations. Moreover, selective disclosure allows the user to reveal only a subset of possible properties of the attributes embedded in the credential: e.g. a credential with the user's date of birth as an attribute can be used to prove that the owner is over 18 without disclosing the exact date of birth or other attributes. The accumulator based revocation schemes are especially useful for anonymous credentials in which multiple shows are unlinkable [START_REF] Chaum | Security Without Identification: Transaction Systems to Make Big Brother Obsolete[END_REF][START_REF] Camenisch | An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation[END_REF][START_REF] Bangerter | A Cryptographic Framework for the Controlled Release of Certified Data[END_REF]. All these schemes originate from existing group signatures and identity escrow schemes. To add support for accumulator-based revocation, the user needs to prove during the show of such a credential, that a hidden identifier bound to the credential is still contained in the accumulator.

Bilinear maps. Let G 1 , G 2 and G T be (multiplicative) groups of prime order q. A bilinear map (also known as a pairing) from

G 1 × G 2 to G T is a computable map e: G 1 ×G 2 → G T with the following properties: 1. Bilinearity: for all u ∈ G 1 , v ∈ G 2 and a, b ∈ Z : e(u a , v b ) = e(u, v) ab 2.
Non-degeneracy: for all generators g ∈ G 1 , h ∈ G 2 : e(g, h) generates G T . 3. Efficiency: there is an efficient algorithm BMGen(1 k ) that outputs (q, G 1 , G 2 , G T , e, g, h) to generate the bilinear map (with k the security parameter and g and h generators) and an efficient algorithm to compute e(u, v)

for any u ∈ G 1 , v ∈ G 2
As the protocols proposed in [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF] and [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF] are both constructed using symmetric pairings, only symmetric bilinear maps (G 1 = G 2 ) will be considered in this paper.

Accumulator Schemes

This section briefly discusses the schemes in [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF][START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF][START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF] (i.e. CL, LN and CKS) and summarizes their properties. We give a common interface for accumulator based revocation of anonymous credentials based on these systems. For a more detailed discussion, we refer to the original papers.

The common interface defines the protocols required for processing anonymous credentials with accumulator-based revocation. The schemes under evaluation, all specify these protocols, hence, we did not modify the protocols in any major way. We do, however, implement a common book-keeping approach that deviates slightly from the one given in the referred papers. An archive table H records the history of the accumulator and allows to derive the list of added and revoked elements (V a resp. V r ) at a given time.

The entities participating in the protocols are: the issuer I, responsible for the creation and revocation of credentials; the user U, the owner of an anonymous credential; and the verifier V. The verifier checks the revocation status of the user with the help of a zero knowledge proof (authCred). In the schemes below, the following notation will be used to denote a local computation performed by X and a protocol between X and Y respectively:

X : (out c ; out x ) ← f (in c ; in x ) X ↔ Y : (out c ; out x ; out y ) ← f (in c ; in x ; in y )
The computations take public input in c and secret input in x , in y from X and Y respectively and result in outputs out x and out y to X and Y respectively; out c is public output. Empty inputs and outputs are represented by ε.

I : (pk I , acc, H = / 0; sk I )← initScheme(1 k , N t ; ε) is a probabilistic key generation algorithm that is executed by the issuer. It initializes the environment for the credential scheme for a given security level k. The second input is the capacity of the accumulator N t , i.e., the maximum number of elements that can be accumulated. The public key pk I also fixes the set X of all elements that can potentially be accumulated (with |X| = N t ). acc is the initial cryptographic accumlator. The history H, is initially empty.

U ↔ I : (acc ′ , H ′ ; cred U ; ε)← issueCred(acc, H, pk I ; ε; sk I )
is a probabilistic interactive algorithm run by the issuer and a user. The issuer issues the credential cred U to the user and adds the credential's identifier id C ∈ X to the accumulator acc. The credential includes witness information wit C and a private key, that is unknown to the issuer. Only the issuer can add new credentials, as the secret key sk I is required for issuing. The new history H ′ = H ∪ { id C , "add" } is updated accordingly.

I : (acc ′ , H ′ ; ε; ε)← revokeCred(acc, H, pk I ; sk I , id C )
is a probabilistic algorithm that is executed by the issuer to revoke the credential id C . The new history becomes

H ′ = H ∪ { id C , "delete" }. U : (ε; wit C ′ )← updWitness(acc ′ , H ′ , pk I ; wit C
) is a deterministic algorithm, usually executed by the user, that updates the witness to correspond with the latest accumulator value acc ′ . However, as no secret data is required, this protocol can be performed by another, possibly untrusted, entity. The duration of witness updates depends on the number of elements added or revoked since the last witness update. The latter can be inferred from the book-keeping information H. U : (ε; boolean)← verifyAccu(acc, pk I ; id C , wit C ) is a deterministic algorithm to verify that id C is indeed accumulated in acc based on the up-to-date witness information wit C .

U → V : (ε; ε; boolean)← authCred(acc, pk I ; cred U ; ε) is a two-party non-interactive zero-knowledge proof protocol that allows the user to prove to the verifier that cred U is a valid credential (i.e. authentic and not revoked).

CL Scheme

Camenisch and Lysyanskaya [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF] were the first to introduce an accumulator scheme for the revocation of anonymous credentials. The scheme extends the collision-resistant accumulator defined by Baric and Pfitzman, based on the strong RSA assumption, allowing dynamic updates of the accumulated set. The core of the accumulator is constructed as follows:

acc = g ∏ id i ∈Va\Vr id i mod n, wit C = g ∏ id i =id C id i ∈Va\Vr id i mod n, verifyAccu: acc ? = (wit C ) id C mod n,
with n an RSA modulus (i.e. the product of two safe primes p and q), g a quadratic residue modulo n, id C the accumulated value (X is the set of random primes from a predefined interval), wit C the witness of the user and id i ∈ V a \V r the currently accumulated values.

The authors applied the accumulator scheme to the identity escrow scheme due to Ateniese et al. [START_REF] Ateniese | A Practical and Provably Secure Coalition-Resistant Group Signature Scheme[END_REF], which was at that time, the most efficient and secure identity escrow scheme known. Later on, the efficiency of the protocol has been further improved. One of these schemes, based on the so-called SRSA-CL-signatures [START_REF] Camenisch | A Signature Scheme with Efficient Protocols[END_REF], is used in the credential scheme proposed in [START_REF] Bangerter | A Cryptographic Framework for the Controlled Release of Certified Data[END_REF]. This scheme, that is also used in idemix, can be easily combined with the proof that a committed value has been accumulated, using Pedersen commitments. This proof was also mentioned in the paper [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF]. We integrate the accumulated value id C as an attribute of the credential. For the signature, we compute

A such that Z = S v R s C 1 R id C 2 A e mod n with S ∈ R QR n , R 1 , R 2 , Z ∈ R S ,
random prime e, master secret s C and accumulated value, prime id C ∈ X.

LN Scheme

Nguyen [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF], was the first to use bilinear maps to implement a dynamic accumulator for revocation. The security of the accumulator is based on the q-SDH assumption, with q an upper-bound on the number of elements to be accumulated. The scheme employs a symmetric bilinear map e:

G 1 × G 1 → G T 4 . acc = g ∏ id i ∈Va\Vr (id i +s) , wit C = g ∏ id i =id C id i ∈Va\Vr (id i +s) , verifyAccu: e(h id C h pub , wit C ) ? = e(h, acc),
with g, h generators of G 1 , id C ∈ R Z * q , the accumulated value and wit C the witness of the user, id i ∈ V a \V r the currently accumulated values, and issuer secret s ∈ R Z * q with h pub = h s .

The signature scheme, used by the authors, is based on the signature scheme due to Boneh and Boyen [START_REF] Boneh | Short Group Signatures[END_REF]

: σ = (h 0 h s C 1 ) 1/(id C +s I ) with h 0 , h 1 generators of G 1 , master secret s C ∈ R Z *
q , accumulated value id C and issuer secret s I . This scheme is proven secure [START_REF] Nguyen | Efficient and Provably Secure Trapdoor-Free Group Signature Schemes from Bilinear Pairings[END_REF] under the q-SDH assumption [START_REF] Boneh | Short Group Signatures[END_REF].

CKS Scheme

A recent scheme (2009) implementing dynamic accumulators was proposed by Camenisch, Kohlweiss and Soriente [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF]. Similar to the LN-scheme, this scheme uses a bilinear map e: G 1 × G 1 → G T . However, the construction of the accumulator is different and is based on another assumption, the n-DHE assumption. Additionally, the n-HSDHE assumption is required for the proof that a hidden value is accumulated.

acc = ∏ id i ∈ V a \V r (g N t +1-i ), wit C = ∏ id i =id j id i ∈ V a \V r (g N t +1-i+ j ), verifyAccu: e(g i ,acc) e(g,wit C ) ? = z,
with g a generator of the group G 1 , N t , the capacity of the accumulator such that X=[g 1 = g s 1 , . . . , g N t = g s Nt ], state information [g 1 , . . . , g N t , g N t +2 , . . . , g 2N t ], issuer secret s and the set of currently accumulated values V a \V r .

The signature scheme originates from the same Boneh and Boyen signatures as the LN scheme, which is further modified by Camenisch et al. [START_REF] Camenisch | Signature Schemes and Anonymous Credentials from Bilinear Maps[END_REF] for the issuance of anonymous credentials and proven secure in [START_REF] Au | Constant-Size Dynamic -TAA[END_REF] under the q-SDH assumption: σ = (g i h 0 h s C 1 ) 1/(c+s I ) with h 0 , h 1 generators of G 1 , master secret s C , issuer secret s I , random number c, and the accumulated value g i .

Implementation

Implementation Notes

To compare the schemes discussed above, they are all implemented in C++. The bilinear maps applied in the LN and CKS scheme, are initialized using the PBC Library [START_REF]PBC: Pairing-Based Cryptography Library by Ben Lynn[END_REF]. This library is built on top of the GNU Multiple Precision Arithmetic Library (GMP [START_REF]GMP: GNU Multiple Precision Arithmetic Library[END_REF]), which performs the underlying mathematical operations. To make the comparison as fair as possible, the CL scheme, which does not use bilinear maps, is implemented using the GMP library directly. Where applicable, optimized versions for applying pairings and multiexponentiations in both libraries are used. However, further optimisations may still be possible.

Various protocols are used to prove knowledge of a valid credential. Most of the papers use the notation introduced by Camenisch and Stadler [START_REF] Camenisch | Efficient Group Signature Schemes for Large Groups (Extended Abstract)[END_REF]. Nevertheless, the implementation of these schemes was not straightforward. We had to deal with many details and small differences: e.g., some schemes use a group of known order, others of hidden order; interactive versus non-interactive proofs of knowledge; the length of random values and nonces. In the implementation, the proofs of knowledge were made non-interactive. Interactive proofs can be converted to non-interactive ones, using the Fiat Shamir heuristic [START_REF] Fiat | How to Prove Yourself: Practical Solutions to Identification and Signature Problems[END_REF].

For the anonymous credential schemes, only the required minimal set of attributes are added to the credentials (i.e the master secret). Thus, the overhead in storage and computation, resulting from additional attributes embedded in the anonymous credential, is not reflected in the results. Likewise, for interactive protocols, the communication overhead is not considered.

Configuration

The pairing-based schemes, LN and CKS are constructed using symmetric pairings. The pairing used, is a 'Type A' pairing, as defined in the PBC Library. This pairing is the fastest, available in the library, and allows the user to select the field-size and subgroup-size. However, as the implementation is independent of the type of pairing, other symmetric pairings could be used as well. The 'Type A' pairing has the following properties: e: G 1 × G 1 → G T on a supersingular curve E : y 2 = x 3 + x with embedding degree 2, field-size l q = 1024 bits, and a subgroup of size l r = 192 bits.

For the idemix-based CL scheme, the following system parameters5 are used: l n = 2048, k ′ = 80, k ′′ = 80, l e = 838, l ′ e = 120, l v = 2965, l Γ = 1632, l ρ = l m = 498, l H = 256, l id i = 160.

Results

This section reports the results of 3 experiments. The storage analysis deals with the size of key-material in the scheme. The computational complexity analysis illustrates the complexity of the protocols and the timing analysis validates the results of the complexity analysis by running the actual protocols. The experiments were executed with the security parameters of section 4.2 on a DELL Latitude P9600 @ 2.53GHz, 4GB RAM.

Storage Analysis

For each of the implementations, Table 1 summarizes the bit-sizes of the private and public key of the issuer, one credential, and the accumulator. Additionally, the size of one accumulated value is listed. Pairings generally allow better results with respect to the size of cryptographic keys than other schemes. This is reflected in the paper of Nguyen [START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF]. However, as can be seen in table 1, the difference is less extreme than in the paper. Since the PBC Library does not provide the pairing proposed in Nguyen's paper, another type of pairing, was used, resulting in a larger subgroup G 1 .

A more important observation is the fact that the public key of the issuer (pk I ) in the CKS scheme contains state information that depends on the capacity of the accumulator. Although, this information can be omitted for most of the protocols, it is required to make witness updates. This will have an impact on how this scheme is used in practice. In case of massive deployment, for instance, witness updates will require special purpose update servers.

Finally, the elements accumulated in the CL and LN scheme are exponents, while in the CKS scheme they are group elements. 16l q + l r 16576 6l q + 2l r 6528 2l q 2048 l r 192 CKS 3l r 576 (16 + 4N t )l q + l r 16576+4096N t 10l q + 2l r 10624 2l q 2048 2l q 2048

Computational Complexity Analysis

Table 2 presents the most computationally expensive operations. As shown in the table, the complexity of the witness update protocol significantly differs for the three schemes. As each call of authCred requires an up-to-date witness, the efficiency of witness updates is very important. The CL scheme only requires one exponentiation for newly accumulated elements, and one for newly revoked elements. However, as the size of the exponents is growing linear Table 2. The most expensive operations (i.e. exponentiations, pairings, multiplications) for the protocols in the credential scheme, with N a the number of accumulated values and N r , the number of revoked values. The numbers between brackets denote operations that can be precalculated. with the number of accumulated, respectively revoked elements (i.e N a .l id i , resp. N r .l id i ), the performance decreases considerably (see Timing Analysis). The LN scheme, on the other hand, requires an exponentiation on a base in G 1 for every element accumulated (N a ) or revoked (N r ), since the last witness update. Updating witness is more efficient in the CKS scheme, as the most expensive operations are a number of multiplications linear in the number of accumulated and revoked elements. Moreover, the scheme requires less expensive operations during the issuance of the credential. However, proving knowledge of a valid credential requires slightly more exponentiations and pairings than in the other schemes. This is due to the fact that id C is a group element. The credential proof of possession needs to be extended to show that this group element is bound to the other credential attributes. Finally, the table reveals that optimizations of the authCred protocol are possible, especially in the LN scheme, in which twelve pairing operations can be precomputed as they do not alter during the lifetime of the credential. Unfortunately, this requires more storage space. Thus, a balance must be found between storage space and processing efficiency.

CL LN CKS exp Z n exp G 1 exp G T pair * / G 1 exp G 1 exp G T pair issueCred 18

Timing Analysis

Table 3 shows the results of the experiments that are applied to all the protocols in the three schemes. The results are averaged over 200 test-runs in an accumulator scheme with a maximum capacity of 2500 elements. The witness update results are presented separately.

As can be seen, the results clearly reflect the analysis of the computational complexity. The setup of the CL scheme takes substantially more time than the schemes using bilinear pairings. CL requires the generation of an RSA-modulus as a product of 2 safe primes, which is dominating the setup. Note that the setup of the CL scheme takes on average 1,5 minutes, while the same algorithm takes about 2,5 minutes in idemix (which was implemented in Java). The setup time of the CKS scheme, however, includes the creation of state information, which is computed by a large number of exponentiations (twice the capacity of the accumulator). For accumulators with a large capacity (N t ), this may take a substantial amount of the initialisation time. Another interesting fact, not shown in the table, is that for the CL scheme, the generation of a prime number of about 2965 bits takes about 1/3 of the time needed for the issueCred protocol.

Figure 1 shows the time required for updating a witness, depending on the number of elements (from 1 up to 10000) that have been revoked since the previous witness update. It clearly shows the linear relation with respect to the number of revoked elements. Similar results are found when elements are added to the accumulator. The figure reveals that the CKS scheme clearly outperforms the others. Nevertheless, the CL and LN scheme may still be useful in specific settings. 6 Discussion

Current Bottlenecks

As the different schemes are based on different security assumptions, a straightforward comparison is difficult. While the CL scheme is based on the strong RSA assumption, both CKS and LN schemes are based on the q-SDH assumption. However, the CKS accumulator scheme requires two additional assumptions: the n-DHE and n-HSDHE assumption. According to [START_REF] Cheon | Security Analysis of the Strong Diffie-Hellman Problem[END_REF], the q-SDH assumption is a weaker assumption than n-DHE assumption. As a result, the CKS scheme could have a weaker security than the LN scheme. Additionally, the efficiency of the pairing based systems (i.e. LN and CKS) strongly depends on the efficiency of the selected pairing and its implementation.

When we analyse the signatures, we can observe that the LN and CKS signature schemes have a similar construction. The most important difference is that in the CKS version, the accumulated value is added as a group element, while in the LN scheme it is an exponent. As a consequence, showing a CKS credential requires the proof of a group element. This makes the proof of knowledge (in the authCred protocol) more complicated than the LN version. Nevertheless, the CL scheme outperforms the others for this protocol.

The benefits and drawbacks of the individual schemes are clearly distinct. The construction of the accumulator is important, with a major impact on the updWitness protocol. On the other hand, the efficiency of the issueCred and authCred heavily depends on the design of the credential scheme accompanying the accumulator scheme. As for efficiency in time and processing, the CL, LN and CKS scheme are comparable, with CL scoring the best on the authCred protocol. However, the LN scheme is faster at the prover side for the same protocol with smaller credentials.

Though still acceptable for most practical applications, the CKS scheme is the slowest for proving a valid credential. On the other hand, this scheme clearly outperforms the others with respect to witness updates. In fact, it's the only scheme that is practical for massive deployment. It is about 180 times faster than the LN scheme, and 22 times faster than the CL scheme. Yet, there is a snag in it. For witness updates, the CKS scheme requires state information, which is linear to the capacity of the accumulator. For instance, with the configuration above, an accumulator for 10 million elements, requires about 4.8 GB of storage. However, since the update of the witness does not require any secret information, special purpose (possibly untrusted) services may perform the update remotely. With respect to storage, the credentials are comparable in size, with the LN-credential the smallest with only 6.528 bits (i.e. 816 bytes).

Large versus small scale environments The scheme that will be selected depends on the characteristics of the concrete application. In small scale environments with a limited num-ber of revocations or additions, the efficiency of the authCred protocol may be more important than the efficiency of the updWitness protocol. However, an important reason for doing this experiment is to explore the applicability of this technology for the use with an electronic identity card (eID) in a nationwide environment. Compared with the Belgian electronic identity card 6 , the accumulator size should contain about 10 million elements. During the introduction of the card, about 2,25 million cards were issued every year, of which 375.000 were revoked.

Suppose in an 'extreme' case, the eID card is used only once a year; this is a valid assumption as a recent survey on the use of the Belgian eID in corporate environments 7 reveals that 56% of the respondents never used it. If we can make an interpolation, this would mean that in the best case (i.e. update time grows linearly) an update of 375.000 revoked elements takes about 0.5 minutes, using the fastest update scheme (CKS) and 10 minutes with the CL scheme. While the former may be acceptable in applications such as eID authentication, the latter certainly is not. In the example, we only take the revocations into account, as the accumulator can be precalculated (see Preissuance-Accumulation below).

Practical Solutions

Together with improving the efficiency of the protocols, some relevant application level optimisations can render the schemes practical:

Clustering. Instead of having one accumulator for all users, each user can be assigned to one of M accumulators. Therefore, they could, for instance, be classified per region or even at random into a specific accumulator. As a result, the average number of updates will be about M times less than would be the case with a single accumulator. However, this may entail important privacy consequences. A service will always be able to link an anonymous user to an accumulator. In the worst case, if only one customer of that service is assigned to a particular accumulator, then the service can link all the user's actions.

Preissuance-Accumulation. The example of the Belgian eID shows that during the introduction of the eID, many users are added to the accumulator. To reduce the number of updates, the accumulator could be pre-computed. Meaning that every required element is added to the accumulator and stored securely by the issuer, together with its respective witness. The CL scheme does not require this pre-computation. As already pointed out by the authors [START_REF] Camenisch | Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials[END_REF], the witness can simply be calculated from the current accumulator by calculating the (id x ) th root of the accumulator, with id x the new 'accumulated' value. This is possible when the factorisation of the modulus is known.

Delegation of witness updates. To make the CKS scheme practical, without loss of privacy, the witness update should be performed by special purpose update servers. This same strategy may be useful for the other schemes as well. For instance, a resource constrained device, such as a smart card, can delegate the calculation to a more resourceful host.

Epochs. With the protocols provided above, every authCred must be preceded by the updWitness protocol. As described in the CKS paper [START_REF] Camenisch | An Accumulator Based on Bilinear Maps and Efficient Revocation for Anonymous Credentials[END_REF], it is possible to make use of epochs. The accumulator is kept valid for a specific amount of time (i.e. epoch), during which the witness remains valid.

Conclusion

The experiments in this paper do not yield a straightforward winner. The revocation of anonymous credentials takes a considerable share in the efficiency of the overall system. Moreover, for nationwide electronic identity cards, the current schemes appear to be inappropriate. Only the CKS scheme may be applicable for massive deployment, provided that special update services are used.

The efficiency of witness updates is an important property in accumulator based revocation systems, and becomes critical in applications with a substantial amount of revocations or additions. The construction of the accumulator has a major impact on the efficiency of the update. Nevertheless, the witness update is also affected by the design of the credential scheme accompanying the accumulator scheme.

The schemes all have different advantages but also different drawbacks. We presented an overview and some relevant guidelines as a lead for future research. Although the accumulators can be used as a building block for anonymous credentials, care must be taken when combining it with a credential scheme.

Fig. 1 .

 1 Fig. 1. Performance results for witness updates with respect to the number of revoked credentials, shown graphically.

Table 1 .

 1 Bit-sizes of objects in the credential schemes.

	sk I	pk I	cred U	acc	id C
	CL l n 2048 5l n + l r + 3l g	15634	2l

n + k + l v + l r 7719 l n 2048 l e 160 LN 3l r 576

Table 3 .

 3 Performance results for the 3 schemes, with respect to the different protocols.

	(ms)	CL LN	CKS
	initScheme (sec.) 97 1, 26 1, 26s + N t .4ms
	issueCred	617 365	219
	Receiver	274 230	110
	Issuer	343 135	109
	revokeCred	23 14	0, 09
	verifyAccu	1, 90 130	93
	authCred	684 754	938
	Prover	389 346	448
	Verifier	296 408	490
			0	250	500	750	1000

Table 4 .

 4 Table 4 summarizes the most important bottlenecks of the schemes. Bottlenecks (ց) and benefits (ր) of the schemes

	CL	LN	CKS
	initScheme ց safe prime generation	ր	ց state info
	issueCred ց prime generation		ր
	updWitness	ց exponentiations	ր (ց size of state info)
	authCred ր		ց exp's + pairings

Note: in the original paper, the group operations were expressed using the additive notation.

Note that the parameters proposed for the CL scheme in[START_REF] Nguyen | Accumulators from Bilinear Pairings and Applications[END_REF] do not satisfy the constraints posed by the respective scheme.

Results obtained from http://godot.be/eidgraphs

SAP Survey: Belgen verdeeld over gebruik van eID op het werk (sept. 2009 by Indigov).

Acknowledgements We want to thank Lan Nguyen and Jan Camenisch for providing insight in their schemes; Frederik Vercauteren, for the recommendations on the configuration and security of the bilinear maps; and Patrik Bichsel and Alfredo Rial for the discussions on various implementation problems. This research is partially funded by the Interuniversity Attraction Poles Programme Belgian State, Belgian Science Policy and the Research Fund K.U.Leuven, and the IWT-SBO project (DiCoMas) "Distributed Collaboration using Multi-Agent System Architectures" Markulf Kohlweiss was supported in part by the Concerted Research Action (GOA) Ambiorics 2005/11 of the Flemish Government, by the IAP Programme P6/26 BCRYPT of the Belgian State (Belgian Science Policy), and in part by the European Commission through the ICT and IST programmes under the following contracts: ICT-216483 PRIMELIFE and ICT-216676 ECRYPT II.


Antoine J Marchand

Eric Hitti

Frédéric Monge

Hervé Saint-Jalmes

Raphaël Guillin

Régis Duvauferrier

Ph.D Giulio Gambarota
email: gambarota@gmail.com

Professor

MRI quantification of diffusion and perfusion in bone marrow by intravoxel incoherent motion (IVIM

Keywords: Intravoxel incoherent motion, IVIM, diffusion, bone marrow, perfusion, NNLS

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Measurements of the water apparent diffusion coefficient (ADC) and tissue perfusion in vertebral bone marrow are of interest for investigations of a number of pathologies [START_REF] Biffar | Diffusion and perfusion imaging of bone marrow[END_REF][START_REF] Biffar | Combined diffusion-weighted and dynamic contrast-enhanced imaging of patients with acute osteoporotic vertebral fractures[END_REF][START_REF] Griffith | Vertebral marrow fat content and diffusion and perfusion indexes in women with varying bone density: MR evaluation[END_REF]. Water diffusion provides a means for tissue microstructure characterization [START_REF] Dietrich | Diffusion-weighted imaging of bone marrow[END_REF][START_REF] Herneth | Diffusion weighted imaging of bone marrow pathologies[END_REF][START_REF] Maeda | Quantitative assessment of diffusion abnormalities in benign and malignant vertebral compression fractures by line scan diffusionweighted imaging[END_REF][START_REF] Yeung | Bone marrow diffusion in osteoporosis: evaluation with quantitative MR diffusion imaging[END_REF] and it has been shown that the water diffusivity in bone marrow allows to distinguish between benign and malignant lesions and to monitor myeloma infiltration [START_REF] Baur | Diffusion-weighted MR imaging of bone marrow: differentiation of benign versus pathologic compression fractures[END_REF][START_REF] Messiou | Optimising diffusion weighted MRI for imaging metastatic and myeloma bone disease and assessing reproducibility[END_REF]. Of relevance in clinical and research studies is also the assessment of bone marrow perfusion, for tumor response to therapy and for evaluation of compression fractures and metastasis [START_REF] Chen | Blood perfusion of vertebral lesions evaluated with gadolinium-enhanced dynamic MRI: in comparison with compression fracture and metastasis[END_REF][START_REF] Fenchel | Early response assessment in patients with multiple myeloma during anti-angiogenic therapy using arterial spin labelling: first clinical results[END_REF][START_REF] Hawighorst | Evaluation of angiogenesis and perfusion of bone marrow lesions: role of semiquantitative and quantitative dynamic MRI[END_REF][START_REF] Nosas-Garcia | Dynamic contrast-enhanced MRI for assessing the disease activity of multiple myeloma: a comparative study with histology and clinical markers[END_REF].

Bone marrow consists of two tissue components: the yellow adipose marrow, which is composed mostly of fatty tissue and accounts for up to 80% of bone marrow in a healthy adult, and red marrow, which consists mostly of hematopoietic cells, but also contains up to 40% of fatty tissue [START_REF] Ricci | Normal agerelated patterns of cellular and fatty bone marrow distribution in the axial skeleton: MR imaging study[END_REF]. The large amount of lipids represents a confounding factor in the measurement of the water ADC [START_REF] Mulkern | In re: characterization of benign and metastatic vertebral compression fractures with quantitative diffusion MR imaging[END_REF] and tissue perfusion in bone marrow [START_REF] Biffar | Quantitative analysis of vertebral bone marrow perfusion using dynamic contrast-enhanced MRI: initial results in osteoporotic patients with acute vertebral fracture[END_REF], thus it is preferable to employ fat suppression techniques.

Measurements of both ADC and tissue perfusion can be achieved with the MRI approach of the intravoxel incoherent motion (IVIM), introduced by Le Bihan more than two decades ago [START_REF] Bihan | MR imaging of intravoxel incoherent motions: application to diffusion and perfusion in neurologic disorders[END_REF].

The IVIM approach has been recently 'rediscovered' as an attractive method for assessing perfusion fraction in different organs [START_REF] Bihan | Intravoxel incoherent motion perfusion MR imaging: a wake-up call[END_REF][START_REF] Luciani | Liver cirrhosis: intravoxel incoherent motion MR imaging--pilot study[END_REF][START_REF] Yamada | Diffusion coefficients in abdominal organs and hepatic lesions: evaluation with intravoxel incoherent motion echo-planar MR imaging[END_REF][START_REF] Döpfert | Investigation of prostate cancer using diffusion-weighted intravoxel incoherent motion imaging[END_REF][START_REF] Shinmoto | An intravoxel incoherent motion diffusion-weighted imaging study of prostate cancer[END_REF][START_REF] Delattre | In vivo cardiac diffusion-weighted magnetic resonance imaging: quantification of normal perfusion and diffusion coefficients with intravoxel incoherent motion imaging[END_REF][START_REF] Federau | Quantitative measurement of brain perfusion with intravoxel incoherent motion MR imaging[END_REF][START_REF] Ichikawa | Intravoxel incoherent motion imaging of the kidney: alterations in diffusion and perfusion in patients with renal dysfunction[END_REF][START_REF] Liu | Intravoxel incoherent motion (IVIM) in evaluation of breast lesions: comparison with conventional DWI[END_REF]. In IVIM measurements, images are acquired with different diffusion-sensitizing gradients (i.e., at different 'b-values') to measure tissue microcapillary perfusion and water diffusivity using the signal decay at relatively small (0-100 s/mm 2 ) and large (100-1000 s/mm 2 ) b-values, respectively. The calculation of the perfusion fraction within the IVIM model relies on the assumption that the diffusion signal decay is bi-exponential.

To date, data analysis approaches based on the non-linear least squares algorithm have been investigated to extract the perfusion fraction from the bi-exponential diffusion decay [START_REF] Yeung | Bone marrow diffusion in osteoporosis: evaluation with quantitative MR diffusion imaging[END_REF][START_REF] Patel | Diagnosis of cirrhosis with intravoxel incoherent motion diffusion MRI and dynamic contrast-enhanced MRI alone and in combination: preliminary experience[END_REF].

However, in certain experimental conditions the low signal-to-noise ratio (SNR) as well as motion artifacts and other factors might affect the data quality and thus the signal decay might not necessarily display two diffusion components. As the knowledge of diffusion decay characteristics (specifically, the number of diffusion components) is a fundamental prerequisite for calculating the perfusion fraction, it is important to employ appropriate methods of data analysis. In this respect, the non-negative least square (NNLS) technique (28) could be of interest for the analysis of IVIM data. In fact, the NNLS technique does not require a priori assumptions about the the number of components in a given decay and in recent years it has been extensively used to investigate the multi-exponential characteristics of transverse relaxation decays [START_REF] Whittall | Quantitative interpretation of NMR relaxation data[END_REF][START_REF] Oh | Measurement of in vivo multi-component T2 relaxation times for brain tissue using multi-slice T2 prep at 1.5 and 3 T[END_REF][START_REF] Reiter | Multicomponent T2 relaxation analysis in cartilage[END_REF][START_REF] Zheng | On the measurement of multi-component T2 relaxation in cartilage by MR spectroscopy and imaging[END_REF][START_REF] Bjarnason | Quantitative T2 analysis: the effects of noise, regularization, and multivoxel approaches[END_REF][START_REF] Hwang | Robust mapping of the myelin water fraction in the presence of noise: synergic combination of anisotropic diffusion filter and spatially regularized nonnegative least squares algorithm[END_REF].

Given the clinical interest in diffusion and perfusion measurements in vertebral bone marrow, and the challenges related to both data acquisition and analysis, the aim of this study was twofold: first, to assess the feasibility of measuring diffusion and perfusion fraction in vertebral bone marrow using the IVIM approach, combined with fat suppression; secondly, to compare two fitting methods, i.e., the NNLS with the more commonly used Levenberg-Marquardt (LM) non-linear least squares algorithm, for the analysis of IVIM data.

Materials and Methods

MR Imaging

All experiments were conducted according to the procedures approved by the local institutional review board. A group of fifteen healthy women volunteers (age between 18 and 30 years) was examined on a 1.5 T scanner (Siemens Healthcare, Erlangen, Germany). This population sample was chosen because women with regular menstruations have more red marrow than men and therefore higher bone marrow perfusion (). A urine pregnancy test was performed before inclusion and pregnant women were not included in the study. The body coil was used for transmission. The spine-coil and a phased array coil that was positioned on the torso of the volunteers were used for reception.

Multi-planar scout gradient-echo images and coronal T2-weighted short-TI inversion recovery (STIR) images were acquired prior to diffusion MRI. Diffusion-weighted echo-planar imaging (EPI) was performed at five different b-values (0, 50, 100, 200, 600 s/mm 2 ) with a STIR module to suppress the lipid signal. The STIR method was chosen because it provides robust fat suppression, though at the expenses of SNR. Other imaging parameters were: TR/TE = 10900/75 ms, inversion time TI = 170 ms, FOV of 312 mm ! 500 mm, slice thickness of 4 mm, 40 slices, matrix size of 269x384 and 2 averages, total scan time of 6 min 22 s. The diffusion sensitization gradients were applied along three directions and trace diffusion-weighted images were generated.The minimum b-value available (with the exception of the b-value = 0 s/mm 2 ) was 50 s/mm 2 and only b-values multiple of 50 s/mm 2 were feasible. Vendor-supplied sequences were used for all measurements.

A dedicated Plexiglas™ support of a cradle-like shape was designed and built for the current study (Figure 1). During the MR experiment, the support was positioned on the spine coil. Four cylindrical phantoms (diameter = 3.5 cm, length = 40 cm) were integrated in this support. Two phantoms were filled with distilled water and the other two phantoms with distilled water and 25% Polyethylene glycol (PEG). These phantoms, employed to verify the performance of the experimental apparatus, allowed for the measurement of the signal decay in water and PEG, which is known to decrease mono-exponentially with increasing b-values.

Data Analysis

A region of interest (ROI) was drawn to encircle the first lumbar vertebra (L1) on the MR diffusion image at the b-value = 0 s/mm 2 . The mean signal intensity and standard deviation was calculated at all b-values for the same ROI. The average area of the ROI over all volunteers was 1.8 ± 0.3 cm 2 . As a reference, ROIs were also drawn in the water and PEG phantoms to measure the ADC of these substances.

Fitting multi-exponential decay curves is a notorious problem in MRI and in many other fields of science [START_REF] Holmström | A review of the parameter estimation problem of fitting positive exponential sums to empirical data[END_REF][START_REF] Istratov | Exponential analysis in physical phenomena[END_REF]. Here, we employed two methods: the NNLS and the LM non-linear least squares algorithm.. Within the NNLS framework [START_REF] Lawson | Solving least squares problems[END_REF], the signal intensity as a function of bvalues is written as:

y(b i ) = ! j exp(-b i D j ) s(D j ) = ! j A ij s j ; i = 1, 2, …N; j = 1, 2, …M [1]
where b i is the ith b-value, y(b i ) the mean signal intensity of the ROI, s(D j ) the unknown amplitude of the component with diffusion coefficient D j , N the number of b-values, M the number of allowed diffusion components and A is the matrix containing the exponential kernel functions. The amplitudes s j that minimize the least-squares misfit are determined by the following equation:

! i (! j A ij s j -y i ) 2 + µ ! i (! j H ij s j ) 2 ; i = 1, 2, …N; j = 1, 2, …M [2]
where µ is the regulizer parameter [START_REF] Whittall | Quantitative interpretation of NMR relaxation data[END_REF] and H is the identity matrix. Thus, the NNLS algorithm calculates the number of diffusion components in a given decay curve and provides the value of the diffusion coefficient and amplitude of each diffusion component. Using the NNLS results, the perfusion fraction was calculated as the normalized amplitude of the faster diffusion component. Furthermore, fits of the signal decay with b-values to a bi-exponential function were performed using a Levenberg-Marquardt (LM) non-linear least squares algorithm. The bi-

exponential function was S = (f) exp(-b n •D*) + (1-f) exp(-b n •ADC) where f and (1-f) are relative
fractions of the amplitudes of the fast and slow diffusion components with diffusion values D* and ADC, respectively. It should be noted here that f represents the perfusion fraction and the ADC is the tissue diffusion coefficient that is typically measured with diffusion MRI.

The data analysis was performed with Matlab (MathWorks, Natick, MA, USA). Data are expressed as mean ± standard deviation.

Results

MR images of one volunteer are shown in Figure 2. On the MR coronal image (Figure 2, left) the location of an axial diffusion-weighted image (Figure 2, right) is illustrated by the horizontal line. The ROI for the analysis of the diffusion decay in the L1 vertebra is indicated on the axial image (Figure 2, right). The graph of Figure 3 shows an example of a fat-suppressed diffusion decay from an ROI in the vertebral bone marrow (L1) of one volunteer. The results of the NNLS analysis of the same diffusion decay are shown in Figure 4. The NNLS analysis revealed two diffusion components: a fast component with diffusion coefficient (D*) of ~ 20x10 -3 mm 2 /s and a slow component with diffusion coefficient (ADC) of ~ 0.7x10 -3 mm 2 /s (Figure 4). The perfusion fraction calculated by NNLS analysis was 14 %. The NNLS analysis of the diffusion decay in the phantoms yielded a single component (Figure 5), with NNLS peaks at ~ 2.1x10 -3 mm 2 /s and ~ 1.2x10 -3 mm 2 /s for water and PEG, respectively.

The results of the NNLS analysis are provided in Table 1. For comparison purposes, the results of the bi-exponential fit performed with the LM algorithm are listed as well in the same table .   The NNLS analysis of diffusion decays revealed two diffusion components in seven out of fifteen volunteers, with (mean ± standard deviation) ADC = 0.60 ± 0.09 (10 -3 mm 2 /s), D* = 28 ± 9 (x10 -3 mm 2 /s) and perfusion fraction = 14 ± 6 % (Table 1). The mean values obtained by the LM bi-exponential fit were: ADC = 0.45 ± 0.27 (10 -3 mm 2 /s), D* = 63 ± 145 (10 -3 mm 2 /s) and perfusion fraction = 27 ± 17 %. It should be noted that in the experiments where the NNLS yielded two diffusion components (volunteer # 3, 5, 6, 8, 10, 12, 13) the NNLS-derived values of ADC, D* and perfusion fraction were similar to the correspondent LM-derived values. In all cases, NNLS analysis yielded a single component for diffusion decay in the water and PEG phantoms.

Discussion

In the current study, the feasibility of measuring the water ADC and perfusion in vertebral bone marrow was investigated on a 1.5 T clinical scanner with the IVIM approach, in combination with the NNLS data analysis. It is well established that MRI has become the modality of choice for abdominal imaging and in particular for assessing non-invasively a number of vertebral bone marrow disorders with T1, T2 and diffusion-weighted MR images. In addition, it has been shown that quantitative diffusion measurements provide an added value to the MR examination, especially in the case of longitudinal studies or group comparisons.

A relatively large range of values for the water ADC in vertebral bone marrow is found in the literature. This is mainly due to the inter-scanner variability and to the differences in pulse sequences -EPI, stimulated-echo (STE), fast spin-echo (FSE), line-scan diffusion imaging (LSDI)-used in each study [START_REF] Griffith | Vertebral marrow fat content and diffusion and perfusion indexes in women with varying bone density: MR evaluation[END_REF][START_REF] Yeung | Bone marrow diffusion in osteoporosis: evaluation with quantitative MR diffusion imaging[END_REF][START_REF] Bammer | Line scan diffusion imaging of the spine[END_REF][START_REF] Oner | Diffusion-weighted imaging of the appendicular skeleton with a non-Carr-Purcell-Meiboom-Gill single-shot fast spin-echo sequence[END_REF]. In studies where the diffusion-weighted EPI sequence with fat suppression was employed, the measured values of the water ADC ranged from 0.23x10 - 3 mm 2 /s (40) to 1.66x10 -3 mm 2 /s (41), with most studies yielding values close to 0.50x10 -3 (mm 2 /s), as in the study by Hatipoglu et In addition to quantitative diffusion measurements, perfusion measurements are of interest in bone marrow for investigations of osteoporosis, tumor, metastases and compression fractures. It has been recently shown that perfusion could also serve as a parameter of early response of myeloma to anti-angiogenic therapy [START_REF] Fenchel | Early response assessment in patients with multiple myeloma during anti-angiogenic therapy using arterial spin labelling: first clinical results[END_REF]. In most cases, perfusion in bone marrow has been measured with dynamic contrast-enhanced (DCE) MRI (1, 3) and only a limited number of studies have employed other approaches such as IVIM [START_REF] Yeung | Bone marrow diffusion in osteoporosis: evaluation with quantitative MR diffusion imaging[END_REF] and arterial spin labeling, ASL [START_REF] Fenchel | Early response assessment in patients with multiple myeloma during anti-angiogenic therapy using arterial spin labelling: first clinical results[END_REF].

In the IVIM study by Yeung et al., fat-suppressed diffusion-weighted images were acquired at 'low' (0-100 s/mm 2 ) and 'high' (100-500 s/mm 2 ) b-values to measure bone marrow perfusion and diffusion of the third lumbar vertebra [START_REF] Yeung | Bone marrow diffusion in osteoporosis: evaluation with quantitative MR diffusion imaging[END_REF]. The value of ADC found by Yeung et al. in the current study is in good agreement with the value of ADC found in the current study; however, values of the perfusion fraction were not reported by Yeung et al. because, as the authors explained, no reliable estimate could be made. In the current study, perfusion measurements yielded reliable results -as assessed by NNLS analysis-only in seven out of fifteen subjects.

Thus, the results of the current study confirm in part the findings of the work by Yeung et al., i.e., the low reliability of the IVIM approach for perfusion measurements in vertebral bone marrow, within the constraints of a clinical protocol.

The NNLS technique gives an important aid in the data analysis of signal decays, since it does not require a priori assumptions about the number of decay components.. The NNLS analysis has been extensively employed to investigate the multi-component characteristics of transverse relaxation (T2 and T2*) decays. Most of these studies have been focused on brain, for myelin quantitation [START_REF] Mackay | Insights into brain microstructure from the T2 distribution[END_REF][START_REF] Meyers | Multicenter measurements of myelin water fraction and geometric mean T : Intra-and intersite reproducibility[END_REF][START_REF] Mackay | In vivo visualization of myelin water in brain by magnetic resonance[END_REF]. Other applications have included the analysis of the T2 relaxation decay in muscle [START_REF] Gambarota | Osmotic effects on the T2 relaxation decay of in vivo muscle[END_REF][START_REF] Ploutz-Snyder | Different effects of exercise and edema on T2 relaxation in skeletal muscle[END_REF] and nerve [START_REF] Gambarota | NMR properties of human median nerve at 3 T: proton density, T1, T2, and magnetization transfer[END_REF].

In the current study, the values of perfusion fraction obtained by the NNLS and by the LM biexponential fit were 14 ± 6 % and 27 ± 17 %, respectively. As indicated by Le Bihan and Turner [START_REF] Bihan | The capillary network: a link between IVIM and classical perfusion[END_REF] the IVIM perfusion fraction is the fractional volume of capillary blood flowing in each voxel. Thus, taking a fat fraction of 0.3 for healthy young female [START_REF] Kugel | Age-and sex-specific differences in the 1Hspectrum of vertebral bone marrow[END_REF], and a tissue NMR-visible water fraction of 0.8 [START_REF] Bihan | The capillary network: a link between IVIM and classical perfusion[END_REF], one can estimate an average value of capillary blood volume of ~ 7,8 mL/min/100 g and ~ x,x mL/min/100 g, obtained by the NNLS and by the LM bi-exponential fit, respectively. The value estimated by the NNLS is close to the value of blood volume of 5.9 ± 2.6 mL/100 mL found by Biffar et al. [START_REF] Biffar | Quantitative analysis of vertebral bone marrow perfusion using dynamic contrast-enhanced MRI: initial results in osteoporotic patients with acute vertebral fracture[END_REF].

Furthemore, in subjects where the NNLS did not provide evidence for the presence of two components -Table 1, subject 15, 9, 7, 1, for instance-the perfusion fraction yielded by the LM bi-exponential fit was 50, 43, 57, 36 %, respectively, which in turn corresponds to a capillary blood volume in the range of 20 to 31 mL/100 g. These values of blood volume appear higher than the physiological range for healthy subjects [START_REF] Biffar | Quantitative analysis of vertebral bone marrow perfusion using dynamic contrast-enhanced MRI: initial results in osteoporotic patients with acute vertebral fracture[END_REF].

It should be noted that simple range criterions could be used to discard the results of the LM biexponential analysis in healthy subjects, where typically the range of physiologically plausible values is known.. On the other hand, this might not be the case in pathological conditionsthus a method without a priori assumptions about the number of diffusion components, such as the NNLS, is relevant. In the current study, the bi-exponential behavior of the diffusion signal decay in the L1 was detectable in seven out of fifteen volunteers. In each experiment, diffusion signal decays were also measured in the water and PEG phantoms positioned next to the volunteers, to check the performance of the experimental apparatus in order to rule out that the bi-exponential feature could originate from mis-adjustments. In all cases, the NNLS analysis yielded a single component for the diffusion signal decay in water and PEG. This suggests that the bi-exponential behavior observed in vivo in the vertebral bone marrow could not be ascribed to mis-calibrations or measurements pitfalls.

When comparing the different methods (DCE-MRI, IVIM and ASL) that have been employed for perfusion measurements in bone marrow, it can be stated that the advantage of both IVIM and ASL over DCE-MRI is that they do not require administration of contrast agent and therefore they are less invasive. Thus, both IVIM and ASL could be an attractive alternative to the more established DCE-MRI -though, at this stage, DCE-MRI measurements appear to be more robust than IVIM and ASL. It should be also noted, however, that due the large amount of lipids a quantitative measure of perfusion with DCE-MRI is more challenging in bone marrow than in other tissues and the lipid content needs to be known and taken into account in the data analysis for a proper interpretation of the DCE-MRI data [START_REF] Biffar | Combined diffusion-weighted and dynamic contrast-enhanced imaging of patients with acute osteoporotic vertebral fractures[END_REF].

IVIM measurements in vertebral bone marrow with the STIR fat suppression suffer from an intrinsic low SNR. On the other hand, due to the large fat content in the vertebra (60-80% of the total tissue), it is preferable to suppress the signal of fat in order to investigate the water diffusion and the perfusion fraction. As shown by Mulkern et al. [START_REF] Mulkern | In re: characterization of benign and metastatic vertebral compression fractures with quantitative diffusion MR imaging[END_REF], even small percentages of lipid within a voxel can drastically affect diffusion coefficient measurements in bone marrow; the same applies to perfusion, as shown by Biffar et al. [START_REF] Biffar | Quantitative analysis of vertebral bone marrow perfusion using dynamic contrast-enhanced MRI: initial results in osteoporotic patients with acute vertebral fracture[END_REF]. Further studies will be required in order to test IVIM measurements with lipid suppression techniques other than the STIR approach, which results in a significant loss of signal.

One limitation of this study is that the imaging protocol was designed for a clinically acceptable scan time and with a spatial coverage that is consistent with standard clinical protocols. This relatively large spatial coverage comes at the penalty of increased scan time and therefore a decreased number of b-values. Future studies will include a more detailed coverage of the water diffusion decay, i.e., the acquisition of additional b-values, especially small b-values, in order to improve the quantification of perfusion [START_REF] Lemke | Toward an optimal distribution of b values for intravoxel incoherent motion imaging[END_REF]. Furthermore, there was a limitation on the choice of b-values in the pulse sequence used in this study. Recently, a new pulse sequence provided by the vendor allows for a more flexible choice of b-values that will significantly improve the sampling of the fast-decaying component. Overall, it should be stressed that additional studies will be necessary to improve the measurement reliability. Improvements in coil design, pulse sequences, motion correction and fat suppression methods will contribute to ameliorate the diffusion decay curve and therefore increase reliability of the IVIM approach in vertebral bone marrow.

Conclusion

The IVIM approach allows for measuring diffusion and perfusion fraction in vertebral bone marrow. The NNLS method, which identifies the diffusion decays that display a bi-exponential behaviour, , provides an added value in the analysis of the IVIM data.

  al., (0.46 ± 0.03 10 -3 mm 2 /s, (42)), by Griffith et al. (0.46 ± 0.08 10 -3 mm 2 /s, (3)), and by Yeung et al. (0.50 ± 0.09 10 -3 mm 2 /s, (7)), for instance. The value of the water ADC of vertebral bone marrow measured in the current study is close to the values found in most of these studies.

Figure 1 .

 1 Figure 1. Plexiglas support for the water and PEG phantoms. The support consists of two separate parts that can be adjusted to the anatomy of the patient. The cylindrical phantoms are integrated into the support. The schematic and a photo of a single element are shown on the top left panel and top right panel, respectively. The support is positioned on the spine coil and the volunteer lies supine on the support during the MR experiment.

Figure 2 .

 2 Figure 2. Representative MR images of one volunteer. A coronal T2-weighted image (left) and an axial diffusion-weighted image acquired at the b-value = 50 s/mm 2 (right) are shown. In both acquisitions, a STIR-preparation module was used to suppress the lipid signal. The horizontal line on the coronal image indicates the position of the axial slice. The elliptical region of interest centered on the first lumbar vertebra (L1) is illustrated on the diffusion-weighted image.

Figure 3 .

 3 Figure 3. Example of intravoxel incoherent motion (IVIM) data acquired on one volunteer. The fat-suppressed diffusion decay from an ROI in the vertebral bone marrow (L1) and from an ROI in the noise are shown. As indicated by the curvature of the decay on the semi-log plot, the diffusion signal in bone marrow displays a bi-exponential behavior with a fast-decaying component for b-values between 0-100 s/mm2 and a slow-decaying component for b-values between 100-600 s/mm2. The NNLS analysis of this diffusion decay is shown in Figure 4.

Figure 4 .

 4 Figure 4. The NNLS spectrum of a fat-suppressed diffusion decay from an ROI in the vertebral bone marrow (L1) of one volunteer.The NNLS spectrum is plotted on a logarithmic scale with diffusion values equally spaced between 10 -1 and 10 2 (x10 -3 ) mm 2 /s. The NNLS spectrum exhibits two peaks at ~ 0.7x10 -3 mm 2 /s and ~ 20x10 -3 mm 2 /s, with a perfusion fraction of 14%. The diffusion coefficient of the slow component (~ 0.7x10 -3 mm 2 /s) is consistent with the water ADC value of vertebral bone marrow. Similarly, the value of diffusion coefficient of the fast component (~ 20x10 -3 mm 2 /s) is consistent with pseudo-diffusion values related to tissue microcapillary perfusion.

Figure 5 .

 5 Figure 5. The NNLS spectra of the diffusion decay in the water (top) and Polyethylene glycol (PEG, bottom) phantoms. A single diffusion peak is observed in water at ~ 2.1x10 -3 mm 2 /s and in PEG at ~ 1.2x10 -3 mm 2 /s.

Figure 1 .

 1 Figure 1. Plexiglas support for the water and PEG phantoms. The support consists of two separate parts that can be adjusted to the anatomy of the patient. The cylindrical phantoms are integrated into the support. The schematic and a photo of a single element are shown on the top left panel and top right panel, respectively. The support is positioned on the spine coil and the volunteer lies supine on the support during the MR experiment.

Figure 2 .

 2 Figure 2. Representative MR images of one volunteer. A coronal T2-weighted image (left) and an axial diffusion-weighted image acquired at the b-value = 50 s/mm 2 (right) are shown. In both acquisitions, a STIR-preparation module was used to suppress the lipid signal. The horizontal line on the coronal image indicates the position of the axial slice. The elliptical region of interest centered on the first lumbar vertebra (L1) is illustrated on the diffusion-weighted image.

Figure 3 .

 3 Figure 3. Example of intravoxel incoherent motion (IVIM) data acquired on one volunteer. The fat-suppressed diffusion decay from an ROI in the vertebral bone marrow (L1) and from an ROI in the noise are shown. As indicated by the curvature of the decay on the semi-log plot, the diffusion signal in bone marrow displays a bi-exponential behavior with a fast-decaying component for b-values between 0-100 s/mm2 and a slow-decaying component for b-values between 100-600 s/mm2. The NNLS analysis of this diffusion decay is shown in Figure 4.

Figure 4 .

 4 Figure 4. The NNLS spectrum of a fat-suppressed diffusion decay from an ROI in the vertebral bone marrow (L1) of one volunteer.The NNLS spectrum is plotted on a logarithmic scale with diffusion values equally spaced between 10 -1 and 10 2 (x10 -3 ) mm 2 /s. The NNLS spectrum exhibits two peaks at ~ 0.7x10 -3 mm 2 /s and ~ 20x10 -3 mm 2 /s, with a perfusion fraction of 14%. The diffusion coefficient of the slow component (~ 0.7x10 -3 mm 2 /s) is consistent with the water ADC value of vertebral bone marrow. Similarly, the value of diffusion coefficient of the fast component (~ 20x10 -3 mm 2 /s) is consistent with pseudo-diffusion values related to tissue microcapillary perfusion.

Figure 5 .

 5 Figure 5. The NNLS spectra of the diffusion decay in the water (top) and Polyethylene glycol (PEG, bottom) phantoms. A single diffusion peak is observed in water at ~ 2.1x10 -3 mm 2 /s and in PEG at ~ 1.2x10 -3 mm 2 /s.

Table 1 .

 1 Values of ADC, D* and perfusion fraction of vertebral bone marrow obtained by the biexponential curve fit (Bi-exp) and the non-negative least square (NNLS) analysis in fifteen volunteers. The bi-exponential curve fit was performed using the Levenberg-Marquardt nonlinear least squares algorithm. The NNLS analysis provided a bi-exponential behavior in seven out of fifteen volunteers. In the last row, the mean values and standard deviation are indicated.

  * Volunteer where bi-exponential fit did not provided two components.

	1	0.01	3.01			36	*
	2	0.64	--			**	*
	3	0.48	22.34	0.49	22.50	16	16
	4	0.74	44.36			43	*
	5	0.55	22.35	0,56	22.56	17	17
	6	0.57	25.73	0.58	25.90	12	12
	7	0.67	63.02			57	*
	8	0.76	18.67	0.77	18.75	18	18
	9	0.01	2.76			33	*
	10	0.44	29.88	0.56	29.78	14	14
	11	0.01	3.57			16	*
	12	0.67	41.79	0.67	43.11	2	2
	13	0.59	39.19	0.58	39.30	21	21
	14	0.60	566.03			50	*
	15	0.11	2.99			50	*
		0.45 ± 0.27	63 ± 145	0.60 ± 0.09	28 ± 9	27 ± 17	14 ± 6
	* Volunteers where NNLS did not provided two components.

*


Davide Carneiro
email: dcarneiro@di.uminho.pt

Paulo Novais

Ricardo Costa

José Neves
email: jneves@di.uminho.pt

Developing Intelligent Environments with OSGi and JADE

Keywords: Ambient Intelligence, Online Dispute Resolution, Multi-agent Systems, Service-Oriented Architectures, OSGi, Jade

The development of intelligent environments poses complex challenges, namely at the level of device heterogeneity and environment dynamics. In fact, we still lack supporting technologies and development approaches that can efficiently integrate different devices and technologies. In this paper we present how a recent integration of two important technologies, OSGi and Jade, can be used to significantly improve the development process, making it a more dynamic, modular and configurable one. We also focus on the main advantages that this integration provides to developers, from the Ambient Intelligence point of view. This work results from the development of two intelligent environments: VirtualECare, which is an intelligent environment for the monitorization of elderly in their homes and UMCourt, a virtual environment for dispute resolution.

Introduction

Ambient Intelligence is a relatively new field of Artificial Intelligence. In this paradigm, computers are seen as a proactive tool that assists us in our day to day. For the first time, the user in placed at the center of the computer-human interaction, which constitutes a major shift in the traditional paradigm [START_REF] Dix | Human-computer interaction[END_REF]. In fact, in the past we had to move ourselves to the vicinity of a computer in order to interact with it, using old-fashioned interaction means. Now we are interacting with environments that are built on numerous and distributed small computers that communicate, embedded in our common devices.

Evidently, the development of such environments poses complex challenges, namely because these are highly dynamic environments, include heterogeneous devices, are very complex to model, and need to be reliable. In this paper we address some of these challenges by bringing together two fields from computer science: Multi-agent Systems and Service-Oriented Architectures. Multi-agent Systems (MAS) [START_REF] Wooldrige | An Introduction to Multiagent Systems[END_REF] emerged from the combination of Artificial Intelligence with distributed computational models, generating a new paradigm: distributed artificial intelligence. From the Ambient Intelligence point of view a MAS can be defined as a group of entities (software or hardware) which will "read" the environment they are in and take decisions in order to achieve some common goal (like the comfort or safety of persons in the environment) based on knowledge from every agent in the system. In to the so-called Service Oriented Architectures [START_REF] Perrey | Service-oriented architecture[END_REF], functionalities are provided in the form of technology-independent services, based on three key concepts: the service provider, the service user and the service registry.

In order to develop an intelligent environment that can incorporate insights from these two trends, we consider in this paper two well known technologies: Jade agent platform [START_REF] Bellifemine | Developing Multi-agent Systems with JADE[END_REF] and OSGi service platform [START_REF]Alliance: Osgi service platform[END_REF]. Jade (Java Agent Development Framework) is a software framework that significantly facilitates the development of agent-based applications in compliance with the FIPA specifications. FIPA (Foundation for Intelligent Physical Agents) promotes standards that aim at the interoperability and compatibility of agents [10]. The use of OSGi (Open Services Gateway Initiative) allows developers to build java applications on a modular basis. The resulting modules are called bundles, which are not only competent to provide services, but also to use services provided from other bundles. In OSGi, a bundle can be installed, started, stopped or un-installed at run-time and without any kind of system reboot, making OSGi-based technologies very modular and dynamic.

Each of these two technologies has already been used successfully to implement a variety of projects in this field following two separate approaches (e.g. [START_REF]The Amigo Project: Amigo -Ambient Intelligence for the networked home environment[END_REF][START_REF] Haigh | The Independent LifeStyle Assistant: Lessons Learned[END_REF][START_REF] Camarinha | Virtual Communities and Elderly Support[END_REF]). In fact, each one has, as will be seen ahead, characteristics that can be incorporated in intelligent environments, resulting in advantages that are noticed in all the phases of the development, ranging from the specification and design of the system to the actual deployment and use. Moreover, there are approaches that use these two technologies together. [START_REF] Spanoudakis | An Ambient Intelligence Application Integrating Agent and Service-Oriented Technologies[END_REF] for example presents one for using Jade and OSGi, together with a methodology for integration. However, a recent development in these technologies has made this step a much simpler one: the recently released version 3.7 of Jade agent platform, which integrates the OSGi technology. Using this integration it is now possible to run JADE agents inside an OSGi environment, package agents code inside separated bundles, update it by means of the bundle update feature of OSGi and give agents access to all typical OSGi features such as registering and using OSGi services. This constitutes an opportunity that must be exploited in order to simplify the process of developing complex intelligent environments.

In this paper we do not present a new methodology for developing agents nor for developing service-based applications. Instead, we present an approach that builds on this new important development and that can make use of existing approaches for agent and service development individually. As an example, a developer could make use of VisualAgent [START_REF] De Maria | VisualAgent: A Software Development Environment for Multi-Agent Systems[END_REF] to easily develop the agents of the system and rely on a Model-Driven Architecture like the one presented in [START_REF]Model-driven Approach to Real-Time Embedded Systems development (MARTES)[END_REF] to implement the OSGi services. It results in an iterative and scalable process for developing highly modular applications targeted at virtual environments.

Specification of the Problem

Intelligent environments can be considered in many different domains, namely domestic, medical, legal, public spaces, workplaces, among others. In this paper, given our previous experience, we consider the development of domestic environments for the enhancement of the comfort and security of the user, with an emphasis on home care. In order to highlight the applicability of the presented approach, we will also use as example the development of UMCourt, a platform-independent virtual environment in which parties in dispute find alternatives to a disadvantageous dispute in court. This delimitation of the problem helps to define which devices and services can be considered.

In the case of UMCourt, as it is a virtual environment, it can be accessed from any regular internet-enabled device. The services considered are used transparently be the agents that represent the users and these users do not know with which services they are interacting. They simply request tasks that are delivered to them. In the case of VirtualECare, however, users explicitly interact with different physical devices, with specific capabilities. These devices can be grouped into three categories or layers: computing, communication and interface. Each of these layers has different devices and objectives and only with a close integration of all of them the system can be built.

In the computing layer one can have a multitude of devices which have computing capabilities and that can work independently from each other. In that sense we can consider small and common devices such as the mobile phone, mobile computers, watches, displays, photo machines, televisions or PDAs. In our modern homes, even window blinds, coffee machines or refrigerators have computing and networking capabilities. We can also consider environmental sensors such as temperature, luminosity and humidity sensors, smoke and flood sensors.

Concerning the communication layer, the main challenge comes from the heterogeneity of devices with communication capabilities and the different protocols and communication means that exist. A common home setting nowadays can have several networks, namely Ethernet, Wi-Fi, Bluetooth, power line, among others. There is a whole infrastructure of communicating devices that need to be compatible so that they can be integrated. The interface layer is also a very important part of the system since the devices through which the user interacts with the system will create the image that the user will have of the whole system. This means that this interaction must be very user friendly. In that sense, devices such as video cameras, microphones or touch-screens must be considered. In the opposite side we can enumerate the devices through which the system interacts with the environment, namely the actuators that allow controlling home appliances such as lights, heaters, air conditioning devices, among others.

It is a fact that nowadays a multitude of interesting devices exist that can improve our day-to-day living. However, these are very hard to integrate as each one has different characteristics. To address this problem there are already some defined standards but it necessary that manufacturers follow them and that all of them follow a single one. The solution is then to find effective ways to integrate these different devices by creating a compatibility layer that not only allows the devices to communicate but also makes it easier to develop applications to make use of the services provided by the devices.

Nature of the Architecture

Given the already mentioned characteristics of the devices that may inhabit an intelligent environment and given the dynamic nature of the interaction paradigm (e.g. user can interact with many eventually mobile devices, user can start or stop devices, user can incorporate new devices), we can state that an architecture for Ambient Intelligence should be dynamic, modular, expansible, flexible, scalable and compatible [START_REF] Carneiro | EMon: Embodied Monitorization[END_REF][START_REF] Costa | VirtualECare: Intelligent Assisted Living[END_REF]. In order to implement such an architecture the two previously mentioned technologies will be considered together, joining the advantages of Service Oriented Architectures and Multi-agent Systems in order to build a dynamic environment that can incorporate a multitude of heterogeneous devices.

The Role of Jade. Agent-based technologies have been used for the most different purposes. Basically, this paradigm intends to solve problems through the interaction of simple entities called agents. Each agent has its knowledge about the world and its objectives to accomplish, which may be individual or collective objectives. Likewise, agents may either cooperate or compete in order to achieve their objectives [START_REF]Coordination Theory and Collaboration Technology[END_REF]. One of the most interesting research trends in this field is in argumentation theory. In argumentation, agents debate, defend their beliefs and try to convince the other agents into believing the same they do in order to achieve their objectives [START_REF] Amgoud | Arguments, dialogue, and negotiation[END_REF]. Argumentation is also suited for solving conflicts that are usual in these environments. The most common example is a situation in which two agents have conflicting objectives (e.g. maintaining comfort versus saving energy). Besides argumentation, negotiation techniques [START_REF] Brito | The logic negotiation: from pre-argument reasoning to argument-based negotiation[END_REF] can and have also been considered to address these challenges.

One important issue here is the one of communication between the agents as these must respect a common standard that ensures that all the agents make use of the same ontology and message syntax. In that sense, the use of FIPA-ACL standard is highly useful. By doing so, many drawbacks concerning communication are solved and the compatibility of the architecture with external agents that respect the defined standard is assured, increasing the expansibility.

Given their features, agents will be used for all the high level decision making processes. It is thus necessary to define agents or groups of agents according to their roles in the architecture. This is, evidently, a task that is domain-dependent. An example focused on a domestic environment is described in section 4.

The Role of OSGi. In a common AmI architecture there is a group of components that must be connected. The objective of using an OSGi platform is to create a compatibility layer that can interconnect all the previously mentioned devices with components such as databases or external service providers. The approach to be followed will consist in hiding each of these different components behind a different OSGi bundle. The key idea of this approach is to hide the singularities of each device and confine them to the respective bundle. This way, depending on the component being controlled, each bundle will be responsible for the interaction logic and the registration and request of necessary services for the correct execution of the component. Developers of other bundles thus do not need to know the specifications of a given component they intend to interact with. They need only to request the services being provided by the bundle that controls the component. In that sense, OSGi bundles can be seen as black boxes providing services: it does not matter what is inside the box as long as we know how to use the service.

The roles of OSGi and Jade in the architecture have already been briefly depicted. We will now detail how these two tools can be used together in order to improve the process of developing intelligent environments. As stated before, the MAS is in charge of the high level decision processes, relying on tools like negotiation and argumentation to take globally optimum solutions. Additionally, OSGi is used to build a service layer that ensures the compatibility between all the different components of the architecture.

There are four main components in the architecture that allow a logical high level organization and a modular style of development: Jade container (the virtual location where the agents execute), Jade platform (may hold several Jade containers), OSGi bundle (able to provide and to use services from other bundles) and OSGi platform. The process of creating an intelligent environment supporting the intended features is organized into a group of sequential and eventual iterative phases, as seen in figure 1. Initial Specification. The process starts with the drawing of an initial specification. When defining this, some important factors must be considered such as the target environment of the system, its context of application, the devices that are likely to be used, among others. It is also important here to draw the first sketch of the functionalities of the system in terms of high level components. When drawing this first sketch it is usually useful to have some insights on the final architecture and the organization of the components, so that the first high level components and their organization do not differ significantly from the expected final version. However, as this approach is highly modular, the first sketch of the architecture may be defined without knowing how the final version will be: the intermediary versions can be easily reorganized by changing functionalities (e.g. moving bundles or agents between platforms). This significantly lifts the pressure on the development teams that have to define the architecture of the system without having a clear picture of how the final system will look like, solving one of the biggest challenges in the development of complex systems [START_REF] Edwards | At Home with Ubiquitous Computing: Seven Challenges[END_REF]. Note that in this first stage there is no need to declare which component is of which type, thus giving more freedom to make future changes to the system. Development. When the process reaches the development phase, the first sketch of the architecture is implemented. This might consist in simply creating high level components according to the initial specification and optionally creating some services with no functionality, only to define the connections between the several components and the way that information will be shared. Note that in this case we define only the several OSGi platforms and the direction of the services that will be used, configuring only high level components.

Another important task that can be performed here is to implement simulated bundles instead of "real" ones. Let us call simulated bundle to a bundle that simulates the services it should provide, for example, a bundle that simulates the value of the temperature instead of reading that value from an actual sensor. This is important as it allows developing a prototype version of the system without having all the necessary devices, thus reducing the costs and allowing for more easily and rapidly developing the prototype in initial stages. This means that in an eventual intermediary phase in the process, the system might be constituted only by simulated bundles or a mixture of simulated and real bundles. With OSGi, the whole architecture can be built out of simulated bundles that are then gradually replaced with real ones. The only main concern here is that the bundles that are being replaced have the same name and the same services signature, i.e., for the remaining services they are the same, although the reality is that they provide the same services in different ways. Assessment. Having implemented this first prototype version, the process moves on to the Assessment phase. In this phase, the system is tested in terms of its efficiency, robustness, usability and scalability. In initial versions, the interest in the assessment is to improve architecture-related parameters. Therefore, one of the important tests to perform is to invoke all the services in order to determine if they are correctly implemented and their signatures respected. It is also vital do evaluate the logical organization of the architecture. This may result in operations like dividing a complex bundle into simpler bundles, dividing an OSGi platform or Jade platform into several ones of the same type if they hold many components, group bundles or agents that are scattered in different platforms into one common platform, among others. In later phases of the development process, the assessment stage may receive as input the experience of interaction with target users. This might result in recommendations for changes suggested by experts in several fields, final users, etc. All these changes are then compiled and passed to a new iteration of the development stage for implementation. This process goes on until a satisfactory architecture is achieved.

By allowing to perform such tasks, this approach allows to develop intelligent environments by following several existing prototyping techniques, namely Throwaway, Evolutionary and Incremental prototyping.

Example Settings

VirtualECare

Having described the nature of the architecture that we achieve with this approach, let us now present an example of how the development process may occur. This example is a simplification of what was the development process of the VirtualECare project [START_REF] Costa | VirtualECare: Intelligent Assisted Living[END_REF]. In this example we will assume that we have only temperature and luminosity sensors. According to the proposed process, the first step is to define an initial specification for the system, in terms of the high level roles and functionalities that one intends to implement. In this case we will consider four objectives: we want to monitor the environment in terms of environmental parameters, control the devices present in the environment, incorporate intelligent decision mechanisms and model the user's preferences and needs.

In the first iteration of the development phase, we implement four bundles, each one representing one of the functionalities enumerated before (Figure 2). We also know that the bundle responsible for the decision mechanisms will contain agents so this will be a Jade-OSGi bundle. This is a rather simple process, consisting in creating only the activators and manifests for each bundle. In the first assessment phase all the bundles are started in order to determine if they have been well defined. In this phase we also define which agents will be necessary in order to be implemented in the next iteration. In this phase we also decide that the Monitorization bundle should be divided into two bundles, one for interacting with real sensors and another one for simulating parameters for which we do not have sensors. In the second iteration, we implement the decisions that have been taken in the previous one, arriving at an architecture as the one seen in Figure 3. Analyzing this system, we conclude that it makes more sense that the preferences and needs are embodied in two agents so that they also take part in the decision process. Therefore the decision is to move the code from a bundle to two agents. While developing the Real Sensors bundle, it was concluded that, due to the differences in the iteration logic of each type of sensor, this bundle should be divided. The same is decided for the Actuator bundle.

In further iterations similar operations can be performed, always without interfering with the components already present. One possible result is the architecture defined in Figure 4, considering a Fault Check bundle that restarts agents that have failed and a database.

UMCourt

UMCourt [START_REF] Carneiro | The Legal Precedent in Online Dispute Resolution, in Legal Knowledge and Information Systems[END_REF] is the second project in which this approach is being successfully applied. This project aims at the creation of an Online Dispute Resolution platform that uses insights from the Artificial Intelligence field, namely Case-based Reasoning (CBR), to implement a group of services intended to help parties in dispute. These services include the estimation of the most likely outcomes of a dispute, the generation of strategies and solutions, a negotiation environment and general tools for legal documentation management. Also here, the two technologies have been used with different purposes. Agents are used here in tasks that require significant context information. Examples are the negotiation and Case-based Reasoning modules. In these modules, FIPA-ACL messages are used not only to model information of the legal cases but also to model the control messages that define the negotiation protocol and the CBR process. An example of an ACL Message is shown below.

Example of an ACL message from agent Coordinator to agent Retriever requesting the cases similar to 1263491000923, assuming the default settings.

Sender : ( agent-identifier :name Coordinator@davide-desktop:1099/JADE :addresses (sequence http://davide-desktop:7778/acc )) Conversation-ID : 1263492569251 Reply-To : Coordinator@davide-desktop:1099/JADE Ontology : CBR_LABOUR Content : RETRIEVE_SIMILAR DEFAULT 1263491000923 OSGi, however, is used differently. It is used to implement the low level tasks that lighten the execution of the agents. Namely, bundles implement behaviors for selecting cases according to given criteria, transparently accessing the database, loading and indexing cases, among others. Adopting this approach has the advantage of decreasing the complexity of the agents by removing these tasks from the scope of the agent. At the same time, it increases code reuse as it is common that different agents make use of some of these tasks that are, this way, encapsulated inside bundles. Figure 5 shows a simplified view of the UMCourt architecture.

Conclusions

Jade and OSGi can be used independently to create intelligent environments following two different approaches. However, their integrated use provides a much more powerful solution that can cut development time and requisites. Following the highly modular approach presented here, it is possible to develop these environments gradually, making changes as needed. Hence, it is easy to add new functionalities (in the shape of new bundles or agents), it is easy to rearrange the existing architecture (e.g. sub-dividing or integrating components) always without interfering with the components already present. Functionally, Jade ensures the development of agents and provides all the advantages of a complete messaging service, facilitating the implementation of complex negotiation and argumentation protocols. OSGi, in the other hand, allows effective integration of very different components, creating a compatibility layer that exposes the functionalities of each component and hides the unnecessary complexity. Concluding, this approach allows to develop intelligent environments following the different prototyping techniques mentioned, fastening the whole process. Moreover, the advantages are present during the development phase and are reflected in the final architecture that is always ready to be improved with a new bundle or agent.

Fig. 1 .

 1 Fig. 1. The three phases of the development process.

Fig. 2 .

 2 Fig. 2. Result of iteration 1 with four bundles.

Fig. 3 .

 3 Fig. 3. Result of iteration 2 with five bundles and three agents.

Fig. 4 .

 4 Fig. 4. A simple AmI architecture with 9 bundles, 5 agents and the external components considered.

Fig. 5 .

 5 Fig. 5. A simplification of the UMCourt architecture.

Acknowledgments

. The work described in this paper is included in TIARAC -Telematics and Artificial Intelligence in Alternative Conflict Resolution Project (PTDC/JUR/71354/2006), which is a research project supported by FCT (Science & Technology Foundation), Portugal.