Adrian Popescu
email: adrian.popescu@telecom-bretagne.eu

Pierre-Alain Moëllic
email: pierre-alain.moellic@cea.fr

Ioannis Kanellos
email: ioannis.kanellos@telecom-bretagne.eu

Rémi Landais
email: remi.landais@exalead.com

Lightweight Web Image Reranking

Keywords: H.3.1 Content Analysis and Indexing Algorithms, Experimentation Image retrieval, reranking, k-NN

Web image search is inspired by text search techniques; it mainly relies on indexing textual data that surround the image file. But retrieval results are often noisy and image processing techniques have been proposed to rerank images. Unfortunately, these techniques usually imply a computational overload that makes the reranking process intractable in real time. We introduce here a lightweight reranking method that compares each result not only to the other query results but also to an external, contrastive class of items. The external class contains diversified images; the intuition supporting our approach is that results that are visually similar to other query results but dissimilar to elements of the contrastive class are likely to be good answers. The success of visual reranking depends on the visual coherence of queries; we measure this coherence in order to evaluate the chances of success. Visual reranking tends to emerge near duplicate images and we complement it with a diversification function which ensures that different aspects of a query are presented to the user. Our method is evaluated against a standard search engine using 210 diversified queries. Significant improvements are reported for both quantitative and qualitative tests.

INTRODUCTION

query time but this is not the case for most existing techniques. Secondly, the discrepancy between query diversification and reranking coherence: queries are conceptually and visually diverse but image reranking performances are good for visually coherent queries; moreover, they are usually tested on narrow domains. For instance, the authors of [START_REF] Kennedy | Generating Diverse and Representative Image Search Results for Landmarks[END_REF] limit their approach to landmarks while the authors of [START_REF] Tversky | Features of similarity[END_REF] test it to canine species. To solve this problem, it would be interesting to have a measure which, given any query and corresponding results, may evaluate the chances for image reranking to be successful. Thirdly, a search engine should maximize results precision and cover different aspects of the query in the same time [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF] but these two measures are often difficult to maximize simultaneously [1]. We introduce an image reranking technique which tries to cope with the three problems cited above. Central to our approach is the conjunction of a contrast model and a focusing hypothesis, idea borrowed from Tversky's work [START_REF] Tversky | Features of similarity[END_REF]. The basic idea is that the similarity between two items is defined in contrastive, structuralist terms: it is not only a proximity relationship (the sharing of common features) but also a distance value that quantifies the dissimilarity to an opponent class of items. We translate this principle to images and suppose that an image is relevant for a query if it is visually similar to other query results and dissimilar to an external class which contains diversified images. To determine the visual coherence of a class we consider the best ranked images and compute the average number of neighbors from the external class. Visual reranking tends to favor near duplicate images [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF]. We then add a diversification step to our method. We index images associated to 210 diversified queries using a texture-color content descriptor [START_REF] Cheng | Image classification using color, texture and regions[END_REF]. This descriptor is efficient when indexing heterogeneous datasets and provides a detailed analysis of the performances of our reranking technique.

RELATED WORK

Image reranking can be performed using textual information associated to images, visual description or a combination of the two. In [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF], the authors adapt the PageRank algorithm to image retrieval in order to find "authority nodes" in a visual similarity graph. Both homogeneous and heterogeneous visual concepts are discussed but the approach is only tested on product images and it largely outperforms the Google standard search. Van Leuken et al. [START_REF] Van Leuken | Visual Diversification of Image Search Results[END_REF] propose techniques for diversifying image search results based on visual clustering. Clustering is applied to both ambiguous and non-ambiguous queries and it is evaluated against manually clustered search results. Tests show that the approach tends to reproduce manual clustering in a majority of cases. Deselaers et al. [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF] discuss the joint optimization of search precision and diversity, with a focus on diversity. They implement a dynamic programming algorithm applied on top of a greedy selection and test their approach on a heterogeneous test database (ImageCLEF 2008 photo retrieval task [1]). An improvement of diversity, accompanied by a small precision loss is reported when comparing results to ImageCLEF runs.

Image retrieval is mainly keyword based. Search engines such as Live or Google only recently introduced content based retrieval, as a complement to textual search, only recently. Results obtained using keyword matching are often irrelevant because the text around images doesn't always describe image content [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF], [START_REF] Kennedy | Generating Diverse and Representative Image Search Results for Landmarks[END_REF].

An important research effort was directed toward developing reranking techniques that exploit image processing; but hard problems are yet to be solved before incorporating image reranking into search engines architectures. Firstly, the topic range: Web image queries address a wide range of subjects and it is impossible to pre-process all possible queries. Consequently, the reranking process should be fast enough to be performed at Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. MM'09, October 19-24, 2009, Beijing, China.

Cai et al. [START_REF] Cai | Hierarchical clustering of www image search results using visual, textual and link information[END_REF] propose a hierarchical clustering approach in order to discover semantic clusters within Web search results. Their method uses textual, visual and link analysis and is mainly designed for ambiguous queries. In [START_REF] Kennedy | Generating Diverse and Representative Image Search Results for Landmarks[END_REF], the authors introduce a multimodal clustering technique (based on k-Means) to produce relevant and diversified results for Flickr landmarks images. Tags, user related information, geotags and temporal information are combined to propose highly accurate results. This technique surfaces images that are well linked to items uploaded by a large number of users, giving thus a social relevance to best ranked results. Whereas the technique in [START_REF] Kennedy | Generating Diverse and Representative Image Search Results for Landmarks[END_REF] is tuned for landmarks, [START_REF] Moëllic | Image clustering based on a shared nearest neighbors approach for tagged collections[END_REF] implements a shared nearest neighbors algorithm (s-NN) which clusters both tags and visual content for any given query. Unfortunately, the technique in [START_REF] Moëllic | Image clustering based on a shared nearest neighbors approach for tagged collections[END_REF] is not fast enough to be performed at query time. Compared to approaches like [START_REF] Kennedy | Generating Diverse and Representative Image Search Results for Landmarks[END_REF] or [START_REF] Tversky | Features of similarity[END_REF], our technique is domain independent. Moreover, it is quite fast because the underlying algorithm, k nearest neighbors (k-NN), is simpler to compute than most other classification methods. The computational complexity has a linear variation with the number of considered images. In [START_REF] Hsu | Video Search Reranking through Random Walk over Document-Level Context Graph[END_REF], reranking is applied on video search results. Initial text search results are reranked using multimodal pair-wise similarity. The reranking problem is formulated using as a random walk by building a context graph. More recently, in [START_REF] Tian | Bayesian Video Search Reranking[END_REF], reranking is seen as a global optimization problem within a Bayesian framework by maximising the ranking score using visual similarity features (global color descriptor) between video shots and minimizing the ranking distance based on the initial text-based ranking. The paper is mainly focused on the likelihood optimisation by proposing two distances between two ranked lists. Though efficient, techniques like s-NN [START_REF] Moëllic | Image clustering based on a shared nearest neighbors approach for tagged collections[END_REF] or dynamic programming [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF] are computationally expensive and are hard to apply under real time constraints. The use of an external class which helps surfacing relevant images is central to our method. To the best of our knowledge, such an approach was not used for image reranking. Another particularity of our method is the introduction of a measure that tries to evaluate if the visual reranking will be efficient for a given query or not. A large number of features can be used to describe visual content. Global image descriptors are computed in [START_REF] Tversky | Features of similarity[END_REF], local features are extracted in [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF] or [START_REF] Moëllic | Image clustering based on a shared nearest neighbors approach for tagged collections[END_REF] and a combination of the two types of features is used in [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF]. Choosing the correct descriptors or combining them are indisputably complex problems, but they fall outside the scope of this paper.

IMAGE RERANKING

The introduction of content based image processing techniques in Live Search and Google Image proves the feasibility of applying such techniques to large volume of images. However, in order for the search process to be computationally efficient, the indexing process needs to be performed offline. We pre-index our images using a global texture-color descriptor presented in [START_REF] Cheng | Image classification using color, texture and regions[END_REF]. Local based approaches provide more robust information but are clearly more expensive due to the high dimensionality of classical local features and usually need nearest neighbors approximation to perform points matching, like in [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF] with an LSH approach used to speed up the construction of the connectivity graph: for 1000 images (about 500,000 local features), 15 minutes were necessary to compute the full similarity matrix. At query time, we select only images associated to the textual query from the index and calculate the similarity matrix dynamically. Such a process takes 0.8 s on average on a 3.0 GHz Intel processor.

Our reranking technique is based on the visual similarity between image search results and on their dissimilarity to an external class. The external class was created by launching a query with "test" in Flickr and recuperating 300 images from different users. A more judicious choice would be to manually build the external class so as to maximize the diversity of its elements. If search results contain an important number of irrelevant images [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF], we presume that i) noisy results are weakly related to relevant results and ii) relevant results are visually related to other answers to the same query. Images in the external class are added to query results in order to find out which elements are close to the class itself and far from the external class. To express the relatedness of each image (noted imgi) to its class, we compare it to other query results and to the external class using content description and finally count the number of extraneous items that are found among the k nearest neighbors of the image (extimgi). A small number of neighbors from the external class indicates that the image is closely related to other query results. The value of k is an important parameter of the reranking procedure and we empirically fixed it at 10. In [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF], the authors make a distinction between visually heterogeneous and visually homogeneous queries (Apple and Mona Lisa). Image reranking is particularly interesting for queries with a large number of results (hundreds or more); a value of k which is significantly smaller than the number of results facilitates the discovery of different aspects of the query. For instance, images of Apple as fruit and Apple as a device are visually dissimilar and will tend to be classified with images that correspond to the same sense of the term. The reranked list of results will propose images with small extimgi firstly, because they are well linked to the class and are likely to be relevant. Clearly, a value of k = 10 will determine a lot of equal extimgi scores; thus, in order to differentiate between images with such scores, we introduce a second score intimgi, which represents the cumulated sum of visual distances between the image and the 5 nearest neighbors from the class. At equal extimgi, images with small intimgi will be presented firstly. The authors of [START_REF] Deselaers | Jointly Optimising Relevance and Diversity in Image Retrieval[END_REF] and [START_REF] Van Leuken | Visual Diversification of Image Search Results[END_REF] note that visual reranking techniques, such as ours, tend to generate results with rather reduced diversity. Since the similarity matrix between the images associated to a query is already computed, we may use it in order to diversify results. In order to ensure that diversified results will be chosen among well linked images, we retain only the best 30% reranked elements (which are more likely to be relevant than other images) and try to find diversified items among them. Once we fixed the number of images the system will finally present to the user, the diversification process is iterated until enough images are retained. We build a list of diversified results by adding new elements to the list whenever these new images are different enough from images that were already selected. To express difference, we count the number of nearest neighbors of the new image that are not nearest neighbors of selected images and use it as threshold. The value of the threshold varies from 1 to 11 and this variation defines an acceptability criterion that is more and more relaxed. The process stops when there are enough elements in the list of diversified results. This list includes 20 elements, a number which roughly corresponds to the number of images on a Web search engine results page. The complexity of the diversification is equal to the product between the size of the list and the number that represents the 30% best ranked results. For a results set containing 300 images, the diversification takes around one second on a 1.6GHz processor and this without any focus on algorithmic optimization.

To characterize the visual coherence (viscor) of a query, we average extimgi for the N best ranked images associated to a query:

viscor = N 1   n 1 i imgi ext (1)
Small values of viscor indicate that the query is visually coherent and that the visual reranking is likely to be successful. Our notion of visual coherence is different from the binary separation of queries in visually homogeneous and heterogeneous proposed in [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF]. For instance, a query with Europe has a low visual coherence and corresponds to a heterogeneous query as defined in [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF]. A query with Monet paintings is heterogeneous according to [START_REF] Jing | VisualRank: Applying PageRank to Large-Scale Image Search[END_REF] but has a good visual coherence because our k-NN algorithm stimulates the discovery of local regularities (here individual paintings).

EVALUATION

Our reranking technique is evaluated on a diversified test dataset comprising 210 concepts which were illustrated with Exalead images [5]. Queries were selected by Exalead according to the following criteria: i) frequency-queries should be chosen among the most frequent queries; ii) diversity-queries should treat a large range of the target domain (geographic entities, celebrities' names, artefacts…); iii) visual coverage-this criterion is related to visual coherence. Examples of concepts in the database include: airplane, Eiffel Tower, crowd or Björk. Up to 300 Exalead images were retained for each query. The effects of the reranking on results precision and diversity were analyzed at a query level in a user study with 22 participants. Then, we performed a smaller scale precision evaluation where three assessors evaluated the P@10 for the original, the reranked and the diversified results. Finally, we reused results of the precision test to assess the utility of viscor (i.e. the visual coherence measure), by means of a threshold on reranking results.

Pertinence vs. Diversity

In our user study the participants were asked to compare the accuracy and the diversity of the results for Exalead images, for the visual reranking technique and for the visual reranking plus diversification. Participants were contacted via e-mail; the participation was voluntary. In order not to overload participants, we asked them to evaluate at most 30 queries. The test dataset was split in seven equal parts; participants had to deal with different parts of the dataset. Since the queries in the dataset were diversified, it was possible that some of them were unknown to participants and these last were instructed to assess only queries they knew well enough. Each query was presented on a distinct page; the top 12 results for each method were displayed on separated columns. To avoid the formation of evaluation patterns, the results columns on different pages were presented in a different order. Participants were asked to evaluate global accuracy and diversity on a scale ranging from 0 (bad quality) to 4 (very good quality) for both query and each retrieval method. The accuracy of results for visually reranked results is significantly higher compared to "Exalead" accuracy (2.94 vs. 2.57); but the results diversity is smaller (2.02 vs. 2.84). To test statistical significance of results difference between "Exalead" and reranked results, we performed a paired T-test (with p < 0.05) and the result (0.00257) shows that the two distributions are statistically different. Values for "Exalead" and "Rerank" in table 1 confirm that visual reranking is efficient in surfacing relevant elements but hurts results diversity. As for results after diversification, the average accuracy is 2.74, compared to 2.57 for "Exalead". The result of the T-test for accuracy in this case (0.1342) is clearly less convincing but the accuracy gain is obtained with little diversity loss (2.76 vs. 2.84). The diversification function has its acceptability parameter set up to a limit case and with a relaxation of this parameter, it is easy to obtain performances ranging from "Rerank+Diversification" to "Rerank" (table 1). The evaluation of image search results is a subjective and context dependant task. In our test, we also noted important variations between the participants. Accuracy varies between 1.87 and 3.21 for "Exalead", between 2.31 and 3.68 for "Rerank" and between 2.125 and 3.43 for "Rerank+Diversification". When considering accuracy, all users preferred Rerank to Exalead and only 5 users out of 22 preferred "Exalead" to "Rerank+Diversification". Visual reranking seems to be preferred to a classical keyword-based approach by a large majority of the users. A results example is presented in figure 1.

Precision Evaluation

The user study focused on a global characterization of answers sets; but we also wanted to assess the precision at 10 (P@10) for all the three methods. To do this, we selected 60 queries from the test dataset and computed the P@10 for each query. In table 2, precision at 10 for "Exalead" varies between 0.628 and 0.713 and between 0.693 and 0.807 for "Rerank". The performed T-tests show statistically significant differences between "Rerank" and "Exalead" for the three users. All participants ranked the three methods in the order they have also done for the global evaluation: "Rerank" scores best followed by "Rerank+Diversified" for User 2 and User 3 and by "Exalead" for User 1. These concordant results indicate that there is a correlation between the global assessment of results quality and the detailed assessment using P@10. Globally, P@10 results confirm the global quality evaluation and show that the highest accuracy is obtained for "Rerank", followed by "Rerank+Diversified" and "Exalead".

Role of Visual Coherence

We hypothesize that it is worth reranking the results for a given query only if its associated visual coherence is sufficiently big (small value of viscor defined in equation 1). We use viscor as a threshold to decide if a query should be reformulated or not and present accuracy results for viscor varying from 0.1 to 7, with a step of 0.1. The use of viscor to decide which queries should be reranked introduces a slight improvement of results (0.1 for all three participants with a threshold value around 2). To confirm the results reported here, the utility of viscor should be evaluated on larger scale query samples; and, of course, with more participants.

CONCLUSION

We introduced an image reranking method that relies on the use of an external class in order to surface relevant images. The method improves results accuracy but hurts diversity and a diversification function was introduced as a compromise. We also defined a visual coherence measure and used it to evaluate if reranking is likely to improve results for a particular query or not. Preliminary tests show that this measure improves results over the use of visual reranking for all queries. Our reranking method is generic, fast and easy to integrate in existing Web image search architectures. We currently investigate the introduction of other content descriptors in the reranking framework, focusing on the use of the visual coherence measure for automatically selecting the best descriptor (or combination of descriptors) for a query. We will also compare our approach with techniques such as VisualRank. Finally, we will investigate the effect of constructing the external class manually and the performances of the method when retaining more than 300 images per query.

Table 1 . Accuracy and diversity for the three tested techniques averaged on a panel of 22 participants. The scale is from 0 (bad) to 4 (good quality results).

 1

				Method
		Exalead	Rerank	Rerank+Diversification
	Accuracy	2.57	2.94	2.74
	Diversity	2.84	2.02	2.76

Table 2 . P@10 for a sample of 60 queries and three users. P@10

 2

		Exalead	Rerank	Rerank+Diversification
	User 1	0.628	0.693	0.615
	User 2	0.671	0.735	0.676
	User 3	0.713	0.807	0.747

ACKNOWLEDGMENTS

This research is part of Georama, a French research project funded by ANR.


J Nasreddine

J Pérez-Romero

O Sallent
email: sallent@tsc.upc.edu

R Agusti

X Lagrange
email: xavier.lagrange@enst-bretagne.fr

A Proposal on Frequency Management Methodologies for WCDMA Systems using Cell Coupling Matrices

Although a single carrier frequency is usually considered in Wideband Code Division Multiple Access (WCDMA) systems, each operator has more than one carrier frequency in practical 3G systems. Moreover, QoS levels and the throughput within a given frequency highly depend on interference patterns, which are mainly related to cell-frequency allocation. Therefore, frequency management plays a key role in WCDMA network planning. However, the frequency management problem has not been in the center of attention for WCDMA systems so far due to the fact that WCDMA has not yet been implemented in wide range with all possible services. Nevertheless, the arrival of multimedia services will emphasize the critical importance of a smart frequency allocation. In this context, the presence of several frequencies for each operator (typically 2 or 3 in Europe) manifests itself as a fertile dimension of flexibility to be exploited. This paper introduces a novel frequency management methodology based on coupling matrices that reflects the interaction between cells for a given interference pattern. The proposed methodology is implemented as an integral task of the planning tool and has lead to better results than the frequency allocation in the classical hierarchical cell structure.

I. INTRODUCTION

In WCDMA systems, several users share the same carrier frequency using different code sequences, which have good autocorrelation and cross-correlation characteristics. However, the lack of synchronization and the impact of multipath reduce the efficiency of these sequences and lead to the appearance of intra-cell and inter-cell interferences. These interferences are the main limiting factors for WCDMA capacity. Hence, interference reduction is a vital task in WCDMA systems and can be achieved by combining radio network planning and Radio Resource Management (RRM) techniques that can distribute efficiently the scarce radio resource units. A resource unit in WCDMA systems can be seen as the combination of a carrier frequency, a spreading code and the power dedicated to this pair. The transmission power allocation and the distribution of spreading codes have been widely studied in the literature using different RRM techniques such as power control, scheduling, call admission control, etc [START_REF] Pérez-Romero | Radio Resource Management strategies in UMTS[END_REF]. On the contrary, and even though each WCDMA operator has several carrier frequencies (typically 2 or 3 in Europe), the Frequency Management Problem (FMP) in WCDMA has hardly been addressed so far in the open literature to the authors' best knowledge. The introduction of the frequency dimension into planning and RRM problems provides an additional degree of flexibility to reduce the interference in each carrier and increase system capacity, thus becoming an important aspect to be developed for a fruitful exploitation of the inherent WCDMA potentials.

Available scarce research works relate the FMP in WCDMA to Hierarchical Cell Structures (HCS) scenarios, mainly by analyzing the feasibility to operate macro-cell and micro-cell layers with the same frequency, then breaking the approach by allocating different frequencies to the two layers [START_REF] Lagrange | Multitier Cell Design[END_REF]- [START_REF] Karlsson | Sharing radio resources in hierarchical cell structures utilizing slow frequency hopping[END_REF]. Nevertheless, the FMP neither has to be limited to the HCS nor it has to be presumed that it has a priori guide on a suitable solution, since it is strongly dependant on interference and traffic distribution along the deployed scenario.

The FMP was widely studied in TDMA/FDMA systems and involved two procedures, namely the design of an appropriate representation of radio constraints and the design of optimization algorithms. Radio constraints include all types of interaction between equipments and they are captured in the so-called compatibility matrix [START_REF] Abril | A multiagent system for frequency assignment in cellular radio networks[END_REF] [START_REF] Anton | An adaptive method to learn the compatibility matrix for microcellular systems[END_REF]. Once radio constraints are captured, optimization algorithms provide frequency allocation that maximizes the capacity while satisfying QoS constraints [START_REF] Kunz | Channel assignment for cellular radio using neural network[END_REF]- [START_REF] Kendall | Channel Assignment Optimisation Using a Hyper-heuristic[END_REF].

Existing methodologies for TDMA/FDMA systems are substantially different from the methodologies envisaged in this paper for WCDMA systems due to the different nature of constraints imposed by the radio interface. In fact, cell interaction in TDMA/FDMA systems depends only on channel characteristics between the two cells due to the presence of one transmission in each cell and a primitive power control. Hence, the estimation of cell interaction is generally simple and has been widely investigated [START_REF] Abril | A multiagent system for frequency assignment in cellular radio networks[END_REF] [START_REF] Anton | An adaptive method to learn the compatibility matrix for microcellular systems[END_REF]. However, the representation of radio constraints in WCDMA systems cannot be extracted with the same simplicity as in TDMA/FDMA due to the existence of intra-cell and inter-cell interference together with fast power control schemes leading to a high correlation between interference profiles, cell loads, mobile positions, etc. This complexity may lead to a questionable representation of cell interaction if the same model as TDMA/FDMA systems is used. Therefore, a specific representation for radio constraints has to be designed to fit WCDMA characteristics. In that sense, the authors of [START_REF] Pérez-Romero | A Novel Framework for Robust WCDMA Planning under Changing Spatial Traffic Distributions[END_REF] presented a methodology based on load gradient computations which revealed its suitability to capture the interaction among cells and was identified as a potential candidate to be used for frequency management in WCDMA.

Taking into account the above framework, this paper addresses the FMP in WCDMA systems as an integral task of an advanced 3G planning tool. The paper considers the WCDMA deployment phase in which traffic requirements are such that not all the available carriers are fully loaded, so that the practical availability of several carriers per operator can be exploited to improve interference patterns. Consequently, system performance can be ameliorated by means of the proposed frequency management strategies. Clearly, in the extreme situation of full load in all carriers, a frequency reuse of one (i.e. all carriers allocated in all base stations) would be the most adequate solution. Accordingly, the particular scope of the paper is the situation in which a single carrier is required per base station, although it is thought that the proposed methodology could be extended to cope with the case in which more than one carrier is required in some base stations depending on traffic patterns. Based on the general two-step procedure used in TDMA/FDMA systems, the proposed methodology covers first the definition of a coupling matrix whose entries capture the degree of interaction among the different cells (i.e. an equivalent concept to the compatibility matrix) using radio network measurements such as E b /N 0 , interference and pathloss. Only very recently, there have been few attempts to design coupling matrices for WCDMA systems. In [START_REF] Ben Jamaa | Quality Indicator Matrices and Their Contribution to WCDMA Network Design[END_REF], the authors have proposed a coupling matrix assuming that the received interference of each cell can be easily isolated, which is not so explicit. In addition to the fact that our contribution proposes solutions for the whole FMP, a relevant novelty included hereinafter is that we propose a methodic scheme to capture the coupling matrix.

In the second step, the coupling matrix is used as the input to a heuristic algorithm that provides the frequency assignment. In this case, the lower number of available frequencies in WCDMA systems when compared to TDMA/FDMA systems leads to a simplification in the heuristic algorithm design.

The proposed methodology considers only the uplink and can be extended to take into account the downlink by using the model developed in [START_REF] Pérez-Romero | Radio Resource Management strategies in UMTS[END_REF]. Furthermore, it is worth mentioning that the methodology can be applicable both at the initial static radio network planning phase and in operational systems in order to cope with significant changes in the distribution of cell loads during time, thus envisaging dynamic frequency planning mechanisms (i.e. frequency assignment to cells may vary along time and space) at a rather long-term scale (i.e. once or twice in a day, several times in a week, etc.). In this case, the dynamic mechanisms will be able to cope with sudden but, at the same time, significant and long lasting traffic variations, which can be of high relevance in practical WCDMA networks.

This paper is organized as follows: In section II, we develop an analytical framework for a coupling matrix and we propose a simple heuristic optimization algorithm to solve the FMP. In section III, we introduce the simulation model, which is used to obtain the results presented in section IV. Finally, we conclude with relevant remarks and future works.

II. FREQUENCY MANAGEMENT METHODOLOGY

Let us consider a well dimensioned WCDMA system of K base stations and F frequencies. Hence, all users' E b /N 0 s are around the required thresholds.

A. Coupling Matrix based on Load Gradient

Coupling matrices are intended to reflect interaction between different cells. In other words, entry C j,l of coupling matrix C represents the impact of cell l on cell j. Hereafter, we propose an analytical framework to derive a suitable representation of cell interactions based on load gradient computation. In the coupling matrix based on load gradient, the entry C j,l is computed using the derivative of the load factor in cell j with respect to the load factor in cell l ( j / l ), which reflects the impact of load factor variation in cell l on load factor variation in cell j. We remind the reader that the load factor of cell j in uplink is given by the following equation:

, 1 N j R j j N P P P η χ = - + + (1)
where P N is the background noise power, P R,j is the total own cell power received by cell j and χ j is the inter-cell interference experienced by cell j. The E b /N 0 of mobile i j is given by: , 0 , ,

j j j j j i i b i R j j i j N P E N P P P χ Θ = - + + (2)
where j i j P , is the useful received power by base station j from mobile i j and j i Θ is the transmission spreading factor of mobile i j . Using the load factor equation from [START_REF] Pérez-Romero | Radio Resource Management strategies in UMTS[END_REF], we can write:

, , 1 , 1 1 1 1
UL K k j UL j j k k k j j UL K k j k k k j S S S η η η = ≠ = ≠ + - = + - (3) where: , , 1 , 1 1 k
k k k k k n i k UL k j i i i j b o i L S L E N = = Θ + (4)
where j i k L , is the pathloss of mobile i k towards base station j and n k is the number of users in cell k. Thus, we can write:

( ) , 2 1 1 UL K j k j k j k l l k k j S B η η η η η = ≠ ∂ ∂ = ∂ ∂ - (5)
where B j is given by: ,

UL j j j UL K k j k k k j S B S η = ≠ - = + - 2 , 1 1 1 1
Furthermore, we define the sum J j by the sum of the gradient vector related to cell j and given by the following relation:

1 K j j m m J η η = ∂ = ∂ (7)
The term J j reflects the impact of load factor variations in all cells on load factor variation in cell j. It must be noted here, that the factor j / j is included in the sum to have a convenient final expression of J j . The value of this term is a constant (i.e. 1); therefore, it does not have any impact.

After sum computation, we find:

( ) , 2 1 1 1 UL K K l j l j j l m m l l j S J B η η η = = ≠ ∂ = ∂ - (8)
Using equation ( 7) for all cells, we find:

( ) , 2 1 1

UL K l j j j l l l l j S J B J η = ≠ = - (9)
Each element of the right term can be seen as the contribution of a neighboring load factor variation to the total variation of load factor in cell j. Thus, the coefficient of element l represents the impact of cell l on cell j. Using these elements, we can define an intermediate coupling matrix A:

( ) UL , , 2
1 i f otherwise 1 l j j l j l l j S A B - = = (10)
This matrix considers only the variation of the load factor. However, the cell load has also a significant impact on the interaction with other cells. In order to take into account this effect, we multiply each column by the corresponding cell load. Then the final coupling matrix C can be written as: = C AL [START_REF] Cheng | A Novel Approach to the Fixed Channel Assignment Problem[END_REF] where L is a diagonal matrix whose entries are defined by: , 1

j j j n j j i i L R = = (12)
where

j i
R is mobile i j data rate at physical layer in Kbits/s.

In order to consider the mutual interaction between two cells, the following symmetric matrix is defined using the asymmetric matrix C: = + t O C C [START_REF] Pérez-Romero | A Novel Framework for Robust WCDMA Planning under Changing Spatial Traffic Distributions[END_REF] where C t is the transpose of C. Hence, each entry O j,k combines the impact of cell j on cell k and the impact of cell k on cell j.

B. Heuristic Optimization Algorithm

The objective of the optimization algorithm is to minimize the total outage probability in the system, which is defined as the ratio of unsatisfied users to the total number of users. A user is considered unsatisfied if its E b /N 0 is lower than the target E b /N 0 . Notice that the outage probability has been considered here as a representative QoS metric taking into account its relationship with other QoS metrics (e.g. a high outage probability will be associated with a high error rate for real time services and with a high delay for non real time services). Moreover, the total outage probability in WCDMA systems is highly related to interference which in turn is related to the coupling matrix. Consequently, our objective is to minimize the interference profile using an offline heuristic algorithm that reduces cell interactions.

Herein, we define X f as the set of cells operating with frequency f. These sets are initially empty sets.

Using matrix O, a heuristic algorithm that tends to avoid high interactions among cells is defined by the following steps: 1. Cells are sorted using the sum of the corresponding rows in matrix O. 2. The F frequencies are allocated with one-to-one association to the first F cells with highest sum and sets X f are updated. 3. For the next cell i of the remaining sorted cells, define the set of variables {ρ f } f=1..F by:

{ } , f f i k k X i S ρ ∈ ∪ = ( 14
)
4. Thereafter, cell i is associated to frequency f c such that:

{ } 1,..., min c f f f F ρ ρ ∈ = (15)
5. Add cell i to set X f . and repeat from step 3 In each step, the algorithm reduces the impact of introducing a new cell on the existing cells and the impact of the latter on the new cell. At the beginning, frequencies are allocated to cells with the highest interference contribution because these cells have the highest impact on interference patterns. The remaining cells are then distributed such as the total cell interaction is minimized. Using this method, we can avoid the allocation of the same frequency to cells with high interaction.

III. SIMULATION MODEL

The performance of the proposed frequency management methodology has been evaluated by means of Monte Carlo simulations in a scenario with 37 macro-cells and a set of micro-cells. Each simulation consists of 10000 snapshots. In the simulation, each mobile is connected to the base station with the highest E c /N 0 (signal energy per chip over Noise power spectral density) of the downlink pilot channel. Simulation parameters are summarized in table I. In order to study the performance of the proposed scheme, the traditional HCS is considered as a reference scheme for comparison purposes. In the HCS, macro-cells share the same frequency, while micro-cells (when they exist) share the second one. The simulations have been carried out with four different representative case studies. In the first three cases, a first traffic layer is uniformly distributed and a second layer including dense hotspots is added. Case study 1 corresponds to the first phase of WCDMA system deployment where hotspots start to appear, whereas no micro-cells are implemented. Consequently, only one frequency is used by the traditional HCS. The cell layout is the same as the layout shown in figure 2 without micro-cells. In case study 2, each hotspot is served by a micro-cell in the center of the hotspot (figure 2). In case study 3, the micro-cells are not at the center of the hotspots (figure 3). In case study 4, there are neither hotspots nor microcells, but each macro-cell has a different traffic density (figure 4). In each case study of the first three cases, three layouts, denoted as layout 1, 2 and 3 respectively, are considered with five, eight and ten hotspots with the corresponding micro-cells.

The micro-cell, when exists, is placed at the intersections of three cells depending on the layout (figure 2).

IV. RESULTS

In this section, we present the results obtained using the different case studies and layouts. First, we show in figure 1 several values of matrix O from layout 2 of case study 2. We remind that the entries of matrix O are used by variables ρ f .

From this example we can see that the matrix efficiently reflects the interaction between cells. For instance, the interaction between micro-cells is very low (0.03) because mobiles in these cells have very low pathloss toward their servers and very high pathlosses toward other base stations. However, the interaction between micro-cells and neighboring macro-cells is very high (84). Indeed, some mobiles that are geographically near to micro-cells are connected to a macrocell due to the difference in pilot power. Therefore, these mobiles introduce high interferences into micro-cells. Moreover, the interaction between macro-cells is higher when the macro-cells are close. Thus, the proposed coupling matrix takes into account both cell loads and geographical positions.

In figures 2, 3 and 4, we show the frequency configurations for case studies 2, 3 and 4 when the proposed methodology is used. Herein, cells with high loads (i.e. generally cells with high entries in the coupling matrix), tend to not share the same frequency with more than one neighboring cell. Moreover, the proposed method tends to allocate the same frequency to a set of neighboring cells when it is possible, which gives users the flexibility of smooth mobility without changing the frequency during each handover.

In figure 5, we show the total outage probability in the system when the HCS and the frequency management methodology are used for the first three case studies. As we can see, the proposed methodology reduces the outage probability by more than 40% in all cases. Moreover, the slope of the outage probability as a function of the number of hotspots (i.e. the different layouts) is smaller when the proposed methodology is used, especially when the micro-cells are not at the center of the hotspots. This is due to the fact that the proposed methodology is slightly dependent on the number of hotspots in contrary to the HCS. In the fourth case study, the outage probability decreases from 5.8% when HCS is used to 0.3% when the proposed scheme is used. In all cases, the traditional HCS appear to be unable to offer an acceptable assignment and an appropriate solution without adding more base stations. In contrast, the proposed methodology manifests as an elegant solution to solve this problem only by changing the frequency allocation. In brief, this solution will reduce the cost of operator infrastructure. It should be emphasized here that the optimization algorithm complexity is a linear function of the number of cells. Therefore, its convergence is very fast and can be easily performed in operational systems even if a large set of cells are considered.

V. CONCLUSIONS AND FUTURE WORKS

In this paper, we have proposed a novel formulation of the interaction between cells, using load factor gradients for the uplink in WCDMA systems. This formulation is used to design an efficient frequency management methodology using a heuristic algorithm. Simulations results have shown that the obtained coupling matrix reflects efficiently cell interactions. Furthermore, the proposed algorithm drastically decreases the outage probability when compared to the traditional allocation according to HCS. The proposed scheme is an offline scheme at this stage. However, an online scheme that can cope with relatively fast variations in the system can be developed thanks to the interesting characteristics of the proposed matrix.

Figure 1 .

 1 Figure 1. The entries of matrix O in case study 2 and layout 2

Figure 2 .

 2 Figure 2. The three cell layouts and corresponding frequency allocation using the proposed coupling matrix for case study 2

Figure 3 .

 3 Figure 3. The three cell layouts and corresponding frequency allocation using the proposed coupling matrix for case study 3

Figure 4 .Figure 5 .

 45 Figure 5. The total outage probability for the first three case studies and the three layouts Case study 1 (mobile densities are 20 and 400 mobiles/km2 respectively in the scenario and hotspots)

TABLE I

 I

	.
	SIMULATION PARAMETERS
	Macro-cell layer
	BS pilot power	30 dBm
	Cell radius	0.6 km
	Hotspot layer
	Micro-cell BS pilot power	12 dBm
	Cell radius	0.2 Km
	Common parameters
	Number of frequencies	2
	Pathloss model	128.1+37.6 log10d (Km)
	Background noise	-103 dBm
	UE maximum transmitted power	21 dBm
	UE minimum transmitted power	-44 dBm
	Eb/N0 target	4 dB
	Spreading factor	256
	Shadowing factor deviation	10 dB
	Shadowing factor crosscorrelation	0.5
	Power control	Perfect power control

ACKNOWLEDGEMENTS This work is partially funded by the European Network of Excellence NEWCOM (Contract number 507325), and by the COSMOS grant (ref. TEC2004-00518, Spanish Ministry of Science and Education and European Regional Development Fund).


G Varillon

J.-M Clarisse

A Couairon

Investigation of supersonic heatconductivity linear waves in ablation flows

  L'archive ouverte pluridisciplinaire

Introduction

Ablation flows relevant to inertial confinement fusion (ICF) are classically described by gas dynamics equations with nonlinear heat conduction. Standard descriptions assume an isothermal conduction region [1,2]. However a local analysis in terms of linear propagating waves [START_REF] Clarisse | 44 th EPS Conf. Plasma Physics[END_REF]5] reveals that temperature stratification in this region gives rise to supersonic upstream propagating waves as a consequence of nonlinear heat conduction. Such �heat conductivity� waves occur for a regime of high heat propagation and are associated with heat flux perturbation inhomogeneities that convey inhomogeneities in temperture and density perturbations.

The latter may trigger radiative heat transport instabilities [START_REF] Yu | [END_REF] that could destabilize the ablation flow.

In the present work, we conduct numerical computations of linear perturbations in self-similar ablation flows. We drop the restriction of a local analysis to address globally the non uniformity and unsteadyness of realistic ablation flows, taking into account exactly, by contrast with previous works reported in [START_REF] Clarisse | 44 th EPS Conf. Plasma Physics[END_REF]5], linear wave coupling and damping due to heat diffusion.

The entire deflagration structure of an ablation wave is described from the fluid external surface where an incoming radiation flux and external pressure are applied, up to the forerunning shock wave front. This corresponds to the ealry stage of an ICF target implosion. We focus on self-similar ablation flows with subsonic and supersonic expansion, and possibly containing a Chapman-Jouguet point [5]. Transmission mechanisms (diffusion, advection and source term) are compared in the conduction zone, and the analysis in terms of hyperbolic waves is found to be relevant.

A local pseudocharacteristic analysis

We consider the motion of a polytropic gas subject to radiative flux and material pressure at its external boundary. Radiation transfers are considered under radiation heat conduction, and diffusive effects are dominated by radiative heat flux. The flow is considered in slab symetry in the x direction. Dimensionless equations of motion in Lagrangian coordinate m -dm = ρdxread

∂ t �1/ ρ) -∂ m ū = 0 � ∂ t ū + ∂ m p = 0 � ∂ t � T /�� -1) + ū2 /2) + ∂ m � p ū + φ) = 0 � (1)
where φ = Ψ�ρ� T� ∂ x T ), Ψ representing the heat flux dependence on density, temperature and its gradient, with ∂ ∂ m T Ψ < 0. This system is closed by the equation of state p = ρ T .

The ablation wave structure extends from the flow external surface (m = 0) through the ablation front up to the forerunning shock wave front. Time dependent pressure and heat flux are applied at m = 0 while Rankine-Hugoniot jump relation are applied at the shock wave front.

Solutions to (1) described continuously all peculiarities of the radiative ablative wave.

Considering first order perturbations of (1)

V �m�t) = � ρ� ū� T ) � → V �m�t) + εV �m�t) + O�ε 2 )� with ε � 1 and V �m�t) = �ρ� u� T ) � , perturbations V are governed by �               ∂ t � ρ ρ ) + ∂ m � ρu) = 0� ∂ t u + ρu∂ m ū + ∂ m p - ρ ρ ∂ m p = 0� ∂ t T � -1 + ρu∂ m T � -1 = p� ρ ρ ∂ m ū -∂ m u) -p∂ m ū + ρ ρ ∂ m φ -∂ m ϕ� (2)
where

ϕ = ρ∂ ρ Ψ + T ∂ T Ψ + ∂ m T ∂ ∂ m T Ψ.
In vector form, this system reads

∂ t V + Ā�m�t)∂ 2 m 2 V + B�m�t)∂ m V + C�m�t)V = 0 � (3)
where Ā, B and C are 3 � 3 matrices depending on � ρ� ū� T ) from (1) [5]. Matrix Ā�m�t) contains only a diffusive term on temperature, matrix B�m�t) is hyperbolic and matrix C�m�t) depends mainly on gradient of base-flow variables.

The reduced, purely hyperbolic, system In the conduction region λ 2�3 correspond to quasi-isothermal right and left going acoustic waves, while λ 1 is a right going wave associated to supersonic heat-conductivity ruled by ∂ ρ Ψ and ∂ T Ψ. In the post-shock region, right and left going isentropic acoustic waves ( λ 1�3 ) and entropy wave (λ 2 ) are recovered [5].

∂ t V + B�m�t)∂ m V = 0 ⇔ ∂ t W + ��m�t)∂ m W = 0 (4) with � = diag�λ 1 � λ 2 � λ 3 ) = L B R
System (3) can be expressed in the characteristic basis of the reduced hyperbolic problem (4) This system (5) cannot be held as an evolution equation but can be analysed at any point �m�t). For each component W i the variation rate reads

∂ t W + � ∂ 2 m 2 W + �∂ m W + C W = 0 � with � = L Ā R and C = L C R. ( 5
)
δW i = 3 ∑ j=1 �-� i j ∂ 2 m 2 W j -λ i ∂ m W i -Ci j W j ) δt.
Therefore contributions from diffusion, advection and source terms can be compared at any given flow location and time.

Application to fast expension flow

For applications we consider radiation heat conduction model φ = -ρ-1 T 6.5 ∂ m T . By comparing the response of system (2) to a sine wave forerunning in W 1 applied at m = 0 for a sufficiently long wavelength [5], we are able to confirm the local analysis (Fig. 2).

Figure 2:

W 1 �left), W 2 �right) and W 3 �bottom).
We observe a posteriori that projections of solutions to (2) on pseudo-characteristic variable, W i Fig. 2, follow the a priori characteristics � i of the reduced hyperbolic system (4). Moreover, advection dominates over diffusion in the conduction region, and source terms are neglibible (Fig. 3).

These observations highlight the existence of a supersonic heat-conductivity propagating wave in the conduction zone and its ability to transmit perturbations from the flow external boundary to the ablation front at supersonic speed. As a consequence, a density perturbation is transmitted to the ablation front by this heat-conductivity wave. Analysis of responses to heat-flux perturbations applied at the external boundary on a supersonic expansion flow shows that advection is still dominant over diffusion in the conduction region, and thus could transmit density perturbation along heat-conductivity characteristic � 1 . However, density component of the wave in this particular flow is too small to be significant. Perturbations of sufficiently long wavelength follow the characteristic trajectories predicted by the reduction of the general equations (2) to its hyperbolic part [START_REF] Yu | [END_REF]. Quantitative analysis of advection, diffusion and source terms shows that advection mechanism is dominant even in the conduction region. Therefore density perturbations can be effectively advected along supersonic heat-conductivity waves up to the ablation front and could possibly trigger radiative heat transport instability [START_REF] Yu | [END_REF]. However, application to a supersonic expansion flow with external heat-flux or pressure perturbations shows that the density contribution to the heat-conductivity mode is actually negligible.

Further works should consider transverse perturbations and shorter longitudinal wavelength.

  and W = LV -L and R being local left and right eigenvectors matrices -defines local characteristics as dW i = 0 along � i .

Figure 1 :

 1 Figure 1: Base-flow at t = 1, m schock = 1.

Figure 3 :

 3 Figure 3: Conduction region -contributions to δW 1 from diffusion �left), advection �right) and source terms �10�bottom) normalized maximum of advection contribution.

th EPS Conference on Plasma Physics P1.2018