Arash Maskooki

Gabriele Sabatino

Nathalie Mitton

Analysis and performance evaluation of the next generation wireless networks

come

Introduction

The data traffic consumption is exponentially growing in wireless networks; this is due to the new applications demanding high-quality of services, high data rate and new advanced user terminals which are evolving rapidly over the past decade.

Mobile data traffic is forecast to grow by more than 24 times between 2010 and 2015, and 500 to 1000 times between 2010 and 2020 [START_REF] Nakamura | Trends in Small Cell Enhancements in LTE Advanced[END_REF]. The forecasts estimate that about 50 billion devices will be connected by 2020.

Long-Term Evolution/Long-Term Evolution-Advanced (LTE/LTE-A) wireless systems as well asIEEE802.11 family of technology are expected to dominate the wireless-communication arena for the next decade.Particularly,LTE/LTE-Aare more and more emerging as the global choice which all mobile-broadband operators are expected to migrate [START_REF] Dahlman | 4G LTE/LTE-Advanced for Mobile Broadband[END_REF][3].

Other radio access technologies are available or under development such as Wireless Personal Area Network (WPAN includingBluetooth and ZigBee) and IEEE802.11p, for very-short-range communication between devices and for communication between vehicles.

The vision of new generation mobile systems is towards unification of various mobile and wireless networks which can be qualified as heterogeneous network (HetNet). HetNets consist of different access networks and provide a wide range of services including enhanced and extended mobility and accessibility. These networks will not only help improving existing services [START_REF] Boudriga | Intelligent services integration in mobile ATM networks[END_REF][START_REF]-E, Version 1.0.0, Wireless Intelligent Networks[END_REF] but integrate intelligent algorithms for mobility management, resource management, access control, routing, etc. This chapter will discuss modeling and analysis of the performance of the next generation wireless networks. This section provides an introduction to this chapter. The following section will discuss the characteristics and development of different generations of cellular wireless network.Section 3 will present the analytical methods to evaluate the performance of the next generation HetNets. Subsequently, Section 4 will discuss the simulation techniques and analysis for HetNets. Finally, Section 5 will conclude this chapter.

The evolution of cellular wireless systems

The First Generation (1G) mobile cellular systems were deployed in the 1980s. The first commercial cellular network was the Nordic Mobile Telephone (NMT) deployed in the Scandinavian countries. Another system developed was the advanced mobile phone service (AMPS) cellular system in the United States and the most popular Total Access Communication Systems (TACS). These technologies were based on analog systems, circuit switching and used Frequency Division Multiple Access (FDMA) radio system.

Second generation (2G) mobile systems were introduced at the beginning of the 1990s in Europe with the Global System for Mobile communication (GSM) systems. The GSM system, developed by the European Telecommunications Standard Institute (ETSI), is a Time Division Multiple Access (TDMA) radio system with data transmission rate up to 9.6 kbps and is the pioneer of the packet switching system.

In United States there were other lines of development such as IS-54 (North America TDMA Digital Cellular), IS-136 also known as D-AMPS and IS-95 based on Code Division Multiple Access (CDMA) known as CDMA-One.

To provide better support for data services, ETSI developed the General Packet Radio Service (GPRS), a packet transmission system that overlays GSM and inter-works with external packet data networks such as the Internet. GPRS is a 2.5 generation (2.5G) wireless communication system.The main feature is that each mobile terminal is assigned an IP address which enables the devices in such networks to integrate with Internet easily.

The evolution towards third generation cellular systems (3G) was driven by the International Telecommunications Union (ITU) and referred to as International Mobile Telecommunications 2000 (IMT-2000).

The Third Generation Partnership Project (3GPP), organization established in 1998, defined a mobile system called universal mobile telecommunications systems (UMTS).Its mainfeature was to evolve GSM core networks and the Radio Access Network (RAN) technologies. 3GPP developed a system that enhanced data rates for GSM evolution (EDGE) standards. The 3G systems can deliver bit rates up to 2 Mbps and support of quality-of-service (QoS). The approach adopted to evolve the core network is called High Speed Packet Access (HSPA) and is widely considered as 3.5G. The HSDPA offered peak rate of 14.4Mbps in 5MHz channel at the downlink.

The 3GPP started to work on the Fourth Generation (4G) cellular systems and standardized the Long-Term Evolution (LTE) [START_REF] Gpp | Overview of 3GPP release 8[END_REF]. LTE in effect was labeled 3.9G and the motivation behind the design of this network was to provide low latency and very high-data rates starting from at 100 Mbps and reaching more than 1 Gbps at the downlink.

LTEis expected to substantially improve the end-user throughputs, sector capacity and reduce user plane latency, bringing significantly improved user experience with full mobility. LTE is scheduled to provide support for IP-based traffic with end-to-end QoS and in particular, also LTE supports a flexible bandwidth deployment and, thanks to Orthogonal Frequency Division Multiplexing (OFDM) and Multiple Input Multiple-Output (MIMO) systems, allows high data rates.

Enhancements introduced in LTE are [START_REF] Gpp | Overview of 3GPP release 8[END_REF]: ), the 4G mobile evolution system, was defined.


LTE-A research is mainly focused on user Signal to Interference Noise Ratio (SINR) improvement and spectrum flexibility. The LTE-A proposes a distributed network architecture, heterogeneous networkwhich consist of a mix of macro-, pico-, femto-cells (HeNBs -Home eNodeB -also called femto-cells, low cost eNodeBs for indoor coverage improvement), and relay base-stations. They can be directly connected to the Evolved Packet Core (EPC) or via a gateway (HeNB-GW -Home eNodeB Gateway), providing additional support for a large number of HeNBs. Self-Organizing Network (SON) concepts have been introduced in LTE standardization in order to increase the network performance and reduce the operational expenditure for operators. The smaller transmission powers from small-cells and the relative proximity of users to a small-cell, more users can now be covered within the same area in a HetNet; consequently, HetNets provide "cell-splitting" gains relative to macro-only networks.

The new technology targets include,better coverage, higher data rates, better QoS performance and fairness among users. 3GPP has been working on various aspects to improve LTE There is a growing interests to interconnect and amalgamate different technologies to support future connectivity and data rates. Make our everyday life more efficient, comfortable and safer is the main objective of the Internet of Things. Services such as smart mobility, smart environment, and e-health will continue to proliferate and become more mobile.

The evolving of cellular wireless networks, fifth generation (5G), are envisioned to overcome the fundamental challenges of existing cellular networks, e.g., higher data rates, user-coverage and crowded areas, energy consumption and cost efficiency. 5G wireless networks are expected to be a mixture of network tiers of different sizes, a multi-tier architecture consisting of macro-cells, different types of licensed small-cells, device-to-device (D2D) networks to serve users with different quality-of-service (QoS) and different radio access technologies (RATs) that are accessed by an unprecedented numbers of smart and heterogeneous wireless devices [START_REF] Hossain | Evolution Towards 5G Multi-tier Cellular Wireless Networks: An Interference Management Perspective[END_REF].

The deployment of small-cells bring an improvement in order of network coverage and due to the changes to the functional architecture of the access network allowed data and control signals to tunnel through the Internet, enabling small-cells to be deployed anywhere with Internet connectivity [START_REF] Chin | Emerging Technologies and Research Challenges for 5G Wireless Networks[END_REF]. Small-cells are also a very promising candidate for the backhauling of WSNs (Wireless Sensor Networks), because terminals can use less power in comparison with other wireless systems [START_REF] Cimmino | The role of small cell technology in future Smart City applications[END_REF]. Recent developments are moving the WSN communication towards Internet protocol (IP)-based systems, according to the IoT paradigm.

The vision of the future 5G seems to be a heterogeneous networks composed of a mixture of different radio access technologies that include WLAN technologies which can offer seamless handovers to and from the cellular infrastructure, and device to device communications.

Another new important aspect where the next generations networks are focusing are the "big data". The future M2M or IoT applications will generate a vast amount of data and obviously will be a technical challenge for RANs. New network architectures may emerge from the necessity of running big data applications, making informed decisions and extracting intelligence from big data. The smart grid can be seen as a huge sensor network, with immense amounts of grid sensor data from various sensors, meters, appliances and electrical vehicles. Data mining and machine learning techniques are essential for efficient and optimized operation of the grid [START_REF] Chin | Emerging Technologies and Research Challenges for 5G Wireless Networks[END_REF].

Generations

Modeling and analysis of interference in the heterogeneous wireless networks

In parallel with cellular system development, the wireless technologies sector provides different access systems: Wireless Local Area Networks (WLAN) 802.11 IEEE standard (Institute of Electrical & Electronics Engineers) and Wireless Metropolitan Area Networks (WMAN) 802.16 (commercialized under the name WiMAX from Worldwide Interoperability for Microwave Access). These technologies can be incorporated in the next generation of wireless systems to balance the load of the macro base station and provide a better coverage.In the future wireless networks, small-cells that use these technologies are considered as a promising solution to the increasing number of users of the next generation of wireless networks. Small-cells are equipped with low power and low cost access points which are set up based on the coverage or capacity demand in specific parts of the network and can offload parts of the demand of the macro base station. Coexistence of these technologies in a multi-tier heterogeneous network triggers the need for a more efficient spectrum management schemes to better utilize the spectrum and limit the level of interference from different tiers of the network.

Interference is a major limiting factor in multi-tier heterogeneous networks due to the coexistence of several tiers in the networks. Thus, modeling and analysis of the interference provide insight to the limitations of the network and lead to more practical solutions to respond to the high demand for capacity.Interference in wireless networks is the unwanted signal energy received from peer transmitters on the same network or other nearby networks. The transmitted power𝑃 𝑡 decays exponentially with respect to the distance 𝑑from the transmitter,

𝑃 𝑟 (𝑑) = 𝐾𝑃 𝑡 ℎ 𝑟𝑡 𝑑 -𝜂 , (1)
where, 𝑃 𝑟 ,𝐾 and ℎ 𝑟𝑡 are the received power, path loss constant, and the random channel gain variation between the transmitter and receiver respectively. Signal to noise and interference ratio (SINR) is defined as,

𝑆𝐼𝑁𝑅 = 𝑃 𝑟 (𝑑) 𝑁 + 𝑃 𝑟 (𝑑 𝑖 ) 𝑖∈𝕀 , (2)
where, 𝑁is the noise power.𝑑 𝑖 and 𝑃 𝑟 (𝑑 𝑖 )are the distance and received power between the receiver and the i th transmitter in the set of nearby transmitters (𝕀) respectively.

Legacy analytical methods for cellular wireless networks assumed hexagonal grids to model the base station (BS) locations and the coverage in the network. However, in practice, placement of the BSs is not regular. This is because the placement is performed based on the demand in specific areas and also the condition of the location and other barriers. Performance metrics of the network can be obtained using the network model. As an example, by assuming Rayleigh fading for point-to-point channel in the network, the cumulative distribution function (CDF) of the signal to noise and interference ratio (SINR) for the test receiver in the network can be calculated as follows [START_REF] Elsawy | Stochastic geometry for modeling, analysis, and design of multi-tier and cognitive cellular wireless networks: A survey[END_REF],

𝐹 𝑆𝐼𝑁𝑅 𝜃 = 𝑃 𝑆𝐼𝑁𝑅 ≤ 𝜃 = 𝑃 𝐾𝑃 𝑡 ℎ 𝑟𝑡 𝑑 -𝜂 𝑁 + 𝐼 ≤ 𝜃 = 𝑃 ℎ 𝑟𝑡 ≤ 𝑁 + 𝐼 𝜃𝑑 𝜂 𝐾𝑃 𝑡 = 𝐹 ℎ 𝑟𝑡 𝑁 + 𝐼 𝜃𝑑 𝜂 𝐾𝑃 𝑡 𝑓 𝐼 𝐼 𝑑𝐼 𝑢 (3)
substituting Rayleigh CDF yields,

𝐹 𝑆𝐼𝑁𝑅 = 1 -𝑒𝑥𝑝 - 𝑁𝜇𝜃𝑑 𝜂 𝐾𝑃 𝑡 ℒ 𝐼 (𝑠)| 𝑠= 𝜇𝜃 𝑑 𝜂 𝐾𝑃 𝑡 (4)
where,

𝑆𝐼𝑁𝑅 = 𝐾𝑃 𝑡 ℎ 𝑟𝑡 𝑑 -𝜂 𝑁 + 𝐼 (5)
𝐹 ℎ 𝑟𝑡 and 𝑓 𝐼 are the cumulative distribution function and probability distribution function of the channel and interference respectively. ℒ 𝐼 (𝑠) is the Laplace transform of the probability distribution function (PDF) of the interference and is obtained based on the statistics of the point process that fits the network such as Poisson point process [START_REF] Andrews | A Tractable Approach to Coverage and Rate in Cellular Networks[END_REF]. This method yields the CDF of SINR and hence the statistics of the other parameters of the systems such as the outage probability and maximum achievable rate.

In the same way, the average transmission rate in the network could be calculated. In [START_REF] Andrews | A Tractable Approach to Coverage and Rate in Cellular Networks[END_REF], the average transmission rate for the downlink and in Rayleigh fading is calculated. BSs and users are modeled by homogenous PPPs. It is shown that the average transmission rate can be obtained as,

𝐸 ln 1 + 𝑆𝐼𝑁𝑅 = 𝑒 - 𝑁𝜇 𝑑 𝜂 𝐾𝑃 𝑡 𝑒 𝑡 -1 ∞ 0 ℒ 𝐼 ( 𝜇𝑑 𝜂 𝐾𝑃 𝑡 (𝑒 𝑡 -1))𝑑𝑡 (6)
However, this method only applies for Rayleigh fading while in general the PDF of SINR may not be obtained in closed form. Another method used in literature is to obtain a lower bound using the major interference contributors. In high path loss environments (𝜂 = 4) the nearest 𝑛 interferers can be included into the interference calculations where 𝑛 is the parameter. e.g. to obtain a lower bound for the outage probability, the vulnerability region is defined such that existence of a transmitter within this region would drive the SINR below a desired threshold 𝜃.

The probability that at least a transmitter is present in vulnerability region is then calculated [21].

Frequency reuse technique is widely used in cellular networks to mitigate the interference experienced by the users at the expense of lower spatial bandwidth efficiency. In generic frequency reuse scheme, the total available bandwidth is divided into Δsub-bands and used by different cells in a way that no two neighboring cells would use the same sub-band.Fractional frequency reuse (FFR) can improve the spatial frequency bandwidth efficiency by reusing a large portion of the available bandwidth for their inner cell users while assigning the rest to the borderline users. This is performed by assigning transmission power P 1 to the inner cell frequencies and P 2 to the boundary frequencies where P 2 >P 1 . Obviously, the neighboring cells would not use will not use the same boundary frequencies.

In general, incorporating frequency reuse schemes in stochastic geometry network models is a challenging task, as frequency reuse will violate the fundamental spatial in independency in PPP. This is because, the base stations with the same set of sub-band cannot be neighbors and hence their locations are correlated. A solution is to assume that the BSs randomly choose their sub-bands. Hence, cells using the same sub-band will form a thinned version of the original PPP which is also a PPP with

λ Δ
where λ is the intensity of the nodes in the original PPP and Δ is the number of sub-bands. Incorporating FFR into the network model is tricky due to the correlation it introduces to the placement of the BSs using similar boundary frequencies.This has been overcome in [25] by introducing a Threshold T ffr where users with SINR lower than threshold are considered boundary users.

Using small-cells in multi-tier next generation cellular networks improves the network coverage and capacity. Spectrum allocation to the small-cells can be universal frequency reuse or by spectrum partitioning. In universal frequency reuse, the whole spectrum is used by macro-cells and small-cells. This improves the spatial spectrum efficiency at the cost of multi-tier interference. i.e. small-cell users will receive interference from macro-cell and vice versa. On the other hand, spectrum partitioning will eliminate the multi-tier interference at the expense of lower spectrum efficiency. This is because, only parts of spectrum is used at every tier of the network. In [26], hexagonal grid model is adopted for macro-cells while small-cells are modeled by PPP and the optimum spectrum partitioning is investigated.The trade-off between spectrum sharing and partitioning is investigated in [19]. All network tiers are modeled by PPP and Rayleigh fading is assumed for channel fading. Results show that universal spectrum sharing is optimal in sparse network deployments while spectrum partitioning is more desired in dense networks in terms of transmission capacity and outage probability.

Using centralized scheduling for spectrum access in future multi-tier wireless network is inefficient in terms of delay and complexity. Hence, cognitive radio and opportunistic medium access are considered viable solutions for this type of networks. Modeling and analyzing interference is crucial in this type of networks as interference is considered a major limiting factor of the efficiency of this type of networks.

Electromagnetic spectrum is a limited natural resource and most of the usable bands are already licensed for specific applications. In addition, a small portion of the spectrum has been released by authorities for industrial, scientific and medical purposes. However, these license free bands are increasingly getting over-populated and hence they have a high level of interference. Nevertheless, study shows that the licensed spectrum is under-utilized by the licensed operators. In other words, there are spatial or temporal white spaces where the spectrum is not used by the primary licensed user. Cognitive radio is a term assigned to the set of schemes where the wireless device can sense and adjust its parameters for a more efficient use of the spectrum. In future, cognitive radio devices will be allowed to access the licensed spectrum as a secondary user, conditioned on limited interference to the primary user. However, before these dynamic sharing schemes can be used in practice, their spectrum efficiency and impact on the primary users must be carefully analyzed as discussed in Chapter XX. *Reference to the chapter "Wireless Cognitive Networks Technologies and Protocols"+ Stochastic geometry models can be used to evaluate the performance of cognitive radio networks. In [27], the aggregate interference by secondary user received at the primary user is obtained. The primary user network consists of one transmitter and one receiver while secondary user network is modeled by a PPP. Candidate distributions are tested against the interference model and shifted log-normal distribution is suggested as the best distribution describing the statistics of the interference. Similarly, in [28], the interference from a secondary user on a one link primary user is investigated. The probability distribution function (pdf) of interference is obtained through its characteristic function. Results show that a truncated alpha-stable function best represents the pdf of aggregate interference at the primary network receiver. The outage probability of the primary user is obtained by assuming Rayleigh fading for the links and PPP for the distribution of the node in secondary user network. In addition, lower bounds on the interference temperature are obtained using the strongest interferers. The abovementioned works assume a simple one-link network for the primary user. A more complex network model for the primary user network is investigated in [START_REF] Lee | Interference and Outage in Poisson Cognitive Networks[END_REF]. Two independent PPPs are considered for primary and secondary users. Two approaches are considered to obtain the statistics of the outage and interference. In the first approach, bounds for theinterference and outage are obtained by assuming a bipolar Poissoncognitive network model. Whereas, in the second approach the secondary user is assumed to transmit only outside the exclusion region where the received power from the primary transmitters is below a certain threshold. It is shown that the network of the secondary user outside the exclusion region can be accurately modeled by a Poisson hole process [START_REF] Lee | Interference and Outage in Poisson Cognitive Networks[END_REF]. However, due to the complexity of the Poisson hole process, the secondary user network model is approximated and analyzed by Poisson cluster process.

Multi-tier structure of the next generation wireless networks leads to a better coverage and more spectral efficiency. However, a centralized coordination of spectrum access for all tiers of the network is not an efficient solution for spectrum access management of the total network. Femto-cells are envisioned to be installed by the user or operators to respond to the demand for coverage in specific areas and hence their distribution tends to be random. Cognitive radio techniques have been investigated as a promising solution for a de-centralized spectrum access management in such multi-tier cellular networks. In [START_REF] Lima | Coordination Mechanisms for Self-Organizing Femtocells in Two-Tier Coexistence Scenarios[END_REF], the aggregate interference for a twotier cellular network consists of a single MBS and a network of femto-cells is obtained through its characteristic function. In their proposed scheme, MBS will transmit a busy tone to reserve the channel and hence femto-cells will defer their transmission if the received power from MBS is above a certain threshold. The outage probability and the average transmission rate areobtained through the aggregate interference statistics and the model is validated through simulations.

In [21], a more complex network model is investigated. The network is composed of two tiers where users are being served by multiple MBSs and femto-cells. Base stations, access points and users are modeled by independent PPPs. It is shown that cognitive techniques can decrease the probability of outage for femto-cells users by 60 percent. In [22], fully cognitive and semi cognitive schemes are investigate for femto-cells in a cellular network. In semi cognitive technique, the femto-cell access point avoid using the channel occupied by MBSs and aggressively use the second-tier frequencies while in fully cognitive scheme the access points sense and avoid using the frequencies used by other femto cells as well. It is shown that semi cognitive scheme outperforms the fully cognitive scheme in terms of outage probability. This is because although cognition with respect to all network tiers reduces the interference level, it limits the transmission opportunity severely in dense networks.

Simulation techniques for the next generation wireless heterogeneous networks

Due to the data traffic demand in cellular networks, improvements in system spectral efficiency are necessary. One possible solution is increasing the base station deployment density. In a relatively sparse deployment of macro base stations, adding another base station does not severely affect inter-cell interference, and solid cell splitting gains are easy to achieve.However, site acquisition in a capacity limited dense urban area can get prohibitively expensive [START_REF] Damnjanovic | A Survey on 3GPP Heterogeneous Networks[END_REF].

Challenges associated with the deployment of traditional macro base stations can be overcome by the utilization of base stations with lower transmit power which are classified as pico-cells, femto-cells and relay nodes. The transmit power of the low power access points intended for outdoor deployments ranges from 250mW to approximately 2W. They do not require an air conditioning unit for the power amplifier and are much lower in cost than traditional macro base stations, which their transmit power typically varies between 5 and 40 W. Pico-cells are regular eNBs with the only difference of having lower transmit power than traditional macrocells. They are, typically, equipped with Omni-directional antennas and are deployed indoors or outdoors often in a planned (hot-spot) manner. Femto base stations are meant for indoor use, and their transmit power is typically 100mW or less. Unlike pico, femto base stations may be configured with a restricted association, allowing access only to its closed subscriber group (CSG) members. Such femto base stations are commonly referred to as closed femtos. Relay nodes are used to extend the macro-cell coverage or fill a coverage hole. A network that consists of a mix of macro-cells and low-power nodes, where some may be configured with restricted access and some may even lack wired backhaul, is referred to as a heterogeneous network. An illustration of such networks is shown in Figure 1,

Figure 1: An illustration of a heterogeneous network

Femto-cells have recently attracted significant attention. The use of femto-cells will benefit both users and operators. Users will enjoy better signal quality due to the proximity between transmitter and receiver and hence communicate with larger reliabilities and throughputs. Furthermore this will also provide power savings, reduce electromagnetic interference and energy consumption. This way, more users will access to the same pool of radio resources or use larger modulation and coding schemes, while operators will benefit from greater network capacity and spectral efficiency. There are a number of technical studies associated with various aspects of femto-cells deployments based on cellular technology. These studies consider operations, administration, and management (OAM) and self-organizing network (SON) protocols, network architecture, local IP access (LIPA), access (open, closed, and hybrid), and interference management [START_REF] Yavuz | Interference Management and Performance Analysis of UMTS/HSPA+ Femto-cells[END_REF][START_REF] Chandrasekhar | Femto-cell Networks: A Survey[END_REF][START_REF] Patel | Femto-cells[END_REF].

Heterogeneous networks are based on different wireless technologies, where macro networks are based on a cellular technology while low power access points are based on WLAN [START_REF] Coupechoux | Network Controlled Joint Radio Resource Management for Heterogeneous Networks[END_REF][START_REF] Song | Performance Analysis of the WLAN-First Scheme in Cellular/WLAN Interworking[END_REF].

Reduced cost is one of the main motives for the adoption of femto-cells. It is shown in [START_REF] Claussen | Financial Analysis of a Pico-Cellular Home Network Deployment[END_REF] that in urban areas a combination of publicly accessible home base stations or femto-cells (randomly deployed by the end user), and macro-cells deployed by an operator for area coverage in a planned manner, can result in significant reductions (up to 70 percent in the investigated scenario) of the total annual network costs compared to a pure macro-cellular network deployment.

The introduction of low-power nodes in a macro network creates imbalance between uplink and downlink coverage. Due to larger transmit power of the macro base station, the handover boundary is shifted closer to the low-power node, which can lead to severe uplink interference problems as UE units served by macro base stations create strong interference to the lowpower nodes.

The performance of a mixed deployment of macro-, pico-, and open femto-cells was evaluated in [START_REF] Nihtila | HSDPA Performance with Dual Stream MIMO in a Combined Macro-Femto Cell Network[END_REF][START_REF] Karimi | Evolution Towards Dynamic Spectrum Sharing in Mobile Communications[END_REF], which showed that the limited coverage of low-power nodes is the main reason for limited performance gain in heterogeneous networks.

In 4G networks, new physical layer design allows for flexible time and frequency resource partitioning. This added flexibility enables macro-, femto-and pico-cells to assign different time-frequency resource blocks within a carrier or different carriers (if available) to their respective UE. This is one of the inter-cell interference coordination (ICIC) techniques that can be used on the downlink to mitigate data interference [START_REF] Boudreau | Interference Coordination and Cancellation for 4G Networks[END_REF][START_REF] Khandekar | LTE-Advanced: Heterogeneous Networks[END_REF]. With additional complexity, joint processing of serving and interfering base station signals could further improve the performance of heterogeneous networks [START_REF] Simeone | Robust Transmission and Interference Management For Femto-cells with Unreliable Network Access[END_REF][42], but these techniques require further study for the scenarios commonly seen in practice.

NS-3 Simulator

ns-3 (network simulator 3) is a discrete time event based network simulator. It can implement a large number of different protocols and it is completely free software, licensed under GNU GPLv2 license. ns-3 is a standalone new simulator and it is not an extension of ns-2. The two simulators are both written in C++, but ns-3 does not support the ns-2 APIs. Some models from ns-2 have already been adapted for use in ns-3. Both ns-2 and ns-3 are discrete event network simulators. This means that the simulation consists of a series of independent events that change their state. Events are actions such as a sending a packet, a new node being added to the network, or a timer expiring.

Each scheduled event runs until completion without advancing the simulation time, and then the simulation time is increased to the start time for the next scheduled event.

ns-3 is developed mostly by the same group of people that work on or have worked on ns-2 [START_REF]ns-3 project description[END_REF]. The ns-3 project started because of some problems associated with the ns-2. In ns-2, C++ and tcl are used to build simulations and the combination of both languages is difficult to debug and it can be considered as a barrier for new developers. Different tests show that ns-2 does not scale well to large simulations, making it unsuitable for some research scenarios. Many models in ns-2 are not validated against the real world, which makes users to doubt whether simulation results are the same as the results that would be measured in real-world implementations.

The nodes in the simulation with ns-3 are more realistic than ns-2. Every node is constructed out of devices and there is an Internet protocol stack that closely resembles the stack on real systems.

Network traffic generated by ns-3 can be traced and written to a file in the pcap (packet capture) format, which makes it possible to analyze it with tools like "Wireshark".

Due to its ability to simulate realistic scenarios, ns-3 can be used as a virtual system or be used in testbeds. Real applications can run on top of a protocol stack implemented by ns-3 and it is also possible to run applications on real networking stacks or to run an instance of ns-3 in a network, where it interacts with 'real' systems.

The ns-3 architecture consists of a core simulator part and a number of layers that add the networking-specific elements. It provides an Internet stack with implementations of protocols like TCP and UDP, as well as lower-level protocols such as various versions of 802.11. Different components and applications can be added to the nodes, after which nodes can be connected to each other. To help with building up nodes and creating a network topology, helper scripts are provided. Compared to ns-2, there are other differences as well, such as the build system.

The simulation core is implemented in src/core. Packets are fundamental objects in a network simulator and are implemented in src/network. These two simulation modules by themselves are intended to comprise a generic simulation core that can be used by different kinds of networks, not just Internet-based networks.

The first open source product-oriented LTE network simulator is developed by Ubiquisys, the developer of intelligent cells, and the Centre Tecnologic de Telecomunicacions de Catalunya (CTTC) [START_REF]Manual LENA release M8[END_REF]. The development of the LTE module for the ns-3 was carried out during the Google Summer of Code 2010. This module provides a basic implementation of the LTE device, including propagation models, PHY and MAC layers. The simulator will provide a common platform for LTE femto-and macro-cells. In WCDMA networks, femto-cells and macro-cells work independently, but in LTE all cells work together as a single self-organizing network. This means that the adaptive behavior of femto-cells and macro-cells is interdependent. Simulations are important because they can evaluate product performance in densely deployed and heavily used networks while real deployments are still in their infancy. The development of the LTE simulator is open to the community in order to foster early adoption and contributions by industrial and academic partners. The most important features provided by this module are: a basic implementation of both the User Equipment (UE) and enhanced NodeB (eNB) devices, Radio Resource Control (RRC) entities for both the UE and the eNB, Adapting Modulation and Coding (AMC) scheme for the downlink, the management of the data radio bearers, Channel Quality Indicator (CQI) management, etc.

In LTE network, a module consists of two main components:

• The LTE Model. This model includes the LTE Radio Protocol stack (RRC, PDCP, RLC, MAC, PHY). These entities reside entirely within the UE and the eNB nodes. This has been designed to support the evaluation of the Radio Resource Management, QoS-aware Packet Scheduling, Inter-cell Interference Coordination, and Dynamic Spectrum Access;

• The EPC (Evolved Packet Core) Model. This model includes core network interfaces, protocols and entities. These entities and protocols reside within the SGW, PGW and MME nodes, and partially within the eNB nodes. The EPC model provides means for the simulation of end-to-end IP connectivity over the LTE model. In particular, it supports for the interconnection of multiple UEs to the Internet, via a radio access network of multiple eNBs connected to a single SGW/PGW node.

Simulations

In this section some example scenarios are simulated using ns-3 network simulator and the results will be presented and discussed. In the following simulations, the scenarios are implemented in ns-3 as shown in Figure 2.

The scenario includes a single macro-cell, a number of femto-cells and users of both macro-cell and femto-cell. Femto-cell coverage is CSG (Closed Subscriber Group) where only the authorized users can access the base station. Figure 2 shows a HetNet composed of a macrocell (eNB), different femto-cells (HeNB) and users where MUE (macro-user equipment) and HUE (home-user equipment) indicate macro-and femto-cell users respectively. Also the core network or EPC has been implemented, following procedures explained in [START_REF] Yavuz | Interference Management and Performance Analysis of UMTS/HSPA+ Femto-cells[END_REF]. Moreover, different applications are considered to generate user traffic in downlink and uplink. LTE provides users traffic with different QoS (Quality of Serivce). Each information flow is associated with a specific QoS class which constitutes a bearer. "Guaranteed Bit Rate Conversational Voice" bearer is used in the following simulations. The built in radio channel model "Multi Model Spectrum Channel" is used for the links, while the Path Loss and Fading are implemented according to the class "ns-3: Hybrid Buildings Propagation Loss Model". Finally, the UE mobility are incorporated using the "Mobility Model" class. The Radio Environment Map (REM) as shown in Figure 3 is a uniform 2D grid of values that represent the Signal-to-Noise ratio in the downlink with respect to the eNB that has the strongest signal at each point. Through the use of this map, we can better examine the tested scenarios, with respect to the possible interference between devices.

Figure 3: REM map with only one eNB without HeNB

Simulation results presented below are referred to the metrics identified at the PDCP layer. For this set of simulations a throughput metric is taken into account, defined as the number of successful received packets during a specific time. Furthermore, two different kind of throughput are defined: the total throughput and the average throughput.

The total throughput represents the amount of total received information per unit of time and is calculated as,

total throughput = 𝑅 𝑥 𝑇 𝑠𝑖𝑚 , (7)
where 𝑅 𝑥 represents the total received number of bits and 𝑇 𝑠𝑖𝑚 is the time of transmission of the bits.

The average throughput is instead expressed by the following equation (1.2):

average throughput = 𝑅 𝑥 𝑇 𝑠𝑖𝑚 • 𝑁 𝑈𝑠𝑒𝑟𝑠 , (8)
which represents the amount of information received by the users per unit of time. 𝑁 𝑈𝑠𝑒𝑟𝑠 is the total number of users. As shown in the Figure 5 the total throughput when 25 UEs are allocated in the macro-cell and the remaining are assigned to one femto-cell, has similar trend as observed in the previous simulations.

On the other hand, when the users decide on connecting the femto-cell and macro-cell base stations based on the power reception (load balancing) the network throughput is increased as shown in Figure 5. The final scenario includes a HetNet with the presence of multiple femto-cells. The number of macro-cell users was fixed at 20. Figure 7 highlights how the throughput improves by increasing the number of femto-cells inside the same macro-cell. As figure shows, with 2 femto-cells, increasing the number of femto UE (greater than 10 HUE) causes a drastic decrease in the throughput while increasing the number of femto-cells to 5 improves the network throughput as more users can be covered. However, the presence of more than 5 femto-cells causes interference in the HetNet system and hence degrades the SINR value and consequently the throughput.

Conclusion

Spectrum is a limited natural resource and hence has to be utilized efficiently to support the increasing spectrum demand. Studies show that the spectrum is underutilized by the licensed users. This triggered tremendous interest in using white spaces where the primary user is not accessing the spectrum in spectrum in spatial, temporal or frequency domains.Heterogeneous networks (HetNet) are promising solution to the challenge of providing coverage for a large number of users within the limited available spectrum. Such networks consist of multiple tiers where each tier can use different communication technology, transmission powerand coverage range.Coexistence of these tiers arise some challenges including the interference level which is a major limiting factor in the performance of the next generation multi-tier networks. In this chapter, mathematical models to analyze the interference in such networks and subsequently the throughput are presented. Following the mathematical models, simulation techniques for these networks are discussed. HetNet performance is investigated to testify the improvements introduced by Long Term Evolution-Advanced (LTE-A) definition. The simulation campaign has been conducted with the aim to demonstrate the pros and cons introduced by the use of the femto-cells in a HetNet scenario. Preliminary results have been obtained exploiting the ns-3, building a scenario in which macro-cells and femto-cells coexist has been implemented, in order to evaluate the performance in terms of throughput. Obtained results show that, in general, by increasing the number of femto-cells the system throughput.

  Downlink peak data rate up to 100 Mbps;  Uplink peak data rate up to 50 Mbps;  Increased data rate for cell-edge users with respect to HSPA;  High spectral efficiency (bit/s/Hz), increased by a factor 3-4 with respect to HSPA;  Round Trip Time (RTT) equals to 10 ms (it was 70 ms in HSPA and 200 ms in UMTS);  Low latency, lower than 100 ms for idle-to-active mode switch;  Mobility support for very high mobility speed (up to 350 km/s);  Backward compatibility (GSM/GPRS and UMTS/HSPA);  Voice and real time services offered over IP network. These enhancements are supported by several features [6]:  OFDM/OFDMA downlink modulation;  SC-FDMA uplink modulation;  High channel bandwidth flexibility (1.

Figure 2 :

 2 Figure 2: Simulation scenario

Figure 4 :

 4 Figure 4: The total throughput for the same scenario

Figure 5 :

 5 Figure 5: Total throughput in a network with an eNB, HeNB and the number of macro users set to 25 (The number of users of the femto-cell has been varied).

Figure 6 :

 6 Figure 6: Comparison between the two scenarios with macro UE equal to 0 and 25 respectively.

Figure 7 :

 7 Figure 7: Comparison of average throughput in a scenario with 2 and 5 HeNB by varying the number of HUE

Figure 8 :

 8 Figure 8: Comparison of the average throughput in a scenario with 5, 10 and 20 HeNB by varying the number of HUE

Table 1 :

 1 [START_REF] Boudriga | Intelligent services integration in mobile ATM networks[END_REF] 3,[START_REF]-E, Version 1.0.0, Wireless Intelligent Networks[END_REF][START_REF] Sharma | Evolution of Mobile Wireless CommunicationNetworks-1G to 5G as well as Future Prospectiveof Next Generation Communication Network[END_REF][START_REF] Weber | Transmission Capacity of Wireless Networks in Foundations and Trends in Networking[END_REF] 20 MHz) both in downlink and uplink direction; Very large section of available spectrum can be assigned to a LTE base station (including GSM or UMTS frequencies or band on 2.6 GHz); Performance LTE and LTE-Advanced.

	 Transmitting and receiving diversity, spatial multiplexing and diversity with Multiple
	Input Multiple Output (MIMO) techniques;
	 QPSK, 16-QAM and 64-QAM modulation schemes.
			LTE (3.9G)	LTE-Advanced (4G)
			Release 8	Release 10
	Peak data rate	DL	300 Mbps	1 Gbps
		UL	75 Mbps	500 Mbps
	Peak spectral	DL	15	30 ( up to 8x8 MIMO)
	efficiency (bps/Hz)	UL	3.75	15 (up to 4x4 MIMO)
	Access methodology	DL	OFDMA	OFDMA
		UL	SC-FDMA	SC-FDMA
	Transmission		20 MHz	100 MHz
	Bandwidth

The main goals of LTE are focused on minimizing system and User Equipment (UE) complexities, allowing flexible spectrum deployment in existing or new frequencyspectrum management and enabling co-existence with other 3GPP Radio Access Technologies (RATs). The definition of 4G wireless, known as the International Mobile Telecommunications Advanced (IMT-Advanced) project, was finally published by the International Telecommunications Union Radio communication Sector (ITU-R) in March 2008. In 2009 LTE-Advanced (LTE-A) (in Release 10

Table 2 :

 2 Generations of mobile technologies[START_REF] Sharma | Evolution of Mobile Wireless CommunicationNetworks-1G to 5G as well as Future Prospectiveof Next Generation Communication Network[END_REF].

  network of randomly distributed points. Stochastic geometry has been used to model and analyze ad-hoc wireless networks for nearly three decades[START_REF] Elsawy | Stochastic geometry for modeling, analysis, and design of multi-tier and cognitive cellular wireless networks: A survey[END_REF][START_REF] Haenggi | Stochastic Geometry and Random Graphs for the Analysis and Design of Wireless Networks[END_REF][START_REF] Cardieri | Modeling Interference in Wireless Ad Hoc Networks[END_REF][START_REF] Haenggi | Interference in Large Wireless Networks[END_REF][START_REF] Weber | Transmission Capacity of Wireless Networks in Foundations and Trends in Networking[END_REF][START_REF] Baccelli | Stochastic Geometry and Wireless Networks in Foundations and Trends in Networking[END_REF][START_REF] Baccelli | Stochastic Geometry and Wireless Networks in Foundations and Trends in Networking[END_REF][18]. It has been shown that stochastic geometry can be used for modeling and analysis of the next generation multi-tier wireless networks as well[19][START_REF] Lima | Coordination Mechanisms for Self-Organizing Femtocells in Two-Tier Coexistence Scenarios[END_REF][21][22][23].In stochastic geometry models, a network is modeled by a point process that best fits the network characteristics. e.g. large networks in vast areas of coverage and randomly distributed nodes such as cellular networks can be modeled by Poisson point process (PPP). A point process is Poisson point process if and only if the number of points in any compact set defined on the region is a Poisson random variable. Other point processes have also been used to model wireless networks. Binomial point process (BPP) is used to model a randomly distributed wireless sensor network where the number of nodes is known andfinite. Poisson cluster process (PCP) is applied to the network where nodes are clustered around specific point due to some physical constraint or MAC protocol specification such as Wi-Finetworks. Hardcore point process (HCPP) is another point process used in the networks where two nodes cannot coexist within a hardcore vicinity𝑟 ℎ .

In addition, placing small-cells would further randomize the network grid in the next generation wireless networks. Stochastic geometry is a mathematical tool that can provide the expected values of the desired parameters in a


Christian Bessiere
email: bessiere@lirmm.fr

Remi Coletta
email: coletta@lirmm.fr

Nadjib Lazaar
email: lazaar@lirmm.fr

Solve a Constraint Problem Without Modeling It

Keywords: Elicitation based resolution, Constraint acquisition, Constraint Learning

We study how to find a solution to a constraint problem without modeling it. Constraint acquisition systems such as Conacq or ModelSeeker are not able to solve a single instance of a problem because they require positive examples to learn. The recent QuAcq algorithm for constraint acquisition does not require positive examples to learn a constraint network. It is thus able to solve a constraint problem without modeling it: we simply exit from QuAcq as soon as a complete example is classified as positive by the user. In this paper, we propose ASK&SOLVE, an elicitation-based solver that tries to find the best tradeoff between learning and solving to converge as soon as possible on a solution. We propose several strategies to speed-up ASK&SOLVE. Finally we give an experimental evaluation that shows that our approach improves the state of the art.

I. INTRODUCTION

The success of constraint programming comes from its efficiency to solve combinatorial problems once they are represented as a constraint network. However, the design of the original model, that is, the construction of the set of constraints defining the problem, remains a delicate task that requires some expertise in constraint programming. This is a bottleneck in the use of constraint solvers by non-experts.

There already exist several techniques to tackle this bottleneck. In [START_REF] Freuder | Suggestion strategies for constraint-based matchmaker agents[END_REF], the matchmaker agent is an interactive process where the user is able to provide one of the constraints of her target problem each time the system proposes an incorrect solution. In [START_REF] Gelain | Elicitation strategies for soft constraint problems with missing preferences: Properties, algorithms and experimental studies[END_REF], a preference elicitation mechanism solves soft constraint problems where some of the preferences are unspecified. The idea is to combine a branch&bound search with elicitation steps where candidate solutions are presented to the user who provides missing preferences on the variables. When restricted to hard constraint problems (that is, preferences are either accept or reject), this approach becomes very close to the matchmaker agent, requiring the user to be able to express her constraints one by one. In Conacq and ModelSeeker the assumption is made that the only thing the user is able to provide is examples of solutions and non-solutions of the target problem or to answer membership queries, that is, classify as positive or negative examples proposed by the system [START_REF] Bessiere | Leveraging the learning power of examples in automated constraint acquisition[END_REF], [START_REF] Bessiere | A SAT-based version space algorithm for acquiring constraint satisfaction problems[END_REF], [START_REF] Bessiere | Querydriven constraint acquisition[END_REF], [START_REF] Lallouet | On learning constraint problems[END_REF], [START_REF] Beldiceanu | A model seeker: Extracting global constraint models from positive examples[END_REF]. Based on these classified examples, the system learns a set of constraints that correctly classifies all examples given so far. A common feature of these techniques is that they require positive examples, otherwise they can learn the (trivial) inconsistent constraint network. QuAcq is a recent learning system that is able to ask the user to classify partial queries [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF]. As opposed to membership queries, partial queries are assignments of only part of the variables of the problem. An interesting property of QuAcq is that it is not necessary that the user provides positive examples to converge. This property opens the door to a new type of use: solve a problem without modeling it even if the user does not have examples of past solutions.

In this paper, we propose ASK&SOLVE, an elicitationbased algorithm that solves an unknown constraint network by asking queries to the user. ASK&SOLVE tries to find the best tradeoff between learning and solving to converge on a solution with as few queries to the user as possible. Based on the ASK&SOLVE algorithm we propose several strategies (restart policies / variable ordering) to speed-up even more convergence on a solution. We experimentally evaluate our approach on several benchmark problems. The results show that ASK&SOLVE improves the basic technique based on QuAcq.

The rest of the paper is organized as follows. Section II gives the necessary definitions to understand the technical presentation. Section III describes the basic algorithm ASK&SOLVE. In Section IV, several strategies (restart policies and variable ordering) are presented. Section V presents the experimental results we obtained when comparing ASK&SOLVE to existing techniques and when comparing the different restart policies / variable ordering in ASK&SOLVE. Section VI concludes the paper and gives some directions for future research.

II. BACKGROUND

We introduce some useful notions in constraint programming and concept learning. The common knowledge shared between a learner that aims at solving the problem and the user who knows the problem is a vocabulary. This vocabulary is represented by a (finite) set of variables X and domains D = {D(x i )} xi∈X over Z. A constraint c represents a relation on a subset of variables var(c) ⊆ X that specifies which assignments of var(c) are allowed. Combinatorial problems are represented with constraints networks. A constraint network is a set C of constraints on the vocabulary (X, D). An example e is a (partial) assignment on a set of variables var(e) ⊆ X. e is rejected by a constraint c iff var(c) ⊆ var(e) and the projection e[var(c)] of e on var(c) is not in c. A complete assignment e of X is a solution of C iff for all c ∈ C, c does not reject e. We denote by sol(C) the set of solutions of C.

The projection C[Y ] of C on a subset Y of X is the set {c ∈ C | var(c) ⊆ Y }.
In addition to the vocabulary, the learner owns a language Γ of relations from which it can build constraints on specified sets of variables. A constraint bias is a collection B of constraints built from the constraint language Γ on the vocabulary (X, D).

In terms of machine learning, a concept is a Boolean function over D X = Π xi∈X D(x i ), that is, a map that assigns to each example e ∈ D X a value in {0, 1}. We call target concept the concept f T that returns 1 for e if and only if e is a solution of the problem the user has in mind. In a constraint programming context, the target concept is represented by a target network denoted by C T .

A query Ask(e Y ), with Y ⊆ X, is a classification question asked to the user, where e Y is an assignment in

D Y = Π Xi∈Y D(X i ). A set of

III. SOLVE BY ASKING AND LEARNING

In this section we present ASK&SOLVE, an algorithm for solving a problem without having a constraint network describing it. The idea in ASK&SOLVE is to try to extend step by step a scope on which we know at least one assignment accepted by the target network C T . Each time there is a chance that the assignment generated by ASK&SOLVE violates one of the constraints in the bias B, ASK&SOLVE asks the query to the user. If the answer to the query is negative, ASK&SOLVE immediately launches a procedure that learns a culprit constraint to avoid generating again an assignment rejected for the same reason.

A. Description of ASK&SOLVE

In lines 1 to 5, ASK&SOLVE initializes several variables that will be used in the main loop. The learned network C L and the scope scp to be extended during search for solution are initialized to the empty set. The set guilty will contain the new variable to be added to the scope scp each time the assignment produced on scp was accepted by the user. guilty is also initialized to the empty set. The counter #negativeanswers counts the number of queries classified negative by the user. It is initialized to zero. #negative-answers is useless in the basic version of ASK&SOLVE but it will be used in versions that implement a restart policy. Finally, the flag F ound, that will break the loop once a solution is found, is set to false.

The main loop in ASK&SOLVE (line 6) starts by computing an assignment e on scope scp (line 7). We look for an assignment satisfying all constraints already learned (in C L ) and hopefully satisfying also all constraints from the bias B that do not involve the new variable guilty. Among the possible candidates, we choose the e that maximizes the number of constraints involving the variable guilty that are satisfied. The reason for trying to satisfy all constraints of B on scp is that if e is classified as negative, we know the variable guilty is involved in a violated constraint. The reason for maximizing the remaining constraints from B is that if C T is representable by the initial bias and if e is classified positive, e is an assignment as close as possible to the solution. However, it is not always possible to generate such an assignment. If not possible (line 8), we compute an assignment that satisfies the current C L and maximizes the satisfied constraints in B (line 10). Satisfying C L is always possible by extending the previous example with any variable assigned to any value. We also set guilty to the empty set because we are no longer sure the variable in guilty will belong to a violated constraint in case e is classified negative. If there are constraints in B able to reject e (i.e., κ B (e) = ∅), the query Ask(e) is presented to the user. If her answer is 'no', we know that e violates at least one constraint in the target problem C T . The functions FindC and FindScope are called to find such a constraint.

We do not give the code of functions FindScope and FindC. They are implemented as they appear in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF], and they are instrumented so that we increment the variable #negative-answers each time a query is answered negatively by the user. Let us say a few words on how they work. Given sets of variables S 1 and S 2 , FindScope(e, S 1 , S 2 , f alse) returns the subset of S 2 that, together with S 1 forms the scope of a constraint in B that rejects e. Inspired from a technique used in QUICKXPLAIN [START_REF] Junker | Quickxplain: Preferred explanations and relaxations for over-constrained problems[END_REF], FindScope requires a number of queries logarithmic in |S 2 | and linear in the size of the final scope returned. The function FindC takes as parameter the negative example e and the scope returned by FindScope. It returns a constraint from C T with the given scope that rejects e. Now, coming back to line 12, the call to FindScope returns the set of variables that together with guilty form the scope of one of the violated constraints. Remember that if e comes from line 7, guilty contains the new variable that belongs to the scope of a violated constraint whereas if e comes from line 10 we are not sure that guilty belongs to a constraint in B violated by e. But this is fine because in this case guilty is empty. Once a scope is returned by FindScope, FindC returns a constraint from B with that scope that rejects e. The constraint found is added to the learned network C L (line 14). If FindC has not found any constraint in B rejecting e, this means that our initial bias was not able to represent C T . ASK&SOLVE returns a collapse (line 13).

We do not describe lines 15-17 as we are in the basic version of the algorithm where restart() always returns +∞. In line 18 we are in the case where the user answered 'yes' to the query. We first test if scp was complete. If yes, this means that e is a solution and we return it (lines 18 and 22). If not, we extend scp with a new variable guilty chosen in the remaining variables (lines 19-20) and we remove all constraints violated by e from the bias (line 21).

IV. STRATEGIES

ASK&SOLVE learns constraints by asking queries during search. Solving an instance by asking as few queries as possible requires to find the good tradeoff between learning and solving. If we try to go fast to a complete assignment, this can lead to expensive constraint elicitation steps on long negative assignments when the problem is critically constrained. If we promote exploring first plenty of short assignments, this allows a fast and cheap learning of constraints, but it can be a waste of time if the problem is easy to solve. We first analyse the behavior of ASK&SOLVE on a sample problem. Based on this analysis, we propose several strategies of exploration of the search space that try to get the best tradeoff between learning and solving and thus to reach a solution as fast as possible.

A. Analysing ASK&SOLVE behavior

We take the well-known zebra problem from Lewis Carroll [7]. The zebra problem has a single solution, which makes it challenging to solve by hand. (It is claimed that only 2% of the population can solve it.) This is thus a good candidate to push our algorithm to the edge. We solved the zebra with our basic version of ASK&SOLVE presented in Section III (that is, with the function restart() in line 15 returning +∞). Figure 1(a) shows how the size scp of the variable assignment evolves during search in ASK&SOLVE (the x-axis is the number of iterations of the while loop in line 6 of ASK&SOLVE). We see that the size of the assignment grows with the number of iterations. This means that, in case of negative answer, the space in which we seek a culprit constraint grows, and thus the cost to find it grows as well. To validate this guess we can observe Figure 1(b). It shows how many queries are asked each time the example generated at the beginning of the while loop of ASK&SOLVE is negative. As the plot is sawtoothed, we drew its approximation of Bezier as interpolation to exhibit the main trend (thick line in Figure 1(b)). We observe that the average number of queries per iteration indeed increases with the number of iterations.

Figure 1 shows that extending too fast the scope on which we look for an assignment leads to a higher cost in number of queries. A technique to avoid remaining on long scopes with long sequences of negative answers is to incorporate a restart policy in ASK&SOLVE. The idea is to count how many negative examples were generated in a row and to restart when a cutoff value is reached.

B. Restart policies

Restart policies have been a long-held goal in AI and they are one of the approaches developed to boost combinatorial search. We propose to use three restart policies that triggers a restart in line 16 of Algorithm 1 when the number of negative answers is greater than or equal to the cutoff value returned by restart().

• Fixed cutoff. The first policy uses a fixed cutoff, noted (FC). This is done by implementing the function restart() so that it always returns |X|. • Geometric. The second policy is the Geometric strategy [START_REF] Walsh | Search in a small world[END_REF]. The cutoff value returned by restart() grows geometrically by a factor of 1.5. We use an initial cutoff size of |X|. • Luby. The third policy we selected is more elaborated. In this case the restart() function implements the universal Luby-restarts policy defined in [START_REF] Luby | Optimal speedup of las vegas algorithms[END_REF]. The Luby-restarts policy is given by the sequence (1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8, 1, . . .) that is multiplied by the factor |X|. Such a policy has been used with great success in SAT solvers [START_REF] Huang | The effect of restarts on the efficiency of clause learning[END_REF]. The goal is, on the one hand to cut the search early enough to escape from bad subtrees and to produce short nogoods, and on the other hand to let the solver the chance to go to a solution. The similarity of this goal and ours led us to try Luby in our setting. The number #negative-answers of negative answers from the user is reset either when we trigger a restart in line 16, or in line 17 when the user has classified as positive (in line 11) an assignment e computed in line 7 or in line 10.

C. Variable ordering heuristics

When we use a restart policy, the question raises of the order in which to select variables in the search following immediately the restart. We tested and compared the following variable ordering heuristics.

• random (RAND). At each restart event, we reorder the variables randomly. • lexicographic (LEX). Here we use the basic lexicographic order. When a restart occurs, we restart on the same variable order:

x 1 , x 2 , x 3 restart ---→ x 1 , x 2 , x 3 , x 4 . . . • reverse-lex (R-LEX).
The algorithm is initialized with a LEX order on the variables. Once a restart event occurs, the variables in the scope scp are reversed: we start by selecting the last variable that was added to scp and continue until the first. If we reach the first (that is, we exhausted all variables from that previous scope), we select the remaining variables in the same order as they were ordered before the restart. And so on.

x 1 , x 2 restart ---→ x 2 , x 1 , x 3 , x 4 restart ---→ x 4 , x 3 , x 1 . . . • countinuous-lex (C-LEX).
Here we use a variant of the lexicographic order. At the beginning we have a LEX order on the variables. Once a restart event occurs, we select the last variable in scp and we continue on the same LEX order. (This LEX order has to be circular:

x n is followed by x 1 .) This heuristic allows the search process to explore the variables in a balanced way.

x 1 , x 2 , x 3 restart ---→ x 3 , x 4 restart ---→ x 4 , x 5 , x 6 . . .

V. EXPERIMENTAL EVALUATION

We made some experiments to evaluate the performance of our ASK&SOLVE algorithm and the restart policies we proposed. The first part of this section is devoted to the comparison of existing techniques to our baseline version of ASK&SOLVE presented in Algorithm 1 (with restart() = +∞). The second part of the section evaluates the different restart policies and variable orderings we proposed.

Our tests were conducted on an Intel Core i7 @ 2.9 GHz with 8 Gb of RAM. We used the following benchmarks:

• Golomb Rulers. (prob006 in [START_REF] Gent | Csplib: a benchmark library for constraints[END_REF]) The problem aims at finding a ruler where the distance between any two marks is different from that between any other two marks. The target network is encoded with m variables corresponding to the m marks, and constraints of varying arity. For our experiments, we selected the 8-marks ruler. • Zebra Problem. Lewis Carroll's zebra problem has a single solution. The target network is formulated using 25 variables of domain size of 5 with 5 cliques of = constraints and 14 additional constraints given in the description of the problem [7].

• Purdey's general store. This problem is described by Jo Mason in [START_REF] Mason | Purdey's general store[END_REF]. It has a single solution. Four families stopped by Purdey's general store, each to buy a different item and paying differently. Under a set of additional constraints given in the description, the problem is how can we match family with the item they bought and how they paid for it.

A. Basic ASK&SOLVE against other techniques

We first want to confirm that our ASK&SOLVE architecture goes in a direction that makes it a good candidate for solving unknown constraint problems without having to model them. We compared ASK&SOLVE to three other techniques that are able to solve by asking queries.

The first one that we can use is standard QuAcq as presented in [START_REF] Bessiere | Constraint acquisition via partial queries[END_REF] that we stop as soon as a solution is found (called QUACQ&SOLVE below).

The second one is a simple backtrack search procedure that asks the user about the validity of the assignment generated at a node of the search tree each time the currently learned constraints do not allow it to infer the answer. If the query is classified as positive we reduce the bias B, otherwise we learn a constraint using the QuAcq principle (i.e., we call a FindScope and a FindC functions on the negative -partial-example). This technique is denoted by BACKTRACK-E.

The last technique, BRANCH&LEARN, is the backtrack search based on elicitation proposed in [START_REF] Bessiere | Branch and learn pour l'acquisition de csp[END_REF]. The approach is very similar to BACKTRACK-E in the way it explores assignments. However, it differs in the way it learns the constraints. BRANCH&LEARN learns constraints using Conacq instead of QuAcq. Each time an example e is classified positive, BRANCH&LEARN reduces the bias B as in BACKTRACK-E. But each time e is classified negative, BRANCH&LEARN does not ask anything to the user. It simply stores a disjunction representing the set of candidate constraints in B rejecting e. At least one of them has to be in the target network. Table I displays the comparative performance of QUACQ&SOLVE, BACKTRACK-E, BRANCH&LEARN, and ASK&SOLVE. We report the size |C L | of the partially learned network (which represents the set of constraints learned during search), the total number #q of queries, and the average time needed to compute a query (in seconds).

The first observation we can make when comparing QUACQ&SOLVE and BACKTRACK-E is that QUACQ&SOLVE learns more constraints than BACKTRACK-E (column |C L | in Table I). This is because QUACQ&SOLVE promotes learning constraints and then finds the solution by chance whereas BACKTRACK-E promotes searching and is forced to learn when it fails to extend its assignment. This observation explains why BACKTRACK-E needs less queries than QUACQ&SOLVE.

Concerning BRANCH&LEARN, we cannot report the size of the learned network C L because it stores a set of disjunctions of constraints without being able to choose a culprit among them. The number of queries needed by BRANCH&LEARN to find a solution is better than that of BACKTRACK-E on the instances it could solve in less than 10 hours. This lower number of queries is due to the lazy strategy used in BRANCH&LEARN: after a negative answer, BRANCH&LEARN does not elucidate a culprit constraint, as done in BACKTRACK-E with the call to FindScope and FindC. The counterpart to this lazy behavior is that BRANCH&LEARN explores a lot of nodes, leading to prohibitive cpu times when the problem is not small enough. For instance, on Golomb, the average time between two queries to the user is 76 seconds. On Zebra, the whole process had not finished in 10 hours.

Concerning ASK&SOLVE, we see that it is incomparable to QUACQ&SOLVE and BACKTRACK-E in terms of the number of learned constraints. It generates the smallest C L on Golomb but the largest on Zebra. However, ASK&SOLVE is consistently faster than the other techniques in terms of the number of queries needed to find a solution. This tends to show that ASK&SOLVE promotes the learning side or the solving side depending on the difficulty of the instance to solve, and then reaches a better tradeoff than QUACQ&SOLVE and BACKTRACK-E.

B. Evaluation of the strategies

In this section we assess the performance of our restart policies and the variable orderings described in Section IV. To speed-up ASK&SOLVE in terms of number of queries, we implemented the three restart policies:

Table II displays the comparative performance of all possible strategies on the same three problems as in Section V-A: Golomb, Zebra and Purdey's general store problems. A strategy is a combination (restart policy × variable ordering). Each strategy has a row in Table II.

The first observation that is obvious from Table II is that all techniques are very fast. They can easily be used in an interactive process, as opposed to BRANCH&LEARN, as seen in the experiments in Table I.

The second information we can draw from Table II is that the choice of the order in which variables are selected after a restart can noticeably affect the efficiency of ASK&SOLVE. RAND and LEX are not efficient variable ordering heuristics to be used by our restart policies. This is obvious for RAND, which is almost always much worse than the baseline ASK&SOLVE with no restart policy. This is also true for LEX, to a lesser extent. Among R-LEX and C-LEX, we see that R-LEX wins more often and with greater margins than C-LEX.

Comparing the three restart policies, ASK&SOLVE with Geometric or Luby is significantly better than with FC. This is true on all problems. This confirms what we expected from the observation of Figure 1: increasing the scope too fast and spending time on long scopes is a waste of time when answers are repeatedly negative.

Finally, if we look at the combinations restart pol-icy+variable ordering, the best compromise is Geometric+R-LEX.

When associated with Luby, C-LEX requires less queries on Golomb, but the difference with Luby+R-LEX is tiny: only 2 more queries for Luby+R-LEX.

Luby with C-LEX seems to be the best deal to solve Golomb rulers. This is related to the nature of the Golomb rulers. In Golomb rulers, we have an order on the marks. Using C-LEX, ASK&SOLVE can learn this order with less queries. Furthermore, Golomb rulers contain a set of notequal constraints on distances. Here also, the use of small restarts as in Luby can speed-up the resolution.

On Zebra (resp. Purdey), Geometric+R-LEX requires 35 (resp. 27) less queries than +C-LEX. As a general conclusion of these experiments, we see that using strategies in ASK&SOLVE improves the performance significantly compared to the baseline ASK&SOLVE without restart. If we compare Geometric+R-LEX to baseline ASK&SOLVE, the saving in number of queries is 7% on Golomb, 32% on Zebra, and 64% on Purdey.

VI. CONCLUSION

We have proposed ASK&SOLVE, an elicitation based algorithm that solves a constraint problem without the need of a constraint network representing it. The elicitation here consists in asking the user to classify partial assignments as positive or negative. We present several strategies (restart policies and variable orderings) to improve the behavior of ASK&SOLVE. Our experimental evaluation shows that ASK&SOLVE presents a good tradeoff between learning and searching for solutions. It outperforms the other techniques by solving problems with less queries. When enhanced with the right strategy, its performance becomes even better. These results are promising for the use of ASK&SOLVE on real problems because there exist several other techniques that could be plugged in ASK&SOLVE to decrease even more the number of queries. We could for instance embed ModelSeeker as an internal stepofASK&SOLVE to quickly learn global constraints each time we get a partial positive.

Algorithm 1 :

 1 ASK&SOLVE: Solving an unknown constraint network C T by asking user queries 1 CL ← ∅; 2 scp ← ∅; 3 guilty ← ∅; 4 #negative-answers ← 0; 5 F ound ← f alse; 6 while ¬F ound do 7 select e in sol(CL[scp] ∪ B[scp \ guilty])[scp] maximizing satisfaction of B[scp]; 8 if e = nil then 9 guilty ← ∅; 10 select e in sol(CL[scp])[scp] maximizing satisfaction of B[scp]; 11 if κB(e) = ∅ and Ask(e) = no then 12 c ← FindC(e, FindScope(e, guilty, scp\guilty, f alse) ∪ guilty); 13 if c = nil then return "collapse"; 14 else CL ← CL ∪ {c}; 15 if #negative-answers ≥ restart() then 16 scp ← ∅; #negative-answers ← 0; else 17 #negative-answers ← 0; 18 if scp = X then F ound ← true; else 19 guilty ← {a variable in X \ scp}; 20 scp ← scp ∪ guilty; 21 B ← B \ κB(e); 22 return e;

Figure 1 :

 1 Figure 1: Variation of the size of the examples and of the number of queries per iteration of the while loop in ASK&SOLVE (Zebra problem).

  constraints C accepts a an assignment e Y if and only if there does not exist any constraint c ∈ C rejecting e Y . The answer to Ask(e Y ) is "yes" if and only if C T accepts e Y . For any assignment e Y on Y , κ B (e Y ) denotes the set of all constraints in B rejecting e Y .

Table I :

 I ASK&SOLVE vs existing elicitation-based solvers

			|CL| #q	time
	Golomb	QUACQ&SOLVE BACKTRACK-E BRANCH&LEARN	111 548 46 432 -389 76.01 0.21 0.16
		ASK&SOLVE	21 179	0.35
		QUACQ&SOLVE	58 623	0.02
	Zebra	BACKTRACK-E BRANCH&LEARN	51 528 --	0.06 -
		ASK&SOLVE	60 509	0.02
	Purdey	QUACQ&SOLVE BACKTRACK-E BRANCH&LEARN	18 157 15 119 -109	0.01 0.01 0.61
		ASK&SOLVE	14 103	0.01

Table II :

 II Various strategies for boosting ASK&SOLVE

	RESTART	VAR-ORDER	|C L |	#q	time
		none	LEX	21 179	0.35
			RANDOM	48 435	0.24
		FC	LEX R-LEX	21 174 30 232	0.34 0.30
			C-LEX	28 203	0.35
	Golomb	Geometric	RANDOM LEX R-LEX C-LEX	56 527 21 202 21 166 21 162	0.27 0.33 0.28 0.31
			RANDOM	45 402	0.31
		Luby	LEX R-LEX	21 161 21 160	0.34 0.33
			C-LEX	11 158	0.32
		none lex	60 509	0.02
			RANDOM	57 560	0.05
		FC	LEX R-LEX	63 558 53 452	0.02 0.05
			C-LEX	59 459	0.03
	Zebra	Geometric	RANDOM LEX R-LEX C-LEX	59 503 60 482 48 346 59 381	0.02 0.05 0.03 0.04
			RANDOM	57 484	0.05
		Luby	LEX R-LEX	60 537 41 356	0.03 0.03
			C-LEX	57 465	0.02
		none	LEX	14 103	0.01
			RANDOM	16 106	0.01
		FC	LEX R-LEX	13 108 11 88	0.01 0.02
			C-LEX	12	82	0.01
	Purdey	Geometric	RANDOM LEX R-LEX C-LEX	16 12 8 15	99 77 37 64	0.02 0.01 0.02 0.01
			RANDOM	16 123	0.01
		Luby	LEX R-LEX	12 9	86 62	0.01 0.02
			C-LEX	11	83	0.01

• Restarting after |X| negative answers (FC).• The geometric restart policy with an initial restart of |X| negative answers and a growth coefficient of 1.5. • A luby restart policy with an initial restart of |X| negative answers. We also implemented the different variable ordering heuristics (RAND, LEX, R-LEX and C-LEX).

ACKNOWLEDGMENT

This work has been funded by the EU project ICON (FP7-284715) and by the ANR project BR4CP (ANR-11-BS02-008).