Amr Abdelfattah
email: amr.abdelfattah@lip6.fr

Naceur Malouch
email: naceur.malouch@lip6.fr

Studying the Impact of LTE-U on Wi-Fi Downlink Performance

Keywords: LTE-U, Duty Cycled LTE, Wi-Fi, 5G, Mobile Communication, Collision Probability, Peformance Evaluation, Simulation

To address the mobile data growth challenges, mobile operators need to access more spectrum resources. LTE in unlicensed spectrum (LTE-U) has been proposed to extend the usual operation of LTE in licensed spectrum to cover also unlicensed spectrum, mainly at 5 GHz band due to its wide spectrum availability. However, this extension poses significant challenges especially regarding the coexistence between LTE-U and legacy systems like Wi-Fi. In case of LTE-U adopts Time-Division Multiplexing (TDM) schemes to share the spectrum with Wi-Fi, we expect performance degradations of Wi-Fi networks. In this paper, we quantify the impact of TDM schemes on Wi-Fi performance in a coexistence scenario. We provide an analytical model to compute the probability of collision faced by Wi-Fi and its downlink throughput performance. This model provides an upper bound of the probability of collision that could be faced by a finite number of Wi-Fi stations. NS3 simulations show that the model estimates accurately the collision probability and the throughput experienced by Wi-Fi. The model is then used to study and compare different coexistence schemes showing for instance that the Wi-Fi frame size impacts globally the performance of Wi-Fi users.

I. INTRODUCTION

According to Cisco forecast, by 2019, the monthly global mobile data traffic will exceed 24.3 Exabyte [START_REF]Cisco visual networking index: Global mobile data traffic forecast update 2014-2019[END_REF] because of the increasing number of mobile broadband data subscribers. This motivates mobile operators to increase the capacity of their cellular networks to cope with this challenge. As nextgeneration communication systems (i.e. LTE, LTE-A) performance is close to Shannon bound in terms of spectrum efficiency, cellular networks move towards data traffic offloading from licensed to unlicensed spectrum which stands out as a promising solution. One technique to perform offloading is to mix wireless technologies by using Wi-Fi networks as an alternative or as a complementary network for cellular networks. In heterogeneous networks, the user equipment accesses licensed and/or unlicensed spectrum to improve data throughput with the price of adding complexity to the network. Another technique is to extend the operation of LTE to unlicensed spectrum, called LTE in Unlicensed band (LTE-U), so that mobile operators have an easy and transparent usage of unlicensed spectrum in a unified network environment which typically promises higher spectral efficiency than Wi-Fi. Enabling LTE-U and Wi-Fi networks to operate in the same shared spectrum requires considering coexistence scenarios carefully. LTE-U has to adopt a spectrum sharing scheme to coexist fairly with Wi-Fi and fulfill telecommunication regulatory agencies requirements to occupy this spectrum.

In regions such as Europe, Japan and India, accessing unlicensed spectrum requires that LTE adopts a Listen Before Talk (LBT) spectrum sharing scheme with the so-called channel clear assessment (CCA) mechanism. To add this new flavor to LTE, we can exploit Load Base Equipment (LBE) or Frame Based Equipment (FBE) mechanisms defined in [START_REF][END_REF] as two options for LBT scheme. As a result, we expect a huge modification on LTE standard and losing backwardcompatibility with latest standards. In a white paper published by Qualcomm [START_REF] Research | Lte in unlicensed spectrum: Harmonious coexistence with wi-fi[END_REF], LTE-U has used an FBE mechanism to coexist with Wi-Fi in an outdoor simulation scenario. The simulation results show that LTE-U is a better neighbor to Wi-Fi than Wi-Fi to itself. However, [START_REF] Chen | Downlink performance analysis of lte and wifi coexistence in unlicensed bands with a simple listen-beforetalk scheme[END_REF] shows that when the load of LTE-U is very high, LBT impacts significantly the performance of Wi-Fi users while LTE-U users remain robust.

LBT adaptation prerequisite was dismissed for other regions such as USA, China and Korea. Therefore, an intuitive and simple way to share the spectrum is to prevent LTE-U and Wi-Fi from accessing the channel at the same time using Time-Division Multiplexing (TDM) schemes. LTE-U occupies the channel for some period of time then vacates it to allow Wi-Fi users to access it for some amount of time. To do so, LTE-U can choose either a short or a long TDM duty cycle dynamically or statically. TDM adaptation is compatible with existing LTE standards thanks to LTE advanced features. Hence, mobile operators can leverage the large LTE ecosystem. For instance, a key LTE feature called SCell activation/deactivation can be used to have a long TDM duty cycle where LTE-U and Wi-Fi access the channel in time across several milliseconds (20 ∼ 100x ms). In [START_REF] Abinader | Enabling the coexistence of lte and wi-fi in unlicensed bands[END_REF], the authors propose a simple way to have a short TDM duty cycle (1 ∼ 10 ms) over an LTE frame of 10 ms through a modified version of Almost Blank Subframes (ABS) feature where LTE reference signals had been totally removed to have blank subframes.

On one hand, TDM schemes allow better control on how and when the spectrum is accessed by LTE and Wi-Fi, and thus master better the sharing. On the other hand, collisions with Wi-Fi may occur when LTE starts a transmission period after a silence period or after a blank subframe. In this paper, we aim at quantifying the impact of LTE TDM schemes on the performance of Wi-Fi networks at the MAC level by computing analytically the probability of collision. We model the interaction between LTE and Wi-Fi using both delayed and ordinary renewal processes associated with a stopping time directly related to LTE-U idle periods. We also use a discrete time Markov chain to model the progress of the interaction over time. We similarly compute the offered downlink throughput of a Wi-Fi access point. In addition, we have implemented the TDM scheme in the open-source NS3 (Network Simulator version 3) simulator [START_REF]Official website[END_REF] and we used its complete implementation of IEEE 802.11 standard to validate our model and assess its robustness when the model assumptions are not quite valid. The previous work [START_REF] Almeida | Enabling lte/wifi coexistence by lte blank subframe allocation[END_REF] has studied the LTE and Wi-Fi interaction through blank subframes in indoor environment for single and multiple-floor scenarios. Multiple TDM configurations have been examined using a proprietary semi-static system-level simulator. The results show first that the more the number of blank subframes over LTE frame, the higher the offered Wi-Fi throughput. Second, for the same number of blank subframes, Wi-Fi can experience different throughputs. These results were partially justified by the system-level simulator since the exact impact on the Wi-Fi performance was not analyzed. Thus, it is hard to compare between TDM schemes to find the best configuration parameters that maximize the throughput and reduce the collision probability. In this work, we provide a formal justification of the possible performance degradation experienced by Wi-Fi. We show how the Wi-Fi performance is related to the number of blank subframes during the LTE frame and also to their distribution along the frame. Through the model and supported by NS3 simulations, we show that the packet size has an important role to increase or decrease the Wi-Fi throughput especially for low Wi-Fi channel bit rates.

In [START_REF] Joey Padden | Wi-fi vs. duty cycled lte: A balancing act[END_REF], the authors found that for a fixed TDM duty cycle percentage, if the duty cycle period is too short, the throughput of Wi-Fi can be negatively impacted. However, if the duty cycle period is too long, it is more the packet latency that will be degraded. Our work complements these results by studying different duty cycle patterns while using a compromised duty cycle period.

Other coexistence techniques were also studied in the previous work. Chen et al. have studied in [START_REF] Chen | Downlink performance analysis of lte and wifi coexistence in unlicensed bands with a simple listen-beforetalk scheme[END_REF] the downlink performance of Wi-Fi when LBT scheme is deployed. They used a Markov chain to model Wi-Fi random access to the spectrum. [START_REF] Cavalcante | Performance evaluation of lte and wi-fi coexistence in unlicensed bands[END_REF], [START_REF] Abinader | Enabling the coexistence of lte and wi-fi in unlicensed bands[END_REF] have investigated spatial spectrum sharing in indoor environment where the objective is to separate away LTE and Wi-Fi devices to avoid interferences. In contrast, [START_REF] Chaves | Lte ul power control for the improvement of lte/wi-fi coexistence[END_REF], [START_REF] Chaves | Lte/wi-fi coexistence: Challenges and mechanisms[END_REF] propose an interference-aware power control to share the spectrum with Wi-Fi. Our work complements these previous works by studying another coexistence approach especially that neither one of them have proved optimal efficiency in all network scenarios. Moreover, TDM schemes have the advantage of being more flexible and easy to deploy.

The paper is outlined as follows. In Section II, we explore the interaction between LTE-U and Wi-Fi. In Section III, we provide an analytical model for Wi-Fi coexisting with LTE-U to quantify the impact of LTE-U on an infrastructurebased Wi-Fi network in terms of probability of collision and saturation throughput. Section IV validates the accuracy of our model by comparing its results with those obtained by means of NS3 simulations. We investigate the performance of Wi-Fi in various TDM schemes and Wi-Fi configurations. Finally, conclusions and future work are drawn in Section V.

II. LTE-U ENODEB INTERACTING WITH WI-FI ACCESS

POINT In this section, we explore the impact of LTE-U eNodeB transmissions on Wi-Fi downlink transmissions by an Access Point (AP) in infrastructure mode. The use of different MAC techniques by LTE-U and Wi-Fi creates a major sharing problem. By default, LTE-U does not sense the channel before transmitting to know whether it is idle or not unlike Wi-Fi which follows an LBT scheme. As a result, an unexpected interruption of Wi-Fi transmission by LTE-U can be produced at several times leading to the collision between the two systems.

In Figure 1, eNodeB is activated/deactivated during ON/OFF periods. This ON/OFF pattern is controlled by three different parameters. First, the duty cycle period that determines how long it takes to the pattern to be repeated again. Second, the duty cycle percentage which is the portion of time where the eNodeB is activated over the duty cycle period. Third, the transmission periods during the duty cycle period which controls how the eNodeB ON/OFF periods are distributed during the duty cycle. This transmission periods can be continuous or separated by several silence periods. Now, we turn our attention to the periods where AP can access the channel corresponding to eNodeB-OFF periods. We look first at the end of these periods (See Figure 1). In each period, after a successful transmission of some frames, when the next eNodeB-ON period starts, it can start when Wi-Fi is sensing the channel during a DIFS which is the Distributed InterFrame Space (Case 1 in Figure 1). The eNodeB period can also start during the decrementing of the backoff counter of the Wi-Fi AP (Case 2). Effectively, after the DIFS sensing period, the Wi-Fi AP transmits its frame after a random number of slots called backoff time. Finally, the eNodeB period can start during the Wi-Fi frame transmission (Case 3).

To get into more details, in the first case, eNodeB interruption comes after the end of a frame transmission that is why the last frame is successfully transmitted. Then, AP defers the next transmission until the eNodeB transmission period is finished. Then, at the next Wi-Fi transmission period (eNodeB-OFF), a new frame will be transmitted after sensing the channel for a time equal to the DIFS and the slotted random backoff time period corresponding to a random backoff counter uniformly chosen in the range of [0, CW ], where CW is the initial backoff contention window size. The backoff time is fully determined by this counter since the slot time is fixed. We denote the slot time by δ.

In the second case, the eNodeB interruption comes during the slotted random backoff time period while AP is decrementing its backoff counter at the end of each slot time δ. When AP senses the channel busy, it freezes the backoff counter and the frame transmission procedure is frozen until the next eNodeB-OFF period that is why we call the last frame is a frozen frame. At the next eNodeB-OFF period, the frozen frame is transmitted after sensing the channel again for a time equals to DIFS and after decrementing the rest of the frozen backoff counter from the previous period.

As for the third case, the eNodeB interruption comes during Wi-Fi frame transmission so a collision is occurred and the frame is lost for that reason we call the last frame is a collided frame. At the next eNodeB-OFF period, AP retransmits that collided frame again after a DIFS period and a uniform random backoff time with a doubled backoff contention window size equals to 2 * (CW + 1) -1.

III. ANALYTICAL MODEL

The analysis is divided into two steps. First, we study the behavior over time of the AP coexisting with eNodeB using a Discrete Time Markov Chain (DTMC). Second, we compute the transition probabilities by considering the Wi-Fi transmissions as a renewal process stopped by LTE-U arrival. Finally, we obtain the probability of collision under the saturation condition, and we express the AP downlink throughput.

Over a duty cycle period, AP can access the channel during different eNodeB-OFF time periods. Let us adopt the notation T i for such periods where i ∈ (1, • • • , M ) and M is the number of disjoint access channel opportunities offered to AP during a duty cycle period (see Figure 1 for M=2). As mentioned in Section II, we enumerated three cases where the AP transmission during any T i period terminates with a frozen, collided or success frame, as shown in Figure 1. Thus, the end of each T i period can be adequately modeled by means of a three-state Markov chain. Let us denote by S = {f i , c i , s i }, the space state for period T i , where f i , c i and s i indicate that the AP transmission has been ended with a frozen, collided and success frame during T i period respectively. As a result, any given T i period has a set of three states which can be visited again only at multiples of M leading to a periodic DTMC with period M . This shown in Figure 2 for M = 3, i.e. periods T 1 , T 2 and T 3 . We should note also that the Markov chain can lose the periodicity when at least two periods of T i periods have the same time values over the duty cycle period. In order to keep the Markov property, we assume that after a collision at the end of a T i period, the retransmitted frame at the beginning of the next T i period does not face a collision. To relax this assumption, we should add the current number of accumulated successive collisions in the Markov chain states which complexifies too much the model without a significant accuracy gain as we shall see later. Indeed, these T i periods are multiples of 1 ms and thus they are relatively large compared to the AP frame transmission time. It is intuitive that this assumption is more valid as long as T i period gets larger and AP frame size gets smaller. Besides, the high rates provided by recent Wi-Fi technologies allows several frame transmissions in 1 ms even for large packet sizes.

A. Transition Probabilities and Probability of Collision

In this subsection, we show how we can calculate the transition probabilities between any two states in our Markovian model using renewal processes. Then, we compute the global probability of collision faced by any AP frame transmission.

After the eNodeB transmission is finished, the AP starts immediately to transmit its frames at the beginning of a T i period. As described in Section II, the amount of time needed for DCF protocol to successfully transmit the first frame depends on how ended the AP transmission during the previous period. The previous period is T i-1 for i ∈ (2, • • • , M ), and T M for i = 1. For simplicity of notation and without loss of generality, we denote by T i-1 the previous period for all i. First, let us consider that T i-1 period state was s i-1 (success). Then, the amount of time needed to successfully transmit the first frame at T i period can be represented by the following uniform random variable:

X = DIF S + δ * BF counter unif (0,CW ) + F rametime (1)
Where BF counter unif (0,CW ) is the backoff counter which is a uniform random variable with lower and upper limits of 0 and CW respectively. F rame time is the frame transmission time which includes the frame airtime over the channel, followed by a period of time equals to Short InterFrame Space (SIFS) and the acknowledgment transmission time (Acktime).

That is F rame time = frame airtime + SIFS + Acktime. We compute frame airtime and Acktime to account for different OFDM physical layer as in [START_REF] Jun | Theoretical maximum throughput of ieee 802.11 and its applications[END_REF]. Now, consider that T i-1 period state was f i-1 (frozen), then the first frame at T i period will be transmitted after a DIF S time plus the remaining time of the frozen backoff period. The probability mass function (pmf) of the remaining number of time slots of the frozen backoff counter depends on when the last eNodeB-ON transmission period has been started during the last slotted random backoff at T i-1 period. Whereas the remaining backoff counter random variable has a lower and upper limits of 0 and CW as the success case, its pmf can be different from the one of a uniform random variable. However, we approximate it as a uniform random variable. As a result, the amount of time needed for DCF protocol to successfully transmit the first frame during T i period given a s i-1 or f i-1 state for T i-1 are the same and equal to X. This approximation would have a light impact on the throughput computation since the sum between the first part of the backoff counter which occurs before the eNodeB-ON period and the second part of the backoff counter which occurs after the end of the eNodeB-ON period is a normal complete backoff. Indeed, if the eNodeB-ON period starts at the beginning of the backoff period or at the end, the next Wi-Fi frame will be transmitted exactly at the same time. More precisely, the time between the last frame sent before the eNodeB-ON period and the first frame sent after that period is DIF S + eN odeB-ON + δ * BF counter unif (0,CW ) + DIF S.

Finally, in the last case when the T i-1 period state is c i-1 (collision), the amount of time needed to successfully transmit the first frame during T i can be represented by the following uniform random variable Y :

Y = DIF S + δ * BF counter unif (0,2 * (CW +1)-1) + F rametime (2)
As for all the next frames that follow the first one, the amount of time needed to successfully transmit any one of these frames can be easily represented by the same random variable X.

In order to compute the transition probabilities, we need to determine when the last AP transmission is interrupted by the starting of the eNodeB-ON period. To do so, it is necessary to know how much Wi-Fi frames are sent during T i period. Let N be the random variable that counts the number of frames which could be transmitted during any T i period. For any given N = n, the first n -1 frames will be successfully transmitted and the n th frame could be a collision, frozen or successful frame as shown in Figure 1. According to the above analysis and equations ( 1) and ( 2), the total time needed to transmit successfully n frames during any T i period is the sum of n uniformly distributed random variables. This sum is equal to n j=1 x j if the state of the previous T i-1 period is s i-1 or f i-1 , and it is equal to y + n j=2 x j if the state of the previous T i-1 period is c i-1 . The first mentioned sum constitues an ordinary renewal process (n ≥ 0), while the second sum is a delayed renewal process because the first random variable in the sum has a different distribution. The pmf of N depends on the state of T i-1 period. However, in any case, it is clear that N is a stopping time with respect to the sequence

{x 1 , x 2 , x 3 , • • • } or {y, x 2 , x 3 , • • • }.
Consequently, the conditional probability of sending n frames during any T i period given that the state of T i-1 is s i-1 can be written as [START_REF] Ross | Introduction to probability models[END_REF]. Here, the stopping condition is n j=1 x j > T i -DIF S -δ. Explanation. This conditional probability corresponds to the number of sent frames regardless of what happens to the last sent frame before the end of the T i period. As a matter of fact, in equation ( 3), the addition of the DIF S + δ period is necessary to cover the three cases, collision, frozen and successful as shown in Figure 1. Particularly, if eNodeB-ON starts at the end of the added DIF S + δ period, then this case corresponds also to n sent frames with the last one being successful. Remind that the backoff counter is decremented at the end of the time slot δ. Hence, a full DIF S +δ period must be added. This probability can be computed exactly by using the pmf of the sum of n uniform random variables which is the n-fold convolution of individual pmfs.

Next, we determine the transition probabilities to s i , f i and c i states with n transmitted frames during T i given s i-1 state in the previous T i-1 as follows For a given T i period, N has an upper bound nmax, which means that P r{N > nmax} = 0, where nmax = T i /xmin with xmin = DIF S + F rame time . Hence, the transition probability to c i state given s i-1 state is expressed as

P r{ci | si-1} = nmax n=1 P r{ci, n | si-1} (7)
Similarly, we can compute all other transition probabilities. In particular, the conditional probability of sending n frames and the conditional transition probabilities to s i , f i and c i states with n sent frames during T i given f i-1 state in the previous T i-1 are the same as equations ( 3), ( 4), ( 5), ( 6) and [START_REF] Almeida | Enabling lte/wifi coexistence by lte blank subframe allocation[END_REF]. As for the conditional probability of sending n frames and the conditional transition probabilities to s i , f i and c i states with n sent frames during T i given c i-1 state in the previous T i-1 , they are obtained similarly except that n j=1 x j is replaced by y + n j=2 x j . Using the transition probabilities, we can deduce the probability of occurrence of each state at multiples of M, ∀i ∈

(1, • • • , M ).
+ P r{fi | si-1} * π(si-1) π(si) + π(ci) + π(fi) = 1 (8)
We remind here again that i -1 refers to M if i = 1. Finally, we can compute the probability of collision P C seen by any frame during a duty cycle period consisting of M different T i periods

P C = E[collided f

rames during duty cycle period] E[sent f rames during duty cycle period]

= M i=1 E[C in T i ] / M i=1 E[N in T i ] (9)
The numerator of ( 9) is equal to the expected value of collided frames C in T i period. As only the n th frame during T i period would face a collision, we can easily compute it as follows

E[C in Ti] = π(ci) (10)
Next, we compute the expected value of N sent frames in T i period

E[N in Ti] = E[N ] -E[F in Ti] (11)
Where E[N ] is the expected values of N sent frames regardless of what happens to the last sent frame before the end of the T i period

E[N ] = E[N | ci-1] * π(ci-1) + E[N | fi-1] * π(fi-1) + E[N | si-1] * π(si-1) (12)
Hence, the conditional expected values of N such that c i-1 , f i-1 or s i-1 are respectively

E[N | ci-1] = nmax n=1 n * P r{N = n | ci-1} (13)
E[N | fi-1] = nmax n=1 n * P r{N = n | fi-1} (14)
E[N | si-1] = nmax n=1 n * P r{N = n | si-1} (15)
Finally, E[F in T i ] is the expected value of frozen frames F in T i period which is necessary to not count it in E[N in T i ] (See Figure 1

case 2). It is calculated as follows

E[F in Ti] = π(fi) (16)
Discussion. The probability of collision in ( 9) quantifies the impact of LTE-U TDM scheme on the Wi-Fi downlink transmissions while assuming one access point AP. The collisions occur exactly at the end of each T i period. Let us consider the downlink and uplink Wi-Fi transmission with a finite number of Wi-Fi stations. Bianchi [START_REF] Bianchi | Performance analysis of the ieee 802.11 distributed coordination function[END_REF] and Altman et al. [START_REF] Kumar | New insights from a fixed point analysis of single cell ieee 802.11 wlans[END_REF] have modeled the exponential behavior of the random backoff time to tie up between the probability of collision and the probability that a station transmits in a randomly chosen time slot. They have shown the intuitive result that when the number of Wi-Fi stations increases, the probability of collision increases as well, which leads to decreasing the probability that a station transmits in a randomly chosen time slot. Consequently, the probability of having the Wi-Fi stations not transmitting at the end of each T i period is increased compared to one station. Indeed, these stations would be in a backoff period or colliding. As a result, our probability of collision on Wi-Fi transmission provides an upper bound of the impact caused by LTE-U TDM scheme on a Wi-Fi network with more than one station transmitting over the uplink. Note also that our model is extendible to take into consideration possible capture effects when Wi-Fi is able to receive correctly a frame even in case of collision [START_REF] Leentvaar | The capture effect in fm receivers[END_REF]. It can be done by reducing adequately the transition probabilities from the collision state.

B. Downlink Wi-Fi Throughput

Let Γ be the downlink saturation throughput defined as the fraction of time the channel is used for successful transmissions. We express Γ as For the expected value of successful frames S in any T i period, we can use the fact that during the T i period, the first n -1 frames are sent successfully. However, the last one is only successful with probability π(s i ). Hence,

E[S in Ti] = E[N ] -1 + π(si) (18)
Particularly, if the eNodeB-ON periods are equal to eNodeB-OFF periods so that the bandwidth is shared "equally" between LTE-U and Wi-Fi, the expression of the throughput becomes

Γ = M i=1 (E[N ] -1 + π(si)) 2 × M i=1 Ti f rames/second (19)
Equation ( 19) provides the maximum throughput that is obtained on the downlink transmissions towards the users of the Wi-Fi access point. This throughput is of course lower than the Wi-Fi bandwidth divided by 2 due to LTE impact as we shall see in the next section.

IV. MODEL VALIDATION AND RESULTS

To validate our analytical model, we have simulated the interaction between LTE-U and Wi-Fi using NS3 simulator. As this paper aims to quantify the impact of LTE-U TDM scheme on the Wi-Fi MAC DCF protocol and since 802.11a/n/ac have similar definitions of the MAC layer, we choose the implementation of IEEE 802.11a standard in the simulator. We simulate a Wi-Fi access point transmitting continuously to its users. We implement a new model to simulate eNodeB-ON and OFF periods. During eNodeB-ON periods, a signal is generated so that Wi-Fi AP detects a busy channel if it is in sensing periods, otherwise the signal causes interferences with Wi-Fi transmissions leading to collisions and the frame is lost.

TABLE I: Wi-Fi transmission parameters used in the comparison between NS3 simulations and the analytical model

Wi-Fi parameters used to obtain the numerical results for both the analytical model and the NS3 simulation are those specified by default in the IEEE 802.11a standard, as reported in Table I. We have used in the simulation runs a Wi-Fi channel with a bit rate equals to 6, 12 or 24 Mbps corresponding to different Modulation and Coding Schemes (MCS), i.e. BPSK, QPSK, 16QAM. The packet payload varies from 11 bytes to 1436 bytes. The Wi-Fi probability of collision obtained by simulation is computed by dividing the number of collided frames (i.e. retransmitted frames) over the total number of transmitted frames at the MAC layer. The simulation throughput is obtained by counting the total successfully received frames during the simulation time at the application layer. For a fixed set of parameters, we repeat the simulations 3 times. Confidence intervals are too small to be drawn on the plots. We remark that each simulation run can last for several hours especially for small packet sizes since the number of events in this case is very high.

Without losing the generality of our analysis, the LTE-U transmission duty cycle period is fixed to 10 ms corresponding to LTE frame duration with duty cycle percentage of 50% so that LTE-U leaves somewhat an "equal" share to Wi-Fi. We vary the distribution of the ON/OFF transmission periods of LTE-U inside the duty cycle. First, LTE-U transmission is activated for 5 ms then deactivated for the rest of LTE frame duration. This configuration refers to 5x0 ON/OFF pattern. Second, LTE-U transmission is activated for 3 ms at the beginning of the duty cycle, then deactivated for same amount of time before it is reactivated again for 2 ms. Consequently, the Wi-Fi AP gets two disjoint transmission opportunities in the same LTE frame to access the channel. This configuration refers to 3x2 ON/OFF pattern. Third, we consider another LTE-U transmission pattern similar to the previous one except we replace 3 ms by 4 ms, and we replace 2 ms by 1ms to get a 4x1 ON/OFF pattern.

A. Comparison With Simulation Results

Figure 3 shows that the analytical results for both the probability of collision and throughput are highly accurate with the simulation results for 6, 12 and 24 Mbps when the LTE-U transmission pattern is 5x0 ON/OFF. Especially, for 6 Mbps, the model follows exactly any abrupt fluctuation of the simulation results as shown in Figure 3b. As Wi-Fi access the channel for the half of the time with 6 Mbps, the optimal theoretical throughput experienced by Wi-Fi in case of full synchronization with LTE-U (i.e. without collision with LTE-U) is also shown in Figure 3b. Evidently, collisions degrade the throughput by a non-marginal amount.

Figure 4 relative to the 3x2 ON/OFF pattern, shows a slight difference between the analytical model and the simulation results especially for the rate of 6 Mbps. This is explained by the assumption made in the model that after a collision at the end of a T i period, the retransmitted frame at the beginning of the next T i period does not face a collision. This assumption is rarely violated for some packet sizes during the 2 ms period.

Figure 5 confirms that our analytical model is still robust even if the previous mentioned assumption is not valid. Actually, the assumption is violated for a larger number of packet sizes in case of 6 and 12 Mbps rate and the small period of 1 ms. As a result, such scenario can not be modeled by our Markovian chain whereas it still can capture globally the probability of collision and the throughput behavior. In contrast, using a rate of 24 Mbps fulfill our assumption and thus the analytical model results coincide again with the simulation results. Note that 6 Mbps is the lowest rate defined in the IEEE 802.11 standard. First of all, the impact of LTE-U on Wi-Fi performance in terms of probability of collision and downlink throughput can be observed clearly when the total number of Wi-Fi packets that can be sent during a duty cycle period is relatively small. As a matter of fact, equation [START_REF] Cavalcante | Performance evaluation of lte and wi-fi coexistence in unlicensed bands[END_REF] shows that for a large number of sent packets by Wi-Fi during a duty cycle, the numerator will be small compared to the denominator, especially that only the last Wi-Fi packet in a T i period can be lost. The average number of sent packets depends on the eNodeB-OFF length, the packet size and the Wi-Fi bit rate. For instance, the larger the bit rate, the lower the impact of LTE-U on Wi-Fi. Also, if the bit rate is small, then the impact is reduced when the packet size is small enough (Figure 3b). However, reducing the packet size does not necessarily increase the performance because a small packet size incurs more overhead.The tradeoff between a small packet size that reduces the collision probability and a large packet size that reduces the overhead becomes tricky. According to Figure 3b, if the rate of Wi-Fi is 6 Mbps, then a judicious choice of the packet size must be made to maximize the throughput. This packet size is computed easily through our proposed model. More precisely, with a small packet size, the probability of collision has a positive linear relationship over the packet size but after a specific packet size, the probability of collision shows some ripples which depends drastically on the value of each packet size. For 24 Mbps, we observe the same behavior of the probability of collision except that the ripples appear from larger packet sizes. Accordingly, the throughput curves reflect the same behavior. For 6 Mbps, throughput ripples are so much sharp that may cause loosing up to 26% of throughput compared to the maximum. In contrast, for 24 Mbps, throughput ripples are negligible. Ripples are explained by the variability of the backoff periods which is not significant if the air frame time is large. In other words, the random part in X becomes small compared to the constant part (see equation ( 1)). In this case, some periodic behavior appears where the number of Wi-Fi sent frames during the eNodeB-OFF period stays the same while increasing the frame size. As a matter of fact, interrupting the last frame in the eNodeB-OFF period at the beginning of the frame or at its end does not change the number of previous sent frames.

Globally, the above observations about the 5x0 ON/OFF pattern apply for 3x2 and 4x1 ON/OFF pattern except that values are different (Figure 6). For instance, with 6 Mbps the packet sizes that approach the optimal theoretical throughput are different for the 3x2 and 4x1 ON/OFF pattern and throughput ripples causes to loosing respectively up to 43% and 40% of throughput compared to the maximum. In contrast, for both 12 and 24 Mbps the throughput for both pattern are nearly the same.

Figure 6 shows, using our analytical model, that 5x0 ON/OFF pattern has a better performance than 3x2 and 4X1 ON/OFF pattern for both probability of collision and throughput and for all different data rates. That could be explained by the probability of collision of the 3x2 or 4X1 ON/OFF pattern is approximately doubled compared to 5x0 ON/OFF pattern for almost all packet sizes because LTE-U transmission interrupts Wi-Fi transmission twice over each duty cycle period. Consequently, 5x0 ON/OFF pattern throughput is always better than the 3x2 and 4x1 ON/OFF patterns. Nevertheless, it is intuitive that for 5X0 ON/OFF pattern, the Wi-Fi packets may have higher delays to access the channel in comparison with the 3X2 and 4X1 ON/OFF pattern. This raises the tradeoff issue between the delay and the throughput experienced by Wi-Fi.

V. CONCLUSIONS AND FUTURE WORK

This paper quantifies the impact of LTE-U on Wi-Fi downlink performance when a TDM sharing scheme is deployed by LTE. Using an efficient analytical model that captures the exact periodic behavior of LTE-U, the impact has been evaluated in terms of probability of collision between the two systems. This probability of collision represents an upper bound of the negative impact when Wi-Fi uplink and downlink transmissions are active together. Accordingly, the maximum throughput that can be achieved by Wi-Fi has been evaluated. Comparing our model results to those obtained by NS3 simulations validates both our analytical model and the new implemented model of IEEE 802.11 MAC in NS3 for the research community.

Performance analyses show that LTE-U must share the channel with Wi-Fi intelligently to reduce the negative impact on Wi-Fi due to collisions. In other words, it is not enough to share equally the channel by deploying a 50% ON/OFF duty cycle. How the channel is shared inside the duty cycle is an important factor as well. Relying on our model, we can measure exactly the performance degradation for any TDM scheme. Henceforth, it is possible to find the required compensation that makes the sharing equal, by increasing the access time available to Wi-Fi during each TDM duty cycle. Thus, LTE-U can recover adequately the disuse of the Wi-Fi CSMA/CA scheme, On the other hand, Wi-Fi can better protect itself from the negative impact of LTE-U by frame buffering and aggregation so that a suitable air frame size is used, especially with low data rates.

Currently, we are considering the case where multiple Wi-Fi access points are competing for the spectrum in presence of LTE-U. Two modeling concepts may be applied here. The first one is extending the model of Bianchi [START_REF] Bianchi | Performance analysis of the ieee 802.11 distributed coordination function[END_REF] or Altman et al. [START_REF] Kumar | New insights from a fixed point analysis of single cell ieee 802.11 wlans[END_REF]. The second is to extend our model by computing for instance the distribution of the inter-arrival time between successive Wi-Fi frames. Initial results show that, regardeless of the adopted approch, modeling Wifi network as a renewal process proposed in this paper is prerequisite to study precisly the interaction between the two systems.

Fig. 1 :

 1 Fig. 1: LTE-U eNodeB interacting with Wi-Fi Access Point

Fig. 2 :

 2 Fig. 2: Periodic Discrete Time Markov Chain modeling the three states at the end of an eNodeB-OFF period (T i ). Left: The global transition diagram showing the periodicity. Right: Detailed state transitions over time

P

  r{N = n | si-1} = P r{ n-1 j=1 xj + DIF S + δ < Ti} -P r{ n j=1 xj + DIF S + δ < Ti} (3)

P

  r{si, n | si-1} = P r{ n j=1 xj < Ti ≤ n j=1 xj + DIF S + δ} (4) P r{fi, n | si-1} = P r{

  π(si) = P r{si | ci-1} * π(ci-1) + P r{si | fi-1} * π(fi-1) + P r{si | si-1} * π(si-1) π(ci) = P r{ci | ci-1} * π(ci-1) + P r{ci | fi-1} * π(fi-1) + P r{ci | si-1} * π(si-1) π(fi) = P r{fi | ci-1} * π(ci-1) + P r{fi | fi-1} * π(fi-1)

  Γ =E[successf ul f rames during duty cycle period] duty cycle period time= M i=1 E[S in Ti]duty cycle period time f rames/second

Fig. 3 :Fig. 4 :Fig. 5 :

 345 Fig. 3: (Left To Right) The probability of collision and throughput versus different packet size for 5x0 ON/OFF pattern

Fig. 6 :

 6 Fig. 6: Comparison of the three ON/OFF patterns with different rates


Franca Giannini
email: giannini@ge.imati.cnr.it

Erika Montani

Marina Monti
email: monti@ge.imati.cnr.it

Jean-Philippe Pernot
email: jean-philippe.pernot@aix.ensam.fr

Semantic Evaluation and Deformation of Curves Based on Aesthetic Criteria

Keywords: geometric modeling, styling, aesthetic features, semantic-oriented 3D modeling

To better simulate the way designers work, specific tools are needed to handle directly specific shape features meaningful for the design intent, without focusing on the underlying mathematic representation. For this purpose it is fundamental to identify proper higher-level shape descriptors as well as the corresponding manipulation techniques. The paper presents the definition and implementation of semantic operators for curve deformation based on a shape characterization that is specific to the industrial design context. The work grounds on the innovative approach suggested by the FIORES-II project for the intent-driven modeling tools for direct shape modification and on the multi-layered architecture proposed by the Network of Excellence AIM@SHAPE for the definition of semantic-oriented 3D models. In particular the paper proposes the use of meaningful aesthetic features for the evaluation of planar curve signature and for their intent-driven direct modification.

INTRODUCTION

The definition of tools more suitable for the mentality of creative users is one of the still open critical issues in the computer-aided design of industrial products. Several results have been obtained in providing various curve and surface manipulation functionalities to obtain high quality curves and surfaces through the specification and control of the curvature [START_REF] Cripps | Quality Surface Construction[END_REF] [START_REF] Farin | Curves and Surfaces for CADCAM[END_REF]; however, as far as we know few results have been obtained in terms of intent-driven modification. In geometric modeling, the featurebased approach aims at facilitating the design activity while enabling shape-oriented manipulations directly linked to the semantics the user has in mind. A form feature is what makes different (functionally in the mechanical design, and aesthetically in the styling domain) two objects that were initially defined by the same overall geometry. While the features defined for mechanical CAD systems are mainly related to canonical geometric shapes, easy to classify and allowing a better association between shape and function, in the styling practice, being a creative process, the designer needs a certain freedom of expression that would take into account personal tastes, visual impressions, fashions, etc.; consequently, features are intended as complex high level entities that allow a faster creation and modification of the geometric model. In literature, it is possible to find several studies focusing on the user interactions with shape product through free-form features [START_REF] Pernot | Incorporating free-form features in aesthetic and engineering product design: State-of-the-art report[END_REF]; there are various meaningful proposal for classification of free-form features [START_REF] Bronsvoort | Developments in Feature Modelling[END_REF][7] [START_REF] Poldermann | Surface design based on parameterized surface features[END_REF], and several interesting works [START_REF] Pernot | Interactive operators for Free Form Features manipulation[END_REF] [START_REF] Vergeest | Parameterization of freeform features, Shape Modeling and Applications[END_REF] dealing with the shape modification by features but they are hardly taking into account aesthetic information; only few consider aspects, such as brand character or emotional feeling but are very peculiar to specific products and not generally applicable.

Defining a strict link between geometric characteristics and aesthetic features is not immediate due to the multitude of the possible shapes and to the fuzziness of the concept of aesthetics. In this context, we must understand which elements are meaningful both for the design and the style judgment: sometimes, derived features are more important for checking the aesthetic quality of the model than the constructive ones. Actually, stylists normally judge the aesthetic character of the product from the flow of certain lines that have no explicit representation in the product model, but can nevertheless be perceived, such as the lines originated by the reflection of the light on the object. Such lines are not belonging to the object model but are derived from it by calculations. Thus, they could be considered both as properties or as features of the model: on the one hand they reveal properties of the underlying surface (all surface points on the lines share the same geometric property, e.g. same angle between the normal to the surface and the light ray), on the other hand they are feature lines with their own set of properties. We regard as styling features both derived and constructive elements as long as they are connected with the aesthetic impression of the object (in contrast to engineering features, which modify the shape for functional or technical reasons). They also carry information about the technical quality (e.g. surface continuity) but mainly about the aesthetics and sometimes the emotional character of the product.

In [START_REF]FIORES-II Project, Character Preservation and Modelling in Aesthetic and Engineering Design[END_REF] authors describe a tool developed in the course of the project FIORES-II [START_REF]FIORES-II Project, Character Preservation and Modelling in Aesthetic and Engineering Design[END_REF], to allow designers both maintaining the aesthetic character during engineering optimizations and to facilitate the achievement of product shapes respecting a given image word. The association between shape and image terms relay on the concepts of styling features and aesthetic properties. These last correspond to the terms used by designers to indicate the wished shape changes (i.e., dynamic or accelerated curve), while styling features are the curves which are modified to drive the wished 3D shape changes and image words are those used by marketing people to describe the product aesthetic character. Some of the aesthetic property terms have been translated in modelling and measuring operators directly acting on the geometry to obtain the desired shape results.

The work presented in this paper is grounded on the results summarized in [START_REF]FIORES-II Project, Character Preservation and Modelling in Aesthetic and Engineering Design[END_REF] and extends and integrates these results within the approach proposed by the AIM@SHAPE network of excellence [START_REF]AIM@SHAPE (Advanced and Innovative Models And Tools for the development of Semantic-based systems for Handling, Acquiring, and Processing knowledge Embedded in multidimensional digital objects[END_REF] for the definition of multi-layered semantic oriented 3D models. The main objective is to define and implement semantic operators to deform curves, based on a shape characterization in terms of styling features: providing functionalities for the evaluation of aesthetic properties of styling features, a semantic-driven deformation directly acting on the styling features modifying their property values becomes possible. In particular, the paper focuses on the straightness aesthetic property implementation. It also illustrates the exploitation of this property for making more accurate the adopted qualitative curve description, indicated as curve signature, originally based on Leyton's shape grammar [START_REF] Leyton | A Generative Theory of Shape[END_REF]. Method for preserving the curve signature during curve modification is presented as well, aimed at guaranteeing shape tuning according to the wished property values. The paper is organized as follows: the first part of the paper describes the implementation of the toolbox for evaluating specific aesthetic properties and how the estimated measures may be used for assessing a curve signature meaningful for styling. The second part focuses on the deformation engine implemented on top of the shape characterization defined by the aesthetic properties.

A SEMANTIC MODELLING MULTI-LAYERED APPROACH FOR STYLING

In the context of a semantic-based approach for curve modelling, the AIM@SHAPE [START_REF]AIM@SHAPE (Advanced and Innovative Models And Tools for the development of Semantic-based systems for Handling, Acquiring, and Processing knowledge Embedded in multidimensional digital objects[END_REF] project proposed a conceptualization of a multi-layered architecture according to which shape models are organized at three different levels of increasing information abstraction: geometric, structural and semantic layer (see Fig. 1.)

The geometric level is the representation of the shape data, in which different types of geometric models can be used (e.g. NURBS, 3D mesh). At the structural level elements are grouped and associated to abstracting elements according to some shape or topological characteristic (e.g. curvature evolution, connected object components). At the semantic level the association between shape model parts and their associated semantics is made explicit, through annotation of shapes according to the specific application domain.

In product design, at the lower geometric layer, NURBS representation [START_REF] Piegl | The NURBS Verlag[END_REF] enables direct manipulation of the shape, through the interaction with its control points or by imposing specific constraints on the geometric parameters defining the shape.

In the higher level it is possible to exploit all the available knowledge to create semantic-driven operators which act on the curves, strictly connected to the stylist's point of view, thus allowing a much more simple and natural mode of interaction. This level therefore permits to define and manipulate the model by the use of the free-form features, and to act on them by adjusting their aesthetic properties.

The aim of the structural layer is to fill the gap between the two other layers and to be the interface for sharing information and data with the other actors of the product design activity, allowing an independence from possible different geometric construction methods and representations. For this reason, this intermediate level should be easily and automatically obtainable regardless of how the object is represented and built. The structural level is seen as a neutral environment in which the curves are classified and treated through the intrinsic information related to the curvature; to this aim, here we started from the Leyton's shape grammar [START_REF] Leyton | A Generative Theory of Shape[END_REF] that provides a classification of the curves through a name or signature, that is a sequence containing information on curvature extremes and inflection points; this structural representation can take into account the possible evolutions of the shape providing a form of possible history inside a shape. Nevertheless, the curve description based on the Leyton's grammar is not accurate enough to give a satisfactory curve classification; therefore, it is necessary to add further information for a more specific characterization of curves, like the characterization in terms of aesthetic properties, which we propose in the following.

2.1

The Leyton Grammar and Curve Signature A shape grammar is a grammar where the symbols of the alphabet and the generated strings are interpreted and visualized as geometric entities. Grammar-based design systems have the potential both to automate the design process and allow greater exploration of design alternatives. We started from a curve description based on the extension of the shape grammar defined by Leyton [START_REF] Leyton | A Generative Theory of Shape[END_REF], and the specification of a set of manipulation operators. Leyton proposed a shape process grammar based on the analysis of the curvature, aiming to characterize the shape and expressing any shape evolution in terms of six types of phase-transitions, by suggesting a rule system for deducing the past history that formed any shape. For example, the shape in Fig. 2(a). can be seen as the result of various processes inferred at a circle. The Process-Grammar relies on two structural factors in a shape: symmetry and curvature. The symmetry axis of a shape is the locus of points O i , which are the midpoints of the arc AB of a circle moved along the shape and always tangent to the shape at these two points A and B (Fig.

2(c). ).

Symmetry axes are closely related to process-histories; actually, according to Leyton, they are the directions along which processes are hypothesized as most likely to have acted. The Leyton's shape grammar is built considering only the intrinsic properties of the curvature evolution, which is independent from the geometric representation, but very important from the shape perception point of view; in particular curvature extremes and inflection points have been chosen as the basis for the symbolic curve description.

These specific points related to the curvature are referred as characteristic points and they are classified as in the following:

• M+ for a positive maximum,

• m+ for a positive minimum,

• M-for a negative maximum,

• m-for a negative minimum,

• 0 for an inflection point. With this classification, the name of a curve is defined as the sequence of its characteristic points, reading the curve from the curvilinear abscissa 0 to the end of the curve; for example, the curve in Fig. 2(a). has name "M+ m+ M+ 0 m-M-m-0 M+ m+".

Moreover, if two different curves have the same name, it is said that they belong to the same class; for example, since all the ellipses are described by the name "M+ m+ M+ m+", they are part of the same class, which also contains other types of curves. Nevertheless, the information contained in the name refers only to the curvature extrema and inflection points, and no others advices in between two characteristic points are given. Thus, two curves with the same name might appear very different from an aesthetic point of view: for example, let E1, E2 be two ellipses, having respectively major semi-axes

1 a ; 1 b and minor semi axes 2 a ; 2 b , with 1 a >> 1 b and 2 2
b a » , as shown in Fig. 3; every ellipses presents the same name M+ m+ M+ m+, but the impression when looking at them may be very different. For this reason, it might be interesting to add further elements at the name in terms of properties that would allow obtaining a more refined classification meaningful for the styling point of view.

Aesthetic Properties Evaluation

In the framework of the FIORES-II project, the characterization of shapes in terms of styling features and their property from an aesthetic and emotional point of view have been deeply analyzed. Among the various outcomes achieved, it emerged that different languages are adopted in different phases of the product design process (marketing, designers, Computer-Aided Styling). In particular, during the creation and modification of the product model, stylists express detailed directives when they work with surfacers at the definition of the 3D digital model using a limited number of terms strictly linked to shape properties: with these terms they provide instructions for the modification of the product shape (e.g. making a curve a bit more accelerated, or decreasing its tension). The terms mostly used in this phase by designers, namely the aesthetic properties, are :

• Softness/Sharpness • Hard/Crude • Lead in • Tension • Acceleration • Convexity/concavity • S-Shaped • Hollowness • Crown • Straightness/Flatness
Even if these terms cannot be considered as a complete lexicon for styling, nor do stylists use all this concepts, it has been proved that is extremely useful to exploit the knowledge that is implicitly inside these terms. Properties' characterization and measures (or more generally shape descriptors) play a key role: they are useful tools to formally characterize the property of the shape which has to be modified focusing on the possibility of translating the concepts linked with the aesthetic properties in an environment able to treat the geometrical entities from a mathematical point of view. For this reason, it is necessary to find meaningful measures for property evaluation allowing the control of the shape; actually, by monitoring these values and correspondingly acting on the associated geometric properties, it could be possible to obtain a required modification of the shape; in particular, what is interesting in the modification process is the capability of modifying the curves by increasing or decreasing these values.

In [START_REF] Podehl | Terms and Measures for Styling Properties[END_REF] and [START_REF]FIORES-II Project, Character Preservation and Modelling in Aesthetic and Engineering Design[END_REF] authors illustrate the meanings and the measures of the above listed properties and the implementation of the corresponding modification operators. In this work we have modified and implemented the measures for some of the FIORES-II aesthetic properties, namely convexity, acceleration, s-shaped and straightness, by using a quite standard library for mathematical computation (i.e. MATLAB ©), in order to allow the complete independence from any commercial CAD system. In particular in this paper we focus on the straightness property, illustrating the proposed new measure and the implemented operator.

2.2.1

Straightness measure definition and implementation In engineering straightness is referred to a straight line; in free-form modelling of styling objects true straight lines are rarely appearing, nevertheless the tendency to straight lines for surface sections and profiles is frequently looked for. Stylists define the straightness property as the capability of a curve to resemble a straight line. Therefore the straightness measure should give precise information on the deviation of the curve from the straight line. In this perspective, we find that the measure provided in the FIORES-II project is quite rough. For example it weakly considers the quantity of oscillations a curve may have, which actually can influence the perception of the curve. The emerged drawbacks suggested to refine such a measure, taking into account all those elements which seem to be meaningful to characterize the straightness of a curve. Then a new measure is proposed:

l L A C ss straightne non 2 _ × × = (2.1) where, C(u) = (x(u), y(u)) with ] 1 , 0 [ Î u is the curve in parametric form, k(u) is the curvature of C(u) du u k C ò = ] 01 [ ) (
is the integral of the absolute value of the curvature,

ò × = ] 1 , 0 [ ) ( ) ( ) ( u d u x u y A !
is the value of the area between the curve and the cord that joins the two extremes of the curve,

du u y u x L ò + = ] 1 , 0 [ 2 2 ) ( ) ( ! !
is the length of the curve and l is the length of the cord.

The factor C gives information on how much the curve deviates, in terms of curvature, from the straight line, because it has curvature equal to zero; the factor A also evaluates the deviation from the straight line, but in terms of area of deviation; the factor l L evaluates the presence of oscillations of the curve, indeed the more oscillations the curve has, the bigger is this value. The second factor l at the denominator is necessary to enable this formula to be independent by the scale; actually, if the curve is scaled with a factor n, the values of the factors change according to Tab. 1.:

scale 1 scale n C C/n A A• n 2 L L• n l L• n
Tab. 1: Scale factors for the straightness measure.

Fig. 4: Some examples of straightness evaluation.

For the measures A, L and l, this relation is trivial because they are measures of area and length; for the measure C, it can be understood by considering the formula of the curvature k(u) of a B-spline curve (written in the parametric form C(u) = (x(u), y(u)) ):

2 3 2 2 ) ) ( ) ( ( ) ( ) ( ) ( ) ( ) ( u y u x u x u y u y u x u k ! ! ! ! ! ! ! ! + - =
The first and the second derivatives are directly proportional respectively to n and n 2 , so C results inversely proportional dependent with the scale factor of the curve. The values of the non_straightness vary between 0 (corresponding to the straight line) to ∞ (there is not an upper limit for the deviation of a curve). In order to obtain an appropriate measure of the straightness, this formula is converted by applying the transformation: With this transformation an evaluation of the straightness which takes values in the interval (0,1] is achieved: the only curve with straightness 1 is the straight line, and the more is the value near to zero, the more is the curve far from the straight line.

Once defined the measure, the function straightness for its evaluation can be implemented. In Fig. 4. some examples of evaluations of the straightness measure are presented.

Regardless of the length and the kind of the curve, the user might want to focus only on the evaluation/deformation of just a segment of the curve. Therefore it is necessary to define tools able to compute the straightness value of portions of the curve: this will lead us to better control the shape of the curve.

Î u u

) the two extremes of the curve segment; the function straightness can be easily adapted at this case and the function straightness_segment has been created, just by considering the segment curve between 1 P and 2 P .

In Fig. 5. an example of the application of the function straightness_segment.

Refining the Curve Signature

We can exploit the capability of evaluating the straightness property to add further elements at the curve name to obtain a more refined classification of the curves meaningful from the aesthetic point of view. We propose to establish a vocabulary according to which the curves are classified depending on their value of the straightness. After analyzing many examples, the vocabulary of the straightness which seemed more significant was defined as (Fig. 6.): The curve signature based on the Leyton Grammar has been extended and improved by means of the evaluation of the straightness for each segment, corresponding to the portion of the curve in between two characteristic points, and the information in terms of the vocabulary defined above is added at the original name.

1
In this way, the signature for the two ellipses in Fig. 3. becomes: E1= M+S+m+SM+Sm+S and E2 = M+sm+sM+sm+s. Therefore, accordingly to the signature, the ellipses can be distinguished within the same class.

THE DEFORMATION ENGINE

The ultimate objective of this work is to create operators acting on the aesthetic properties, according to the other possible imposed requirements and/or maintaining unchanged some shape properties. For example, in our grammar-based environment, in which every curve is classified according to the information contained in its name, being able to modify a curve while preserving its connotation, which means to apply a modification only inside a class, ensures that certain shape characteristics are maintained. Moreover, to be able to act only on the aesthetic property of a specific portion of a curve, preserving G1 or G2 continuity conditions at the extremes could be very important in aesthetic design process. The mathematical definition of the straightness measure (Eqn. 2.1), as well as the other property measures, is the bridge linking the aesthetic intent of the stylist to act on specific aesthetics aspects, and the setting of appropriate tools able to modify the curve in response of the imposed requirements. This requires a geometric modelling tool able to act on the related underlying geometric characteristics, in other words, a deformation engine able to manipulate the curve under a set of local and global constraints.

Constraint-based deformation is a procedure widely used in current modern CAD systems. In [START_REF] Cheutet | Constraint Modelling for curves and surfaces in CAGD: a survey[END_REF] it is proposed a taxonomy of the constraints classically used for curve and surface modelling, and the various ways a user can express them; four semantic levels are defined according to the type of the constrained entity, which can be covered by two types of specifying constraints: strict and soft constraints.

Strict constraints have to be closely respected by the modeller during the shape creation and manipulation processes; they are commonly named geometric constraints in the literature because directly related to geometric parameters. Here, two types of constraints can be taken into account:

• global constraints if they act on the entire entity. They refer to some integral properties of the curve/surface, as for example preserving the length or a prescribed area of the curve;

• local constraints, if they are applied only to an arbitrary subset of the entity. They are used to locally control a shape, for example through a set of point constraints like position constraints, tangent and normal constraints and curvature constraints.

Moreover strict constraints can be classified in direct (if the constraints are applied on a geometric entity) and indirect (if the constraints are defined without a geometric entity as reference).

Soft constraints can be of various types and sometimes it is difficult to express them in a mathematical form. These constraints do not have to preserve a strict value during the deformation process, expressing the final aspect of a component shape or at least, the expectation to obtain a solution close to it; for example the constraint of requiring a rather smooth curve, or a sharper blending.

In our context, according to this taxonomy, the aesthetic property may be seen as soft constraints (i.e. requiring a curve a bit more straight). However, the mathematical formalization of the aesthetic measures allows such constraints to be also considered as an indirect strict constraint, either global or local, depending if it is related to the whole curve or to a portion. In addition, also direct and indirect local strict constraint can be simultaneously applied to specific points of the curve (e.g. curvature value, position and tangency constraints). The curve deformation is defined in such a way that the new elements defining the modified curve (the coordinates of the new control points) are found while the resulting curve satisfies the imposed constraints, expressed into a mathematical environment by systems of equalities or inequalities to be solved. Once the constraints are defined, one curve among all the possible ones which could satisfy the constraints has to be selected. For this reason it is necessary to add a further condition, the 'objective function' F to be minimized (generally called the minimization condition).

The straightness is a nonlinear constraint because of the nonlinearity of the straightness measure (Eqn. 2.1). In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities (constraints), over a set of unknown real variables, along with an objective function to be maximized (or minimized), where some of the constraints or the objective function are nonlinear. In our context, the constrained optimization problem can be formalized as:

Beq X Aeq = × (3.1) B X A £ × (3.2) 0 ) ( = X Ceq (3.3) 0 ) ( £ X C )) ( min( X F (3.5)
Where:

) 1 ( 2 + Î n R X
is the unknown of the problem, namely a vector containing the coordinates of the control points (n + 1 = number of the control points);

B Beq A Aeq , , ,
are respectively real matrix and vectors representing the linear equality and inequality constraints;

) 1 ( 2 + Î n q R Aeq , q R Beq Î , ) 1 ( 2 + Î n r R A and r R B Î
(q and r are respectively the number of the linear equality and inequality constraints);

w n t n R R C R R Ceq ® ® + + ) 1 ( 2 ) 1 ( 2 :
, :

are functions representing the non-linear equality and inequality constraints (t and w are respectively the number of the non-linear equality and inequality constraints);

R R F n ® + ) 1 ( 2 :
is the objective function (it gives information on the type of minimization chosen to solve the problem). Depending on the choice of the objective function, there can be defined several methods to create the deformation model. We have adopted the Force Density Method [START_REF] Pernot | Fully Free Form Deformation Features for Aesthetic and Engineering Designs[END_REF][17] to a set of bar networks coupled with the B-spline control points. It enables geometric manipulation of B-spline curves and surfaces through the modification of external forces applied to the control points. The control polygon of a B-spline curve is seen as a bar network, that is a set of nodes (the control points) linked with bars (the edges of the control polygon) having a certain stiffness, more precisely a force density, so that they can be extended. During the modification process, at every node an external force is applied to maintain the static equilibrium of this structure and then, the position of the control points is automatically updated to compensate the external forces' variation. In details, each bar can be seen as a spring with a null initial length and a stiffness q (in our model, q = 1). To preserve the static equilibrium of a bar of length l, the external force l q f × = has to be applied to the endpoints of the bar (Fig. 7.). The set of external forces applied to the initial bar network can be obtained through the static equilibrium equations at each node (Fig. 7(b).). In order to define a criterion to deform the curves according to the constraints, and select one solution among all the possible ones, an objective function to be minimised is added, which depends on the external forces. Being i f the quantity of the force on the control point P i, the objective function is defined as:

2 , 0 , ) ( final i n i initial i f f F - = å =
In this way, the solution (the control points of the modified curve) is found, under the requirement of a minimal variation of the forces, ensuring that the final curve is the closest to the initial one while satisfying the imposed constraints.

The Straightness Operator

The requirement to modify the straightness of a curve must be translated into the mathematical environment, that is defining the appropriate constraints in the optimization problem. Let where X is the vector containing the coordinates of the control points, as already said, in such a way that the control point When we want to increase the value of the straightness, the objective of the deformation is univocal: the straight line. Mathematically, this means that all the values that appear in Eqn. 2.1:

= ® + ) ( , : ) 1 ( 2 X Ceq R R Ceq n straightness S u C - )) ( (
2 _ l L A C ss straightne non × × = must tend to minimum; that is, let C(u) be the original curve, S = straightness(C(u)), then: l L A C S S S = Û = Û = ® ® ® 1 1 1 lim 0 lim 0 lim
On the contrary, if we consider a constraint that requires a value of the straightness close to zero, the problem may be ill defined, since the way to obtain such a result is not univocal. For example, the curvature at a specific point can grow significantly, increasing the value of C but without having appreciable changes in A and L, or alternatively, the curve might present an elevate number of oscillations, increasing significantly the value of L and not of A and C.

However, for the purpose of this work, decreasing the straightness can be meaningful only if the change is really minimal compared to the original value; mostly because, in aesthetic design, if a curve is required to be 'less straight', this needs to be more precisely translated into a modification of some other properties, such as convexity, acceleration or crown. Moreover, acting on these properties results from the evaluation of already existing models, and often the modifications required are very small compared to the dimension of the object.

Once the straightness operator based on the deformation engine has been created, it has been possible also combining it with position and curvature constraints in specific points of the curve. Some examples of deformed curves by imposing position and/or curvature constraints with straightness constraints are illustrated in Fig. 9.

3.1.1

Straightness deformation on a curve segment Since it is extremely useful in industrial design to have a better control of the curve shape by acting in a specific area, we have added the possibility of applying straightness operator also only to a curve portion. The function to apply straightness operator to a curve segment has been defined taking into account a mathematical property of the B-spline curves, i.e. the local modification scheme, according to which moving the control point P i , the curve C(u) changes only in the interval [u i , u i+p+1 ], where p is the degree of the B-spline curve. The basic idea is to insert in the nodal sequence the two knots corresponding to the extremes of the portion to be modified, using the Boehm's knot insertion algorithm [START_REF] Piegl | The NURBS Verlag[END_REF] in order to have the possibility to restrict the attention on those control points which don't act precisely outside the curve segment to be modified.

There are two ways to apply the developed straightness function: (i) either while fixing the two extremes of the piece with position constraints or (ii) while letting them free, accordingly with the requirements. It must be noted that the curve is modified just by fixing the control points that have no influence on the piece of the curve, but in this way some control points that can have influence out of the segment are allowed to be free. If it is required to change only the shape of the segment, all control points which have influence outside the curve segment have to be fixed; however, in this way it could be possible to have not enough control points for the modification, and then, it may be useful to reconsider a solution obtained by inserting control points inside the segment (as for the first method). Up to now, all the methods implemented for the curve deformation had not taken into account the consequence they could produce in terms of curvature and hence about the change of the name. In general, the creation of new curvature extremes and inflection points is almost frequent, and therefore the name of the curve is changed. Further constraints are required to avoid the creation of new characteristic points.

3.1.2

Control of the curve signature of a curve during the deformation As mentioned earlier, one of the objectives of this research is to be able to control the signature of a curve. To this aim the creation of new characteristic points in the straightness deformation phase have to be avoided; in particular, from the styling point of view, it is crucial to avoid the appearance of new inflection points.

The approach we adopted consists, firstly, in the imposition of a global convexity constraint, taking into account that the curvature along a convex/concave curve maintains the same sign. Therefore, in order to avoid the creation of new inflection points, the convex and the concave parts of a curve have to be maintained. To do this, a simple property of the B-spline curves was taken into account: If the polygon of a B-spline is convex, the curve will be convex. If only a defined portion of the curve has to be considered, the local polygon consists on the set of control points which have influence on this area.

In Fig. 10 the two deformations of a curve are compared, first imposing a straightness constraint in the original way and then with the new convexity constraints; as it is shown, the imposition of such constraints prevents the creation of inflection points. Note that in the example of Fig. 10. the solution is found obtaining a straight segment on the right of the curve; this should not worry: actually, imposing the constraints explained above, the optimization problem has to solve not strict inequalities and the straight line (if the straightness constraints = 1) or the straight curve segment (if straightness constraints is quite high) can be attained. With this method, it has been defined a deformation tool acting on the straightness property, while avoiding the appearance of new characteristic points.

CONCLUSIONS

The paper describes the definition and implementation of aesthetic properties suitable for design of styling products. Even if the defined measures do not discriminate univocally the curves, they satisfy the main purpose of formalizing the relationships between a change of their values and the corresponding resulting shape from an aesthetic point of view. Since the straightness property is a clear concept and widely accepted, it was considered here more into detail.

Actually, even if the here described tools act on 2D curves, they play a key role for 3D shape manipulation since they can support the qualitative modification of both structural features and details features (through the adjustment of the defining curve parameters) in 3D shape definition.

The future work concerns the implementation of the other aesthetic properties, such as tension, and sharpness, in order to allow an easier satisfaction of the designer's requirements. Finally, to achieve a more complete intent-driven design framework that better supports designer in the product shape manipulation, all these new modelling tools should be integrated in a unique feature-based modelling system, starting from the prototype developed in [START_REF] Cheutet | 3D Sketching for Aesthetic Design using Fully Free Form Deformation Features[END_REF] and defining a completely new user interface naturally adhering the stylists way of working. Moreover, since in the industrial design process it could be required to manipulate a set of consecutive curves (for example the curves constituting the profile of a car), the results should be extended to the manipulation of multiple curves; this requires an adaptation of the considered measures too. For some elements composing the measure, it could be sufficient to consider the sum of what obtained for the various curve components. In other cases, different elements should be considered, as for instance, for evaluating the straightness of several consecutive curves, the cord considered in the straightness measure is not the union of the various cords but it is the segment between the first extreme of the first curve and the last extreme of the last curve.

Fig. 1 :

 1 Fig. 1: Multi-layered semantic design approach.

Fig. 2 :

 2 Fig. 2: Symbolic description of a C2 continuous curve: a) grammatical description of a smooth curve, b) curvature plot, c) definition of the symmetry axis.

Fig. 3 :

 3 Fig. 3: Two ellipses have the same name.

Fig. 5 :

 5 Fig. 5: (a) Evaluation of the straightness of the curve segment between u=0.5 and u=0.7. (b) The evaluated curve segment in its local coordinate system.

Let

Fig. 6 :

 6 Fig. 6: Examples of straightness measure of different curves.

Fig. 7 :

 7 Fig. 7: (a) A single bar force displacement. (b) Simple scheme of external forces applied on a B-spline curve.

  then the straightness constraint is defined by the function:

Fig. 8 :

 8 Fig. 8: Examples of curves deformed with straightness constraint.

  objective function F and the straightness constraint C eq are sufficient conditions to obtain the desired curve (which satisfies the condition straightness (C(u)) = S) by solving the optimization problem. In Fig.8. some examples of deformed curves imposing straightness constraints are shown.

Fig. 9 :

 9 Fig. 9: Curve modification with position, curvature and straightness constraints.

Fig. 10 :

 10 Fig.10: Increasing straightness with one position constraint, without convexity and derivative curvature constraints (on the top) and with convexity and derivative curvature constraints (on the bottom).