Member, IEEE Cédric Gueguen
email: cedric.gueguen@irisa.fr

Member, IEEE Abderrezak Rachedi
email: rachedi@ieee.org

Fellow, IEEE Mohsen Guizani
email: mguizani@ieee.org

Gaspard Monge

Incentive Scheduler Algorithm for Cooperation and Coverage Extension in Wireless Networks

Keywords: Coverage extension, Incentive Scheduling, Cooperation, Selfish nodes, Quality of Service, Multipath fading

In this paper, we focus on the wireless coverage extension and nodes' cooperation. We propose a new protocol based on an incentive approach and a scheduling algorithm in order to reward cooperative nodes. The cost of cooperation can be prohibitively expensive in terms of QoS and energy consumption which does not motivate some nodes to cooperate. Therefore, we introduce a percentage of cooperation and QoS parameters in the scheduling algorithm called CEI in order to incite potential mobile relaying nodes to cooperate and in turn extend the wireless areas. We use the cross-layer approach in order to optimize the QoS parameters. The proposed solution does not only incite the nodes to cooperate but also enhance the QoS by increasing the average throughput and decreasing the delay. The simulation results show that the proposed solution does not only give better results than the well known scheduling algorithms like MaxSNR and WFO but also allows the cooperative mobile nodes to increase their own throughput by around 114%. The total amount of data transmitted out of the cell in order to extend the coverage can be increased by around 59% compared to the scheduling algorithm MaxSNR.

I. INTRODUCTION

The basic purpose of the coverage extension area in wireless networks is to increase the network connectivity without increasing the infrastructure. This is one of the main applications of cooperative communications in wireless networks. The coverage extension issue requires the cooperation of border mobile nodes to relay the packets of neighbouring nodes that are located outside the base-station area. For instance, the nodes located at two hops from the Access Point (AP) can access the services offered by the AP through the relayed nodes like Internet as illustrated in figure 1. Many researchers worked on strategies to find the optimal placement for the relayed nodes in order to guarantee a high Quality of Services (QoS) [START_REF] Sadek | Distributed relay-assignment protocols for coverage expansion in cooperative wireless networks[END_REF]. Other works dealt with the optimal number of hops between relayed nodes in wireless networks [START_REF] Florea | The optimal number of hops in infrastructure-based fixed relay networks[END_REF] [START_REF] Sikora | Bandwidth and power-efficient routing in linear wireless networks[END_REF]. However, they assume that the relayed nodes by definition are fixed and cooperative, which is not interesting in the case of a dynamic wireless network where the nodes freely move and may be selfish.

The mobility of relayed nodes has to be taken into account in order to be close to reality. Other works use mobile relayed nodes to extend the wireless coverage with throughput enhancement [START_REF] Xiao | Mobile relaying: Coverage extension and throughput enhancement[END_REF] [START_REF] Bakaimis | Connectivity investigation of mobile relays for the next generation wireless systems[END_REF]. However, no incentive approach is considered in the latter works. The relayed nodes must share their throughput with other neighbouring nodes that can impact their own packets' transmission. In addition, the energy consumption of the relayed nodes is more important than the one of other classical nodes. They do not only transmit their own packets but also the packets of other neighbouring nodes. Therefore, the user of potential relayed nodes can disable the cooperative functionality in order to keep the performance in terms of QoS only for its own transmission. In this paper, we consider that mobile relayed nodes are not part of the fixed wireless infrastructure. That is why the incentive strategy for potential mobile relay nodes has to be taken into account in the cooperation protocol design. The main incentive models discussed in the literature are based on game theory [START_REF] Chen | Conflicts and incentives in wireless cooperative relaying: A distributed market pricing framework[END_REF] [START_REF] Depeng | Distributed relay selection over multi-source and multi-relay wireless cooperative networks with selfish nodes[END_REF][8] [START_REF] Dapeng | A spatial game for access points placement in cognitive radio networks with multi-type service[END_REF]. However, it is hard to implement these models because of some assumptions and because no implementation or performance evaluation is given. We believe that the scheduling algorithms can tackle this problem by adapting and introducing new parameters like incentives with QoS. Moreover, the scheduling algorithms are already implemented in the Access Point and in routers thus facilitating our study.

A. Contributions

In this paper, we propose a new cooperative protocol based on an incentive approach that takes into account the QoS for mobile relayed nodes in order to extend the coverage area. This approach consists of increasing the priorities of the relayed nodes according to their cooperation rate. The idea is to reward the relayed nodes for their cooperation instead of penalizing them by increasing the cost of cooperation. Consequently, the nodes have no interest in selecting and acting selfishly, by using their throughput only to transmit their own packets. Moreover, our protocol guarantees that the nodes are free to cooperate, because they choose their percentage of cooperation. The proposed solution combines the QoS parameters and cooperation rate using the crosslayer approach with a scheduling algorithm. This solution is called Coverage Extension based on Incentive scheduling (CEI). Moreover, the physical layer information is used in order to take advantage of the time, frequency and multiuser diversity and to optimize the system capacity until it is close to the Shannon limit. Unlike some existing models, our solution can be widely implemented. In addition, we present the performance evaluation of our solution in terms of delay, throughput and relaying efficiency with different cooperation ratios of nodes. The comparison between the proposed CEI and other existing resource allocation strategies like the classical Round-Robin (RR) [START_REF] Nagle | On packet switches with infinite storage[END_REF], acknowledged MaxSNR [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF][12] and WFO [START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF] are presented and analyzed.

B. Organization

This paper is organized as follows: in Section 2, we present the existing works related to coverage extension using cooperation in wireless networks, incentive models and scheduling algorithms. Section 3 provides a detailed description of the system under study and describes the proposed coverage extension protocol based on the incentive scheduler. The fourth section presents the obtained simulation results and their analysis. Finally, Section 5 concludes the paper and presents our future works.

II. RELATED WORK

In this section, we present existing works related to coverage extension protocols, cooperation incentives models and scheduling algorithms.

A. Coverage extension Protocols

Wireless coverage extension is one application of the cooperation communications system. Many existing works deal with the coverage extension by analysing the different strategies to find the optimal placement for the relayed nodes in order to guarantee a high Quality of Services (QoS). Sadek et al. [START_REF] Sadek | Distributed relay-assignment protocols for coverage expansion in cooperative wireless networks[END_REF] proposed two distributed relay-assignment protocols in order to reduce the outage and increase the network connectivity. The first protocol selects the relayed node that is best placed while taking into account the quality of SNR and the distance between nodes. The second protocol gives the optimal placement for the fixed relayed nodes so that they help the existing users. Other works deal with the optimal number of hops between relayed nodes in multi-hop wireless networks. Florea and Yanikomeroglu [START_REF] Florea | The optimal number of hops in infrastructure-based fixed relay networks[END_REF] have shown that the optimal number of relayed nodes can be determined for multihop link under the assumption that all links have the same path loss exponent and that the relays are located at equal intervals. Only a few works propose to use the mobile relayed nodes to extend the wireless coverage and enhance the throughput. Xiao et al. [START_REF] Xiao | Mobile relaying: Coverage extension and throughput enhancement[END_REF] propose quantitative studies of benefits offered by mobile relayed nodes for a potential coverage area extension. The mobile node relays offer substantial coverage extension benefits. However, no incentive approach is considered in these works and they assume that the relayed nodes are all cooperative.

B. Cooperation Incentives Models

Two types of uncooperative nodes can be distinguished: the malicious nodes and the selfish nodes. The malicious nodes try to attack the system by choosing an uncooperative behaviour and creating a network disconnection. The goal of the selfish nodes is to maximize their benefits in terms of QoS (like throughput and delay) and to minimize their costs like the energy consumption. In this paper, we focus on the selfish behaviour of potential cooperative nodes. The cooperation is an important parameter in wireless networks, because without any packet forwarding the ad hoc network cannot exist and the wireless coverage extension is not possible.

The concept of cooperative communication (CC) technique in wireless networks was introduced in [START_REF] Nosratinia | Cooperative coomunication in wireless networks[END_REF]. In literature, two main solutions were proposed to overcome the problem of selfish nodes. The first one is based on the reputation mechanisms that consist in assessing a nodes' contribution to the network, like its forwarding and routing functionalities [START_REF] Michiardi | Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF][16] [START_REF] Buchegger | Performance analysis of the cofidant protocol[END_REF][18] [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF]. The reputation model called CONFI-DANT was proposed to share the reputation metric and alarm messages in order to detect and punish the misbehaving nodes [START_REF] Buchegger | Performance analysis of the cofidant protocol[END_REF]. Another model called CORE is proposed to implement the reputation function by using the monitoring technique. Each node computes the reputation value of its neighbour and refuses to provide any service to misbehaving nodes when their reputation is lower than a certain threshold [START_REF] Michiardi | Core: a collaborative reputation mechanism to enforce node cooperation in mobile ad hoc networks[END_REF]. However, these solutions neither overcame the problems of false observation related to collisions nor considered the performance of potential relayed nodes. In [19][20] the authors introduce the concept of cross-layer in order to reduce the false observation rate related to collisions, but no incentive model is proposed.

The second one is based on economic mechanisms like price-based and game theories [START_REF] Dapeng | Coalitional game theoretic approach for secondary spectrum access in cooperative cognitive radio networks[END_REF][9] [21] [START_REF] Xiao | Game theoretic analysis for spectrum sharing with multi-hop relaying[END_REF]. In these models nodes are paid to offer message forwarding services and also pay to receive forwarding services. These proposed incentive models based on the price and game theories have introduced the concept of virtual cash. The nodes are rewarded for packets forwarding by trading virtual cash with source and next hop nodes. Buttyan and Hubeaux [START_REF] Buttyan | Enforcing service availability in mobile ad-hoc wan[END_REF] proposed nuglets as credits to manage forwarding transactions. The source node pays relay intermediate nodes by storing a nuglet in the packet head. The intermediate nodes acquire the nuglets when forwarding the packets. In [START_REF] Li | Analysis of a hybrid reputation management system for mobile ad-hoc networks[END_REF] a hybrid model used the reputation metric and the price-based mechanism was proposed to overcome the issue of selfish nodes. However, the implementation of these solutions in resource allocation schedulers is not easy and the model assumptions must be adapted. That is why we propose a new scheduling algorithm based on QoS and the incentive parameters in order to reward cooperative mobile nodes. The scheduling algorithms are already implemented in Access Point and in routers. Their implementation can be carried out with a performance evaluation.

C. Scheduling Algorithms in Wireless Networks 1) Maximum Signal-to-Noise Ratio Scheduling: The conventional access methods like Round Robin (RR) [START_REF] Nagle | On packet switches with infinite storage[END_REF] and Random Access (RA) [START_REF] Mergen | Random scheduling medium access for wireless ad hoc networks[END_REF] are not adapted to the wireless environment and provide poor throughput. More recently intensive research efforts have been made in order to propose more efficient schedulers: opportunistic schedulers. They preferably allocate resources to active mobile(s) with the most favourable channel conditions at a given time. One major scheduling algorithm has emerged and appeared in the literature as a reference: the Maximum Signal-to-Noise Ratio (MaxSNR) [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF] [START_REF] Wang | An OFDM-TDMA/SA MAC protocol with QoS constraints for broadband wireless LANs[END_REF].

Denoting m k,n the maximum number of bits that can be transmitted on a time slot of Resource Unit (RU) n if this RU is allocated to mobile k, MaxSNR scheduling consists in allocating RU n to mobile j which has the greatest m k,n such as:

j = argmax k (m k,n ) , k = 1,..., K, (1)
with K as the number of mobiles in the access point coverage zone.

Benefiting from multiuser and frequency diversity, MaxSNR scheduling continuously allocates radio resources to the mobile that has the best spectral efficiency. Consequently, MaxSNR strongly increases the system throughput. Dynamically adapting the modulation and coding that allows one to always make the most efficient use of the radio resources and to come closer to the Shannon limit. However, MaxSNR does not take into account any other aspect than the throughput. Indeed, MaxSNR scheduling does not manage priorities in order to favour cooperative mobiles. Consequently, the cooperative mobiles have no guaranteed reward. Their supplementary energy consumption and the personal throughput loss are not compensated. These results show that cooperation means penalty, and thus they do not encourage any cooperative network or coverage extension.

2) Weighted Fair Opportunistic Scheduling: We have recently proposed a new MAC scheduler called Weighted Fair Opportunistic (WFO) for an efficient support of multimedia services in multi-user OFDM wireless networks [START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF], [START_REF] Gueguen | An efficient and fair scheduling scheme for multiuser OFDM wireless networks[END_REF]. Built in accordance with a cross-layer approach, this scheme is designed to benefit from the multi-user diversity while taking advantage of the dynamics of the multiplexed traffic. It takes into account both the transmission conditions in order to maximize global cell throughput and the higher layer constraints (such as traffic patterns, QoS constraints) in order to to ensure the same QoS level to all mobiles whatever the context.WFO dynamically favours the mobiles that go through a critical period in terms of QoS requirements, by using dynamic priorities.

The meaningful constraint regarding delay is the limitation of large values occurrences. In [START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF], we define the concept of delay outage by analogy with the concept of outage used in system coverage planning. A mobile k is considered in delay outage (in a critical period) when its packets experience a delay greater than a given threshold defined by the mobile application requirements. The Packet Delay Outage Ratio (PDOR) of mobile k (P DOR k ) represents the emergency for mobile k to be served. A mobile can be considered satisfied when, at the end of its connection, its delay constraint is met, i.e. its P DOR experienced is less than a PDOR target specific to the mobile application.

The WFO scheduling principle is to allocate a Resource Unit n to mobile j which has the greatest WFO parameter value W F O k,n with:

j = argmax k (W F O k,n ) , k = 1,..., K, (2)
where W F O k,n is equal to:

W F O k,n = m k,n × f (P DOR k ), (3)
with f a strictly increasing polynomial function defined in [START_REF] Gueguen | A fair opportunistic access scheme for multiuser OFDM wireless networks[END_REF].

With this original weighted system, WFO keeps a maximum number of flows active across time but with relatively low traffic backlogs which results in a well-balanced resource allocation. Preserving the multiuser diversity allows to continuously benefit from opportunistic scheduling and thus maximize the bandwidth usage efficiency. The results have shown that WFO better conceals the system capacity maximization, QoS support and fairness objectives than MaxSNR scheme. WFO tackles the fairness problem between mobiles that have different cooperation ratios. However, we can notice that even if the cooperative nodes benefit from the same quality as selfish nodes, they are not rewarded for their supplementary energy consumption.

In this paper, unlike the existing scheduling algorithms like MaxSNR and WFO, we introduce the an incentive approach in order to reward the cooperative nodes and to balance their energy consumption by increasing their priority in terms of ressource allocation.

III. COVERAGE EXTENSION PROTOCOL

A. Preliminaries

In this subsection, we give some definitions and the wireless network context. We focus on the coverage extension of the Wireless Local Area (WLAN) and particularly of the access point area using the allocation of radio resources while considering a cooperative behaviour. However, the proposed solution can be applied to the Mobile Ad hoc Networks (MANETs) context under one condition, that is to use the cluster-based architecture. Figure 2 illustrates an example of the radio resources allocation among nodes located in the Access point coverage area.

We consider a centralized approach based on access point in WLAN or on cluster-head in MANETs. Indeed, maximizing the system capacity is one of the most crucial issues of wireless networks and a centralized approach is needed to allow an opportunistic scheduling which provides significant system throughput gains compared to a decentralized resources allocation. The packets originating from the backhaul network are buffered in the AP which schedules the downlink transmissions. In the uplink, the mobiles signal their traffic backlog to the access point which builds the uplink resource mapping. We assume that the physical layer operates using the structure described in Fig. 3. The total available bandwidth is divided into sub-frequency bands or subcarriers. The radio resource is further divided into frames in the time domain. Each frame is itself divided into time slots of constant duration. The time slot duration is an integer multiple of the OFDM symbol duration. Moreover, the frame duration is fixed to a value much smaller than the coherence time (inverse of the Doppler spread) of the channel. With such assumptions, the transmission on each subcarrier is subject to flat fading with a channel state that can be considered static during each frame.

The elementary Resource Unit is defined as any (subcarrier, time slot) pair. Each of these RUs may be allocated to any mobile with a specific modulation order. Transmissions performed on different RUs by different mobiles have independent channel state variations [START_REF] Andrews | Providing quality of service over a shared wireless link[END_REF]. On each RU, the modulation scheme is QAM with a modulation order adapted to the channel state between the access point and the mobile to which it is allocated. This provides the flexible resource allocation framework required for an opportunistic scheduling.

The system operates using time division duplexing with five subframes: the control subframe, the cell downlink data subframe, the cell uplink data subframe, the relayed downlink data subframe and the relayed uplink data subframe. The cell uplink and downlink data subframes are used for the transmission of intra-cellular user data while the relayed uplink and downlink data subframes are used for the transmission by the relaying nodes of extra-cellular user data. During the control subframe, the access point sends control information towards its mobiles. This control information represents the scheduler decision which is constituted of three main parts: the resources mapping, the selected modulation order, and the selected emission power. In addition, during this subframe, the active mobiles send their current traffic backlog and information elements such as transmission power. This subframe is also used by the mobiles to establish their connections. This frame structure supposes a perfect time and frequency synchronization between the mobiles and the access point as described in [START_REF] De Beek | A time and frequency synchronization scheme for multiuser OFDM[END_REF]. Therefore, each frame starts with a long preamble used for synchronisation purposes. Additional preambles may also be used in the frame.

B. The Incentive Scheduler Algorithm

The main element of the proposed protocol is its scheduling algorithm called CEI. The scheduler, located in the central node like access point or cluster-head node, grants RUs to each mobile as a function of: (1) its channel state, (2) its current cooperation ratio, (3) its network confidence percentage, (4) its traffic backlog.

The channel state is supposed to be available at the receiver [START_REF] Li | Channel estimation for OFDM systems with transmitter diversity in mobile wireless channels[END_REF]. The current channel attenuation on each subcarrier and for each mobile node is estimated by the access node based on the SNR of the signal sent by each mobile during the uplink contention subframe. Assuming that the channel state is stable on a scale of 50 ms [START_REF] Truman | A measurement-based characterization of the time variation of an indoor wireless channel[END_REF], and using a frame duration of 2 ms, the mobiles shall transmit their control information alternatively on each subcarrier so that the access node may refresh the channel state information once every 25 frames. The CEI scheduling algorithm relies on weights that set the dynamic priorities to allocate the resources. These weights are built in order to satisfy two major objectives: to maximise the system throughput and to encourage the nodes cooperation.

1) System Throughput Maximization Parameter: The CEI scheduler maximizes the system throughput in a MAC/PHY opportunistic approach. Data integrity requirements of the mobiles are enforced to adapt the modulation scheme and the transmission power to the mobile specific channel state. At each scheduling period, the scheduler computes the maximum number of bits m k,n that can be transmitted in a time slot of subcarrier n if assigned to a mobile k, for all k and all n. This number of bits is limited by two main factors: the data integrity requirement and the supported modulation orders.

The bit error probability is upper bounded by the symbol error probability and the time slot duration is assumed to be equal to the duration T s of an OFDM symbol [START_REF] Wong | Multiuser OFDM with adaptive subcarrier, bit, and power allocation[END_REF]. The required received power P r (q, k) for transmitting q bits in a RU while keeping below the data integrity requirement BER target,k of the service flow of mobile k is a function of the modulation type, its order and the single-sided power spectral density of noise N 0 . For QAM and a modulation order M on a flat fading channel [START_REF] Proakis | Digital Communications[END_REF]:

P r (q, k) = 2N 0 3T s erf c -1 BER target,k 2
2 (M -1), (4)
where M = 2 q and erf c is the complementary error function. P r (q, k) may also be determined in practice based on BER history and updated according to information collected on experienced BER. The transmission power P k,n of mobile k on subcarrier n is upper bounded to a value P max which complies with the transmission Power Spectral Density regulation:

P k,n ≤ P max . (5)
Given the channel gain a k,n experienced by mobile k on subcarrier n (including path loss and Rayleigh fading):

P r (q, k) ≤ a k,n P max . (6)
Hence, the maximum number of bits q k,n of mobile k which can be transmitted on a time slot of subcarrier n while keeping below its BER target is:

q k,n ≤     log2   1 + 3P max × T s × a k,n 2N 0 erf c -1 BER target,k 2 2         . (7)
We further assume that the supported QAM modulation orders are limited so that q belongs to the set S = {0, 2, 4, . . . , q max }. Hence, the maximum number of bits m k,n that will be transmitted on a time slot of subcarrier n if this RU is allocated to the mobile k is:

m k,n = max {q ∈ S, q ≤ q k,n } . (8)
Opportunistic schedulers like MaxSNR based schemes allocate the resources to the mobiles which have the greatest m k,n values. This bandwidth allocation strategy maximizes the bandwidth usage efficiency but do not encourage the nodes cooperation. In order to extend the coverage area while preserving the system throughput maximization, a new parameter is added on m k,n which modulates this pure opportunistic resource allocation.

2) Incentive Parameter: The second major objective of the CEI is to incite nodes to participate to frame relay in order to extend the network coverage zone. This is achieved by extending the above cross-layer design to other layers. A new "Incentive Parameter" (IP k ) is introduced based on the current estimation of the cooperation ratio:

IP k = R k D k = D k + i i=0...i=K D ki D k , (9)
where R k is the global amount of data transmitted by mobile k. It is the sum between D k , the amount of data transmitted to mobile k for its own requirement and D ki , the amount of data transmitted to the mobile k for a mobile i (then these data will be relayed to mobile i by mobile k in the relaying subframe). This information could be directly monitored by the access point, or signalled by each mobile to the access point.

We also define the cooperation ratio C k as the number of packets that mobile k is ready to relay for other mobiles when it receives 100 packets for its own consumption, for example:

• when mobile k relays no traffic out of the cell, C k equals 0%;

• when it is ready to relay 50 packets out of the cell since it receives 100 packets for its own consumption, C k equals 50%; • when the mobile relays as many packets out of the cell as its own received for its own consumption, C k equals 100%.

Assuming that there are always packets to relay out of the cell, IP k will be respectively for these three cases equal to 1, 1.5 and 2. Consequently, the resource allocation on IP k allows to give higher priority to mobiles that cooperate to extend the coverage zone with frame relaying.

3) Confidence Parameter: We assume that each mobile signals its R k and D k to the access point. Thanks to this information, the CEI scheduler will make adequate resource allocation rewarding the mobile according to its cooperation degree. However in order to block malicious mobiles that could lie on this information, we introduced a last parameter called the confidence parameter. The confidence parameter T k depends on the correspondence between the announced cooperative ratio and the observed forwarding ratio. This control is carried out by a monitor node (in our case the AP or cluster-head (CH)) in order to efficiently evaluate T k . Unlike the existing monitoring mechanisms [START_REF] Rachedi | Toward a cross-layer monitoring process for mobile ad hoc networks[END_REF][20] [START_REF] Marti | Mitigating routing misebehaviour in mobile ad-hoc networks[END_REF], the proposed solution is centralized and consequently is not impacted by the false evaluation related to the collision at the monitor node. Each T k varies between 0 and 1 included. When the access point monitoring R k and D k corresponds to the announced cooperative ratio, T k is set to 1. Otherwise, when the mobile does not relay the announced amount of data for which it had previously received more priority, its T k is set to 0 for one round of scheduling in order to punish it. This ensures a deterrent threat for mobiles that would try to mislead the system.

4) Global CEI Algorithm Description:

In the allocation process of a given time slot, the priority of a mobile k for UR n is determined by the magnitude of its CEI parameter:

CEI k,n = m k,n × R k D k × T k . (10)
Based on the m k,n and IP k factor, the CEI k,n directly takes into account the channel states and the mobile behavior. Like MaxSNR, the physical layer information is used with m k,n in order to take advantage of the time, frequency and multiuser diversity and maximize the system capacity. However, contrary to existing schedulers, cooperation information as cooperation ratio C k is exploited in a weighted system with IP k parameter that introduces dynamic priorities between mobiles in order to ensure good rewards to mobiles that help extend the coverage zone. This results in an efficient scheme which guarantees a better network connectivity while avoiding tradeoff with the system capacity.

The T k parameter is an additional factor that allows to temperate CEI k,n value function of network confidence. Include T k parameter allows to be resistant to malicious nodes that would lie on their i i=0...i=K D ki . Thanks to this control parameter, no mobile malicious behavior may provide benefits in terms of network resources.

As shown in Fig. 4, the probability for a mobile to receive Resource Units depends on the magnitude of its CEI k,n and consequently highly depends on the quantity of data relayed by the mobile to other mobiles in order to contribute to the coverage extension. The higher the cooperation ratio, the higher IP k and, unlike other schedulers, the higher the probability to receive bandwidth resources and to benefit from a low delay and a high throughput is. Consequently, with CEI algorithm, mobiles are encouraged to cooperate. If they want high priority and high QoS, they must not be selfish.

The CEI scheduling algorithm is detailed in Fig. 5. The scheduling is performed subcarrier by subcarrier and on a time slot basis for an improved granularity. In the allocation process of a given time slot, the priority of a mobile is determined by the magnitude of its CEI parameter. In the following items, we describe the proposed scheduling algorithm step by step.

• Step 0: The scheduler refreshes the current m k,n and updates cooperation ratio IP k , confidence ratio T k and buffer occupancy BO k values. Then, it computes the CEI k,n parameter for each mobile and each subcarrier. Then, n and t are initialized to 1. • Step 1: For subcarrier n, the scheduler selects the mobile k that has the greatest CEI k,n value. If CEI k,n is the same for several mobiles, the scheduler chooses the mobile that has the highest BO k value.

-Sub-step 1-1: If the virtual buffer occupancy 1 of mobile k is positive, the scheduler goes to Substep 1-2. Otherwise, if all virtual buffers are null or negative, the scheduler goes to Step 2. Otherwise, the scheduler selects the next mobile k that has the greatest CEI k,n value and restarts Sub-step 1-1 (if CEI k,n is the same for several mobiles, the 1 We define the virtual buffer occupancy as the current buffer occupancy of mobile k minus the number of bits already allocated to this mobile. • Step 2: All buffers are empty or all time slots of all subcarriers are allocated and the scheduling ends.

5

) Discussion: We propose to limit IP k values to a maximum of 2 that corresponds to a cooperation ratio of 100%. Indeed, we assume that a mobile with a C k value higher than 100% could be considered irrational. Indeed, it could be a problem that a mobile relays more packets than it receives for its own consumption. We consider that it could be not profitable for it and also for the system since a mobile with a disproportionate cooperation ratio could quickly use its battery and obtain all resources in the cell and this will excessively penalize other mobiles, even those that have a good cooperation ratio.

IV. PERFORMANCE ANALYSIS

In this section we evaluate the performance of the proposed CEI scheduling and we compare it to the classical Round Robin allocation and the well known MaxSNR scheduler. We consider four kinds of nodes: the selfish nodes that do not relay any packet (C k = 0%), the nodes that relay a few packets with C k = 10%, the nodes that are more cooperative with C k = 50% and the nodes that are really network friendly with a maximum cooperative ratio of 100%. We focus on two main performance metrics: the mean packet delay and the mean throughput provided at each mobile. Performance evaluation results are obtained using OPNET discrete event simulations with the simulation parameters presented in the next subsection.

A. Simulation setup

The scenario of the simulation is illustrated in figure 6. We assume that each frame is formed by 128 subcarriers and 5 time slots. We select 128 subcarriers for each frame in order to make the proposed system compatible with IEEE 802.11n where the channel is divided into 128 subcarriers (for 40MHz transmission). The channel gain model on each subcarrier considers free space Path Loss a k and multipath Rayleigh fading α 2 k,n :

a k,n = a k × α 2 k,n . (11)
where a k is dependent on the distance between the access point and mobile k and α 2 k,n represents the flat fading experienced by mobile k on subcarrier n. α k,n is Rayleigh distributed with an expectancy equal to one [START_REF] Parsons | The Mobile Radio Propagation Channel[END_REF]. Additionally, the maximum transmission power satisfies:

10 log 10 P max T s N 0 × a ref = 31 dB (12)
and BER target is equal to 10 -3 . With this setting, the value of m k,n is 3 bits when α 2 k,n equals one. We consider that all mobiles run the same videoconference application. This demanding type of application generates a high volume of data with a high sporadicity and requires tight delay constraints which substantially complicate the task of the scheduler. Each traffic is composed of an MPEG-4 video stream [START_REF] Baey | Modeling MPEG4 video traffic based on a customization of the DBMAP[END_REF] and an AMR voice stream [START_REF] Brady | A model for generating on-off speech patterns in two-way conversation[END_REF]. The traffic load variation is carried out by increasing the mobile bit rate requirement of each mobile all together.

B. Delay impacts

First we focus on the mean mobile packet delay provided by each scheduler according to different traffic loads, paying close attention to their ability to encourage the mobile cooperation with low delay guaranteed. The obtained results are plotted in figure Fig. 7 with the mean throughput required by each mobile of the cell represented on the abscissa.

Figure 7(a) shows the case of RR with different cooperation ratios of nodes. We remark that the classical RR fails to promote cooperation activities. The RR fairly allocates the RUs to the mobiles without taking into account the effort of the cooperative mobile nodes that share their allocated resources with other nodes located out of the primary access point cell. Consequently, the more cooperative the nodes are, the less resources for their own transmission they have. Moreover, the RR does not benefit from multiuser diversity which results in a bad utilization of the bandwidth and consequently, a poor system throughput. Thus, an unacceptable packet delay is experienced even with relatively low traffic loads.

Figure 7(b) illustrates the obtained results in the case of MaxSNR with different cooperation ratios of nodes. We point out that even if a higher traffic load is supported with an acceptable packet delay, the cooperative nodes are not rewarded and their performance in terms of QoS are inferior to those of the non-cooperative nodes.

Our recent proposed scheduling algorithm, WFO, Figure 7(c) gives the beginning of a solution. It guarantees the same QoS to each mobile whatever the context (all the curves are superimposed). Consequently, cooperative mobiles are not penalized in terms of mean packet delay. The only cost to pay to help network extension by relaying frame to other mobiles is energy consumption. However, the energy consumed by the cooperative nodes must not be ignored. That's why the proposed CEI rewards the cooperative mobile nodes according to their cooperation ratio. Figure 7(d) shows the obtained results in the case of the scheduler: CEI. We remark that CEI does not only encourage the nodes to cooperate but also enhances the performance in terms of delay. When the nodes increase their cooperation ratio, the enhancement of their delay is more important. For example, the nodes with 100 % as cooperative ratio, have a delay inferior to 100ms when the mean required throughput is less than 3 × 10 5 bps which is not possible with other schedulers. The CEI dynamically and gradually adjusts the relative priorities of the mobiles in order to fairly and adequately reward them according to their relative cooperation ratio. With this approach, sparingly delaying the selfish mobiles, the CEI helps the others and whatever the traffic load, the mobile that provides the best cooperative ratio experiences the lowest packet delay. This adequately compensates the supplementary energy consumption of a network friendly behavior.

C. Buffer occupancy and PDOR impacts

The obtained results regarding the mean packet delay outage ratio (fig. 8) and the mean buffer occupancy (fig. 9) corroborate with the analysis in the previous subsection.

As expected, classical RR yields bad results. Indeed, since multiuser diversity is not exploited, the overall spectral efficiency and system throughput are low. Consequently, the delay thresholds are widely exceeded and the mobiles are dissatisfied while the buffers are quickly filled. The mobile satisfaction is directly impacted and the PDOR gives high values even with a low traffic. More generally, the higher the cooperation ratio of a mobile is, the more it will face difficulties.

MaxSNR, WFO and CEI opportunistic schedulers take into account the wireless specificities, increasing system capacity and providing better results. However, MaxSNR is highly unfair and still gives inadequate priorities, such as RR. It fully satisfies the required QoS of selfish mobiles at the expense of the satisfaction of friendly mobiles that encourage the network extension.

In contrast, WFO reduces this severe lack of fairness and each mobile benefits from the same QoS which results in the same mean buffer occupancy and the same mean PDOR. In order to compensate the supplementary energy consumption generated by each relay, the CEI rewards the mobiles according to their behavior. The higher the cooperation ratio of a mobile is, the less it will face difficulties.

D. Throughput impacts

We will now have a look at the mean mobile throughput provided by each scheduler according to the different traffic loads paying a special attention to their ability to encourage mobile cooperation with a high guaranteed throughput. The obtained results are plotted in figure 10. The first parts of these four figures, where all the curves are superimposed, correspond to an unoverloaded system. Each mobile can be served and each scheduler is able to provide the required throughput.

In the second parts of these figures, the system capacity is exceeded and the scheduler has to make a choice. With RR the system capacity goes past its limit when each source requires 200Kbps. With MaxSNR and CEI which provide an efficient spectral efficiency thanks to their opportunistic approaches, this limit is set to 250Kbps. However, with WFO, this limit is higher because the multi-user diversity is better used.

In an overloaded context, clearly, RR and MaxSNR give advantage to the selfish mobile nodes as illustrated in figures 10(a) and 10(b). Indeed, with these schedulers, each mobile of the primary access point coverage receives the same mean number of RUs. However, a mobile with a cooperation ratio of 100% only keeps the half of its allocated RUs for its own consumption while a selfish mobile with a C k of 0% keeps all its allocated RUs for its own requirements. Consequently, the friendly mobile with C k equal to 100% has a personal provided throughput half lower than the one of the selfish mobile. This result is a really disheartening situation for cooperative mobiles that are eventually penalized 2 .

Again in an overloaded context, WFO (Fig 10(c)), provides a fair management between mobiles whatever their cooperation ratio. This results in the same provided throughput for all mobiles whatever the traffic load. At last, friendly mobiles are not penalized even if they are not rewarded for their good behaviour either. Unlike these schedulers, the CEI does not deploy the same strategy while reaching the overloaded limit with the same traffic load as MaxSNR as illustrated in figure 10(d). The more network friendly a mobile is and relays packets in order to help primary access point coverage extension, the more the CEI increases its priority. Consequently, when the CEI can not serve all mobiles, it first sacrifices the selfish mobiles, then the next least friendly mobiles. The result of this new scheduling strategy is that mobiles are encouraged to cooperate to keep a high throughput.

E. Relay efficiency impacts

Figure 11 illustrates the relay efficiency in terms of the total mean throughput that each scheduling algorithm has allowed to provide out of the cell 3 . We remark that RR provides the worst performances compared to MaxSNR, WFO and CEI. MaxSNR allows to relay more packets but it is the CEI which gives the best number of provided throughputs out of the cell. In addition, we can observe that the mean provided throughput offered by MaxSNR and RR decrease when the system capacity is reached. This is due to an unfair and high penalty of the best cooperative mobile. WFO gives better performance results than RR and MaxSNR. CEI gives anyway the best performance results. The CEI, according more priority to friendly mobiles, continues to increase the total amount of forwarding throughputs until a high traffic load which corresponds to a high network extension capacity. With this new resource allocation strategy, when the mean required throughput of each mobile is equal to 500 Kbps, the total amount of data transmitted out of the cell in order to extend the coverage area can be increased around 59% compared to the well acknowledged MaxSNR and around 129% compared to the classical scheduling algorithm RR. Provided throughput function of cooperation ratio in overload system.

F. Results summarization

provided throughput according to their cooperation ratio and the total mean provided throughput out of the cell (on the right). These latter results clearly corroborate the previous results.

With RR and MaxSNR schedulings, there is no interest for a mobile to cooperate. To be friendly induces to increase its mean packet delay as illustrated in figures 7(a) and 7(b), but also to reduce its potential throughput particularly in an overloaded context (Fig. 10(a) and 10(b)). Unlike RR and MaxSNR, there is a significant interest for a mobile to cooperate with CEI. To be friendly induces to decrease its mean packet delay whatever the traffic load on the system (Fig. 7(d)) but also allows to increase its potential throughput in an overloaded context (Fig. 10(d)). Thanks to this new resource allocation strategy, mobiles are not penalized anymore when they cooperate but receive high rewards in terms of QoS which could easily compensate their cooperative energy cost. For a high traffic load of 500Kbps for each mobile, the cooperative mobiles can increase their own throughput by around 114% compared to MaxSNR and by around 209% compared to RR resource allocation strategy. Therefore, this allows a significant coverage extension which was not achieved with RR and MaxSNR strategies and free mobiles.

V. CONCLUSION

In this paper we proposed a new protocol based on an incentive approach and a scheduling algorithm in order to reward cooperative nodes and extend the wireless area coverage. This incentive approach encourages nodes to relay neighbours' frames by increasing their priority to access resources' allocation. In addition, the cross-layer approach is used in order to optimize the QoS parameters. With our proposed scheme, a mobile remains free to cooperate or not but the proposed CEI scheduler sparingly rewards participating nodes so that it is more attractive for them to actively contribute to a high network coverage. This results is a well-balanced resource allocation which allows an increase in the network coverage area while never reduces the global system throughput. These optimistic results are attributed to a combined opportunistic approaches that help the system reaches a balanced state. A minimum throughput is guaranteed to all mobiles of the cell and, thanks to its high spectral efficiency, the mean packet delay provided to the selfish mobiles by having the CEI staying close to the best RR performance. Moreover, the simulation results show that the proposed solution gives better results than the available scheduling algorithms like MaxSNR and WFO. These CEI interesting performance results show that a significant priority is given to mobiles which help the network provides a low packet delay and a high personal throughput. In future work, we plan to introduce services' differentiation in our proposed solution.

Fig. 1 .

 1 Fig. 1. Coverage extension in wireless network.

Fig. 2 .

 2 Fig. 2. Allocation of radio resources among the set of mobiles situated in the coverage zone of an access point.

Fig. 3 .

 3 Fig. 3. Frame structure in TDD mode.

Fig. 4 .

 4 Fig. 4. Allocation probabilities for mobile 1 with CEI scheduler.

Fig. 5 .

 5 Fig. 5. CEI scheduling algorithm flow chart.

Fig. 6 .

 6 Fig. 6. Simulation setup.

Fig. 7 .

 7 Fig. 7. Measured mobile mean delay with respect to their cooperation ratio.

Fig. 8 .

 8 Fig. 8. Measured mobile dissatisfaction with respect to their cooperation ratio.

Fig. 9 .

 9 Fig. 9. Measured moibile mean buffer occupancy with respect to their cooperation ratio.

Fig. 10 .

 10 Fig. 10. Measured mobile throughput with respect to their cooperation ratio.

Fig. 11 .

 11 Fig. 11. Relay efficiency.

Figure 12

 12 Figure 12 concludes these performance evaluations. We notice that for a high traffic load of 500Kbps for each mobile, the scheduler behaviour showing the mean cell mobile

Fig. 12 .

 12 Fig. 12.Provided throughput function of cooperation ratio in overload system.

The penalty is proportional to the C k magnitude. For example, when C k equals 50%, the mobile forwards 50 packets when it receives 100 packets for its own consumption. Consequently, its personal provided throughput is a third lower than the one of the selfish mobile.

The cell can be assimilated to the primary access point coverage zone, without assuming relaying.


Hichem Bannour
email: hichem.bannour@ecp.fr

Céline Hudelot
email: celine.hudelot@ecp.fr

Building Semantic Hierarchies Faithful to Image Semantics

This paper proposes a new image-semantic measure, named "Semantico-Visual Relatedness of Concepts" (SVRC ), to estimate the semantic similarity between concepts. The proposed measure incorporates visual, conceptual and contextual information to provide a measure which is more meaningful and more representative of image semantics. We also propose a new methodology to automatically build a semantic hierarchy suitable for the purpose of image annotation and/or classification. The building is based on the previously proposed measure SVRC and on a new heuristic, named TRUST-ME, to connect concepts with higher relatedness till the building of the final hierarchy. The built hierarchy explicitly encodes a general to specific concepts relationship and therefore provides a semantic structure to concepts which facilitates the semantic interpretation of images. Our experiments showed that the use of the constructed semantic hierarchies as a hierarchical classification framework provides a better image annotation.

Introduction

Achieving high level semantic interpretation of images is necessary to match user expectations in image retrieval systems. Effective tools are then required to allow a precise semantic description of images and allow at the same time a good interpretation of them. A wide number of approaches have been proposed for automatic image annotation, i.e. the textual description of images, to address the well-known semantic gap [START_REF] Smeulders | Content-based image retrieval at the end of the early years[END_REF] problem. However in most of the proposed approaches the semantics is often limited to its perceptual manifestation, i.e. by the learning of high-level concepts from low-level features [START_REF] Barnard | Matching words and pictures[END_REF][START_REF] Lavrenko | A model for learning the semantics of pictures[END_REF]. These approaches adequately describe the visual content of images but are unable to extract image semantics as humans can do. They are also faced with the scalability problem when dealing with broad content image databases [START_REF] Liu | A survey of content-based image retrieval with high-level semantics[END_REF]. The obtained performance varies significantly according to the concept number and the targeted data sets as well [START_REF] Hauptmann | How many high-level concepts will fill the semantic gap in news video retrieval?[END_REF]. This variability may be explained by the huge intra-concept variability and wide inter-concept similarities on their visual properties that often lead to uncertain annotations and even contradictory. Thus, it is clear there is a lack of coincidence between the high-level semantic concepts and the low-level features, and that semantics is not always correlated with visual appearance. Therefore, the only use of machine learning seems to be insufficient to solve the problem of image annotation.

A new trend to overcome the aforementioned problems is to use semantic hierarchies [START_REF] Bannour | Towards ontologies for image interpretation and annotation[END_REF]. Indeed, the use of explicit knowledge such as semantic hierarchies can help reduce, or even remove this uncertainty by supplying formal frameworks to argue about the coherence of extracted information from images. Semantic hierarchies have shown to be very useful to narrow the semantic gap [START_REF] Deng | What does classifying more than 10,000 image categories tell us?[END_REF]. Three types of hierarchies have been recently explored for image annotation and classification: 1) language-based hierarchies: based on textual information (ex. tags, surrounding context, WordNet, Wikipedia, etc.) [START_REF] Marszalek | Semantic hierarchies for visual object recognition[END_REF][START_REF] Wei | Ontology-enriched semantic space for video search[END_REF][START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF], 2) visual hierarchies: based on low-level image features [START_REF] Sivic | Unsupervised discovery of visual object class hierarchies[END_REF][START_REF] Bart | Unsupervised learning of visual taxonomies[END_REF][START_REF] Yao | I2t: Image parsing to text description[END_REF], 3) semantic hierarchies: based on both textual and visual features [START_REF] Li | Building and using a semantivisual image hierarchy[END_REF][START_REF] Fan | Hierarchical classification for automatic image annotation[END_REF][START_REF] Wu | Flickr distance[END_REF]. Although the two first approaches have received more attention, they showed a limited success in their general usage. Indeed, conceptual semantics is often not correlated with perceptual semantics, and is then insufficient to build a good hierarchy for image annotation. Whereas perceptual semantics cannot lead by itself to have a meaningful semantic hierarchy, as it is hard to interpret in higher levels of abstraction. Therefore, it seems mandatory to combine the both component of image semantics in order to build a semantic hierarchy faithful to image application purposes. The use of semantic hierarchies is then more convenient as they consider both, perceptual and conceptual semantics.

The rest of this paper is structured as follows: Section 2 reviews some related work. Section 3 introduces our proposal to build suitable semantic hierarchies for image annotation. Section 4 reports our experimental results on Pascal VOC dataset. The paper is concluded in Section 5.

Related Work

Several methods [START_REF] Li | Building and using a semantivisual image hierarchy[END_REF][START_REF] Fan | Hierarchical classification for automatic image annotation[END_REF][START_REF] Marszalek | Semantic hierarchies for visual object recognition[END_REF][START_REF] Wei | Ontology-enriched semantic space for video search[END_REF][START_REF] Sivic | Unsupervised discovery of visual object class hierarchies[END_REF][START_REF] Bart | Unsupervised learning of visual taxonomies[END_REF] have been proposed to build semantic hierarchies dedicated to image annotation. A semantic hierarchy classifier based on WordNet is proposed in [START_REF] Marszalek | Semantic hierarchies for visual object recognition[END_REF]. Their hierarchy is built by extracting the relevant subgraph of WordNet that may link all concepts. ImageNet is proposed in [START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF], which is a large-scale ontology of images built upon the backbone of WordNet. LSCOM [START_REF] Naphade | Large-scale concept ontology for multimedia[END_REF] aims to design a taxonomy with a coverage of around 1000 concepts for broadcast news video retrieval. An Ontology-enriched Semantic Space (OSS) was built in [START_REF] Wei | Ontology-enriched semantic space for video search[END_REF] to ensure globally consistent comparison of semantic similarities. The above approaches can be qualified as language-based hierarchies, as those hierarchies are built upon textual information. While these hierarchies are useful to provide a meaningful structure (organization) for concepts, they ignore visual information which is an important part of image semantics.

Other approaches are based on visual information [START_REF] Sivic | Unsupervised discovery of visual object class hierarchies[END_REF][START_REF] Bart | Unsupervised learning of visual taxonomies[END_REF][START_REF] Yao | I2t: Image parsing to text description[END_REF]. An image parsing to text description (I2T) framework is proposed in [START_REF] Yao | I2t: Image parsing to text description[END_REF], which generates text descriptions for images and videos. I2T is mainly based on an And-or Graph for visual knowledge representation. Sivic & al. propose to group visual objects using a multi-layer hierarchy tree that is based on common visual elements [START_REF] Sivic | Unsupervised discovery of visual object class hierarchies[END_REF]. Bart & al. proposed a Bayesian method to organize a collection of images into a tree shaped hierarchy [START_REF] Bart | Unsupervised learning of visual taxonomies[END_REF]. A method to automatically build classification taxonomy in order to increase classification rapidity is proposed in [START_REF] Griffin | Learning and using taxonomies for fast visual categorization[END_REF]. These hierarchies serve to provide a visual taxonomy, and a major problem with them is how they can be interpreted in higher levels of abstraction. Therefore, building meaningful semantic hierarchies should be done upon both semantic and visual information.

Among approaches for building semantic hierarchies, Li & al. [START_REF] Li | Building and using a semantivisual image hierarchy[END_REF] proposed a method based on visual features and tags to automatically build the "semantivisual" image hierarchy. A Semantic hierarchy based on contextual and visual similarity is proposed in [START_REF] Fan | Hierarchical classification for automatic image annotation[END_REF]. Fan & al. [10] proposed an algorithm to integrate the visual similarity contexts between the images and the semantic similarity contexts between their tags for topic network generation. Flickr distance is proposed in [START_REF] Wu | Flickr distance[END_REF], which is a novel measurement of the relationship between semantic concepts in visual domain. A visual concept network (VCNet) based on Flickr distance is also proposed [START_REF] Wu | Flickr distance[END_REF]. Semantic hierarchies have great potential to improve image annotation, particularly through their explicit representation of concepts relationships that may help to understand image semantics.

Discussion

Many approaches for hierarchical image annotation use WordNet as a hierarchy of concepts [START_REF] Marszalek | Semantic hierarchies for visual object recognition[END_REF][START_REF] Deng | Imagenet: A large-scale hierarchical image database[END_REF]. However, WordNet is not very appropriate to model image semantics. Concepts organization in WordNet follows a psycholinguistic structure, which may be useful for reasoning about concepts and understand their meaning, but is limited and inefficient to reason about image context or its content. Indeed, distances between related concepts in WordNet do not necessarily reflect an appropriate semantic measure for reasoning about images, i.e. distances between concepts is not proportional to their semantic relatedness with respect to image domain. For example, according to the shortest path in WordNet the semantic relatedness of "shark" and "whale" is 11 (nodes), and of "man" and "whale" is 7. This is meant that concept "whale" is closer to "human" than to "shark". This is coherent from a biological point of view because "whale" and "human" are mammal while "shark" is not. However, in image domain it is more accurate to have higher similarity between "shark" and "whale" as they live in the same environment, share many visual features, and it is more common that they co-appear in a photo, unlike with humans. Then, an appropriate semantic hierarchy should represent this information or allow it to be deducted to help understand image semantics.

Building of the Hierarchy

Based on the previous discussion, we define the following assumptions underlying our approach: A suitable semantic hierarchy for image annotation should: 1) model images context (as defined in the previous section), 2) allow grouping visually similar concepts in order to obtain better performance of classifiers, 3) reflect image semantics, i.e. the organization of concepts into the hierarchy and their semantic relatedness reflect image semantics.

Following the above assumptions, we propose in this paper a new method for building appropriate semantic hierarchies to images annotation. Our approach is based on a new measure to estimate the semantic relatedness between concepts, which is more faithful to image semantics since it is based on its different modalities. This measure, named SVRC, is based on 1) a visual similarity which represents the visual correspondence between concepts, 2) a conceptual similarity which defines a relatedness measure between target concepts, based on concepts definition in WordNet, and 3) a contextual similarity which measures the distributional similarity between each pair of concepts (cf. Fig. 1). SVRC is then used in TRUST-ME, a set of heuristic rules that allow deciding the likelihood of the semantic relatedness between concepts, and help building the hierarchy.

Given a set of pairs image/annotation, where each annotation describes a set of concepts associated with an image, our approach allows to automatically build a semantic hierarchy suitable for image annotation. Formally, we consider

I =< i 1 , i 2 , • • • , i L > all images of a considered database, and C =< c 1 , c 2 , • • • , c N >
the annotation vocabulary of these images, i.e. the set of concepts associated with these images. The approach we propose consists in identifying M new concepts that link all the concepts of C in a hierarchical structure that best represents image semantics.

Visual Similarity

Let x v i be any visual representation of an image i (a visual features vector), we learn for each concept c j a classifier that can associate this concept with its visual features. For this, we use N binary Support Vector Machines (SVM) [START_REF] Cortes | Support-vector networks[END_REF] (one-versus-all) with a decision function G(x v ):

G(x v ) = k α k y k K(x v k , x v ) + b (1)
where K(x v i , x v ) is the value of a kernel function for the training sample x v i and the test sample x v , y i ∈ {1, -1} the class label of x v i , α i the learned weight of the training sample x v i , and b is a learned threshold parameter. Notice that the training samples x v i with weight α i > 0 are the support vectors. After several tests on the training sample, we decided to use a radial basis function kernel:

K(x, y) = exp x -y 2 σ 2 (2)
Now, given these N trained SVMs where inputs are images visual features and outputs are concepts (image classes), we want to define a centroid ϑ(c i ) for each concept class c i that best represent it. These centroids should then minimize the sum of squares within each set S i :

argmin S N i=1 x v j ∈Si x v j -µ i 2 (3)
where S i is the set of support vectors of class c i , S = {S 1 , S 2 , • • • , S N }, and µ i is the mean of points in S i .

The objective being to estimate a distance between these classes in order to assess their visual similarities, we compute the centroid ϑ(c i ) of each visual concept c i using:

ϑ(c i ) = 1 |S i | xj ∈Si x v j (4)
The visual similarity between two concepts c i and c j , is then inversely proportional to the distance between their visual features ϑ(c i ) and ϑ(c j ):

ϕ(c i , c j ) = 1 1 + d(ϑ(c i ), ϑ(c j )) (5)
where d(ϑ(c i ), ϑ(c j )) is the Euclidean distance between ϑ(c i ) and ϑ(c j ).

Conceptual Similarity

Conceptual similarity reflects the semantic relatedness between two concepts from a linguistic and a taxonomic point of view. Several conceptual similarity measures have been proposed [START_REF] Budanitsky | Evaluating wordnet-based measures of lexical semantic relatedness[END_REF][START_REF] Resnik | Using information content to evaluate semantic similarity in a taxonomy[END_REF][START_REF] Banerjee | Extended gloss overlaps as a measure of semantic relatedness[END_REF]. Most of them are based on a lexical resource, such as WordNet [START_REF] Fellbaum | WordNet: An Electronic Lexical Database[END_REF]. A first family of approaches is based on the structure of this external resource (often used as a semantic network or a directed graph), and the similarity between concepts is computed according to the distances of the paths connecting them in this structure [START_REF] Budanitsky | Evaluating wordnet-based measures of lexical semantic relatedness[END_REF]. However, as aforementioned, the structure of these resources does not necessarily reflect image semantics, and therefore such measures does not seem suited to our problem. An alternative approach to measure the semantic relatedness between concepts is to use their provided definition. In the WordNet case, these definitions are known as the glosses and are provided by the synsets associated to each concept. For example, Banerjee and Pedersen [START_REF] Banerjee | Extended gloss overlaps as a measure of semantic relatedness[END_REF] proposed a measure of semantic relatedness between concepts that is based on the number of shared words (overlaps) in their definitions (glosses).

In this work we used the gloss vector relatedness measure proposed by [START_REF] Patwardhan | Using wordnet-based context vectors to estimate the semantic relatedness of concepts[END_REF], in which they suggest to exploit "second order" co-occurrence vector of glosses rather than matching words that co-occur in it. Specifically, in a first step a word space of size P is built by taking all the significant words used to define all synsets of WordNet. Thereby, each concept c i is represented by a context vector -→ w ci of size P, where each n th element of this vector represents the number of occurrences of n th word in the word space in the gloss of c i . The semantic relatedness of two concept c i and c j is therefore measured using the cosine similarity between -→ w ci and -→ w cj :

η(c i , c j ) = - → w ci • - → w cj | - → w ci || - → w cj | (6)
Some concepts definitions in WordNet are very concise and thus make the measure unreliable. Consequently, [START_REF] Patwardhan | Using wordnet-based context vectors to estimate the semantic relatedness of concepts[END_REF] proposed extending the glosses of concepts with the glosses of adjacent concepts (located in their immediate neighborhood). Hence, for each concept c i the set Ψ ci is defined as all the adjacent glosses connected to c i (Ψ ci ={gloss(c i ), gloss(hyponyms(c i )), gloss(meronyms(c i )), etc.}). Then each element x (gloss) of Ψ ci is represented by -→ w x as explained above. The similarity measure between two concepts c i and c j is then defined as the sum of the individual cosines of the corresponding gloss vectors:

θ(c i , c j ) = 1 |Ψ ci | x∈Ψc i ,y∈Ψc j - → w x • - → w y | - → w x || - → w y | , where|Ψ ci | = |Ψ cj |. (7)
Finally, each concept in WordNet may match several senses (synsets) that differ from each other in their position in the hierarchy and their definition. A disambiguation step is then necessary to identify the good synset. For example, the similarity between "Mouse" (Animal) and "Keyboard" (device) differs widely from the one of "Mouse" (device) and "Keyboard" (device). Therefore, we first compute the conceptual similarity between the different senses (synset) of c i and c j . The maximum value of similarity is then used to identify the most likely meaning of these two concepts, i.e. disambiguate c i and c j . Thus, the conceptual similarity is calculated as following:

π(c i , c j ) = argmax δi∈s(ci),δj ∈s(cj ) θ(δ i , δ j ) (8)
where s(c x ) is "all synsets that can be associated to the meanings of c x ".

Contextual Similarity

It is intuitively clear that if two concepts are similar or related, it is likely that their role in the world will be similar, and thus their context of occurrence will be equivalent (i.e. they tend to occur in similar contexts, for some definition of context). The information related to the context of appearance of concepts, called contextual, is used to connect concepts that often appear together in images although semantically distant from the taxonomic point of view. Moreover, this contextual information can also help to infer higher-level knowledge from images. For example, if a photo contains "Sea" and "Sand", it is likely that the scene depicted in this photo is the one of beach. It is therefore important to measure the contextual similarity between concepts. However, unlike the visual and the conceptual similarity, this one is a "corpus-dependent" measure, and more precisely depends on the distribution of concepts in the corpus.

In our approach, we define the contextual similarity between two concepts c i and c j as the Pointwise Mutual Information (PMI) ρ(c i , c j ):

ρ(c i , c j ) = log P (c i , c j ) P (c i )P (c j ) (9)
where: P (c i ) is the probability of occurrence of c i , and P (c i , c j ) is the joint probability of c i and c j . These probabilities are estimated by computing the frequency of occurrence and cooccurrence of concepts c i and c j in the database.

Given N the total number of concepts in the database, L the total number of images, n i the number of images annotated by c i (occurrence frequency of c i ) and n ij the number of images co-annotated by c i et c j , the above probabilities can be estimated by:

P (c i ) = ni L , P (c i , c j ) = nij L . ⇒ ρ(c i , c j ) = log L * n ij n i * n j (10)
ρ(c i , c j ) quantifies the amount of information shared between the two concepts c i and c j . Thus, if c i and c j are independent concepts, then P (c i , c j ) = P (c i ) • P (c j ) and therefore ρ(c i , c j ) = log 1 = 0. ρ(c i , c j ) can be negative if si c i et c j are negatively correlated. Otherwise ρ(c i , c j ) > 0 and quantifies the degree of dependence between these two concepts. In this work, we only want to measure the positive dependence between concepts and therefore we set negative values of ρ(c i , c j ) to 0. Finally, to normalize the contextual similarity between two concepts c i and c j into [0,1], we compute it in our approach by:

γ(c i , c j ) = ρ(c i , c j ) -log[max(P (c i ), P (c j ))] (11)

Semantico-Visual Relatedness of Concepts (SVRC )

For two given concepts c i and c j , their similarity measures: visual ϕ(c i , c j ), conceptual π(c i , c j ) and contextual γ(c i , c j ) are first normalized into the same interval using the Min-Max Normalization. Then, the Semantico-Visual Relatedness φ(c i , c j ) of these concepts c i and c j is defined as:

φ(c i , c j ) = ω 1 • ϕ(c i , c j ) + ω 2 • π(c i , c j ) + ω 3 • γ(c i , c j ) , 3 i=1 ω i = 1 ( 12
)
The choice of weights ω i is very important. According to the target application, some would prefer to build a domain-specific hierarchy (that best represents a specific-domain or corpus), and can therefore assign a higher weight to the contextual similarity (ω 3 ր). Others would be conducted to build a generic hierarchy, and will therefore assign a higher weight to the conceptual similarity (ω 2 ր). However if the purpose of the hierarchy is rather to build a hierarchical framework to image classification, it may be advantageous to assign a higher weight to the visual similarity (ω 1 ր).

Heuristic Rules for Hierarchy Building

Once we have estimated the semantic relatedness between each pair of concepts, it is important to regroup them in a more comprehensive hierarchy despite the uncertainty introduced by semantic similarity measurements. In the following we propose a heuristic named TRUST-ME, that allows to infer Hypernym relationships between concepts, and to bring together these various concepts in a hierarchical structure.

Let us define the following functions to understand the reasoning rules we used for the building of our hierarchy:

-Closest(c i ) returns the closest concept to c i according to the SVRC measure:

Closest(c i ) = argmax c k ∈C\{ci} φ(c i , c k ) (13)
-LCS(c i , c j ) allows to find the Least Common Subsumer of c i and c j in Word-Net:

LCS(c i , c j ) = argmin c l ∈{H(ci)∩H(cj )} len(c l , root) (14)
where H(c i ) allows to find all of hypernyms of c i in WordNet, root is the root node of WordNet and len(c x , root) returns the length of the shortest path in WordNet between c x and root. -Hits 3 (c i ) returns the 3 closest concepts to c i within the meaning of Closest(c i ).

Basically TRUST-ME consists of three rules which are based on the SVRC measure and on reasoning about the Least Common Subsumer (LCS) to select concepts to be connected to each other. These rules are illustrated and executed in the order described in Fig. 2. First rule checks whether a concept c i is classified as the closest relative to more than one concept ((Closest(c j ) = c i ), ∀j ∈ {1, 2, • • • }). If so and if these concepts {c j } are reciprocal in Hits 3 (c i ), then according to their LCS they will be connected either directly to their LCS or in a tow level structure as illustrated in Fig. 2(a). In the second, if (Closest(c i ) = c j ) and (Closest(c j ) = c i ) (can also be written as Closest(Closest(c i )) = c i ) then c i and c j are actually related and are connected to their LCS. The third rule covers the case when (Closest(c i ) = c j ) and (Closest(c j ) = c k ) -cf. Fig. 2(b).

The building of the hierarchy is bottom-up (starts from leaf concepts) and uses an iterative algorithm until it reaches the root node. Given a set of tags associated with images in a dataset, our method compute the SVRC φ(c i , c j ) between all pairs of concepts, then links most related concepts to each other while respecting the defined rules in TRUST-ME. Thus, we obtain a new set of concepts in a higher level resulted by the linked concepts in the lower level. We iterate the process until all concepts are linked to a root node. Fig. 3 illustrates the built hierarchy on Pascal VOC dataset.

Experimental Result

As part of this work, we evaluate our semantic hierarchy by comparing the performance of a flat image classification versus a hierarchical based one. Pascal VOC'2010 dataset (11 321 images, 20 concepts) is used for building the hierarchy and evaluating the classification.

Visual Representation of Images

To compute the visual similarity of concepts, we used in our approach the Bag-of-Features (BoF) model, also known as bag-of-visual words. The used BoF model is built as following: feature detection using Lowe's DoG Detector [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], feature description using SIFT descriptor [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF] and codebook generation. The generated codebook is a set of features assumed to be representative of all images features. Given the collection of detected patches from the training images of all categories, we generate a codebook of size D = 1000 by performing k-means algorithm. Thus, each patch in an image is mapped to the most similar visual word in the codebook through a KD-Tree. Each image is then represented by a histogram of D visual words, where each bin in the histogram correspond to the occurrence number of a visual word in that image.

Weighting

As this paper aims to build a hierarchy suitable for image classification/annotation, we set the weighting factors in an experimental way as follows: ω 1 = 0.4, ω 2 = 0.3, and ω 3 = 0.3. Our experimentations on the impact of weights (ω i ) showed also that the visual similarity is more representative of concepts similarity, as it will be illustrated with the produced hierarchies in Fig. 3.

Evaluation

To evaluate our approach, we used 50% of VOC images for learning concepts and the others for testing. Each image may belong to one or more of the 20 existing classes. For the flat classification we used N SVM one-against-all, where the inputs are the BoF images representations and outputs are the desired SVM responses for each image (1 or -1) -for details cf. Section 3.1. However Pascal VOC dataset is unbalanced, i.e. many concepts are represented by few hundred of images among the 11321 images in the database (much more negative data than the positive ones for many concepts). To overcome this problem we used cross-validation, taking at each fold as many positive as negative images. Hierarchical classification is made by training a set of (N +M) hierarchical classifiers consistent with the structure of the hierarchy in Fig. concept) as positive and all images of children nodes of its immediate ancestor as negative. For example, to train a classifier for "Carnivore" all images of "Dog" and "Cat" are taken as positive while images of "Bird", "Sheep", "Horse" and "Cow" as negative. Thus, each classifier is trained to distinguish one class from others in the same category. For testing the hierarchical classification, a given image can take one (or more) path in the hierarchy based on classifiers responses, and starting from the root node until reaching a leaf node. Results are evaluated with the recall/precision curves and the average precision score. Fig. 4 compares the performance of our semantic hierarchic classifier with the performance of a flat classification. Our approach performs a better classification than the flat one, with a mean improvement of +8.4%. Using half of the training images from the VOC challenge (we have used the validation set for testing) and including the images marked as difficult, hierarchical classification achieves an average precision of 28.2% when the flat one achieves 19.8%. Fig. 5 shows the recall/precision curves for concepts "Person" and "Tv_Monitor" using hierarchical and flat classification. This comparison shows that hierarchical classification has the best performance at all levels of recall.

Conclusion

This paper proposes a new approach to automatically build a suitable semantic hierarchy for image annotation. Our approach is based on a new measure of semantic relatedness, called SVRC, that takes into account the visual similarity, the conceptual and the contextual ones. SVRC allows estimating the semanticovisual relatedness of concepts. A new heuristic, TRUST-ME, is also proposed for reasoning about concepts relatedness, and to link together concepts that are semantically related in a semantic hierarchy. Our experiments showed that the built semantic hierarchy improves significantly the classification performance on Pascal VOC dataset. Our future research will concern the evaluation of our approach on larger datasets (MirFlicker and ImageNet), and the assessment of our hierarchy in terms of structure and contribution of knowledge.

Fig. 1 .

 1 Fig. 1. The SVRC is based on visual, conceptual and contextual similarities.

  c i ,c j )=H(LCS(c j , c k )) then if LCS(c i ,c j ) = LCS(c j , c k ) then if c j , c k 誠 Hits 3 (c i ) then Build Build (a) 1 st Rule.

  c i ,c j )= H(LCS(c j , c k )) then if LCS(c i ,c j ) = LCS(c j , c k ) then if (c i 誠 Hits 3 (c j )) AND (c j 誠 Hits 3 (c k )) then Build Build (b) 3 rd Rule.

Fig. 2 .

 2 Fig. 2. Rules in TRUST-Me allowing to infer the relationship between the different concepts. Preconditions (in red) and actions (in black).

Fig. 3 .Fig. 4 .

 34 Fig.3. The semantic hierarchy built on Pascal VOC'2010 dataset. Green nodes are original concepts, and the red one is the root of the produced hierarchy.

Fig. 5 .

 5 Fig. 5. Precision/recall curves for hierarchical (green) and flat (in red) classification on concepts "Person" and "TV_Monitor".

  [START_REF] Barnard | Matching words and pictures[END_REF]. M is the number of new concepts created during the building of the hierarchy. For training the classifier of each concept in the hierarchy, we took all images of children nodes (of a given

								Photo
					Abstraction			Organism
		Instrumentality		Whole		Conveyance		Person		Vertebrate
	Bottle	Tv_monitor	Pot_plant	Furniture	Train	Bus	Craft	Vehicle	Wheeled_vehicle	Bird	Carnivore	Bovid
			Sofa	Dining_table	Chair	Boat	Aeroplane	Car	Bicycle	Motorbike	Cat	Dog	Sheep	Horse	Cow


Romain Boulet
email: boulet@univ-tlse2.fr

Disjoint unions of complete graphs characterized by their Laplacian spectrum *

Keywords: Graphs, Laplacian, complete graphs, graphs determined by its spectrum, strongly regular graphs AMS subject classifications: 05C50, 68R10

A disjoint union of complete graphs is in general not determined by its Laplacian spectrum. We show in this paper that if we only consider the family of graphs without isolated vertex then a disjoint union of complete graphs is determined by its Laplacian spectrum within this family. Moreover we show that the disjoint union of two complete graphs with a and b vertices, a b > 5 3 and b > 1 is determined by its Laplacian spectrum. A counter-example is given when a b = 5 3 .

Introduction and basic results

The Laplacian of a graph G is the matrix L defined by L = D -A where D is the diagonal matrix of the degrees of G and A is the adjacency matrix of G. The Laplacian spectrum gives some informations about the structure of the graph but determining graphs characterized by their Laplacian spectrum remains a difficult problem [START_REF] Van Dam | Which graphs are determined by their spectrum? Linear Algebra and its Applications[END_REF].

In this paper we focus on the disjoint union of complete graphs. A complete graph on n vertices is denoted by K n and the disjoint union of the graphs G and G ′ is denoted by G ∪ G ′ . The Laplacian spectrum of K k1 ∪ K k2 ∪ ... ∪ K kn is {k

(k1-1) 1 , k (k2-1) 2
, ..., k (k1-1) n , 0 (n) } but in general the converse is not true: a disjoint union of complete graphs is not in general determined by its Laplacian spectrum. For instance [START_REF] Van Dam | Which graphs are determined by their spectrum? Linear Algebra and its Applications[END_REF] the disjoint union of the Petersen graph with 5 isolated vertices is L-cospectral with the disjoint union of the complete graph with five vertices and five complete graphs with two vertices, these graphs are depicted in figure 1.

In this paper we show in Section 2 that the disjoint union of complete graphs without isolated vertex is determined by its Laplacian spectrum in the family of graphs without isolated vertex. Then in Section 3 we study the disjoint union Figure 1: The graph drawn on the left is a graph non-isomorphic to a disjoint union of complete graphs but Laplacian cospectral with the disjoint union of complete graphs drawn on the right of two complete graphs K a and K b and show that if a b > 5 3 then K a ∪ K b is determined by its Laplacian spectrum.

To fix notations, the set of vertices of a graph G is denoted by V (G) and the set of edges is denoted by E(G); for v ∈ V (G), d(v) denotes the degree of v. The complement of a graph G is denoted by G and concerning the spectrum,

Sp(G) = {µ (m1) 1 , • • • µ (m k ) k
} means that µ i is m i times an eigenvalue of L (the multiplicity of µ i is at least m i , we may allow µ i = µ j for i = j).

We end this introduction with some known results about the Laplacian spectrum and strongly regular graphs.

Theorem 1 [START_REF] Mohar | The Laplacian Spectrum of Graphs[END_REF] The multiplicity of the Laplacian eigenvalue 0 is the number of connected components of the graph.

Theorem 2 [START_REF] Fiedler | Algebraic connectivity of graphs[END_REF][START_REF] Mohar | The Laplacian Spectrum of Graphs[END_REF] Let G be a graph on n vertices whose Laplacian spectrum is

µ 1 ≥ µ 2 ≥ ... ≥ µ n-1 ≥ µ n = 0. Then: 1. µ n-1 ≤ n n-1 min{d(v), v ∈ V (G)}. 2. If G is not a complete graph then µ n-1 ≤ min{d(v), v ∈ V (G)}. 3. µ 1 ≤ max{d(u) + d(v), uv ∈ E(G)}. 4. µ 1 ≤ n.

5.

i

µ i = 2|E(G)|. 6. µ 1 ≥ n n-1 max{d(v), v ∈ V (G)} > max{d(v), v ∈ V (G)}.
Theorem 3 Let G be a graph on n vertices, the Laplacian spectrum of G is:

µ i (G) = n -µ n-i (G), 1 ≤ i ≤ n -1
Corollary 1 Let G be a graph on n vertices, we have µ 1 (G) ≤ n with equality if and only if G is a non-connected graph.

Theorem 4 [2]

A complete graph is determined by its Laplacian spectrum.

Definition 1 [START_REF] Godsil | Algebraic Graph Theory[END_REF] A graph G is strongly regular with parameters n, k, α, γ if

• G is not the complete graph or the graph without edges

• G is k-regular
• Every two adjacent vertices have exactly α common neighbors

• Every two non-adjacent vertices have exactly γ common neighbors

Theorem 5 [START_REF] Godsil | Algebraic Graph Theory[END_REF] A regular connected graph is strongly regular if and only if it has exactly three distinct adjacency eigenvalues.

A strongly regular non-connected graph is the disjoint union of r complete graphs K k+1 for a given r.

Theorem 6 [START_REF] Godsil | Algebraic Graph Theory[END_REF] Let G be a connected strongly regular graph with parameters n, k, α, γ and let k, θ, τ the eigenvalues of its adjacency matrix. Then:

θ = α -γ + √ ∆ 2 τ = α -γ - √ ∆ 2 where ∆ = (α -γ) 2 + 4(k -γ) = (θ -τ ) 2
Moreover, let m θ (resp. m τ ) the multiplicity of θ (resp. τ ), then:

m θ = - (n -1)τ + k θ -τ m τ = (n -1)θ + k θ -τ
That is:

m θ = 1 2 n -1 - 2k + (n -1)(α -γ) √ ∆ m τ = 1 2 n -1 + 2k + (n -1)(α -γ) √ ∆

Disjoint union of complete graphs

The aim of this section is to show that if we consider graphs without isolated vertex then the disjoint union of complete graphs is determined by its Laplacian spectrum.

We first state some results about disjoint union of complete graphs (including isolated vertices).

Proposition 1

The Laplacian spectrum of a graph G with one and only one positive Laplacian eigenvalue a is {a (ra-r) , 0 (r+p) } and G is isomorphic to

K a ∪ K a • • • ∪ K a r times ∪ K 1 ∪ K 1 ∪ • • • ∪ K 1 p times . Proof :
Let G be a graph with one and only one positive Laplacian eigenvalue a and let H be a connected component of G different from K 1 . The graph H has one and only one positive eigenvalue a. If H is not a complete graph, then by theorem 2 we have a

≤ min{d(v), v ∈ V (G)} ≤ max{d(v), v ∈ V (G)} < a, contradiction.
As a result H is a complete graph and H is isomorphic to K a and there exists r

∈ N * , p ∈ N such that G is isomorphic to K a ∪ K a • • • ∪ K a r times ∪ K 1 ∪ K 1 ∪ • • • ∪ K 1 p times .
Theorem 7 There is no cospectral non-isomorphic disjoint union of complete graphs.

Proof : Let G = K k1 ∪• • •∪K kn and G ′ = K k ′ 1 ∪• • •∪K k ′ n ′ , we have n = n ′ (same number of connected components).
If G and G ′ are not isomorphic then there exists λ ∈ N \ {0, 1} such that the number of connected components of G isomorphic to K λ is different from the number of connected components of G ′ isomorphic to K λ . Therefore, the multiplicity of λ as an eigenvalue of the Laplacian spectrum of G is different from the multiplicity of λ as an eigenvalue of the Laplacian spectrum of G ′ and so G and G ′ are not cospectral.

Theorem 8 Let G be a graph without isolated vertex. If the Laplacian spectrum of G is {k

(k1-1) 1 , k (k2-1) 2 , ..., k (kn-1) n , 0 (n) } with k i ∈ N\{0, 1} then G is a disjoint union of complete graphs of order k 1 , ..., k n .
Proof : The graph G has n connected components (Theorem 1) G 1 , ..., G n of order l 1 , ..., l n . We denote by N the number of vertices of G. We have

N = n i=1 l i = n i=1 k i
Let k j be an eigenvalue of G, there exists i such that k j is an eigenvalue of G i , so l i ≥ k j (Theorem 2).

Let G i be a connected component, as G does not have isolated vertices we have l i > 1 and G i possesses at least one eigenvalue different from 0, let k j be this eigenvalue, we have l i ≥ k j . As a result

∀j ∃i : l i ≥ k j ∀i ∃j : l i ≥ k j We assume k 1 ≥ k 2 ≥ ... ≥ k n > 0 and l 1 ≥ l 2 ≥ ... ≥ l n > 1.
We now show by induction on j that k n-j ≤ l n-j , ∀j = 0...n -1.

• j = 0: we know that there exists j such that k j ≤ l n , so k n ≤ l n .

• Let j 0 > 0. We assume that ∀j < j 0 , k n-j ≤ l n-j et let us show that k n-j0 ≤ l n-j0 by contradiction. If k n-j0 > l n-j0 then k n-j0 > l n-j , ∀j < j 0 so k n-j , j ≥ j 0 , cannot be an eigenvalue of G n-j , j < j 0 . So

j<j0 (Sp(G n-j ) \ {0}) ⊂ j<j0 {k (kn-j-1) n-j }. But j<j0 Sp(G n-j ) \ {0} = j<j0 l n-j -j 0 ≥ j<j0 k n-j -j 0 = j<j0 {k (kn-j-1) n-j } so j<j0 (Sp(G n-j ) \ {0}) = j<j0 {k (kn-j-1) n-j }.
As a result k n-j , j < j 0 cannot be an eigenvalue of G n-j0 and as k n-j0 > l n-j0 , k n-j , j ≥ j 0 cannot be an eigenvalue of G n-j0 . That implies that G n-j0 does not have any positive eigenvalue which contradicts that G is without isolated vertex. So k n-j0 ≤ l n-j0 which conclude this induction.

As l i = k i and ∀j = 1, • • • , n, l j ≥ k j we have ∀j = 1, • • • , n, l j = k j . We now show by induction on j that Sp(G n-j ) \ {0} = {k (kn-j-1) n-j }, ∀j = 0, • • • , n -1.
• j = 0. Let k r be an eigenvalue of G n then k r ≤ l n = k n and as k r ≥ k n we have k r = k n . So the k n -1 positive eigenvalues of G n are the k n 's.

• Let j 0 > 0. We assume that ∀j < j 0 Sp(G n-j ) \ {0} = {k

(kn-j-1) n-j }. Then k (kn-j -1) n-j
for j < j 0 are not eigenvalues of G n-j0 and as k n-j = l n-j ≥ l n-j0

for j ≥ j 0 the positive eigenvalues of G n-j0 are necessarily l n-j0 i.e. k

(kn-j 0 -1) n-j0

. By Theorem 1 we have that G i , i = 1, • • • , n are the complete graphs on k i vertices.

Disjoint union of two complete graphs

In this section we consider the disjoint union of two complete graphs and we want to replace the condition "without isolated vertex" of Theorem 8 (this condition cannot be deduced from the spectrum) by a condition on the eigenvalues.

The spectrum of K a ∪ K b , a ≥ b > 1 is {a (a-1) , b (b-1) , 0 (2) }. The disjoint union of two complete graphs is not in general determined by its spectrum, here is a counter-example. The Laplacian spectrum of the line graph of K 6 (which is a strongly regular graph with parameters 15, 8, 4, 4) is {10 (9) , 6 (5) , 0}, so the Laplacian spectrum of L(K 6 )∪K 1 is {10 (9) , 6 (5) , 0 (2) } which is also the spectrum of K 10 ∪ K 6 .

As the disjoint union K a ∪ K a ∪ ... ∪ K a is determined by its spectrum [START_REF] Van Dam | Which graphs are determined by their spectrum? Linear Algebra and its Applications[END_REF], we assume a = b The aim of this section is to show that a graph with Laplacian spectrum {a (a-1) , b (b-1) , 0 (2) } with a > 5 3 b is the disjoint union of two complete graphs.

The paper [START_REF] Van Dam | Graphs with constant µ and µ[END_REF] and the thesis [START_REF] Van Dam | Graphs with few eigenvalues-An interplay between combinatorics and algebra[END_REF] study graphs with few eigenvalues. We can in particular mention the following results: Proof : Let G be a regular graph with Laplacian spectrum {a (a-1) , b (b-1) , 0}, then according to Theorem 9 G is strongly regular with parameters n, k, α, γ. The spectrum of the adjacency matrix of

G is {(k -a) (a-1) , (k -b) (b-1) , k}. By Theorem 6 we have k -b = α-γ+ √ ∆ 2 and k -a = α-γ- √ ∆ 2 where ∆ = (α -γ) 2 + 4(k -γ) = (a -b) 2 and we have α -γ = 2k -a -b so (remind that a + b -1 = n): α -γ = 2k -n -1 (1)
Moreover Theorem 6 gives b -

1 = 1 2 n -1 -2k+(n-1)(α-γ) √ ∆ and a -1 = 1 2 n -1 + 2k+(n-1)(α-γ) √ ∆ so a -b = 2k+(n-1)(α-γ) √ ∆ and so (a -b) 2 = 2k + (n -1)(α -γ) (2)
But ab = γn (Theorem 9) so

(a -b) 2 = 2k + nα -ab -(α -γ) (3)
Equations 1 and 3 give:

(a -b) 2 = 1 + n(α + 1) -ab (4)
As the mean of the degrees is k, we have k = 2|E| n and 2|E| is the sum of the Laplacian eigenvalues, so k = a(a-1)+b(b-1) n i.e.

nk = a 2 + b 2 -n -1 (5)
Equation 4 gives a 2 + b 2abn -1 = nα, using Equation 5we have nkab = nα i.e. n(kα) = ab. But ab = γn so

α + γ = k (6)
Using ∆ = (α-γ) 2 +4(k-γ) and ∆ = (a-b) 2 = 2k+(n-1)(α-γ) (Equation 2) we obtain (αγ) 1) and 2k = 2α + 2γ (Equation 6), so (αγ)

2 + 4(k -γ) = 2k + (n-1)(α -γ) but n-1 = -α + γ + 2k -2 (Equation
2 + 4α = 2α + 2γ + (α + 3γ -2)(α -γ) that is (α -γ)(4 -4γ) = 0 (7)
As a result we have α = γ or γ = 1. Let us show that γ = 1 is impossible: γ = 1 implies α = k -1 and Equation 1 becomes n = k + 1 and so G is the complete graph with n vertices, which is impossible because {a (a-1) , b (b-1) , 0} with a > b > 1 is not the spectrum of a complete graph.

Finally α = γ = k 2 (Equation 6) and (Equation 1) k = n+1 2 and (Equation 2) (ab)

2 = 2k = n + 1 = a + b.
Theorem 11 Let G be a graph whose Laplacian spectrum is {a (a-1) , b (b-1) , 0} with a > b > 1, a, b ∈ N \ {0, 1} and a > 5 3 b. Then G is not regular.

Proof : Proof by contradiction. Let G be a graph whose Laplacian spectrum is {a (a-1) , b (b-1) , 0} with a > b > 1, a, b ∈ N \ {0, 1} and a > 5 3 b and we assume that G is a k-regular graph. Then by the previous lemma we have that G is strongly regular and (ab)

2 = a + b. This implies a 2 -2ab -a = b -b 2 < 0 so a -2b -1 < 0 and a ≤ 2b. Then 3b ≥ a + b = (a -b) 2 > 4
9 b 2 so b( 4 9 b -3) < 0 which gives b ≤ 6. We have Proof : Let G be a graph with Laplacian spectrum {a (a-1) , b (b-1) , 0} with a, b ∈ N\{0, 1} and a > 2b, then G is not regular (Theorem 11) and by Theorem 10 we have that G possesses exactly two different degrees k 1 and k 2 verifying:

k 1 + k 2 = a + b -1 k 1 k 2 = ab -ab
= a+b-1+ √ ∆ 2 , k 2 = a+b-1- √ ∆ 2
.

On one hand we have:

∆ = (a + b) 2 -2(a + b) + 1 -4ab + 4 ab n = (a -b) 2 -2(a + b) + 1 + 4 ab n ≥ (a -b) 2 -2(a + b) + 9
and on the other hand we have (remind that k 2 ≥ b + 1):

∆ = (a + b -1 -2k 2 ) 2 ≤ (a + b -1 -2(b + 1)) 2 ≤ (a -b -3) 2 = (a -b) 2 -6a + 6b + 9 = (a -b) 2 -2a -4a + 6b + 9 but a > 2b i.e. -4a < -8b < (a -b) 2 -2a -2b + 9 = (a -b) 2 -2(a + b) + 9 Contradiction.
Theorem 12 There is no graph with Laplacian spectrum {a (a-1) , b (b-1) , 0} with a, b ∈ N \ {0, 1} and 5 3 b < a.

Proof : Let G be a graph with Laplacian spectrum {a (a-1) , b (b-1) , 0} with a, b ∈ N \ {0, 1} and 5 3 b < a. By Lemma 2 we can assume a ≤ 2b. The graph G is not regular (Theorem 11) and by Theorem 10 we have that G possesses exactly two different degrees k 1 and k 2 verifying:

k 1 + k 2 = a + b -1 k 1 k 2 = ab -ab n with k 2 ≥ b + 1.
First we show that we have b ≥ 6; for that aim we use the relation

2 = b + 1 is impossible. If k 2 = b + 1 then k 1 = a -

Theorem 9 [ 3 ,Remark 1

 31 Theorem 2.1 and Corollary 2.4] A k-regular connected graph with exactly two positive Laplacian eigenvalues a and b is strongly regular with parameters n, k, α, γ with γ = ab n . Moreover k verifies k 2 -k(a+b-1)-γ +γn = 0. In [3], the relation γ = ab n and the equation k 2 -k(a+b-1)-γ+γn = 0 are given in the proof of Theorem 2.1. Theorem 10 [3] Let G be a non-regular graph with Laplacian spectrum {a (a-1) , b (b-1) , 0} with a > b > 1, a, b ∈ N * . Then G possesses exactly two different degrees k 1 and k 2 (k 1 ≥ k 2 ) verifying:k 1 + k 2 = a + b -1 k 1 k 2 = ab -ab n and k 2 ≥ b with k 2 = b if and only if G or G is not connected.Lemma 1 A regular graph with Laplacian spectrum {a (a-1) , b (b-1) , 0} is a strongly regular graph with parameters n, n+1 2 , n+1 4 , n+1 4 . Moreover we have (ab) 2 = a + b.

5 3Remark 2 Lemma 2

 522 b < a ≤ 2b and b ≤ 6, by listing the different cases we show that (a-b) 2 = a+b for b = 3: b a a + b (ab) b = 3 then a = 6 and n + 1 = a + b = 9 but, according to Lemma 1, n + 1 is even, a contradiction. When b < a ≤ 5 3 b, the equation (ab) 2 = a + b admits an infinity of solutions; it is not difficult to show that the couples (a, b) = (u i , u i-1 ) where u 0 = 3 and u i = u i-1 + i + 2 are solutions. There is no graph with Laplacian spectrum {a (a-1) , b (b-1) , 0} with a, b ∈ N \ {0, 1} and a > 2b.

n with k 2 ≥

 2 b + 1 because G and G are connected (G is disconnected if and only if the greatest eigenvalue of G is |G|, but here |G| = a + b -1 = a). We have ab n ∈ N * , but ab = n because a+b = n+1 and a, b ≥ 2 ⇒ ab ≥ a+b. So ab n ≥ 2. The integers k 1 and k 2 are solutions of the equation x 2 -(a+b-1)x+ab-ab n = 0 whose discriminant is ∆ = (a + b -1) 2 -4ab + 4 ab n and so k 1

2 .Theorem 13 Corollary 2

 2132 We denote by n 1 (resp. n 2 ) the number of vertices of degree k 1 (resp. k 2 ). The sum of the degrees is on one hand k 1 n 1 + k 2 n 2 and on the other hand a(a -1) + b(b -1) (sum of the eigenvalues) i.e. k 1 (k1 + 3) + k 2 (k 2 -3) + 4. So k 1 n 1 + k 2 n 2 = k 1 (k 1 + 3) + k 2 (k 2 -3) + 4 i.e. k 1 (n 1 -k 1 -3)+k 2 (n 2 -k 2 +3) = 4. But (n 1 -k 1 -3)+(n 2 -k 2 +3) = 0 because n = k 1 +k 2 = n 1 +n 2 so (n 1 -k 1 -3)(k 1 -k 2 ) = 4 i.e. (n 1 -k 1 -3)(a-b-3) = 4.As a result ab -3 divides 4. The graph K a ∪K b with a, b ∈ N\{0, 1} and5 3 b < a is determined by its Laplacian spectrum.Proof : Let G be a graph with Laplacian spectrum {a (a-1) , b (b-1) , 0(2) } with a, b ∈ N * and 5 3 b < a then G has two connected components. If G has an isolated vertex then the Laplacian spectrum of a connected component of G is {a (a-1) , b (b-1) , 0}, which is impossible (Theorem 12). Consequently G does not have isolated vertex and we apply Theorem 8.The following corollary is straightfoward thanks to Theorem 3: The complete bipartite graph K a,b with a, b ∈ N\{0, 1} and5 3 b < a is determined by its Laplacian spectrum.

  5 3 b < a ≤ 2b and list the possible values of a if b < 6 and we show that n does not divide ab. This is summed up into the following table.

	b	a n ab Does n divide ab?
	3	6 8 18	no
	4	7 10 28 8 11 32	no no
	5	9 13 45 10 14 50	no no
	Henceforth we assume b ≥ 6. Let us show that the case k

-If b = 6 then a = 11 and n = 16, ab = 66 and 16 does not divide 66.

This case is impossible.

-If b = 7 then a = 12 and n = 18, ab = 84 and 18 does not divide 84. This case is impossible.

• We have on one hand:

and on the other hand (remind that a