Yan Li
email: li@ensiie.fr

Yacine Ghamri-Doudane

Marwen Abdennebi
email: abdennebi@ensiie.fr

Channel-hole Based Scheduling in Relay-assisted Wireless Networks

Relay technologies are capable to significantly improve network performances in terms of cell capacity, coverage extension and system throughput. However, it should rely on an efficient scheduling scheme to fully profit from this potential gain. Although opportunistic scheduling is considered as the most promising scheduling technology for future networks in many literatures, it is not appropriate for the relay-assisted wireless systems due to some special features of the relay mode. In addition, most of the current literatures only discuss the scheduling in Base Station (BS) and neglect the channel state asymmetry between the BS-RS (Relay Station) link and RS-MS (Mobile Station) link. So we argue that an appropriate scheduling in RS can extremely improve the performance of the system. In this paper, we define a new concept called "channel-hole" which is used to precisely measure the wasted subchannel resources caused by the channel state asymmetry, and then propose a new scheduling algorithm, namely channel-hole based scheduling, in the RS based on this new concept. We also propose a theoretical model to analyze the proposed scheduling. Simulation results show that our proposed channel-hole scheduling is capable to utilize the radio resource more efficiently compared to the case where an opportunistic scheduling is used at the RS.

I. INTRODUCTION

Recently, relay technologies have been actively studied and considered in the standardization process of next-generation mobile broadband communication systems, such as IEEE 802.16j [START_REF]Draft Amendment to IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems: Multihop Relay Specification[END_REF], and IEEE 802.16m [START_REF] Abdennebi | Network Architecture Stage 2-3[END_REF]. The profit of introducing Relay Stations (RS) in the system is the extension of signal and service coverage, the enhancement of the system's overall throughput performance, and the power saving compared to the sole use of Base Stations (BS). The RS can forward high data rates in remote areas while keeping a low cost of infrastructure. But this potential gain in capacity and coverage is highly dependent on the scheduling scheme, a topic which draws more and more attention of the research community [START_REF] Byung-Gook | Opportunistic Power Scheduling for OFDMA Cellular Networks with Scheduling at Relay Stations[END_REF][4] [START_REF] Chi-Yao | 3-Approximation algorithm for joint routing and link scheduling in wireless relay networks[END_REF][6] [START_REF] Senarath | Multi-hop Relay System Evaluation Methodology[END_REF]. Some works on scheduling schemes can be found in [START_REF] Chi-Yao | 3-Approximation algorithm for joint routing and link scheduling in wireless relay networks[END_REF][6] [START_REF] Senarath | Multi-hop Relay System Evaluation Methodology[END_REF], but they only focus on the scheduling in BS and assume that all the packets transmitted from the BS to RS are immediately relayed to the destination MS without the need of scheduling at the RS. However, as the channel states of the links (BS-RS and RS-MS) vary in time independently to each other, if there is asymmetry between the channel states of the BS-RS link and RS-MS link, radio resources might be wasted. This asymmetry also leads to potential queuing in the RS and thus to the necessity of scheduling. In [START_REF] Byung-Gook | Opportunistic Power Scheduling for OFDMA Cellular Networks with Scheduling at Relay Stations[END_REF], the authors studied the above mentioned problem and propose the use of opportunistic scheduling in both BS and RS. The basic idea is to allocate subchannels to the Mobile Station (MS) experiencing the best channel condition at each frame. However, as we will show throughout the paper, due to some specific features of relay networks, the opportunistic scheduling scheme is not the best choice for relay-assisted networks, although it is considered as the most promising scheduling algorithm in the non relay-assisted networks. For example, in a two-hop transmission, even the RS-MS link is good enough to be chosen according to opportunistic scheduling, it might be wasted if there is no buffered packets to be transmitted. Similarly, for the bad RS-MS link, the packets buffered in RS might be finally dropped after a long period as this bad RS-MS link will not be allocated with subchannels due to the principle of opportunistic scheduling. In this case, the BS-RS link capacity which is used to transmit these dropped packets is also wasted as the packets did not finally reached their destinations. Considering this as well as other situations that may arise while opportunistic scheduling is used at the RS level, we think that this kind of scheduling is not effective in relay based networks and thus not appropriate.

Actually, we strong believe that if the RS adequately allocates subchannels to those MSs with suboptimal RS-MS links status but who has queued packets in the RS buffer or those MSs with suboptimal BS-MS links but with good RS-MS links, the radio resource can be utilized more effectively. [START_REF] Kaneko | Radio Resource Allocation Algorithm for Relay-Aided Cellular OFDMA System[END_REF] notices this problem, but it assumes the RS-MS links are stable for long period of times (several frames) once their status are detected to be good. This assumption is not reliable and not precise as the channel status change frequently especially when the MS is moving with high speed or the communication environment is complete, such as in presence of massive high buildings. Hence, by using a the scheduling scheme based on such assumption, it is still possible to result in radio resource wasting due to link asymmetry.

Considering the above mentioned issues, we will first define in this paper a new concept, channel-hole, as the measurement for the wasted radio resource in the following frames when the channel varies. Then, in an aim to efficiently use the radio resources, we propose a new scheduling algorithm to be used in the RS based on this new concept. Since the radio resource waste situation (i.e. channel-hole) is more precisely defined than in [START_REF] Kaneko | Radio Resource Allocation Algorithm for Relay-Aided Cellular OFDMA System[END_REF] in asymmetric links, the proposed scheduling algorithm is expected to be more efficient and improve the system performance more significantly than when using opportunistic scheduling in the RS. We also validate this by simulations. The remainder of this paper is organized as follows. The system model and the problem statement are presented in Section II. The term channel-hole is also defined in this section. In Section III, we propose the channel-hole based scheduling algorithm followed in Section IV by the link capacity analysis needed by our algorithm. The simulation results are provided in Section V. We conclude the paper and give directions for future work in Section VI.

978

II. SYSTEM MODEL AND PROBLEM STATEMENT

A. System Model

In this paper, we consider a single cell downlink transmission using Orthogonal Frequency-Division Multiple Access (OFDMA), with one BS and one RS in the cell as depicted in Figure 1. The frame structure is illustrated in Figure 2. In the frequency domain, the downlink channel is divided into N orthogonal subchannels each of which is constituted of a group of adjacent subcarriers. In the time domain, each frame is divided into a BS subframe and an RS subframe. In the BS subframe, only the BS can transmit data to the RS and MSs while in the RS subframe, the BS and RS can transmit data to MSs. Hence, an RSs can receive data only in the BS subframe and transmit data only in the RS subframe, while the BS can transmit data in both subframes. It is also assumed that the RS cannot transmit and receive data simultaneously.

Moreover, we assume the wireless channel is time-varying and frequency-selective but it is supposed to be flat within a subchannel and to be unchanged during a frame period. So Adaptive Modulation and Coding (AMC) will perform on per frame basis, and MSs feed back to the BS or to the RS their Channel State Information (CSI) containing their persubchannel Signal-to-Noise-Ratio (SNR) in each frame.

Then, similarly to [START_REF] Byung-Gook | Opportunistic Power Scheduling for OFDMA Cellular Networks with Scheduling at Relay Stations[END_REF], we define the following sets of elements: For K, "k 0 " represents the BS and "k 1 "represents the RS. For T , "1" represents the BS subframe and "2" represents the RS subframe. During a frame, all the data are delivered to the destination (RS in the BS subframe and MS in the RS subframe) through a logical link (s, d), where s ∈ K and

d ∈ k 1 ∪ M. Different combinations of s and d constitute the aggregate X = {x 0 , x 1 , • • • , x i , • • • }, i.e. (s, d) ∈ X .
Since each subchannel is assigned to each subframe, there is no intracell interference. During the tth frame, we define the subchannel assignment indicator:

d t (l, n, τ ) = ⎧ ⎨ ⎩ 1 if subchannel n is assigned to the l -th path at subframe τ , 0 otherwise (1)
where n ∈ N , l ∈ X and τ ∈ T .

We suppose the power is equally distributed on each subchannel which gives:

P τ (n) = P tot N ( 2
)
where P tot is the total transmission power of the system. The noise in the system is defined as

σ 2 = N 0 B N ( 3
)
where B is the bandwidth and N 0 is the power spectrum density of the noise. We also define the subchannel gain of the lth link on the subchannel n as h t (l, n, τ ), where n ∈ N , l ∈ X , τ ∈ T . So during the tth frame, the instantaneous capacity of the lth link on the subchannel n can be written as:

c t (l, n, τ ) = B N log 2 (1 + p τ (n) |h t (l, n, τ )| 2 σ 2 ) (4)
Then, during the tth frame, the capacity of the lth link can be calculated as:

R t (l) = N n=1 2 τ =1 d t (l, n, τ) c t (l, n, τ) (5)
1stM S queue: A fter served:

1 1 2 (-1)1 1 (-1)0 0 (-1)0 2nd M S queue: 1 1 2 (-1)1 1 (-1)0 0 ( -

B. Problem statement

As mentioned in the introduction section, opportunistic scheduling is not efficient in relay-assisted systems due to the specificities of the relay feature. Here we will present a simple example, illustrated in Figure 3, to explain with more details the "channel-hole" problem and then show how our proposed scheduling scheme will deal with this problem.

For simplicity and visibility, in Figure 3, it is temporarily assumed that there are only three MSs in the system, and two subchannels are allocated to the RS-MS link in the four frames shown in the Figure 3, i.e. from 3 rd frame to 4 th frame. Here we mainly illustrate the "hole" in subchannels during the RS subframe because the RS-MS link is the major bottleneck in the relay transmission. But the same problem can also happen in the BS subframe. We assume that there are three different small buffers in the RS buffer storing the packets to be forwarded to the corresponding destination MSs. Since only two subchannels are available, only two RS-MS links have right to forward packets in each RS frame, as denoted by squares in the figure. We list 3 statistics in the example, which are newly arrived packets through BS-RS link and to be stored in the RS buffer, i.e. "new arrival", number of queued packets sorted by the specific MS destination in the RS buffer when the RS subframe begins, i.e. "queue length", and the packet number that the RS served, i.e. "after served". "queue length" correspond to the sum of "new arrival" in current RS subframe and the "after served" in the previous RS subframe. "after served" is calculated by the "queue length" minus the number of packets that are forwarded to the destination in the same frame.

When the opportunistic scheduling is adopted in RS, it always chooses the two RS-MS links which have the best CSI to forward the packets. The squares in the figure represents the chosen link. For example, in the 1 st RS subframe, the squares show the 2 nd RS-MS link and the 3 rd RS-MS link has better link condition than others. So, the packets buffered in the RS queue, which are destined to the 2 nd MS and the 3 rd MS, can be forwarded during this RS subframe. We also simply assume only one packet can be forwarded for each chosen link in a RS subframe. Actually, in the real system, the number of packets which can be transmitted are decided by the AMC and is also different in each frame. In the 1 st subframe, "after served" equals to the "queue length" because its RS-MS link is not chosen; packets in the RS buffer and that are destinated to 2 nd MS is zero after one packet is forwarded; 3 rd "after served" equals to "-1" because there is no queued packets whose destination is 3 rd MS. But 3 rd RS-MS link is allocated with subchannel according to our definition of "after served". So, 3 rd "after served" should then be "-1" as the 3 rd MS queue is 0.

We notice that in the 1 st RS subframe, the radio resource which is allocated to the 3 rd RS-MS link is wasted because there is no packet that needs to be forwarded although this link has better CSI than the 1 st link. We use the term "channel hole" to define this situation, which is defined as the number of packets which are supposed to be forwarded but actually not due to the fact that RS buffer is empty. Hence, in the example above, the channel-holes related to the 3 rd RS-MS link should be "1". It is notable that channel-holes is also linked to the instantaneous channel rate, that is if the channel-hole problem is expected happen, high channel rates means a high number of channel-holes.

However, in the 1 st RS subframe, although the link condition of 1 st RS-MS link is worse than the 3 rd RS-MS link, there is queued packets for the destination of 1 st MS. So we can imagine to assign the subchannel to the 1 st RS-MS link. In this case, the radio resource will not be completely wasted. Indeed, even if with bad channel condition, the 1 st RS-MS can still forward some packets to the destination even the number of these packets is less than the one that can go through the 3 rd RS-MS when there are buffered packets to the 3 rd MS. So, it can be supposed that if these channel-holes can be used, the system performance will be improved by reducing the wasted channel capacity.

III. CHANNEL-HOLE BASED SCHEDULING ALGORITHM

Based on the above analysis, we propose in this section an improved scheduling algorithm which is called channelhole based scheduling. In this paper, we assume there exist a fixed or dynamic path selection that decides whether the MSs should select the relayed link or the direct link. Once the path is selected for each MS, the selected links are kept until the long-term average SNR of the MS change significantly. The path selection is performed periodically by assessing the long-term channel statistics. The proposed scheduling scheme is described in Algorithm 1.

As mentioned in section II, we assume that the channel rate to be flat within a frame and unchanged during it. So in this algorithm, we first estimate the instantaneous capacities and sort them in descending order. The sorting list contains BS-MS links, BS-RS links and RS-MS links. As we mainly consider the scheduling scheme in RS, the scheduling in BS can implement any. Here we use the opportunistic scheduling in the BS subframe, i.e. the BS always chooses the best links for its transmissions, which includes BS-MS direct transmissions and BS-RS relayed transmission. Each subchannel is assigned to only one link in each subframe. Actually, the allocations Algorithm 1 Channel-hole based scheduling algorithm. t + +; 36: end while are also performed according to the path selection which determines the number of direct links and relayed links in each frame. Our focus is to improve the performance of relay links. Thus here we simply first satisfy the direct links and then use the left subchannels to support the relay transmissions.

In the BS subframe, the packets sent from the BS and buffered in the RS will constitute the RS queue and they are classified and accumulated according to the destination MS, that is RSque (MSi) , while i = 1, 2, • • • , M. Then in the RS subframe, the direct link is given the higher priority and will be allocated Ny subchannels while the remaining y subchannels are used for the RS-MS links. The RS starts by temporarily allocating the subchannel to the top y RS-MS links which have good link statuses. Then, the RS check whether this allocation leads to channel-hole problems. The principle is if the ith RS-MS link is allocated with subchannels by the RS and the ith MS queue length is zero in the meanwhile, there will be a channel-hole. It is notable that if all the RSque (MSi) equals to zero, it means no packets in the RS queue. In this case, even it belongs to the channel-hole concept according to the definition, it is actually not because there are no packets in the buffer and no more subchannel become needed. We use F lag channel-hole = 1 to denote the existence of a channel hole. When F lag channel-hole = 1, it means that a channel-hole problem is experienced and that re-allocation is needed. When F lag channel-hole equals to 1, the RS choose the sub-optimized RS-MS links to use the channel-hole resources. The RS check the sorting list in the My remaining links and find the links whose RS queue length is bigger than zero, which means the links that have packets in the buffer and needs suchannel resources to forward them. Our scheduling algorithm will thus re-allocate the subchannel to them. After the transmission, the "after served" and "queue length" parameters need to be updated for each MS, since these variables are used for channel-hole detection. One should also note that the "after served" value should be set to zero here when the channel-hole problem happens. One should finally note that when no channel-hole is experienced (F lag channel-hole = 0) after the first allocation to the RS-MS links, the subchannel suplus is given to the direct BS-MS lnks.

IV. THEORETICAL ANALYSIS

In this section, we discuss the theoretical analysis of the proposed channel-hole scheduling algorithm. More precisely, we aim in this section at deriving the exact capacity expression which is needed in our scheduling algorithm to sort the links according to their capacities. We first define the average arrival rate and average service rate for each RSque (MSi) = k as bing λ i,k and μ i,k respectively with i = 1, 2, • • • , M. For different MSs, the RS -que (MSi) is stochastic. There are four possible statuses for each RSque (MSi) during a small time period (t, t + h) when h → 0:

1) 0 packets arrive and 0 packets are forwarded with probability (1

-λ i,k h) (1 -μ i,k h);
2) 0 packets arrive and 1 packet is forwarded with probability (1λ i,k+1 h) μ i,k+1 h;

3) 1 packet arrives and 0 packets are forwarded with probability

λ i,k-1 h (1 -μ i,k-1 h);
4) 1 packet arrives and 1 packet is forwarded with probability λ i,k h • μ i,k h; So, the transition probability at t + h for the ith MS with k packets in the queue length can be written as:

P i,k (t + h) =P i,k (t) (1 -λ i,k h) (1 -μ i,k h) + P i,k+1 (t) (1 -λ i,k+1 h) μ i,k+1 h + P i,k-1 (t) λ i,k-1 h (1 -μ i,k-1 h) + P i,k (t) λ i,k h • μ i,k h (6)
where t > 0, k > 0, i = 1, 2, • • • , M, and h is infinitesimal of higher order. Thus, we define the following equation which represents the differential equation for the transition probability when t tends to 0.

dP i,k (t) dt = lim h→0 P i,k (t + h) -P i,k (t) h = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ -P i,0 (t) λ 0 + P i,1 (t)μ 1 , k = 0 P i,n-1 (t) λ i,n-1 h -P i,n (t) (λ i,n + μ i,n ) +P i,n+1 (t) μ i,n+1 h, k = 0. (7)
If the system is stable, the transition probability matrix Λ of the system should satisfy PΛ = 0, where

P = [π i,0 , π i,1 , • • • , π i,k , • • • π i,K
] is the probability distribution vector for each RSque (MSi) and π i,k is the value of stable probability for 7), we can calculate P as follows:

P i,k when k = 1, 2, • • • , K; K > 0; i = 1, 2, • • • , M. With equation (
λ i,o π i,0 = μ i,1 π i,1 , k = 0 (λ i,k + μ i,k ) π i,k = λ i-1,k π i-1,k + μ i+1,k π i+1,k , k > 0 (8) where i = 1, 2, • • • , M.
In the mean while, above equation also satisfies:

∞ k=0 π i,k = 1, i = 1, 2, • • • , M. (9)
Combining ( 8) and (9), the elements of stable probability distribution vector are calculated as:

π i,0 = (1 + ∞ k=1 λi,0λi,1•••λ i,k-1 μi,1μi,2•••μ i,k ) -1 π i,k = λi,0λi,1•••λ i,k-1 μi,1μi,2•••μ i,k (1 + ∞ j=1 λi,0λi,1•••λ i,k-1 μi,1μi,2•••μ i,k ) -1 k > 0, i = 1, 2, • • • , M. (10)
As each subchannel has the same opportunity to be used for the service because they have no priority for each other, the subchannel capacity can be considered to obey the same probability distribution, i.e. μ 1,j = μ 2,j = • • • = μ M,j = μ. Then equation (10) can be expressed by:

π i,k = (λ i,k /μ) k 1 + ∞ k=1 (bλ i,k /μ) k (11)
As the subchannel assignment indicator d t (l, n, τ ), obey (0, 1) the distribution, the probability that d t (l, n, τ) equals to 1 is the probability to have RS ( que(M Si)) > 0 according to our algorithm, that is

P (d t (l, n, τ ) = 1) = M i=1 (1- 1 1 -λ i,0 /μ ). (12)
With equation ( 5) and ( 12), the capacity of the lth link during the τth frame can be expressed by:

R t (l) = N n=1 2 τ =1 M i=1 (1- 1 1 -λ i,0 /μ )c t (l, n, τ ) (13)
V. SIMULATION RESULTS

In this section, we present the simulation results for the proposed scheduling algorithm. Parameter settings of the simulation are shown in Table 1. The simulations are made in a single cell with a radius of 1000m, containing one BS and one RS. The RS is placed 800m away from the BS. MSs are distributed uniformly in the cell. The time-varying frenquency-selective channels are modeled by using pathloss, shadow fading and fast Rayleigh fading [8]. We assume that the channel condition of each subcarrier varies independently with each other. We assume that if the distance between the BS and an MS is smaller than 800m, all subchannels of the MS are allocated to the one-hop path in both the BS subframe and the RS subframe. Otherwise, these subchannels are allocated to the two-hop path through the RS. Simulations are made for a duration of 10000 frames. In the simulation, we compare the performance when opportunistic scheduling and our proposed channel-hole based scheduling are adopted in the RS. In the BS, we use the opportunistic scheduling, that is the BS allocates the subchannel to the link which have the best CSI.

Figure 4 compares the queue length in the RS buffer when different scheduling algorithm are adopted. The packet arrival processes for all the MSs follow the Poisson distribution with arrival rate of 0.3 packets/frame. Figure 4(a) shows the RS queue length when the opportunistic scheduling is used in the RS, while Figure 4(b) shows the RS queue length when our proposed channel-hole based scheduling is used in the RS. As we can see in Figure 4(a), the RS queue length increases more dramatically than that in Figure 4(b). This means that the opportunistic scheduling cannot well deal with the buffered packets in such situation and these packets cannot be sent out in time leading to congestion. Since we do not consider the packet loss rate caused by long delays, it is possible to record the packets number in the buffer. Contrarily, from Figure 4(b), we can see that the queue length in RS can keep a small value, i.e. a maximum of 15, which is clearly less than that in Figure 4(a). Thus we denotes that with our proposed scheduling algorithm, the resources can be used more efficiently to forward the buffered packets through the relay link, which results in small queue lengths.

Figure 5 compares the number of channel-holes in RS-MS link as defined in the Section II when both scheduling schemes are used. The packet arrival processes for all the MSs also follow the Poisson distribution with arrival rate of 0.3 packets/frame. Figure 5(a) shows the number of channel-holes when the opportunistic scheduling algorithm is used in the RS and Figure 5(b) shows the number of channel-holes when our proposed scheduling is used in the RS. With this figure, we can easily see that the number of channel-holes in Figure 5(a) is higher than that in Figure 5(b). Actually, channel-holes indicate the wasted subchannels. The wasted radio resource when opportunistic scheduling is used are twice more than wasted when our channel-hole based scheduling is used in the RS.

Finally, Figure 6 shows the channel utilization varying with the arrival rate of the MSs when opportunistic scheduling and our proposed channel-hole scheduling are adopted respctively. Again, the packet arrival processes follow the Poisson distribution. From Figure.8, we can see when the arrival rates increase, the channel utilization also increase. However, the channel-hole resource scheduling gives better results than the opportunistic scheduling and keeps higher utilization percentage because the former try to use the links which are not the best but with queued packets to be sent.

VI. CONCLUSION

In this paper, we first discussed the special features of relayassisted network, and disclosed the shortcomings of opportunistic scheduling when it is used in RSs for relay-assisted wireless networks. According to this, we define a new concept, i.e. channel-hole, which is linked to the wasted subchannel resources caused by link asymmetry. This concept precisely measures the wasted subchannel resources. To efficiently use the subchannel resources especially when asymmetric links exists, we proposed a new scheduling algorithm which is called channel-hole based scheduling to be used in the RS. For the purpose of our scheduling algorithm, we also derived analytically the link capacity expression. Simulations showed that by allowing the proposed scheduling at the RS, the amount of wasted subchannels are significantly lower to those wasted while adapting the opportunistic scheduling at RS. In the mean while, the system performance in terms of resource utilization and buffer occupancy are also improved. In our future work, we aim to study the case where multiple RSs are used and extend our scheduling to handle this case.

Fig. 1 :

 1 Fig. 1: Relay model.

Fig. 2 :

 2 Fig. 2: Frame structure for the relay-assisted networks.

Fig. 3 :

 3 Fig.3: Example of the "holes" in subchannels.

for i = 1

 1 to N do 19: if exist RSque (MSi) > 0 then 20: F lag channel-hole = 1; channel-hole = 1 then 24: for i = 1 to M do 25: if RSque (MSi) = 0 and the ith RS-MS link is allocated with subchannel k then 26:Re-allocated subchannel to sub-optimum RSthe y,"after served" and "queue length"; the packets using the Ny subchannels;

Fig. 4 :Fig. 5 :

 45 Fig. 4: RS queue length with (a) opportunistic schduling and (b)channel-hole based scheduling in the RS.

Fig. 6 :

 6 Fig. 6: Channel utilization when different scheduling algorithms are used in the RS.

TABLE I :

 I Simulation Settings

	Parameter	Value
	Number of BS	1
	Number of MSs	15
	Number of subchannels	128
	Frame lenghth	10ms
	Path loss exponents for BS-RS links	2
	Path loss exponents for BS-MS links and RS-MS links	4
	Standard deviation of shadow fading	8dB
	Power of BS	40w
	Power of RS	5w

ACKNOWLEDGMENT

This work is supported by European project ITEA2 HDTVnext.


USFD Stuart N Wrigley
email: s.wrigley@dcs.shef.ac.uk

Raúl García-Castro

Liliana Cabral

Cássia Trojahn

Dos Santos

Keywords: evaluation campaign, methodology, design, guidelines, timeline

. SEALS Deliverable D3.1 described the sequence of activities necessary to conduct the evaluation campaigns. This sequence was divided into four phases called Initiation, Involvement, Preparation and Execution, and Dissemination.

This deliverable covers the initial preparation of the second SEALS Evaluation Campaign. Chapters 2 and 3 describe the tasks performed during the Initiation and Involvement phases respectively.

Chapter 5 summarises the plan of work required in the remainder of the Involvement phase and then the Preparation and execution and Dissemination phases together with two timelines (one targeting participants and the other targeting the SEALS consortium members).

The deliverable also contains a number of appendices which contain two forms of announcements for the second SEALS Evaluation Campaign as well as the specific evaluation scenarios which each of the five technology areas will be addressing. Finally, the general SEALS Evaluation Campaign terms and conditions are provided.

List of Figures

Introduction

The SEALS project aims to create a lasting reference infrastructure for semantic technology evaluation (the SEALS Platform) and thus facilitate the continuous evaluation of semantic technologies at a large scale. The SEALS Platform will be an independent, open, scalable, extensible and sustainable infrastructure that will allow the evaluation of semantic technologies by providing an integrated set of evaluation services and test suites.

The SEALS project will take place in two 18-month stages and in each of these stages different evaluation campaigns will be performed for each of the technologies covered in the project. The SEALS Platform will be used in these evaluation campaigns and the results from the second SEALS Evaluation Campaign will be employed in creating semantic technology roadmaps that will identify sets of efficient and compatible tools for developing large-scale semantic applications.

This document focusses on the design of the second SEALS Evaluation Campaign and draws heavily upon the methodology and design recommendations made in SEALS Deliverable D3.1 [START_REF] García-Castro | D3.1 SEALS Methodology for Evaluation Campaigns v1[END_REF]. SEALS Deliverable D3.1 described the sequence of activities necessary to conduct the evaluation campaigns. This sequence, shown in Figure 1.1, is divided into four phases called Initiation, Involvement, Preparation and Execution, and Dissemination. The second SEALS Evaluation Campaign, which will address five core semantic technology areas, will run until April 2012 with final results being available by June 2012. This deliverable covers the initial preparation of the second SEALS Evaluation Campaign and starts describing the tasks performed during the Initiation and Involvement phases in chapters 2 and 3, respectively. Specifically, these chapters address the formation of two types of committee: the Evaluation Campaign Organizing Committee As can be seen from Figure 1.1, the Preparation and Execution phase runs concurrently with the Involvement phase. In Chapter 5 we summarise the plan of work required in the remainder of the Involvement phase, the Preparation and execution and Dissemination phases together with two timelines. Each timeline targets a different set of people associated with SEALS: the set of participants and the members of the SEALS consortium.

Chapter 4 describes a number of activities related to community engagement. This chapter addresses the role of external persons both in terms of their participation in the E.C.O.C. and E.C.E.C.s as well as their potential participation in the wider research of the SEALS project. Chapter 4 also summarises efforts to promote SEALS and the second SEALS Evaluation Campaign.

The deliverable also contains a number of appendices which contain the specific evaluation scenarios which each of the five technology areas will be addressing. Finally, the general SEALS Evaluation Campaign terms and conditions are included in Appendix D.

Tasks performed in the Initiation phase

The Initiation phase comprises the set of tasks where the different people involved in the organization of the evaluation campaign and the evaluation scenarios are identified and where the different evaluation scenarios are defined. These tasks and their interdependencies are shown in Figure 2.1. The first aspect of this task is the identification of the organisers; this is concerned with the creation of the two committees, described in Section 2.1, namely the E.C.O.C. and E.C.E.C.. The second aspect is the organisation of the evaluation scenarios, which is described in Section 2.2.

Identify organizers

The tasks of the evaluation campaign process are carried out by different actors according to the kind of roles that must be performed in each task. The SEALS Deliverable D3.1 (García-Castro and Martín-Recuerda, 2009) defined a number of different actors who will participate in the evaluation campaign process. This section presents the different kinds of actors involved in such process. ).

• Participants. The evaluation campaign participants are tool providers or people with the permission of tool providers that participate with a tool in the evaluation campaign.

For the second evaluation campaign, effort has been made to expand the membership of the E.C.O.C. (and also the E.C.E.C.s) to include prominent, external members (see also Chapter 4). Therefore, membership of the E.C.O.C. and E.C.E.C. will be:

Organize evaluation scenarios

The E.C.E.C. is in charge of organizing the evaluation scenarios that are performed in the evaluation campaign and of taking them to a successful end. The evaluation scenarios identified by each E.C.E.C. are described in Appendix A.

Tasks performed in the Involvement phase

The Involvement phase comprises the set of tasks in which the evaluation campaign is announced and participants show their interest in participating by registering for the evaluation campaign. These tasks and their interdependencies are shown in Figure 3.1.

Announce the evaluation campaign

As part of the Involvement phase, each E.C.E.C. has created two forms of public announcement: a 'short' and a 'long' announcement. These will be used both by WP2 and the E.C.E.C.s themselves to advertise the SEALS Evaluation Campaigns.

The short announcements have been combined to create a single announcement which gives a general description of the SEALS project and a broad introduction to each technology area's evaluation campaign (Appendix B). The target audience for this announcement is the semantic technology community in general and allied fields. Specifically, these distribution channels will be those maintained by STI International for such promotional activities as well as providers who have already registered an interest in SEALS via the SEALS Portal.

Each longer announcement will form the core information provided on the SEALS Portal for each technology area's second SEALS Evaluation Campaign. In addition, this information will also be emailed to researchers and tool developers known to be active in that particular tool field. These announcements give more details regarding the goals and evaluation scenarios involved in the evaluation campaign as well as information regarding how to participate. These announcements will be sent to the vendors identified as part of SEALS task T2.1 (described in D2.1 and enumerated on the SEALS private wiki) in which each of the work packages responsible for a particular technology area created a list of potential participants.

The announcements for each technology area's second SEALS Evaluation Campaign can be found in Appendix C with further details and up-to-date announcements being provided at http://www.seals-project.eu/seals-evaluation-campaigns/ 2nd-seals-evaluation-campaigns.

Provide registration mechanisms

Registration mechanisms were put in place on the SEALS Portal for the first SEALS Evaluation Campaign. These have been updated following consultation with each individual research workpackage (this consultation was conducted prior to the formal creation of each E.C.E.C.).

The general terms and conditions associated with participation in the SEALS Evaluation Campaigns (see appendix D) remain unchanged from the first SEALS Evaluation Campaign and are available on the SEALS Portal.

Community engagement

The SEALS Evaluation Campaigns are naturally community-oriented exercises with the overall goal of the project being to create a lasting infrastructure and best practice which persists after the funded duration of the project. At the core of the community involvement lies the participation of tool providers / developers who wish to evaluate their tools as well as tool adopters who will use the SEALS technology roadmaps and evaluation results to inform their technology decision processes.

However, it is also a goal of the SEALS project to involve technology providers and adopters in the design and execution of the SEALS Evaluation Campaigns themselves. This aspect is explicitly described in the methodology and design recommendations made in SEALS Deliverable D3.1 [START_REF] García-Castro | D3.1 SEALS Methodology for Evaluation Campaigns v1[END_REF]. In practice this relates to the involvement of persons external to the project in both the Evaluation Campaign Organizing Committee (E.C.O.C.) and each of the five technology areas' Evaluation Campaign Executing Committees (E.C.E.C.s). Such persons don't necessarily have to be drawn from technology developers or adopters, it is the intention of the SEALS consortium that high profile academic and industrial researchers also be involved. With respect to this, the SEALS Consortium has extended invitations to a number of external, well-respected members of the community (see Section 2.1). We are currently awaiting their responses.

Furthermore, it is hoped that existing evaluation efforts by members of the semantic community be aligned or even incorporated into the relevant SEALS Evaluation Campaigns. For instance, the SEALS Semantic Search Tool evaluation is currently working with the organisers of the Question Answering over Linked Data (QALD1 ) workshops with the intention of running their next campaign as part of SEALS. Additionally, Universidad Simón Bolívar is currently working with the SEALS Ontology Engineering Tool evaluation team with the intention of evaluating RDF storage systems.

Furthermore, the ability to incorporate external persons onto an E.C.E.C. provides a mechanism for this. In collaboration with the relevant E.C.E.C. and WP leader, the organiser can discuss the form of collaboration relevant to their evaluation effort. For instance, the SEALS Evaluation Campaign for Ontology Matching has an external member on its E.C.E.C. and it is likely that the SEALS Semantic Search Tool E.C.E.C. will also have an external member (representing QALD).

Incorporating external persons in SEALS

In addition to the inclusion of external representatives on the E.C.O.C. and the various E.C.E.C.s, the consortium has also put procedures in place for the creation of Associated Partners. Such persons could be identified by WP leaders on the basis that potential candidates can contribute concretely to the work done in SEALS, and specifically in their technology area. For instance, Universidad Simón Bolívar is currently working with WP11 as an Associated partner. The procedure that has been accepted by the SEALS consortium is the following:

1. WP leaders can either identify potential candidates which can contribute concretely to the work done in SEALS or be approached by such candidates. 2. Potential candidates formulate a short justification for their inclusion as associated partners including which SEALS work package they plan to contribute. This must be with the agreement of the respective WP leader. 3. The proposal is made by e-mail to the Project Management Board (PMB). 4. A decision will be made within one week based on the responses of the PMB members. 5. If accepted, a formal notification will be send to the new Associated Partner and their details, including planned contribution to SEALS, will be published on the SEALS Portal.

Associated partners can be invited to (parts of) SEALS meetings and participate in SEALS activities. Throughout their involvement with SEALS, the respective WP leader will act as the main liaison with the associated partner.

It must be noted that the granting of Associated Partner status does not infer any entitlement to SEALS funding nor any formal place in the SEALS consortium.

Promotion of SEALS and the SEALS Evaluation Campaign

SEALS Deliverable D2.1 [START_REF] Nixon | D2.1 Plans for community building and dissemination v1[END_REF] describes the SEALS community building and dissemination plan which is split into two phases covering the lifespan of the project (M1-18, and M19-36). It identified three target groups to be addressed by the plan: the research community, the tool provider community and technology adopters. Clearly, the first phase is largely focused on the first two groups (research and tool provider communities), with the third group (technology adopters) receiving more focus in the second phase once the first SEALS Evaluation Campaign results are available. Since we now enter this second phase, and with the results of the first evaluation campaign available, SEALS has taken care to promote the campaign results by presentations (at ESTC 2010, and online, promoted from the SEALS webpage frontpage) and a whitepaper to be distributed to vendors. Updated promotional materials and a tutorial are used to introduce interested people to participation in the second campaign.

In particular, the ESWC 2011 conference, which took place on Crete from May 29 to June 2, 2011 was the launchpad for promoting the second evaluation campaign, and SEALS itself, to the semantic technology community. Following the SEALS tutorial on May 29, an ESWC booth in the reception area of the conference was available during all conference days and staffed by SEALS volunteers, giving attendees the opportunity to see and discuss more about SEALS and the evaluation campaign.

Future activities and timeline

This chapter describes the tasks -as identified in SEALS Deliverable D3.1 (García-Castro and Martín-Recuerda, 2009) -that will form the focus of work related to the organisation of the second SEALS Evaluation Campaign. This chapter has been split into two parts: the first part addresses the remaining phases and their associated tasks; the second part describes the timeline by which these tasks will be completed. Note that this latter part is further split into two to emphasise the differing responsibilities for SEALS Evaluation Campaign participants and SEALS Evaluation Campaign organisers (the E.C.E.C.s).

Tasks for the next period

This section summarises the tasks that need to be accomplished as part of the Involvement, Preparation and execution and Dissemination phases. These tasks will largely be the responsibility of the individual E.C.E.C.s for each of the five technology areas. However, some of the tasks described also require input from the technology providers / participants.

Initiation phase

The Initiation phase comprises the set of tasks where the different people involved in the organization of the evaluation campaign and the evaluation scenarios are identified and where the different evaluation scenarios are defined. This phase is complete except for the finalising of the E.C.O.C. with repect to the external members who will be invited to sit on the committee.

Involvement phase

The Involvement phase comprises the set of tasks in which the evaluation campaign is announced and participants show their interest in participating by registering for the evaluation campaign. These announcements have been created (see Sec. 3.1) and are available from the SEALS Portal. These, together with generic SEALS Evaluation Campaign publicity material were used to formally launch the SEALS Evaluation Campaign at ESWC 2011 (29 May -2 June, 2011).

Preparation and Execution phase

The Preparation and Execution phase comprises the set of tasks that must be performed to insert the participating tools into the evaluation infrastructure, to execute each of the evaluation scenarios, and to analyse the evaluation results. These tasks and their interdependencies, shown in Figure 5.1, are the following:

1. Provide evaluation materials.

The E.C.E.C. must provide to the registered participants all the evaluation materials needed in the evaluation, including:

(a) Instructions on how to participate.

(b) The evaluation description.

(c) The evaluation test data.

(d) The evaluation infrastructure.

(e) Any software needed for the evaluation.

2. Insert tools.

Once the participants have all the evaluation materials, they must insert their tools into the evaluation infrastructure and ensure that these tools are ready for the evaluation execution.

3. Perform evaluation.

The evaluation is executed over all the participating tools and the evaluation results of all the tools are collected.

Dissemination phase

The Dissemination phase comprises the set of tasks that must be performed to disseminate the evaluation campaign results by publicly presenting them and to make all the evaluation campaign results and resources available. The tasks that compose this phase can be performed either independently for each evaluation scenario or covering all the evaluation scenarios in each task. These tasks and their interdependencies, shown in Figure 5.2, are the following:

1. Present results. The E.C.O.C., the E.C.E.C. and the participants will present and discuss the results of the evaluation campaign. It is envisaged that this will take the form of a workshop at ESWC 2012. The workshop will also be used to obtain feedback about the evaluation campaign.

2. Publish results. The E.C.O.C., the E.C.E.C. and the participants will publish the results of the evaluation campaign and of each of the tools either as workshop proceedings or journal special issues.

Finalize.

All the evaluation resources used in the evaluation campaign will be made public. The final report -SEALS Deliverable D3.6 -will include the results of the campaign as well as feedback for improving future campaigns beyond the funded period of the SEALS project. In addition to this, SEALS Deliverable D3.7 will identify the semantic technology roadmaps showing inter-tool compatibilities. Finally, SEALS Deliverable D3.8 will provide an updated version of the benchmarking methodology in light of the lessons learned from both the first and second evaluation campaigns.

Present results

Publish results

Feedback

Timeline

This section provides two timelines describing the work planned until the completion of the second SEALS Evaluation Campaign. Each timeline targets a different set of people associated with SEALS: the set of participants and the members of the SEALS consortium. However, each timeline should not be read in isolation: they are inherently interdependent and only together do they give a full description of the project's future work. Both timelines are shown Figure 5.3 with more details in Sections 5.2.1 and 5.2.2. -The E.C.O.C., led by the WP2 leader, will disseminate the general announcement including all evaluation campaigns to the existing distribution channels (mailing lists, blogs, SEALS Portal, etc.).

Participants

-Each E.C.E.C. will send technology area-specific announcements to all the vendors identified for T2.1 and T2.5 announcing details of their evaluation campaigns including timelines aimed at the potential participants.

•

A. Evaluation scenarios

A.1 WP10: Ontology Engineering Tools

The following naming scheme has been adopted to enable easy identification of evaluation campaign scenarios:

<ToolType> <Name/Criterion> <Year>

The evaluation scenarios are as follows (OET = ontology engineering tool):

• OET Conformance 2011 Testing conformance of OETs according to a language specification.

-RDF(S)

-OWL Lite -OWL DL -OWL Full -OWL 2 Full
-Ontology Design Pattern

• OET Interoperability 2011 Testing interoperability between OETs when using an interchange language.

-RDF(S)

-OWL Lite -OWL DL -OWL Full -OWL 2 Full
-Ontology Design Pattern

• OET Scalability 2011 Testing loading times for handling large ontologies with OETs.

-Real-world -LUBM

A.2 WP11: Storage and Reasoning Systems

The following naming scheme has been adopted to enable easy identification of evaluation campaign scenarios:

<ToolType> <Name/Criterion> <Year>
The evaluation scenarios are as follows (DLBS: Description logic based system; RDF SS: RDF storage system; RDF RS: RDF reasoning system):

• DLBS Classification 2011

A.3 WP12: Matching Tools

In 2010 we used a web-based evaluation service, which did not allow to measure runtime efficiency. In contrast to the 2010 evaluation all scenarios will be executed on the SEALS platform in 2011. The following naming scheme has been adopted to enable easy identification of evaluation campaign scenarios:

<ToolType> <Name/Criterion> <Year>
The evaluation scenarios are as follows (MT = Matching Tool):

• MT Benchmark 2011 Criteria: conformance with expected results, efficiency in terms of execution time, and interoperability.

• MT Anatomy 2011 (refined version of MT Anatomy 2010) Criteria: conformance with expected results, efficiency in terms of execution time, and interoperability.

• MT Conference 2011 Criteria: conformance with expected results, efficiency in terms of execution time, interoperability, and alignment coherence.

Currently other datasets are analyzed and might be used to complement these scenarios. For example, we have developed a new test data generator, which will probably be used to create an additional Benchmark dataset that is build on a different reference ontology compared to MT Benchmark 2011. Moreover, we have contacted the organizers of the OAEI directory and instance matching track. The corresponding datasets might be used in additional SEALS scenarios. A final decision about the usage of these datasets will be made soon.

B. General announcement of the SEALS Evaluation Campaigns

In order to announce the various SEALS Evaluation Campaigns, the E.C.O.C. will distribute a general communication using any mechanism available (e.g., mailing lists, blogs, etc.) with the goal of reaching the developers of the tools that are targeted by the evaluation scenarios. This appendix contains this announcement and incorporates short explanations of each area's campaign and targets the general semantic web community.

Dear Sir/Madam,

We are pleased to announce the second world-wide SEALS Evaluation Campaign for semantic technologies which will take place during Autumn 2011 / Spring 2012. The SEALS project has created a lasting reference infrastructure for automated semantic technology evaluation (the SEALS Platform) and thus facilitating the continuous evaluation of semantic technologies at a large scale with minimal effort from participants.

We cordially invite you to participate in the SEALS Evaluation Campaign in one or more of the five core areas shown below. Participation is open to anyone who is interesting in benchmarking a semantic technology tool. Detailed information regarding each area's campaign together with terms and conditions and general information about SEALS can be found on the SEALS Portal at http://www.seals-project.eu.

SEALS evaluations will address five core semantic technology areas:

Ontology Engineering Tools: addresses the ontology management capabilities of semantic technologies in terms of their ontology language conformance, interoperability and scalability. The main tools targeted are ontology engineering tools and ontology management frameworks and APIs; nevertheless, the evaluation is open to any other type of semantic technology.

Storage and Reasoning Systems: assesses a reasoner's performance in various scenarios resembling real-world applications. In particular, their effectiveness (comparison with pre-established 'golden standards'), interoperability (compliance with standards) and scalability are evaluated with ontologies of varying size and complexity.

Matching Tools: builds on previous matching evaluation initiatives (OAEI campaigns) and integrates the following evaluation criteria: (a) conformance with expected results (precision, recall and generalizations); (b) performance in terms of memory consumption and execution time; (c) interoperability, measuring the conformance with standard such as RDF/OWL; and (d) measuring the coherence of the generated alignments.

Semantic Search Tools: evaluated according to a number of different criteria including query expressiveness (means by which queries are formulated within the tool) and scalability. Given the interactive nature of semantic search tools, a core interest in this evaluation is the usability of a particular tool (effectiveness, efficiency, satisfac-tion).

Semantic Web Service Tools: focuses on activities such as discovery, ranking and selection. In the context of SEALS, we view a SWS tool as a collection of components (platform services) of the Semantic Execution Environment Reference Architecture (SEE-RA). Therefore, we require that SWS tools implement one or more SEE APIs in order to be evaluated.

C. Long announcements of evaluation campaigns

Once the different evaluation scenarios are defined, the E.C.O.C. must announce the evaluation campaign using any mechanism available (e.g., mailing lists, blogs, etc.) with the goal of reaching the developers of the tools that are targeted by the evaluation scenarios. This appendix contains the full announcements of each area's evaluation campaign. These will target tool providers and researchers in specific areas.

C.1 Common to all tool areas

C.1.1 Instructions on how to participate

Tool developers are cordially invited to participate in the SEALS Evaluation Campaign in one or more of the five core areas. Participation is open to developers interested in evaluating their tool or to anyone who wants to evaluate a certain tool.

From the tool provider's perspective, the SEALS Evaluation Campaign has been designed to require minimal effort on their part. For the majority of SEALS Evaluation Campaigns, the evaluation process is fully automated from the point at which the tool has been uploaded to the SEALS Platform. The SEALS Platform will manage all aspects of the evaluation. Once the evaluation has been completed, the results and analyses will be available from the SEALS Portal. In order to facilitate interaction between your tool and the SEALS Platform, the SEALS teams from each technology area have defined an easy to use API. Details about each technology area's API is available from their SEALS Evaluation Campaign's Portal page (http://www.seals-project.eu).

C.1.2 Evaluation Process

The timeline described in the following holds for all technology areas.

Preparation Phase (June 2011 -Nov 2011)

The first stage of this phase is the release of the detailed SEALS Evaluation Campaign materials. These will consist of Once these materials have been made available, participants will be able to submit and install their tools on the SEALS Platform. During this phase, the tool provider assisted by the E.C.E.C. have to verify that the tools submitted for evaluation run correctly on the SEALS Platform. In addition, first tests can be run with datasets associated with that SEALS Evaluation Campaign.

Execution Phase (Nov 2011 -March 2012)

Participants can submit different versions of their tool and use the SEALS Plat-In this edition of the evaluation campaign we will also evaluate conformance, interoperability and scalability, using the same test data as in the previous edition and extending it with

• Test data based in ontology design patterns and OWL 2 Full test data for conformance and interoperability evaluations. • New real-world and synthetic test data for scalability evaluations.

The evaluation campaign will take place by the end of 2011. Participation is open to developers interested in evaluating their tool or to anyone who wants to evaluate a certain tool.

Participants are just expected to collaborate in the connection of their tool with the SEALS Platform, which will be the infrastructure that will run all the evaluations automatically. Besides checking their results and comparing with others, once the tool is connected to the SEALS Platform participants will also be able to run the evaluations on their own with these and future test data.

If you want to participate, register your tool in the SEALS Portal (http://www. seals-project.eu) and stay tuned to the evaluation campaign web page where you can find detailed descriptions of the evaluations that we will perform and the latest information and results of the evaluation campaign.

If you have any question or comment about the evaluation campaign, please contact us.

• Raúl García-Castro (rgarcia@fi.upm.es).

• Michael Schneider (schneid@fzi.de).

We count on your participation!

C.3 Storage and Reasoning Systems

Semantic technologies are at the heart of the future Web providing ways to express knowledge and data so that it can be properly exploited. These technologies will empower a new class of Information and Communication Technologies much more scalable, interoperable, and with a higher degree of process automation support that will fulfil the needs of an emergence market that will exceed $10 billion by 2010.

Description logic based systems (DLBSs) evaluation aims at assessing interoperability, performance and scalability of one of the core building blocks of semantic technologies vision namely description logic reasoners. Resource description framework reasoning systems (RDF RS) evaluation is targeted at assessing interoperability and performance of RDF reasoners. Resource description framework storage systems (RDF SS) evaluation assesses efficiency and effectiveness of RDF storage systems.

This evaluation, thus, serves several purposes:

• Helps researches and users to select appropriate technologies;

• Gives an objective comparison among existing technologies;

• Stimulates technologies advancement through continuous evaluation.

The overall objective of evaluation campaign is to evaluate DLBSs standard inference services: classification, class satisfiability, ontology satisfiability, logical entailment and instance retrieval. The challenge uses a set of set of state of the art ontologies for evaluation. The set includes OWL 2 test cases repository, ontologies from Gardiner suite, various versions of the GALEN ontology, ontologies that have been created in EU funded projects SEMINTEC, VICODI, AEO and SNOMED CT ontology. DLBSs are expected to support OWL 2 language and provide interface to their functionalities through a set of evaluation interfaces defined in the SEALS Platform (http://www.seals-project.eu/seals-platform).

The RDF RS evaluation includes inconsistency checking and entailment checking inference services. Test data includes OWL 2 Conformance suite with over 1000 of specification-level and feature-level tests and artificially generated RDF datasets.

The RDF SS evaluation includes dataset loading and query assessment inference services. The real-world datasets include DBpedia, YAGO, linkedCT, US congress votes and set of SPARQL queries for each of these datasets. Artificially generated datasets include LUBM and Berlin SPARQL benchmark. RDF SS are expected to support SPARQL query language.

The evaluation is administered by the EU FP7-238975 SEALS -Semantic Evaluation at Large Scale project http://www.seals-project.eu/.

If you want to participate, register your tool in the SEALS Portal (http://www. seals-project.eu) and stay tuned to the evaluation campaign web page where you can find detailed descriptions of the evaluations that we will perform and the latest information and results of the evaluation campaign.

If you have any question or comment about the evaluation campaign, please contact us.

• Mikalai Yatskevich (mikalai.yatskevich@comlab.ox.ac.uk ).

• Michael Schneider (schneid@fzi.de).

• Daniel Winkler (daniel.winkler@sti2.at). We count on your participation!

C.4 Matching Tools

The SEALS evaluation campaign, built on the previous matching evaluation initiatives (Ontology Alignment Evaluation Initiative -OAEI), aims at evaluating the competence of matching systems with respect to different evaluation criteria. The evaluation will focus on demonstrating the feasibility and benefits of automating matching evaluation.

Important modifications for 2011

SEALS is supporting the OAEI organizers in running several OAEI 2011 tracks on the SEALS platform. This year, participants are required to upload their tools into the SEALS platform instead of implementing web service interfaces. Participants must provide their tools in a ZIP file format. A tutorial is provided (details can be found below) in order to explain how to prepare, upload, and package the tools in the required format. The webbased evaluation service used in the 2010 campaign, now integrated into the SEALS portal (https://www.seals-project.eu/ontology-matching-evaluationui), is still available for testing purposes but it will be not be used in the campaign to generate the official results.

Overview of the Evaluation Campaign

In 2011 we focus on the following criteria:

• Conformance against a reference alignment (precision, recall, f-measure);

• Interoperability, measuring the conformance with standard such as RDF/OWL;

• Coherence of alignments generated by matching systems;

• Efficiency in terms of runtime (elapsed runtime) Notice that efficiency metrics are for the first time part of the evaluation compared to previous OAEI evaluations. Measuring efficiency was already planned for 2010, however, we finally had to postpone this issue to 2011. Running tools on the platform in 2011 allows us now to include runtime efficiency criteria (and also to take care of the reproducibility of results in a controlled environment).

Evaluation scenarios and datasets

The evaluation campaign contains at least three different scenarios, where the tools will be evaluated according to common datasets and criteria.

Scenario 1: Benchmark The goal of this benchmark series is to identify the areas in which each matching algorithm is strong or weak. The test is based on one particular ontology dedicated to the very narrow domain of bibliography and a number of alternative ontologies on the same domain for which alignments are provided.

• Criteria: conformance with expected results.

• URL in SEALS testrepository http://seals.sti2.at/tdrs-web/testdata/ persistent/Benchmark+Testsuite/2010full/suite Scenario 2: Anatomy The anatomy real world case is about matching the Adult Mouse Anatomy (2744 classes) and the NCI Thesaurus (3304 classes) describing the human anatomy. Both ontologies are relatively large biomedical ontologies described in a typical medical language.

• Criteria: conformance with expected results, efficiency in terms of execution time.

• URL in SEALS testrepository http://seals.sti2.at/tdrs-web/testdata/ persistent/Anatomy+Testsuite/2010/suite Scenario 3: Conference The conference dataset consists of acollection of conference organization ontologies. This effort was expected to materialize in alignments as well as in interesting individual correspondences ('nuggets'), aggregated statistical observations and/or implicit design patterns.

• Criteria: conformance with expected results and alignment coherence.

• URL in SEALS testrepository: http://seals.sti2.at/tdrs-web/testdata/ persistent/Conference+Testsuite/2010/suite

We are currently investigating the possibility of adding more scenarios to be executed in the SEALS modality. As soon as we know more, we will forward the information via a SEAL news article.

Timeline and Tutorial

More information can be found on the relevant OAEI pages. Note also that, due to supporting OAEI 2011, the timeline of the ontology matching campaign differs from the timeline of the other SEALS campaigns.

OAEI 2011 Webpage (http://oaei.ontologymatching.org/2011/) Informs about all tracks of OAEI 2011 and contains a timeline binding also for the tracks supported by SEALS. This page links also to track specific information.

SEALS platform evaluation modalities (http://oaei.ontologymatching.org/ 2011/seals-eval.html) Contains specific instructions for participants of tracks in SEALS modality. In particular, a tutorial for wrapping a matching tool and software that supports the process is offered for download. The concrete steps for participating are described in detail.

Tools have to be wrapped following the provided tutorial. Otherwise it is not possible to evaluate them in the SEALS platform.

How do I get involved?

If you want to participate, register your tool in the SEALS Portal (http://www. seals-project.eu) and stay tuned to the evaluation campaign web page where you can find detailed descriptions of the evaluations that we will perform and the latest information and results of the evaluation campaign.

If you have any question or comment about the evaluation campaign, please contact us.

• Jérôme Euzenat (jerome.euzenat@inrialpes.fr ).

• Christian Meilicke (christian@informatik.uni-mannheim.de).

• Cássia Trojahn dos Santos (cassia.trojahn-dos-santos@inrialpes.fr ).

We count on your participation! C.5 Semantic Search Tools

C.5.1 Introduction

The goals of the semantic search tool evaluation initiative are to support developers to improve their tools; compare their tools against their competitors and to generally improve the interoperability of semantic technologies.

The short-term goal is to create a set of reference benchmark tests for assessing the strengths and weaknesses of the available tools and to compare them with each other. As such, these tests will focus on the performance of fundamental aspects of the tool in a strictly controlled environment / scenario rather than their ability to solve open-ended, real-life problems.

C.5.2 Criteria

Semantic search tools will be evaluated according to a number of different criteria including query expressiveness, usability (effectiveness, efficiency, satisfaction) and scalability. Scalability will address a number of factors including the tool's ability to query a large repository in a reasonable time; the tool's ability to cope with differing ontology sizes; and the tool's ability to cope with a large amount of query results. Query expressiveness will investigate the means by which queries are formulated within the tool and the degree to which this facilitates (or even impedes) the user's questionanswering goal. However, given the interactive nature of semantic search tools, a core interest in this evaluation is the usability of a particular tool.

C.5.3 Two phase approach

The core functionality of a semantic search tool is to allow a user to discover one or more facts or documents by inputting some form of a query. The manner, in which this input occurs (e.g.: natural language, keywords, visual representation) is not of concern; however, the user experience of using the interface is of interest. Therefore, it is essential, that the evaluation procedures described in this document emphasize the users' experience with each tool.

In order to achieve this goal, the evaluation of each tool is split into two complementary phases: the automated phase and the user-in-the-loop phase. The userin-the-loop phase involves a series of experiments involving human subjects, who are given a number of tasks (questions) to complete using a particular tool operating on an particular ontology.

Hence, the two core implications of this are that the user-in-the-loop experiments will be run by each tool provider participating in the evaluation and that additional software will be provided by this workpackage in order to both run the experimental workflows and likewise obtain the test data and return the results data to the various SEALS repositories. All materials required for the user-in-the-loop experiments will be provided by the SEALS consortium.

1. 1

 1 The evaluation campaign process. . . . . . . . . . . . . . . . . . . . . . 2.1 Initiation phase of the evaluation campaign process. . . . . . . . . . . . 3.1 Involvement phase of the evaluation campaign process. . . . . . . . . . 5.1 Preparation and execution phase of the evaluation campaign process. . 5.2 Dissemination phase of the evaluation campaign process. . . . . . . . . 5.3 Timeline of events for the second SEALS Evaluation Campaign. . . . .

Figure 1

 1 Figure 1.1: The evaluation campaign process.

  (E.C.O.C.) and a number of Evaluation Campaign Executing Committees (E.C.E.C.s) which will oversee the running of the second SEALS Evaluation Campaigns and specify the individual memberships of those committees. Furthermore, Chapter 3 describes the work undertaken to date by the E.C.E.C.s.

Figure 2 . 1 :

 21 Figure 2.1: Initiation phase of the evaluation campaign process.

Figure 3 . 1 :

 31 Figure 3.1: Involvement phase of the evaluation campaign process.

4.Figure 5 . 1 :

 51 Figure 5.1: Preparation and execution phase of the evaluation campaign process.

  .O.C. + E.C.E.C.

Figure 5 . 2 :

 52 Figure 5.2: Dissemination phase of the evaluation campaign process.

•

  June 2011 onwards: Register for participation at the SEALS Portal • August 2011: Obtain evaluation materials • October 2011 onwards: Insert tools into the SEALS Platform • November 2011 onwards: In conjunction with E.C.E.C., perform evaluation • March 2012: Result analysis • Early June 2012: Workshop at ESWC 2012 5.2.2 SEALS Partners • June 2011: Evaluation Campaign Announced.

  July 2011: Each E.C.E.C. makes evaluation materials available. • August 2011: Each E.C.E.C. publishes final release (FR) version of v1.0 evaluation software. • September 2011: Each E.C.E.C. inserts final test data into the SEALS Platform. • September 2011: Tools may be inserted. • End October 2011: Each E.C.E.C. inserts the final evaluation scenarios (description + workflow) into the SEALS Platform. This will include the provision of any software needed for the evaluation, inserted/connected into/with the SEALS Platform. • November 2011: Evaluations conducted by each E.C.E.C. (possibly directly including participants, e.g., WP13). • January 2012: Each E.C.E.C. publishes beta version of v2.0 evaluation software. • February 2012: Each E.C.E.C. inserts final results analysis tools into the SEALS Platform. • March 2012: Evaluation results ready. • March 2012: Result analysis begins. • May 2012: Result analysis complete. • Early June 2012: Workshop at ESWC 2012. • June 2012: Each E.C.E.C. makes evaluation resources public. • June 2012: Each E.C.E.C. publishes results of evaluation. • June 2012: E.C.O.C. and E.C.E.C.s produce final report D3.6. • June 2012: Roadmap report (D3.7) and updated methodology (D3.8). • June 2012: Each E.C.E.C. publishes final release (FR) version of v2.0 evaluation software.

  (a) Instructions on how to participate. (b) The evaluation description. (c) The evaluation test data. (d) Any software needed for the evaluation.

Table 2 .

 2 1: Membership of the E.C.O.C..

	Member	Affiliation Project Role
	Asunción Gómez-Pérez	UPM	EPMB Member
	Fabio Ciravegna	USFD	EPMB Member
	Jérôme Euzenat	INRIA	EPMB Member
	Raúl García-Castro	UPM	Quality Assurance Coordinator
	Lyndon Nixon	STI2	WP2 Leader
	Catherina Burghart	FZI	WP10 Leader
	Mikalai Yatskevich	OXF	WP11 Leader
	Cássia Trojahn dos Santos INRIA	WP12 Leader
	Stuart Wrigley	USFD	WP13 Leader and WP3 Leader
	Liliana Cabral	OU	WP14 Leader

• Evaluation Campaign Organizing Committee (E.C.O.C.). SEALS Executive Project Management Board (EPMB) and the SEALS research work package leaders plus any external personnel. • Evaluation Campaign Executing Committee (E.C.E.C.). A subset of the relevant research work package as defined by the work package leader plus any external personnel. 2.1.1 Membership E.C.O.C. The E.C.O.C. is composed of the SEALS Executive Project Management Board, the SEALS research work package leaders and other prominent external people. The constituent members are shown in Table 2.1. Note that the E.C.O.C. also contains the WP3 Leader (coordinator of the evaluation campaign organisation work package) and the WP2 Leader (coordinator of the dissemination and community building work package). Furthermore, as specified in the Description of Work,

Table 2

 2

		.2: Membership of each E.C.E.C..
	WP WP Name	Members	Affiliation
	10	Ontology Engineering Raúl García-Castro Tools Michael Schneider	UPM FZI
		Storage and Reasoning Mikalai Yatskevich	OXF
	11	Systems	Michael Schneider	FZI
			Daniel Winkler	UIBK
		Matching Tools	Jérôme Euzenat	INRIA
	12		Christian Meilicke Ondřej Šváb-Zamazal Univ. of Economics, UMA
				Prague, Czech Rep.
	13	Semantic Search Tools Stuart Wrigley Dorothee Reinhard	USFD UZH
		Semantic Web Service Liliana Cabral	OU
	14	Tools	Ning Li Daniel Winkler	OU UIBK
			John Domingue	OU
	• Enrico Motta, Professor of Knowledge Technologies, Knowledge Media Institute
	(KMi), The Open University, UK
	• Mark Musen, Professor of Medicine (Biomedical Informatics), Stanford Center
	for Biomedical Informatics Research, Standford University, USA.
	• Natasha Noy, Senior research scientist, Stanford Center for Biomedical Infor-
	matics Research, Standford University, USA.
	• Matthias Klusch, Research Fellow, German Research Centre for Artificial Intel-
	ligence (DFKI), Germany.
	• Birgitta König-Ries, Professor, Friedrich-Schiller-Universität Jena, Germany.
	E.C.E.C.
	Each E.C.E.C. contains a subset of the relevant WP personnel as shown in Table 2.2.

http://www.sc.cit-ec.uni-bielefeld.de/qald-1

seals-project.eu/ Document URL EU Project Officer Carmela Asero

Document Information

IST Project Number

List of Tables

A.4 WP13: Semantic Search Tools

The following naming scheme has been adopted to enable easy identification of evaluation campaign scenarios:

The evaluation scenarios are listed below (SST = Semantic Search Tool). It should be noted that participants of the Semantic Search Evaluation Campaign do not need to participate in both phases.

A.4.1 Automated Phase

SST Automated Search Performance 2011

The tool's core search quality in terms of precision, recall, etc. The tool's scalability will be considered according to measures such as processing / load time.

A.4.2 User-in-the-loop Phase

SST User Usability 2011

• How do the end-users react to the tool's query language? Do they like the tool? Are they able to express their questions effectively and fast? Is the language easy to understand and learn? These aspects of user satisfaction will be assessed in the questionnaires.

• Interpretation of the correlations between the user demographics and the measures.

2. SST User Query expressiveness 2011

• Testing the formal (by asking the test subjects in the questionnaire), as well as, the practical expressiveness (by running queries in order to test the actual coverage and robustness) of the tool's query language, i.e. if the tool is able to answer complex queries.

• Were all queries answered by the tool; i.e., could an answer be found?

A.5 WP14: Semantic Web Service Tools

The following naming scheme has been adopted to enable easy identification of evaluation campaign scenarios:

The evaluation scenarios are as follows (SWS = Semantic Web Services):

• SWS Tool Discovery Evaluation 2011 Retrieval and execution time performance evaluation of SWS tools for the discovery of Web Services based on their semantic annotations.

form to evaluate them at any moment. When they feel confident that it is correctly configured, they can submit the final version to the system. It will then be evaluated and the raw results of the evaluation experiments will be stored in the SEALS Results Repository.

Analysis Phase (March -June 2012)

The evaluation results will be automatically generated by the SEALS Platform using the evaluation criteria identified by your tool's technology area E.C.E.C.. This process will generate different data representations, such as graphs and tables for visualizing recall/precision, time execution, and comparisons between the different campaign participants. The results will be publicly accessible in the SEALS Portal after the evaluation phase has been conducted.

C.1.3 How to find out more

Detailed information regarding the SEALS Evaluation Campaign together with terms and conditions and general information about SEALS can be found on the SEALS Portal at http://www.seals-project.eu.

C.2 Ontology Engineering Tools

When dealing with the many existing semantic technologies, some questions arise sooner or later:

• Tool A is able of managing OWL DL ontologies but, up to what extent can it manage OWL Full ontologies? • I am using an OWL Full ontology in Tool B and I want to use it in Tool C, which only supports OWL Lite. Can I make it with a minimal loss of information? • Someone recommended me Tool D, but I need to manage very big ontologies.

Can this tool make it efficiently? If not, which one can?

The SEALS Yardsticks For Ontology Management is an evaluation campaign that comprises a set of evaluations defined with the goal of evaluating the ontology management capabilities of semantic technologies in order to answer those questions.

The main tools targeted for these evaluations are ontology engineering tools and ontology management frameworks and APIs; nevertheless, the evaluation is open to any other type of semantic technology.

In the previous evaluation campaign (http://www.seals-project.eu/seals-evaluation-campa 1st-evaluation-campaigns/ontology-engineering-tools) we evaluated ontology development tools in terms of their conformance and interoperability (using RDF(S), OWL Lite, OWL DL, and OWL Full) and their scalability (using both real-world ontologies and synthetically-generated ones).

C.5.4 Take part

The evaluation campaign will take place by the end of 2011.

Participation is open to developers interested in evaluating their tool or to anyone who wants to evaluate a certain tool.

Participants are just expected to collaborate in the connection of their tool with the SEALS Platform, which will be the infrastructure that will run all the evaluations automatically. Besides checking their results and comparing with others, once the tool is connected to the SEALS Platform participants will also be able to run the evaluations on their own with these and future test data.

If you want to participate, register your tool in the SEALS Portal (http://www. seals-project.eu) and stay tuned to the evaluation campaign web page where you can find detailed descriptions of the evaluations that we will perform and the latest information and results of the evaluation campaign.

If you have any question or comment about the evaluation campaign, please contact us.

• Stuart Wrigley (s.wrigley@dcs.shef.ac.uk ).

• Dorothee Reinhard (dreinhard@ifi.uzh.ch).

We count on your participation!

C.6 Semantic Web Service Tools

C.6.1 Evaluation Scenario Overview

The SWS discovery activity consists of finding Web Services based on their semantic descriptions. Tools for SWS discovery or matchmaking can be evaluated on retrieval performance, where for a given goal, i.e. a semantic description of a service request, and a given set of service descriptions, i.e. semantic descriptions of service offers, the tool returns the match degree between the goal and each service, and the platform measures the rate of matching correctness based on a number of metrics.

In the SEALS Semantic Web Service Discovery evaluation scenario we will test and compare SWS discovery tools/matchmakers on retrieval performance using the SEALS platform. SEALS services for applying standard IR measures such as Precision and Recall over registered datasets will be available. Retrieval results will be generated and stored for each registered tool.

C.6.2 Evaluation datasets

To evaluate the retrieval performance of SWS discovery tools/matchmakers, we will use:

C.6.3 Take part

The evaluation campaign will take place by the end of 2011.

Participation is open to developers interested in evaluating their tool or to anyone who wants to evaluate a certain tool.

Participants are just expected to collaborate in the connection of their tool with the SEALS Platform, which will be the infrastructure that will run all the evaluations automatically. Besides checking their results and comparing with others, once the tool is connected to the SEALS Platform participants will also be able to run the evaluations on their own with these and future test data.

If you want to participate, register your tool in the SEALS Portal (http://www. seals-project.eu) and stay tuned to the evaluation campaign web page where you can find detailed descriptions of the evaluations that we will perform and the latest information and results of the evaluation campaign.

If you have any question or comment about the evaluation campaign, please contact us.

• Liliana Cabral (l.s.cabral@open.ac.uk ).

• Ning Li (n.li@open.ac.uk ).

• Daniel Winkler (daniel.winkler@sti2.at).

• John Domingue (j.b.domingue@open.ac.uk ).

We count on your participation!

D. Evaluation campaign agreements

The following agreements describe the general terms for participation in the SEALS Evaluation Campaigns and the policies for using the resources and results produced in these evaluation campaigns. These were defined in SEALS Deliverable 3.1 (García-Castro and Martín-Recuerda, 2009) and are reproduced here for completeness.

D.1 Terms of participation

By submitting a tool and/or its results to a SEALS Evaluation Campaign the participants grant their permission for the publication of the tool results on the SEALS web site and for their use for scientific purposes (e.g., as a basis for experiments).

In return, it is expected that the provenance of these results is correctly and duly acknowledged.

D.2 Use rights

In order to avoid any inadequate use of the data provided by the SEALS Evaluation Campaigns, we make clear the following rules of use of these data.

It is the responsibility of the user of the data to ensure that the authors of the results are properly acknowledged, unless these data are used in an anonymous aggregated way. In the case of participant results, an appropriate acknowledgement is the mention of this participant and a citation of a paper from the participants (e.g., the paper detailing their participation). The specific conditions under which the results have been produced should not be misrepresented (an explicit link to their source in the SEALS web site should be made).

These rules apply to any publication mentioning these results. In addition, specific rules below also apply to particular types of use of the data.

D.2.1 Rule applying to the non-public use of the data

Anyone can freely use the evaluations, test data and evaluation results for evaluating and improving their tools and methods.

D.2.2 Rules applying to evaluation campaign participants

The participants of some evaluation campaign can publish the results as long as they cite the source of the evaluations and in which evaluation campaign they were obtained.

Participants can compare their results with other published results on the SEALS web site as long as they also:

• compare with the results of all the participants of the same evaluation scenario; and

• compare with all the test data of this evaluation scenario.

Of course, participants can mention their participation in the evaluation campaign.

D.2.3 Rules applying to people who did not participate in an evaluation campaign People who did not participate in an evaluation campaign can publish their results as long as they cite the sources of the evaluations and in which evaluation campaign they were obtained and they need to make clear that they did not participate in the official evaluation campaign. They can compare their results with other published results on the SEALS web site as long as they:

• cite the source of the evaluations and in which evaluation campaign they were obtained;

• compare with the results of all the participants of the same evaluation scenario; and

• compare with all the test data of this evaluation scenario.

They cannot pretend having executed the evaluation in the same conditions as the participants. Furthermore, given that evaluation results change over time, it is not ethical to compare one tool against old results; one should always make comparisons with the state of the art.

D.2.4 Rules applying to other cases

Anyone can mention the evaluations and evaluation campaigns for discussing them.

Any other use of these evaluations and their results is not authorized (you can ask for permission however to the contact point) and failing to comply to the requirements above is considered as unethical.