Jagdish Prasad Achara
email: jagdish.achara@inria.fr

Javier Parra-Arnau

Claude Castelluccia
email: claude.castelluccia@inria.fr

MyTrackingChoices: Pacifying the Ad-Block War by Enforcing User Privacy Preferences

Keywords: Ad blocking, privacy, economy

Free content and services on the Web are often supported by ads. However, with the proliferation of intrusive and privacy-invasive ads, a significant proportion of users have started to use ad blockers. As existing ad blockers are radical (they block all ads) and are not designed taking into account their economic impact, ad-based economic model of the Web is in danger today.

In this paper, we target privacy-sensitive users and provide them with fine-grained control over tracking. Our working assumption is that some categories of web pages (for example, related to health, religion, etc.) are more privacy-sensitive to users than others (education, science, etc.). Therefore, our proposed approach consists in providing users with an option to specify the categories of web pages that are privacy-sensitive to them and block trackers present on such web pages only. As tracking is prevented by blocking network connections of third-party domains, we avoid not only tracking but also third-party ads. Since users will continue receiving ads on web pages belonging to non-sensitive categories, our approach essentially provides a trade-off between privacy and economy. To test the viability of our solution, we implemented it as a Google Chrome extension, named MyTrackingChoices (available on Chrome Web Store). Our real-world experiments with MyTrackingChoices show that the economic impact of ad blocking exerted by privacy-sensitive users can be significantly reduced.

I. INTRODUCTION

According to PageFair 2015 report [START_REF]The cost of Ad Blocking, PageFaire and Adobe Ad Blocking Report[END_REF], 45 million Americans (16% of online users) and 77 million Europeans had installed ad blockers 1 as of the second quarter of 2015. All this globally accounts for 21.8 billion dollars worth of blocked ads in the year 2015. Since ads fuel the free content and services over the Web, this monetary loss puts the adbased economic model of the Web under threat. The nature of this threat has become more devastating over time since, in the early days of online advertising, ad industry ignored this potentially dangerous situation in favor of immediate benefits.

Users generally block ads due to an unpleasant adexperience, which could be a fallout of several concerns. Some users simply do not want to see ads, while others block ads because they find them too annoying (in terms of usability) or perceive them as a source of privacy and/or security issues on the Web [START_REF]The cost of Ad Blocking, PageFaire and Adobe Ad Blocking Report[END_REF], [START_REF] Marti | Targeted Advertising Considered Harmful[END_REF], [START_REF]A Way to Peace in the Adblock War[END_REF], [START_REF]Profiling Adblockers[END_REF], [5], [START_REF]Why Millennials Block Ads[END_REF], [START_REF]Why do people block online ads?[END_REF], [START_REF] Brenner | Survey on search engine use[END_REF], [START_REF] Turow | Americans reject tailored advertising and three activities that enable it (september 29[END_REF]. In fact, the 1 All tools that eventually end up blocking ads even though they are initially designed for some other purpose (privacy, transparency, etc.) reasons behind ad blocking are not mutually exclusive and some users may block ads as a result of their combinations. Apparently, the general ad-experience has deteriorated over the last few years, and this has resulted into an unprecedented use of ad blockers on the Web.

Apart from the poor ad-experience, radical design choices adopted by ad blockers is another reason why ad blocking has become a threat to the Web economy today. A scrutiny of current ad blockers further reveals that they do not take into account: 1) the economic impact of ad blocking, and 2) the social and economic benefits of non-intrusive and rational advertising. This demands better tools that cater to users' concerns, while at the same time are designed to ensure that their economic impact does not get sidelined.

In this work, we address the evoked concerns by proposing a three-dimensional approach that combines user privacy, ad blocking and its economic impact. We target users who are not against ads but block them due to privacy concerns. Our working assumption is that users consider their visits to some web pages (for example, related to religion, health) more privacy-sensitive than to others (such as news, sports) [START_REF] Giovanni Leon | What matters to users?: Factors that affect users' willingness to share information with online advertisers[END_REF], [START_REF] Chanchary | User perceptions of sharing, advertising, and tracking[END_REF]. Therefore, our approach consists in providing users an option to specify the categories of web pages where they do not want to be tracked and thus, do not want to receive third-party ads 2 . Unlike current ad blockers, it allows users to continue receiving ads on categories of web pages that they consider non-sensitive. In concrete terms, the proposed approach attempts to find a trade-off between privacy and economy.

To test the viability of our approach, we have developed an extension for Google Chrome called MyTrackingChoices3 . While users browse the web, the extension categorizes the visited web page on the fly and, depending on the users' choices, it blocks the network connections of third-party domains present on the web page. As tracking is prevented by blocking third-party network requests, we avoid not only tracking but also third-party ads. It is worth noting that, unlike other ad blockers, our extension does not block ads served directly from the publisher on both sensitive and non-sensitive web pages.

Contributions. We make the following contributions in this paper.

• We review existing ad blockers for their design choices and the ensuing impact on the Web economy. Our findings reveal that their approach to ad blocking is not appropriate both to users and the economy. We also show that current self-regulatory initiatives by the ad industry and various other organizations are not sufficient because users' choices are not guaranteed to be enforced. • Building on the lessons learned, we propose a new approach that is user-centric and gives fine-grained control to users. Being user-centric ensures that user privacy and ad preferences are enforced on the user-side while fine-grained control provides users a a trade-off between privacy and economy. Our solution consists in providing users with an option to select categories of web pages that are privacy-sensitive to them and block network connections of third-party domains (and thus, ads delivered through third-party domains) present on such web pages. To test the viability of our proposed approach, we implement it as a Google Chrome extension. • We present some preliminary results based on the pseudoanonymous data collected from 96 users of the MyTrack-ingChoices extension. Our results regarding the impact of MyTrackingChoices on the Web economy show that the economic impact of ad blocking exerted by privacysensitive users can be significantly reduced. We also evaluate the usability and the performance aspects of MyTrackingChoices which confirm that it can be adopted on a wide scale. Outline. Section II discusses the problems and perspectives associated to existing ad blockers. In Section III, we present our new approach to ad blocking and its implementation as MyTrackingChoices. The impact of MyTrackingChoices on the Web economy is evaluated in Section IV whereas Section V assesses the usability and performance of MyTrackingChoices. In the end, Section VI measures the presence of third-party domains and Section VII concludes our paper with some directions for future work.

II. EXISTING AD BLOCKERS: PROBLEMS AND PERSPECTIVES

Due to proliferation of intrusive 4 and privacy-invasive ads, ad blockers have become very popular. They can be divided into two classes: "ad blockers" and "anti-trackers". Ad blockers are those which exists solely for blocking ads whereas antitrackers exist for other reasons like privacy and transparency, but eventually block ads. Some examples of ad blockers are AdBlock [START_REF] Gundlach | AdBlock[END_REF], AdBlock Plus [START_REF]Adblock plus[END_REF], etc. whereas Ghostery [START_REF] Ghostery | [END_REF], Disconnect [START_REF]Disconnect[END_REF], PrivacyBadger [START_REF]Privacy badger[END_REF] are examples of antitrackers. In terms of functionalities, ad blockers in the first class block all ads whereas anti-trackers allow users to block a particular tracker or a particular category (related to analytics, privacy, advertising, etc.) of trackers or trackers on a per domain basis. Considering this distinction in terms of their functionalities and objectives, in the remainder of this section, we make the distinction between them.

Problem with current ad blockers and anti-trackers. Ad blockers are too radical because they take a binary approach towards ad blocking, i.e., they block all ads. Additionally, as they simply block all ads by default and do not let users configure their choices, it is evident that the developers have not considered their economic impact on the Web.

Anti-trackers give users the option to decide by which trackers or category of trackers they do not want to be tracked. However, we argue that most users are not concerned with the trackers but the other dimension of tracking, i.e., on which web pages they do not want to be tracked. In this respect, anti-trackers let users decide to block trackers on a per domain basis, i.e., users can whitelist or blacklist a specific domain. However, we argue that domain-level granularity is not the right approach for three reasons:

1) Given the huge number of domains, it is almost impossible for users to determine and pre-define all the domains where they do not want to be tracked. 2) Some domains can host web pages belonging to different categories, for example, belonging to both sensitive (health, religion, etc.) and non-sensitive (sports, science, etc.) categories [START_REF]Handbook on European data protection law[END_REF]. Domains belonging to the "news" category, e.g., cnn.com or bbc.com, are good examples because they usually include web pages from a variety of categories (sports, economy, politics, health, travel, religion, etc.). Therefore, except some domains that have all web pages belonging to a same category, it makes more sense to block trackers based on the category of the web page and not on a per domain basis. In fact, page-granular (and not domain-granular) blocking makes more sense both from users' privacy point of view and with respect to reducing the economic damage incurred by publishers. The reason being that, for a given domain, ads would eventually be blocked only on web pages belonging to sensitive categories chosen by users and not on the whole domain. 3) Blocking trackers based on the category of web pages (instead of configuring it for each and every domain) makes it easier for users to configure as they just need to select once the categories of web pages that are sensitive to them. As the number of web page categories are limited, these pre-defined categories can be made available to the user when the tool is installed and user choices can be respected from the very beginning.

With the exception of PrivacyBadger [START_REF]Privacy badger[END_REF], another issue with existing ad blockers and anti-trackers is that, in order to block trackers or ads, they rely on black-lists manually maintained by their developers or, in some cases, by user communities. The use of these lists by AdBlock Plus [START_REF]Adblock plus[END_REF], currently the most popular among ad blocking tools, stirred controversy for accepting money from some ad companies to whitelist them [START_REF] Cookson | Google, Microsoft and Amazon pay to get around ad blocking tool[END_REF], [START_REF]Adblock plus[END_REF]. Furthermore, it is very cumbersome to maintain these lists as 1) new trackers and/or ad companies keep appearing in the market and 2) already existing companies keep introducing new mechanisms to deliver ads.

Self-regulatory initiatives by the ad industry are not appropriate. Without giving control to the user (i.e., providing users a tool), various self-regulatory initiatives [START_REF]Getting LEAN with Digital Ad UX[END_REF], [START_REF]Acceptable Ads Manifesto[END_REF] from the ad industry have proposed solutions to counter some of the concerns behind ad blocking (like annoyance, usability and performance). These efforts envisage to improve the ad experience for users but none of them gives the control back to users. Moreover, these initiatives from the ad industry do not take into account the privacy concerns behind ad blocking even though various studies confirm that a non-negligible number of users block ads because of privacy concerns [START_REF]The cost of Ad Blocking, PageFaire and Adobe Ad Blocking Report[END_REF], [START_REF]Profiling Adblockers[END_REF], [5]. The LEAN program from IAB talks about non-invasive ads but it is not in terms of privacy [START_REF]Getting LEAN with Digital Ad UX[END_REF]. "Acceptable ads manifesto" include five points to improve the ad-experience and thus, making them acceptable. However, none of these five points tackles privacy concerns [START_REF]Acceptable Ads Manifesto[END_REF].

Other examples of self-regulatory initiatives are "Your online choices" (from a group of European organizations) [START_REF]YourOnlineChoices[END_REF] and DNT (from World Wide Web Consortium) [START_REF]Tracking preference expression (DNT)[END_REF]. Your online choices lets users block ads tailored to their web browsing interests but users can never be sure if their choices are actually honored and if they are still being tracked. These initiatives do not suffice since users' choices are not technically enforced at the user side. Similarly, DNT allows users to notify websites and ad industry if they want to stop being tracked through third-party cookies. However, the problem of enforcement of user choices still persists.

III. MYTRACKINGCHOICES

As we have discussed in the Section II, current ad blockers and existing self-regulatory initiatives are not appropriate to tackle the current threat to ad-based economic model of the Web. Today there is a need of better tools that give users more fine-grained control over tracking and thus, third-party ads.

A. New approach to ad blocking

We propose a different approach as a solution to the aforedescribed concerns. Our approach targets users who are not against ads but block them due to privacy reasons. It is based on the assumption that most people do not want to be tracked on "sensitive" websites (for example, related to religion, health), but accept to be tracked and receive ads on less sensitive ones (such as news, sport) to support the content provider.

The underlying objective is to sustain the ad-based economic model of the Web and hence, is in contrast to the design rationale of existing ad blockers. The idea is to let users choose the categories of web pages that are privacysensitive to them (for example, health, religion) and exclusively block the respective trackers and/or ads on those web pages. The granularity of selecting where users accept ads gives it an advantage over other ad blockers in various respects as mentioned in Section II. Thanks to our approach, users can continue receiving profile-based targeted ads5 on categories of web pages they accept to be tracked.

Our approach does not follow an "all-or-nothing" policy as opposed to current ad blockers. We allow users to select the categories of web pages that they consider sensitive and do not want to be tracked and receive ads on. Additionally, users can be even more selective in the sense that they can block a web page without blocking the entire category. For instance, if a particular web page hosts intrusive ads that belongs to a non-sensitive category, users can selectively penalize it while allowing ads on other web pages in the same category. This feature may encourage publishers not to include intrusive ads on their web pages.

It is worth noting that our proposed approach is not a replacement but complements other initiatives of the ad industry [START_REF]Getting LEAN with Digital Ad UX[END_REF], [START_REF]Acceptable Ads Manifesto[END_REF]. While these initiatives aim to improve the quality of ads delivered to users, we give the onus to users to decide where they want to accept tracking and third-party ads. We emphasize that users who outrightly reject all ads are not considered. Other economic models (for example, subscription-based access to the content) must be put in place for such users [START_REF] Brave | [END_REF].

MyTrackingChoices is a tool that implements our approach and is described in more details in the following section.

B. Implementation Details

MyTrackingChoices is developed as Chrome extension and is available to download from Chrome Web Store [START_REF]MyTrackingChoices: Available to download at Chrome Web Store[END_REF]. In terms of functionalities, it allows users to block trackers (and thus, third-party ads) based on pre-defined categories of web pages or on a per web page basis. If users do not agree with the categorization of a web page by MyTrackingChoices, they are allowed to change the category of that web page. Users can also view the list of third-party domains present on a web page.

MyTrackingChoices extension on Chrome currently supports web pages in English, French, Spanish and Italian. This is due to the limitation of our current "Categorizer" module (described next) but we plan to extend support for more languages in the near future.

MyTrackingChoices is composed of three main modules namely "Categorizer", "Policy module", and "Blocking module". Below is the detailed description of these modules. We note that, in the rest of the paper, the terms "web page" and "URL" are interchangeably used.

1) Categorizer: This module classifies the pages visited by users into a predefined set of topic of interests. The module employs a 2-level hierarchical taxonomy, composed of 32 top-level categories and 330 bottom-level categories or subcategories. For the sake of usability, in the current version of the extension, we display and let users interact only with top-level categories. However, depending on the The categorization algorithm integrated into our system is partly inspired by the methodology presented in [START_REF] Kae | Categorization of display ads using image and landing page features[END_REF] for classifying non-textual ads into interest categories. The algorithm also builds on the taxonomy available with the Firefox Interest Dashboard plug-in [27] developed by Mozilla.

Our categorizer relies on two sources of previouslyclassified data. First, a list of URLs, or more specifically, domains and hostnames, which is consulted to determine the page's category. Here, it is worth noting that this list of URLs only contain domains that have all web pages belonging to a particular category. For instance, techcrunch.com contains all articles related to "technology & computing" category. Second, a list of unigrams and bigrams [START_REF] Manning | Foundations of Statistical Natural Language Processing[END_REF] that is used when the URL lookup fails. The former list is justified by the fact that a relatively small part of the whole Web accounts for the majority of the visits [START_REF] Gerbet | A Privacy Analysis of Google and Yandex Safe Browsing[END_REF]. It is evident that pre-categorized lookup requires few computational resources on the user's browser and can be more precise. The latter list, on the other hand, is justified as a fall-back and allows us to apply common natural-language heuristics to the words available in the URL, title, keywords and content of the web page.

To build the first list of URLs, we incorporate Alexa.com's 500 top Web sites for almost each of the top-level categories. The list also includes the domains and hostnames (around seven thousand) classified by Mozilla's Interest Dashboard plug-in [27].

On the other hand, in the list of unigrams and bigrams, we have approximately 76 000 entries for English language. Three additional lists of unigrams and bigrams, although with a fewer number of entries, are also available for French, Spanish and Italian. To compile all these words lists, we have built on the following data:

• a refined version of the categorization data provided by the Firefox Interest Dashboard extension; • a subset of the English terms available at WordNet 2.0 [START_REF] Miller | WordNet: A lexical database for english[END_REF] for which the WordNet Domain Hierarchy [START_REF] Magnini | Integrating subject field codes into wordnet[END_REF], [START_REF] Bentivogli | Revising wordnet domains hierarchy: Semantics, coverage, and balancing[END_REF] provides a domain label; • a subset of the terms available at the WordNet 3.0 Multilingual Central Repository [START_REF] Gonzalez-Agirre | Multilingual central repository version 3.0: upgrading a very large lexical knowledge base[END_REF], to allow the categorization of Web sites written in the aforementioned languages;

• and the synset-mapping data between the versions 2.0 and 3.0 of WordNet [START_REF] Daudé | Validation and tuning of wordnet mapping techniques[END_REF]. The categorizer module resorts to word lists only when the hostname and domain are not found in the URL list. When this happens, the algorithm endeavors to classify the page by using the unigrams and bigrams extracted from the following data fields: URL, title, keywords and content of the page. Depending on the data field in question, the categorizer assigns different weights to the corresponding unigrams and bigrams. In doing so, we can reflect the fact that those terms appearing in the URL, the title, and especially the keywords specified by the publisher (if available), are usually more descriptive and explanatory than those included in the body of the page.

As frequently done in information retrieval and text mining, our web page classifier also relies on the Term Frequency-Inverse Document Frequency (TF-IDF) model [START_REF] Salton | A vector space model for automatic indexing[END_REF]. Said otherwise, we weigh the resulting category(ies) based on the frequency of occurrence of the corresponding unigrams and bigrams in the web page, and on a measure of their frequency within the whole Web.

Based on the categorization using words, we have a score for each category depending on the algorithm above described. To select the categories that best represent a web page, we select all the categories that have a score larger than a threshold value, where threshold (T ) is defined as

T = α × (maximum score -average score),
where α is a constant and its value is chosen based on how much weight we want to give to accuracy versus completeness (false positives versus true negatives). In our current implementation, we choose α equal to 0.3. If there are less than three such categories, the web page is classified into all these categories. However, if there are more than three such categories, we pick only three top categories and categorize the web page into them. Thus, the maximum number of categories a page may belong to is upper bounded by 3.

For the sake of computational efficiency, the algorithm caches the categories derived from the user's last 500 visited pages. This way, when the user re-visits one of those pages, the interest-categories of these pages are obtained directly without needing to go through the whole process of categorization described above.

In terms of storage, the whole list of unigrams, bigrams and their corresponding IDF values occupies approximately 1 megabyte in compressed format. We believe this is an acceptable overhead in terms of the extension download size. Lastly, a manual inspection of the categorization results for a small collection of web pages indicates that the algorithm works reasonably well. Experimental results will show later in Section V-B that users are satisfied with our categorizer (only 18 web pages with erroneous categorization are reported from 12 users). However, further investigation is required to evaluate the performance of the categorizer in a more rigorous manner.

A potential approach to improve categorization. As seen in Section II, a web page should be categorized based on its content and not on its domain name except if all the pages in the domain belong to a particular category. This is because a particular domain can host web pages from several different categories. For example, domains belonging to the "news" category, such as cnn.com, usually include web pages from a variety of categories (sports, economy, politics, health, travel, religion, etc.). To this end, our tool takes a best-effort approach to categorization by deriving semantic information from several data associated to the web page such as URL, title, keywords and content. Unfortunately, this approach does not guarantee accuracy. A simple yet effective solution to this problem would be to recommend web developers to include the category of the web page in the <head>...</head> tag of the HTML code. One potential way to encourage Web developers in doing so would be to include our recommendation in the W3C best practices. Apart from the obvious advantage of a more accurate categorization, this solution also eliminates the extra overhead (in terms of computation, memory and network bandwidth) incurred by the tool to categorize a web page. However, enforcing developers to include (correct) categories in web pages is a challenging task.

2) Policy module: This module is responsible for applying the blocking policies defined by users. Policies can be defined either on per category basis or on per web page basis.

To simplify the implementation, our extension allows users to define only per category blocking policies. That is, instead of specifying categories of web pages where tracking should be allowed and categories of web pages where tracking should be blocked, we just enable the latter blocking declaration.

Fig. 1 shows the configuration panel where users may configure the per category blocking. After having installed the extension and before the extension starts functioning, users are presented with the options panel so that they can configure their choices (by default, no categories are blocked). Configuration of blocked categories can also be performed at a later stage by clicking on "configure your tracking choices" option in the popup page of MyTrackingChoices.

Contrary to the per category policies, users are allowed to configure both block and allow per URL policies. This is to allow users to be more granular if they are occasionally not satisfied with per category blocking policies. For example, in a scenario where a user has blocked a category of web pages but wants to support a specific web page in that category by receiving ads. Fig. 2 shows how the popup page of MyTrackingChoices looks like. It provides users with options to define per URL policies.

The operation of this module is described next. When a user visits a page, the module waits for the categorizer to send the topic category of the web page browsed. Being equipped with the URL as well as the category, the module decides whether the network connections of third-party domains should be blocked or not. We emphasize here that in case of a conflict between per web page and per category based policy, per URL based policy prevails. In case a web page is categorized in more than one category, if any of the category is selected by the user to be blocked, third-party network connections on that web page are blocked.

3) Blocking module: This module is responsible for blocking network connections of third-party domains if a user has selected to block them. There are two main tasks. First, finding third-party domains and then, second, to block them. To find third-party domains, we just need to check if the domains of network connections match with the domain the user typed in the address bar. If it is not the same, then, such domains can be considered as third-party domains.

The next task is to block network connections to such domains. However, blocking network connections of all thirdparty domains may break the functionality of some web pages. This is because of the fact that some web pages download useful content from other domains (a different domain belonging to the first-party domain or a content provider or some other domain). To counter this problem, existing ad blockers keep the list of domains that deliver ads or are tracking users. More specifically, this list of domains is also accompanied with some regular expressions that are used to pinpoint only some network connections from those domains.

MyTrackingChoices takes a different approach to find which network connections of third-parties to block so that the functionality of the web page is not broken. Instead of collecting all tracking and advertising domains (which are huge and dynamic), we build a list of domains that are essential for the functionality of a web page. In our experience, such a list is smaller and easier to maintain than the list of tracking and advertising domains. Therefore, we only keep the list of such domains [START_REF]List of allowed third-party domains[END_REF]. We block all other domains that do not belong to this list and are classified as a "tracker" based on a heuristic described below.

We classify a third-party domain as a "tracker" if it is present on three or more different domains that a user visited in the past. This implies that the extension becomes fully functional only after a user visits a couple of web pages after installation. This heuristic is employed so that we do not need to maintain a list of third-party domains that are specific to a first-party domain to deliver content. For example, "lemonde.fr" uses "lemde.fr" domain to deliver content to their web pages. However, this domain is only specific to "lemonde.fr" and is probably used by Le Monde only for this purpose. Therefore, such domains are not classified as "trackers". As we do not need to keep the list of such domain specific third-party domains, this helps us to keep our list of useful domains reasonably small.

IV. ECONOMIC IMPACT

This section assesses if our approach can contribute to decreasing the impact of ad blocking on the Web economy. This assessment is based on the data collected from users of MyTrackingChoices. In the following, we first describe our dataset and the ethical considerations regarding the data collection and use. And in the sequel, we measure the economic impact of MyTrackingChoices.

Dataset. Before the extension is put on the Chrome Web Store 6 , it was distributed among friends and colleagues for beta testing. Data from these users are not collected and used in our study. The collected data is from those users of MyTrackingChoices who downloaded it directly from Chrome Web Store. Such users either found the extension on the Chrome Web Store independently or came to know about it through various publicilty channels (word-of-mouth, twitter, facebook, etc.). The dataset, used for different analyses in this paper, includes data from January 11 to February 20, 2016.

The dataset contains 96 users 7 . These 96 users are those who browsed 20 or more web pages and configured at least once their options regarding blocking of third-party domains (either on a per category or on a per web page basis). Users, who did not configure blocking feature at all, have not been considered in this study because the installation of the extension serves no purpose in this case. The choice of minimum browsing of 20 web pages is somewhat arbitrary but the intuition behind this is not to take into account the preferences of users who did not considerably use the extension. Such users may further distort the ensuing analysis.

Based on data uploads from users to our server, we find that different users used MyTrackingChoices extension for different time intervals ranging from a minimum of around 6 hours to a maximum of 44 days. Even though it is possible for users to continue using the extension and just opt-out of data upload, we consider that they stopped using the extension when no data is received from users. There were 7.29% users (7 users out of 96 users) who used our extension for less than 1 day. A vast majority of users used it for more than 1 day.

Ethical considerations regarding data collection. The collected data is considered to be pseudo-anonymized because it does not contain any information that can be directly used to re-identify users. It contains hashes and categories of web pages visited by the users along with third-party domains and URLs of iframes present on those web pages. As a part of responsible disclosure, users were informed that the extension is developed by Inria as a research project and collected data will be used to study the impact of MyTrackingChoices on the Web economy. We provided users with the option to opt-out of data collection as well as delete previously uploaded data to our servers. Furthermore, we assured users not to make an attempt to re-identify them and also, not to share the data with any outside party. MyTrackingChoices privacy policy 8 clearly specifies all the details regarding our data collection, storage, processing and sharing.

A. Analysis

The analysis is done under the reasonable assumption that users know how to properly use the extension. To ensure proper functioning of the extension, we had put a clear notice 9on our project web page 10 as well as extension download page [START_REF]MyTrackingChoices: Available to download at Chrome Web Store[END_REF] on Google Chrome Store to uninstall other ad blockers or disable blocking functionality in other anti-trackers. Indeed, such extensions could intervene in the functionality of MyTrackingChoices and therefore, user choices may not be completely respected.

In the following, we present results cumulated over all the users of MyTrackingChoices since our goal is to measure the global effect on the Web economy. As we are interested in different aspects related to different categories of web pages, most of our results do not focus on users but categories of web pages.

To measure the impact on economy, we first start by looking at number of users who actually exercised fine-granular choices. We find that 69.98% users accept the presence of third-party domains and thus, tracking and hosting ads in some categories of web pages that they do not consider much sensitive. On an average, a user blocked 15.28 categories (almost half) out of a total of 32 categories. The median of the number of blocked categories is 11. These bare statistics suggest that the impact on the Web economy due to ad blocking can be reduced if users are provided with such finegrained choices. However, we need to keep in mind that such a solution is for users who block ads because of privacy reasons, who are not against ads and do not want to be tracked on some categories of web pages that they consider sensitive.

We also note that 30.02% (29 users out of a total of 96) users selected all categories to block network connections of third-party domains. These are probably the users that are either against tracking altogether or probably the ones who do not want to see ads at all. In fact, blocking trackers on all visited web pages will block almost all ads as most ads are delivered today through third-party domains present on a web page. As these users simply do not want to exercise finegranular choices, providing them such an option will not be help survive the ad-based Web economy.

Next, we are interested in knowing categories of web pages that are most or least blocked by users. This should enable us to know the categories that are the most sensitive to users (where most users do not want to be tracked) and categories that users care the least with respect to tracking. Equipped with this information, in future, we can propose to users the categories of web pages to block by default and let user tweak them if they are not satisfied.

Fig. 3 presents the categories blocked by users in the order of the most blocked to the least blocked. We note here that the three most blocked categories are "adult", "religion" and "health & fitness". These categories are, in fact, also considered as sensitive by European Data Protection Law [START_REF]Handbook on European data protection law[END_REF]. The three least blocked categories are "technology & computing", "science" and "news". This result confirms that users are more concerned about sensitive categories [START_REF]Handbook on European data protection law[END_REF]. Therefore, it actually makes sense to provide them with such an option, i.e., to block trackers based on the categories of web pages.

As we now know the most and the least blocked categories by users, it is interesting to study the browsing habits of users (category of web pages they browse the most/least) to get more insights about the impact on the web economy. The total number of browsed web pages by these 96 users are 86,922, out of which 12,543 are distinct. Fig. 4 presents the distribution of total and distinct visited pages per category. This also shows the distribution of blocked versus allowed pages in each category. In order to detect any bias in the distribution of browsed web pages (owing to small number of users or type of users), we check it with other studies and the pattern seems to resemble well [START_REF] Goel | Who does what on the web: A large-scale study of browsing behavior[END_REF], [START_REF] Kumar | A characterization of online browsing behavior[END_REF].

We find that the top-5 most browsed categories by our extension users are "society", "technology & computing", "arts & entertainment", "science" and "hobbies & interests". Here it is worth noting that web pages browsed in these 5 categories constitute for roughly 65% of the total browsing activity. However, none of these top-5 most browsed categories (Fig. 4) are in the top-5 of the most blocked (Fig. 3). This explains why there are more allowed than blocked web pages in the top-5 categories of Fig. 4.

There are more blocked than allowed web pages, in the Fig. 4, for the categories that are the most blocked in Fig. 3. As the most blocked categories are least browsed and the most browsed categories are the least blocked, the effect on the economy is less damaging. In total, only 33.19% of browsed web pages were blocked. This shows that the number of blocked web pages are far too less than the ones where trackers (and thus, third-party ads) are allowed.

Until now, we studied the effect on the economy due to finegrained blocking options on per web page basis. This already indicates that MyTrackingChoices can reduce the impact of ad blockers on the Web economy. However, as we also collect the source URLs of all iframes included in the web pages browsed by users, this allows us to measure how many iframebased ads actually got blocked. As iframes are generally used to deliver ads from third-party domains directly into a web page, we can make an accurate estimate of the impact of MyTrackingChoices on the Web economy. It is worth noting that this study excludes non-iframe based ads as well as those delivered directly by the publisher. However, as per our experience, percentage of such ads is very low.

In total, we find 958 different domains delivering iframes over all 96 users. However, since all iframes do not necessarily contain ads, we first filter those iframes that are used to deliver ads. This filtering is done based on the list of advertising domains from Mozilla Focus project and their partner Disconnect [START_REF]Efficient & optional filtering of domains in Recursor 4.0.0[END_REF]. After this filtering, we find a total of 115 different ad domains and a total of 27,861 iframes or ads served by these domains. Table III, in the appendix of this paper, contains top 40 ad domains that delivered ads through iframes.

Fig. 5 presents per category distribution of ads. For each category, we also have the fraction of ads that are allowed or blocked due to blocking policies specified by users. The categories of web pages which host most of the ads are "arts & entertainment", "technology & computing" and "news". As expected, we find that the percentage of ads the most blocked are in categories that are most blocked by users, for example, "adult", "health & fitness", "religion", "politics", "personal finance". However, as web pages belonging to these categories are comparatively less visited by users as well as such web pages have comparatively lesser number of ads, the total number of ads blocked by all users of MyTrackingChoices is small. In total, only 23.8% of all ads are blocked.

Conclusion.

Assuming that our collected data is representative of users blocking ads due to privacy reasons, we believe that the economic impact of ad blocking exerted by privacyaware users can be significantly reduced if we provide users with such a fine-grained control. As the loss due to ad blocking was 21.8 billion dollars in the year 2015 according to PageFair 2015 report [START_REF]The cost of Ad Blocking, PageFaire and Adobe Ad Blocking Report[END_REF], this could have been reduced to 14.7 billion dollars with the use of MyTrackingChoices. We estimate this reduction in the economic loss based on the facts that only 23.8% ads are blocked by MyTrackingChoices users and 50% of users block ads due to privacy concerns [START_REF]The cost of Ad Blocking, PageFaire and Adobe Ad Blocking Report[END_REF].

V. USABILITY AND PERFORMANCE EVALUATION

This section assesses the usability and performance of MyTrackingChoices. We report upon the pseudo-anonymous data collected from users of our extension.

A. Usability

As usability is an essential factor for a wide scale adoption of a tool, we evaluate two of its important aspects. Before going into further details, we reiterate that current anti-trackers allow users to block ads based on a per URL basis whereas MyTrackingChoices lets users specify their blocking policies based on categories of web pages. Bearing in mind this distinction, our first evaluation criterion considers the frequency with which users need to change the two blocking policies. Under this criterion, we compare the blocking policies used by current anti-trackers and MyTrackingChoices. It is evident that category-based blocking should outperform URL-based blocking. However, for the sake of completeness and accuracy, we measure the performance of MyTrackingChoices in this regard. We note that in certain circumstances, category-based blocking can be too coarse. For example, a user may not want to block a specific web page in a blocked category or vice versa. To this end, MyTrackingChoices, offers an additional possibility to be even more granular and block or allow on per web page basis. Our second criterion captures the usage of this feature. This criterion is evaluated by counting the number of users who exercise such a granular feature and at how many web pages this feature is used.

In the following, we measure the afore-described criteria on our dataset.

First, we study how users' tracking choices evolve over time. Specifically, we want to know if users are satisfied by just configuring once their tracking choices when they install the extension or they change their tracking choices postinstallation. Fig. 6 presents the percentage of users who change their tracking choices. We note here that 81% users configure their choices once and then, do not feel the need to change it. This signifies that blocking based on categories is stable over time and this makes it highly usable. Additionally, we highlight that almost all (16 out of 18) remaining users added one or more categories, while only 2 users removed an already blocked category.

Next, we measure how users exercised per URL blocking option. We find that 52 users out of a total of 96 users, i.e., 54.17% users, used this functionality. This clearly suggests that such an option is useful to have. In total, web pages where URL-based blocking feature is used, constitute for 1.01% (127 web pages out of 12,543) of total web pages browsed by these 52 users. This is not a considerable percentage but we need to keep in mind that all such users also exercised their choice regarding blocking trackers based on the categories of web pages. They usually need to exercise per web page blocking in case they are not satisfied with their per category blocking decision. Fig. 7 presents the distribution of per URL granular policies exercised by these 52 users over different categories of web pages. It is worth noting that the top-5 categories for which per URL policies are defined, none of them belongs to the top-5 categories blocked by users (Fig. 3). This means that the web pages which contribute the most to the per URL policies are those that belong to non-sensitive categories. Also, we note that 37.42% of per URL policies are defined to allow trackers on different web pages where tracking is blocked as per their category. This leads us to the conclusion that some users are willing to accept ads on web pages belonging to non-sensitive category and indeed want to support publishers. However, at the same time, we also notice that trackers/ads are blocked on a per URL basis for web pages that are not blocked based on their categories. This implies that users do block trackers and thus, eventually ads on certain web pages even if they did not consider their categories sensitive. This user behavior suggests that these web pages may contain intrusive ads and therefore, users opted for blocking of third-party domains.

B. Performance

We measure the performance of MyTrackingChoices in various respects. First, we measure the performance of our extension in terms of correctness of categorization algorithm and proper functioning of the web pages. We find that incorrect categorization is reported for only 18 web pages (out of a total of 12,543 distinct web pages browsed by all the 96 users) by 12 users. This shows that users are mostly satisfied with the categorization of web pages by our extension. Also, seven users reported 23 web pages whose functionality broke due to MyTrackingChoices. Most of the times, it was because of blocking of content-provider domains and we corrected the problem by updating the list of allowed domains.

Next, we assess our extension in terms of average pageloading time, maximum memory usage and maximum CPU usage, and compare these results with some of the most prominent ad-blockers and anti-trackers. This is necessary because our extension provides certain privacy guarantees in Fig. 8: The first row shows the peak CPU usage (in %), peak memory usage (in MegaBytes) and average loading time (in seconds) for home page of CNN website (cnn.com). The second and third rows show the same information for home pages of Le Monde (lemonde.fr) and New York Times (nytimes.com) respectively.

terms of user tracking but it comes at the cost of processing and computational overhead. Fig. 8 presents the benchmark analysis of this comparison. The results of this benchmark analysis have been obtained after ten consecutive visits to these three popular web pages: cnn.com, lemonde.fr and nytimes.com. The main conclusion that can be drawn from this figure is that our extension, despite its higher complexity, outperformed most of the tools evaluated in this study. In terms of page loading time, MyTracking-Choices is close to Ghostery and uBlock Origin, the two tools which led this aspect. As for memory usage, our extension required between 37 and 39 MB, ranking third after Ghostery and uBlock Origin in lemonde.fr and nytimes.com, and second after Ghostery in cnn.com. Finally, with just 2% of processing usage, our extension outperformed all tested tools in terms of CPU consumption. In a nutshell, the performance of MyTrack-ingChoices was above the average for those three web pages, and this was despite the inclusion of more sophisticated and advanced privacy features.

VI. PRESENCE OF TRACKERS

In this section, we study the prevalence of trackers on the Web. We first discuss how this study is conducted and then, present the measurement results.

If a third-party domain is present on a web page, we assume that it is tracking users. Moreover, a third-party domain is classified as "tracker" only if it is found to be tracking users on three or more web pages (as described in Section II). The consequence is that first two presence of a third-party domain does not suffice for the domain to be classified as a "tracker". In addition, we exclude from our study web pages that are blocked by users. This is because if the initial request to a tracker is blocked, none of the consequent requests, that would have been made otherwise, can be captured. Users in our dataset were tracked 239,420 times by a total of 588 different trackers. The average number of trackers, over all users, per web page is 3.2 with a standard deviation of 5.1. However, the maximum number of trackers present on a web page can be as high as 98 in some cases whereas the minimum is zero. Fig. 9 presents the distribution of trackers over different categories. From this figure, we note that web pages in the "news" category contain the maximum number of trackers on average. However, if we contrast it with number of ads received on web pages in the "news" category (Cf. Fig. 5), we find that the web pages in the "news" category did not receive the maximum number of ads. This suggests that web pages in the "news" category include many additional trackers other than those related to ads. In fact, the average number of trackers in the "news" category is 14.28 with a standard deviation of 10.37. This is much higher than the global average of 3.2 trackers per page.

From the same figure, it is interesting to note that web pages in the "technology & computing" have the most number of different trackers, close to 500, even though the average number of trackers per web page is quite small. In fact, web pages categorized as "news" are tracked by 284 different trackers even though the average number of trackers per page is the highest. This result suggests that the trackers are most spread in web pages belonging to "technology & computing" category.

We refer interested readers to Table IV in the appendix of the paper which shows the list of frequent trackers overall and in some of the sensitive category web pages.

VII. CONCLUSION AND FUTURE WORK

Considering the poor ad-experience on the part of users, ad blockers and anti-trackers have become an indispensable tool. They provide absolute privacy to users at the cost of an adverse impact on the Web economy. In this paper, we proposed a new approach that provides a balance between user privacy and the Web economy. The proposed approach is user-centric and allows users to exercise fine-grained options. It allows users to choose the categories of web pages that are privacy-sensitive to them and block trackers on such web pages only. As a result, it helps users to control their profile collected by different third-parties, e.g., advertising companies, data brokers, insurance companies, etc. We believe that our proposed approach can provide the desired level of privacy while simultaneously supporting the ad-based economic model of the Web. Overall, it can also help improving the user adexperience and the quality of ads.

As a future work, we aim to extend our tool by proposing users an option to block annoying ads irrespective of where they appear. Another line of work consists in letting user specify the maximum number of ads they are willing to receive on a web page belonging to a non-sensitive category web page. Finally, we plan to block trackers by default on sensitive category web pages but users would have the option to tweak the default settings if they do not agree.

Fig. 1 :

 1 Fig. 1: The configuration panel shown in this figure allows users to define per category blocking policies.

Fig. 2 :

 2 Fig. 2: Screenshot of the popup page. It shows the category(ies) of the current visited page along with the decision about blocking or allowing the trackers. Depending on the first experience with the web page, users are also given the option to block or allow trackers the next time they visit that web page.

Fig. 3 :

 3 Fig. 3: Percentage of total users blocking a category. Total number of users considered in this study are 96.

Fig. 4 :

 4 Fig. 4: Distribution of blocked and allowed visited pages by category. Right side y-axis presents distribution of distinct visited web pages by category. The total number of browsed web pages are 86,922 whereas the total number of distinct web pages browsed are 12,543.

Fig. 5 :

 5 Fig. 5: Distribution of ads by category and on the fact if they are blocked or allowed. Total number of ads are 27,861.

Fig. 6 :

 6 Fig.6: Percentage of users modifying the "category-wise blocking of trackers setting" different number of times.

s p o r t s s c ie n c e p o li t ic s la w n e w s p e r s o n a l f in a n c e s o c ie t y a r c h it e c t u r e b u s in e s s a u t o m o t iv e h e a ltFig. 7 :

 7 Fig. 7: Distribution of per URL defined policies by category.

n e w s h o m e t r aFig. 9 :

 9 Fig. 9: Distribution of trackers by category. Left-side y-axis (in green) represents average number of trackers with standard deviation whereas rightside y-axis represents number of distinct trackers.

TABLE I :

 I Top-level interest categories. , e.g., if they find the top-level categorization too coarse, we can further allow users to interact with bottomlevel categories. Top-level categories can be found in the TableI, whereas subcategories corresponding to three of these categories are shown in TableIIin the appendix of this paper.

	adult	economics	hobbies & interests	politics
	agriculture	education	home	real estate
	animals	family & parenting	law	religion
	architecture	fashion	military	science
	arts & entertainment	folklore	news	society
	automotive	food & drink	personal finance	sports
	business	health & fitness	pets	technology & computing
	careers	history	philosophy	travel
	feedback of users

Such ads are delivered by domains other than the one navigated by a user.

https://chrome.google.com/webstore/detail/mytrackingchoices/ fmonkjimgifgcgeocdhhgbfoncmjclka?hl=fr

Ads are considered to be intrusive if they hide content or if they pop up randomly on the screen making user browsing experience frustrating.

As users are okay to be tracked on some categories of web pages. They still can receive useful ads targeted to those interest-categories of users.

https://chrome.google.com/webstore/detail/mytrackingchoices/ fmonkjimgifgcgeocdhhgbfoncmjclka?hl=fr

We consider one installation as one user. However, it is technically possible for a user to uninstall the extension and install it again. We assume that users did not do this.

Available at https://myrealonlinechoices.inrialpes.fr/privacy policy.html

Here is the excerpt from our web page: "Please uninstall other Adblockers or disable blocking functionality in other anti-tracking extensions like Ghostery, DisConnect, PrivacyBadger etc. before installing MyTracking-Choices. Otherwise, your choices would not be completely respected.

" 10 https://myrealonlinechoices.inrialpes.fr/

ACKNOWLEDGMENT

The writing quality of this paper is benefited by comments from Amrit Kumar. This work is partially funded by the Inria Project Lab CAPPRIS. J. Parra-Arnau is the recipient of a Juan de la Cierva postdoctoral fellowship, FJCI-2014-19703, from the Spanish Ministry of Economy and Competitiveness.

APPENDIX

Table IV shows the list of frequent trackers overall and in some of the sensitive category web pages. For each thirdparty" domain, we show the percentage of total web pages (browsed by all users) where it was present. We find that, irrespective of the categories of web pages, Google and Facebook domains as third-party domains are prevalent.


Imen Dhief

Houda Dougui

Daniel Delahaye

Noureddine Hamdi

Strategic Planning of Aircraft Trajectories in North Atlantic Oceanic Airspace Based on Flocking Behaviour

The North Atlantic Airspace (NAT) accommodates traffic between Europe and North America. This area is considered as the most congested oceanic airspace in the world. Radar-Based surveillance is not applied in the most of the oceanic area due to its limited coverage. So, aircraft become obliged to follow predefined routes called Organized Track System (OTS). These routes require very restrictive separation standards which limit the traffic of aircraft. Thus, a new kind of communication system, called Automated Dependence Surveillance Broadcast (ADS-B), has been introduced in order to afford the aircraft a reliable communication with both controllers and surrounding traffic. Hence, aircraft crossing the NAT will be able to follow more flexible routes, which will improve significantly the air traffic situation over this area. In this paper, we propose a strategic planning 1 model that overcomes the constraints of the OTS system in order to produce the closest routes to the direct ones of aircraft. This method is based on flocking boid model. It provides us with satisfying results on a portion of one day traffic over the NAT airspace.

I. Introduction

It is worth-noting that the air navigation in the oceanic area differs from the continental one because of the lack of the navigational and communication equipments. Thus, aircraft are required to follow predefined routes and respect highly restrictive separation standards. The Organized Track System (OTS) is a route structure that has been established in the North Atlantic Oceanic area. These routes have been constructed in order to handle as many flights as possible on, or close to, their minimum time tracks and altitude profiles [START_REF]Guidance concerning air navigation in and above the north atlantic mnps airspace[END_REF]. The new Automated Dependance Surveillance Broadcast (ADS-B) technology is an airborne-based system that provides both controllers and pilots with more accurate and reliable information. In fact, the aircraft transponders receive GPS signals to define the aircraft actual position. Then, the position as well as other information are broadcast and sent to both 1 Strategic planning: this step consists in constructing a day traffic in order to overcome the constraints of the sector capacities with better considering the needs of the airlines companies. This planning is done before the plane taking-off.

the aircraft neighbours and the controllers. Due to ADS-B, the air traffic situation in the oceanic air space has been improved. Thus, flights are allowed to follow more flexible and direct routes from the departure airport to the arrival one. In this study, we propose a strategic planning of aircraft trajectories while transiting flights off the predefined structure routes OTS. This planning method is inspired from the Flocking swarm model named "Boids Flocking", which is a swarm model introduced by Craig Reynold's in the 1980s [START_REF] Reynolds | Flocks, herds and schools: A distributed behavioral model[END_REF]. Reynold's implemented an algorithm for simulating animal motion such as bird flocks and fish school, where boids refer to the generic flocking simulated creature. The aggregate motion represents the result of interaction between the simple behaviour of each boid. Recently, the paradigm of multi-agent systems has become widely applied for air traffic management. Several researches are devoted to apply multi-agent systems for air traffic management and collision avoidance in the continental airspace [START_REF] De Oliveira | Multi-agent tools for air traffic management[END_REF][START_REF] Emami | An overview on conflict detection and resolution methods in air traffic management using multi agent systems[END_REF]. Nevertheless, to our knowledge, no research works has applied these systems in the oceanic airspace. This paper introduces an algorithm based on flocking model for strategic planning aircraft over the NAT airspace. We suppose that all aircraft are equipped with ADS-B system. We take advantages from the reliable information that can be transmitted between flights to construct a full swarm behavior. Thus, each aircraft is considered as an agent. Besides, all agents communicate with each other. They adjust their caps in order to avoid conflict while maintaining the swarm behavior. The rest of this paper is organized as follows : The next section presents a brief description of the North Atlantic airspace and defines the principle of the Flocking model. Section III contains relevant works on optimum trajectory generation in the oceanic area. Section IV exposes the problem formulation, and shows how we adapt the Flocking model to construct conflict-free trajectories in North Atlantic airspace. The simulation and computational results are presented and analyzed in section V. Finally, section VI presents some concluding remarks.

II. Background

In this part, we define the main concepts related to our research subject. First, we describe the North Atlantic airspace. Then, we display the Flocking model which is the key element of our approach.

A. North Atlantic Airspace (NAT)

The Atlantic Oceanic covers a total area of about 106,400,000 square kilometers. It is considered as the second largest oceanic airspace after the Pacific airspace. North Atlantic Airspace accommodates traffics between Europe and North America. Daily, about 1000 transatlantic flight cross this area in each direction, which makes it the busiest oceanic airspace. Since radar coverage is limited in the middle of the Atlantic airspace, aircraft are required to follow predefined tracks referred to as the Organized Track System (OTS). Besides, they are compelled to respect highly restrictive separation standards. The organized track system is constructed to be as closer as possible to the minimum time and to the altitude profiles of flights. NAT traffic was divided into two major flows: a westbound flow from Europe to North America in the morning and an eastbound flow from North America to Europe in the evening. Thus, a congestion of this region is detected in the west direction between 11h30 and 18h00 UTC and in east direction between 01h00 and 08h00 UTC. The OTS includes between 5 to 7 tracks in each direction for different flight level 2 . In order to ensure safety, these tracks are separated by 60NM laterally and 1,000 feet vertically. Around 10 waypoints are planned in each track. Transatlantic flights using OTS tracks are required to follow the same track, and any rerouting decision should be taken in the waypoints. The longitudinal separation standards, which is defined between two consecutive aircraft following the same track, is defined by 10 minutes if aircraft are following the same track and by 15 minutes when an aircraft is changing its track. These very demanding separation standards result from the lack of surveillance coverage in the oceanic area. As the traffic in this region increases, these procedural separations generate inefficiencies in oceanic operations and limit oceanic air routes capacities. Considering these issues, an innovative technology, known as Automatic Dependence Surveillance-Broadcast (ADS-B), has been recently introduced by the International Civil Aviation Organization (ICAO). The ADS-B systems rely upon automatic position reports by making use of satellites to provide global coverage. ADS-B is a surveillance application that transmits periodically aircraft information (position, velocity and heading, etc...) via a broadcast mode data link to both controllers and surrounding traffics. Thanks to the accuracy of this communication tools, a significant reduction in separation standards can be accommodated. In fact, the longitudinal 2 Flight level is a pressure altitude expressed in hundreds of feet.

separation between aircraft becomes 2 minutes if aircraft are successive in the same track, and 3 minutes if an aircraft changes its track. Further details about the functionalities and benefits behind the design and development of this advanced technology are given in [START_REF] Parkinson | Space-based ads-b: A small step for technology a giant leap for atm?[END_REF] and [START_REF] Blomenhofer | Space-based automatic dependent surveillance broadcast (ads-b) payload for in-orbit demonstration[END_REF].

B. Flocking model

In nature, flocks could be considered as self-organized networks of mobile agents that cooperate with each other to form group behaviour. The flocking model was introduced by Craig Reynold's in 1986 [START_REF] Reynolds | Flocks, herds and schools: A distributed behavioral model[END_REF]. It represents the form of collective behavior of a large number of interacting agents with a common group objective. It is especially exploited to provide realistic life-look representations of the aggregate motion of animal groups, such as birds, fish and sheep. In Reynold's model, each agent was called "boid". The boid model has the three following heuristic rules applied to the boids at each time sample: Separation (figure 1 (a)) : this rule is applied in order to maintain a specific separation distance between agents. Each boid is required to ensure a separation distance with his flock mates to avoid collision and prevent crowding. It is important to note that the separation rule acts as a complement of the cohesion rule. In fact, if only cohesion is applied all boids will merge into the same point. Figure 1 illustrates the behavior of an agent when applying the three flocking forces.

III. Related work

There are several works aiming to improve air traffic situation in the oceanic airspace. The first study, that examined the benefits of transitioning from the fixed predefined routes to user-preferred routes in the Central East Pacific (CEP) airspace, was proposed in [START_REF] Grabbe | Central east pacific flight routing[END_REF]. In this survey the user's preferences were assumed to be Wind-optimal. The simulation of new aircraft trajectories was developed via a minimum-travel-time and Windoptimal dynamic programming(DP). The potential time and distance gain were 9.9 min and 36 NM per flight, respectively. This research proved that significant benefits could be achieved by surrogating the fixed routes to use wind-optimal routes. After constructing the new windoptimal trajectories structure, the same authors treated the problem of conflict detection and its resolution in [START_REF] Grabbe | Central east pacific flight scheduling[END_REF]. The problem was modeled as a job shop scheduling issue and was solved afterwards via 0-1 integer programming model. The maneuvering resolution consists in calculating the optimal departure and en-route delays. This method was tested with a set of 175 flights and with two different sizes of the machine in the job shop. The first type, where the size of machine was 30NM*30NM, generates a conflictfree trajectories. However, it is highly restrictive since it enhances the computational complexity of the problem by increasing the number of variables and constraints. The second algorithm, where the size of machine was 100NM*100NM, is less restrictive, but it may require further tactical separation maneuvers. It was thought that this method achieved considerable economic benefits to the airlines when applied on the CEP. Nevertheless, in this paper, we solve the problem of air traffic in the North Atlantic Airspace which accommodates daily about 1,000 flights in each direction. To deal with this issue, we cannot apply the above-mentioned method because it may increase exponentially the constraints of the problem, which makes it unsuitable in our study case. Recent approach of optimizing air traffic over the NAT airspace has been proposed in [START_REF] Rodionova | Optimization of aicraft trajectories in north atlantic oceanic airspace[END_REF]. In this work, the authors have presented an optimization model to improve the air traffic situation over the OTS tracks when implementing the ADS-B technology. The problem consists in searching for the optimal flight path within the OTS in order to reduce the congestion while exiting the continental airspace.The simulated annealing algorithm has been applied to solve the high complexity of the combinatorial optimization. Computational results prove that operating the ADS-B systems has widely ameliorated the traffic situation. In [START_REF] Sridhar | Strategic Planning of Efficient Oceanic Flights[END_REF], they used wind-optimal trajectory instead of the north Atlantic Tracks. Therefore, flight trajectories were generated based on wind-optimal routes. Small adjustments in departure time and rerouting have reduced the number of potential conflicts. The deconfliction strategy was ensured with a simulated annealing combined with a local gradient search. The findings show the efficiency of this methodology mainly in fuel saving. In our study, we intend to apply an innovative bio-inspired method based on Multi-Agent algorithm for generating and de-conflicting aircraft trajectories without using the OTS structure. The following section presents the flocking model on which our method is based.

IV. Problem Formulation

In this section, we start by modeling the flight, subject of our study. Then, we introduce some assumptions in order to simplify the problem. Finally, we explain how we adapt the above-mentioned Flocking model.

A. Flight model

Each flight is defined by a number of parameter values. Some of these values are fixed data, while others can be modified and represent our scope for reducing conflict. In this paper, we assume that the flight level and the Mach number are constant since we are tackling only the enroute phase 3 . For each flight the following input data are given :

Entry and exit points in the NAT space are characterized by its latitude and longitude coordinates.

Cruise altitude in feet which is supposed to be constant for the entire trajectory.

Desired entry time

True airspeed in knots is supposed to be constant during the entire trajectory. Preliminary experiments have proved that this state space is insufficient to guarantee conflict-free trajectories. For this reason, entry delay less than 20 minutes is allowed. Besides, the positions of entry and exit points are not fixed, they can be changed. In fact, if we consider that the desired exit point is the center of a circle having a 5 NM radius, any point of its surface is an potential exit point. This radius may not be sufficient to choose the entry point. In fact, we intend to separate aircraft when they enter at the same point (or when distance between their entry points is less than the separation norm), and the difference between their entry times is less than 3 minutes. The decision variables in our model are given below: pp i , V i q, i 1, 2, 3, ..., N where p i px i , y i , z i q is a sequence of points defining the position of the aircraft at time sample and V i is the motion vector applied at the point p i . d In the time delay at the entry point P In the assigned entry point P Out the assigned exit point These variables must be determined to guarantee a set of conflict-free trajectories while respecting the limit of the permitted-delay and the allowed deviation from the desired entry and exit points.

B. Problem model

This section presents a description of the mathematical model used in our trajectory-planning methodology. In this paper, we intend to construct flight trajectories while adopting the swarm behavior introduced by Reynolds. Since we assume that the flights altitude profile does not change for their entire trajectory, we can work in 2D airspace. We consider the airspace as a Euclidean space. Latitudes and Longitudes in the earth space are projected in 2D space by a Lambert azimuthal projection with the center of projection is located at the center of the North Atlantic airspace. The flight trajectory is represented as a set of discrete points from the departure to the destination. The range between each two points represents 1 minute navigation with the given data. Initially, we suppose that aircraft cap is directly steered to the destination point. Thereafter, the cap is adjusted in each point in order to avoid conflict with neighbours while maintaining the swarm behaviour.

1) Conflict detection: As we have already mentioned, the separation standards in the oceanic area are greater than the continental ones due to the lack of reliable means of surveillance. Aircraft operating over the NAT airspace are required to maintain lateral, vertical and longitudinal separations. The lateral separation is set to be 60 NM that is equal to approximately 111.11 km, or 1 H of latitude. The minimum vertical separation is 1,000 feet. It is ensured by using different flight level. Using the OTS tracks, these two separation standards are already respected. Thus, the only separation to respect in the OTS is the longitudinal one which is set to be 10 minutes, and it is defined between two consecutive aircraft in the same tracks. In our work, we do not use the OTS tracks. Aircraft are allowed to follow nearly its direct route from its entry point to its destination. Since we assume that all aircraft are equipped with ADS-B system, it is possible to reduce the separation standards. Thus, we consider, in this paper, the lateral separation which is reduced to 20 NM and the current vertical separation which is 1,000 feet between flight levels. Thus, for each aircraft, we can define a protection zone represented as a cylinder with radius equal to the lateral separation (R h 20N M ), and half-altitude equal to the vertical separation norm (R v 1000f eet) as shown in figure 2. Thus, a conflict is detected when the protection zone of an aircraft is crossed by another aircraft. In this Fig. 2: The protection zone paper, trajectories are sampled with a time step of ∆t 60 second. This time step is small enough to ensure that all potential conflicts are identified. Thus, a flight trajectory is a set of points pp f i , t f i q where p f i is the position of the concerned flight at the time t f i n ¦ ∆t (where n is a positive integer). If we consider two flights f and g and their trajectories which are respectively pp f i , t f i q and pp g i , t g i q. A conflict is detected between f and g if at the time t t f i t g j the positions p f i and p g j violate both lateral and vertical separation norms. Therefore, conflict at point p f i , denoted Φ f i , is defined as the total number of aircraft whose protection zone crosses the protection zone around p f i . The conflict associated with the trajectory of the flight f, denoted Φ f is set as follows:

Φ f N i1 Φ f i (1)
where N is the number of points in the trajectory of the flight f. The total number of conflicts between trajectories of the set of flights, Φ tot , is defined as:

Φ tot fS Φ f (2)
Since aircraft do not have the same speed, another type of conflict can be detected. It happens when an aircraft is slower than the one following it. This conflict must be resolved from the start otherwise our algorithm of resolution can not deal with it. We consider two flights f and g and respectively their entry points pP f in , P g in q and exit points pP f out , P g out q. Besides, t f in and t g in are respectively the entry time of f and g. If we consider that the two flights f and g satisfy the inequalities in (3), then g may catch up f.

$ ' ' & ' ' % distancepP f in , P g in q 20N M distancepP f out , P g out q 20N M Speedpf q Speedpgq t f in t g in (3)
where the function distance calculates the distance between two points in the space, and Speed gives the velocity of the aircraft. First, we have to calculate the distance crossed by f at t g in . Then, we compute the time necessary for g to catch up f. If that time is less than the time necessary for f to reach its destination, then a conflict must occur between f and g.

2) Defining neighbourhood : For each flight, we define a set of flight neighbours within a predefined distance. In our study, the neighbourhood regions differ according to the application of the flocking rules. As it is illustrated in the figure 3, the separation area can be defined as the space surrounding the aircraft (red color). In this area, we apply the separation force with the closest aircraft in order to prevent collision. We fix experimentally the radius of this area to be the double of the standard lateral separation between aircraft. The green color in figure 3 shows the area where we apply the alignment force, while the blue area corresponds to the region where we apply the cohesion force to the farther aircraft to make them stay in the group. The alignment and cohesion area are Fig. 3: Neighbourhood area also experimentally tuned to be respectively five and eight times the standard lateral separation.

3) Resolution algorithm: First of all, we sort the flights according to their entry time. Then, we have to ensure that the set of flights is free of conflict in the departure point. Otherwise, we decongest the flights by a sequential method of shifting entry time. In fact, the delay in the entry time of each aircraft must not exceed 20 minutes. If a conflict-free situation at the departure points is not possible with constrained time shifts, it may be necessary to slightly modify the positions of the departure points. The distance between the assigned and the desired entry points must be less than 20 NM. Once all the departure conflicts are resolved, we start with the first point of each flight path, beginning from the earliest flight in the set. Then, we calculate the motion vector V i to construct the next point in the trajectory. Thus, the motion vector is defined as in (4):

V i 60 ¦ V ¦ U i || U i || (4)
where i refers to the aircraft index, V is the speed of the aircraft expressed in meter per second. To have the distance covered in 1 minute navigation, We multiply by 60 seconds. The vector U i corresponds to the weighted sum of the five following vectors.

a) The alignment vector of the Flocking model: it causes a flight to line up with its neighbours. Each flight has to adjust its heading. The new heading of each flight is equal to the average of headings of its neighbours. This vector is computed at each point of the flight trajectory as the average of the velocity vector of its neighbours. Thus, the alignment vector is calculated as the displacement vector in [START_REF] Parkinson | Space-based ads-b: A small step for technology a giant leap for atm?[END_REF].

A i °kN pV k q N ( 5
)
where A i is the alignment vector of the flight i, N is the number of neighbours of the considered flight i and V k is the velocity vector of the neighbours' aircraft k. As it is illustrated in the former section, the neighbours flights, considered to compute this vector, are those detected in the green region of figure 3. b) The separation vector of the Flocking model: prevents flights from local crowding. To implement this rule, we calculate the separation vector of each flight i S i by applying [START_REF] Blomenhofer | Space-based automatic dependent surveillance broadcast (ads-b) payload for in-orbit demonstration[END_REF].

S i °kN pp P i ¡ P k q{dist 2 p P i , P k qq N ( 6
)
where S i is the separation vector of the flight i, N is the number of neighbours, P i is the position of flight i, P k is the position of its neighbours aircraft k, and dist() calculates the distance between two points. In this case, we apply this force to the closest neighboring flights. They are located in the red region of the figure 3. If only the separation rule is applied, the flights will dissipate. c) The cohesion vector of the Flocking model: this vector tries to gather the flights to form a swarm behavior. Cohesion of flight i is calculated by following two steps. First, we compute the center of the neighbours positions of a flight i, which we called F c i , as in [START_REF] Grabbe | Central east pacific flight routing[END_REF]. Then, we need to steer the flights toward its neighbours center density by calculating the cohesion displacement vector in [START_REF] Grabbe | Central east pacific flight scheduling[END_REF].

F c i °kN P k N ( 7
)
C i F c i ¡ P i ( 8
)
where P k is the position of flight k and N is the number of neighbours. To compute this vector, neighbours flight are those located in the blue area of figure 3. If we apply only cohesion, separation and alignment rules, the aircraft will follow the same direction. Thus, we used a force that made each plane reach its specific destination. Actually, we are obliged to add a Destination Vector that steers each aircraft to its destination. But, adding only this force does not solve the whole problem. We notice that the trajectory of the aircraft becomes widely sinuous. This behavior is expected since boids are flexible in their movements, which is not allowed for airplanes trajectories. So, we add another force that represents the Previous Motion Vector. Hence, we introduce here two additional forces that we should be considered in our study.

d) Destination vector: this vector is introduced in order to oblige the flight to navigate toward its destination point. Thus, it is a vector that links the actual position of the flight with the destination position. It is denominated with D i where i is the flight index. e) Previous motion vector: labelled U pred , is added in order to avoid oscillation of the trajectory. It corresponds to the displacement vector applied in the previous point of the trajectory. Obviously, we do not add this vector in the first point of the flight path.

Finally, the resulting vector, applied in each point of the i th flight path, is calculated as the weighted sum of the afore-mentioned five vectors as depicted in [START_REF] Rodionova | Optimization of aicraft trajectories in north atlantic oceanic airspace[END_REF].

U i w 1 ¦ U pred w 2 ¦ D i w 3 ¦ A i w 4 ¦ S i w 5 ¦ C i (9)
where i is the flight index, and w j s are the coefficients used to balance the five forces describing the influence of each steering force.

4) Optimization process: The balance between different forces allows us to obtain better results. In our paper, for each aircraft, we intend to find the shortest path between departure and destination points while avoiding conflicts. The decision variables are the coefficients w i , where i varies from 1 to 5, and the objective function is calculated as in [START_REF] Sridhar | Strategic Planning of Efficient Oceanic Flights[END_REF].

F obj distancepP f , D f q (10)
where P f represents the flight actual position, D f stands for its destination, and distancepp 1 , p 2 q is the distance between two positions p 1 and p 2 . Our goal is to minimize the objective function F obj while eliminating all the conflicts. To achieve our aim, we propose to apply the simulated annealing algorithm. This optimization method is a methaheuristic algorithm inspired from thermodynamics theory where atoms, that have not yet acquired a globally optimal state of energy, move further until they reach stability. The idea of the simulated annealing is to accept changes even to a worse solution, relative to the current one, but in a controlled manner. In fact, the worse the neighbour is, the lower the probability of acceptance will be. This probability is called the temperature. A neighbourhood solution is generated by slightly modifying the coefficients w i from the current values. Therefore, for each coefficient we add or subtract a random value less inferior to 0.1. The whole process is split into two steps. The first stage is the heating up by increasing the temperature, which enhances the probability of acceptance in order to promote the exploration of the search space. Then, the cooling down schedule is launched by decreasing the temperature gradually in order to converge the system to a better solution. In our case, we diminish the temperature by applying a geometrical law. First, we evaluate the number of conflict induced by the considered flight, Φ f 1 , using 1. Then, a neighbourhood solution is generated. After that, we calculate the new number of conflicts Φ f 2 . If the new solution yields to a minimum number of conflicts, that is Φ f 1 ¡ Φ f 2 , then it is accepted. In the case when the neighbourhood solution does not affect the number of conflicts, it will be accepted if it improves the objective function described in 10. Otherwise, the solution is accepted with the probability e pΦ f 1 ¡Φ f 2 q{T where T is the temperature (the simulated annealing parameter). After a predefined number of iterations, the temperature T is decreased by applying a geometrical law where the ratio is experimentally tuned.

V. Results

First of all, we have checked the efficiency of our algorithm with a small set of strategic aircraft paths leading to a considerable number of conflicts. The considered set contained 200 flights and was extracted from real eastbound traffic in 20 July 2012. It generated initially 3620 conflicts. We consider the separation standard as it is described in the former section, and we assume that the departure delay varies up to 20 minutes. Figure 4 displays 2D flight trajectories of the considered set before and after the application of our algorithm. Conflicts are shown via the red color in figure 4. It is obvious that after applying our algorithm the number of conflict became significantly reduced to 39 conflicts. We note that 11 flights were delayed, and the path-elongation rate did not exceed 10%. The extension path defined the rate of the extra path added to the direct route. To determine this rate, we calculated first the length of the direct route between entry and exit points denoted d1. Then, we computed d2, the sum of distances between each two consecutive points generated for each trajectory. The extension path is obtained as follows: |d1¡d2| d1 ¦ 100.

Besides, the analysis was also conducted for four different sets of aircraft routes in July 2012. The number of flights in each set ranged from 368 to 649. The number of conflicts produced by the different sets before and after the application of the algorithm is presented in I. The number of conflicts before and after the de-confliction method varied between r2321 ¡ 4533s and r18 ¡ 59s, respectively. Even though a conflict-free solution did not exist, a significant reduction of the number of conflict was noticed. As seen in table II, most of flights were not delayed. This result is reasonable since we used the alternative of delaying flights only for eliminating conflicts in their departure points. Obviously, it is recommended to be as closest as possible to the aircraft desired entry times in order to satisfy the preference of airline companies. Table III represents statisticson of the rate of extension path regarding the direct one. The first important conclusion that can be deduced based on these results is that 75% of flights were within 1, 2% from their direct routes. Moreover, about 50% of flights in each set took almost their direct routes. Thus, it is worth mentioning that fuel consumption was not affected by conflict reduction strategy since we had small variation from direct path between entry and exit points. However, one or two flights in each set are affected. Their extension paths exceed 10%. In fact, the maximum of extension trajectory reached 17, 6% for set 4 and 13, 8% for set 1. It affected respectively one and two flights.

VI. Conclusion

This paper presents an efficient planning method for aircraft trajectories in the oceanic airspace. Assuming that all aircraft are equipped with the ADS-B system, we intended to improve the oceanic air traffic situation by reducing the separation standards. Based on the Flocking boid model, an algorithm for improving aircraft routes and avoiding conflicts has been implemented. In order to optimize the trajectory length, a method, based on simulated annealing algorithm has been applied. The algorithm has been tested with a real traffic data during July 2012. The computational results show that we can reduce considerably conflicts with reasonable delay and elongation from the direct path. Due to the highly-complex computations, we have been incapable to manage a bigger number of flights as it is the case for the current traffic that carries up to 1000 flights per day. The methodology adopted in this paper has been programmed sequentially. In the future work, we look forward to better the aforementioned results with a parallel computing program.

  Alignment (figure 1 (b)): is performed in order to oblige boids to follow each other in quasi-parallel trajectories. Each boid matches the direction and the speed of its neighbors. Cohesion (figure 1 (c)): this rule is performed in order to ensure the swarm behaviour. Each boid moves to the average position of its neighbours.

Fig. 1 :

 1 Fig. 1: The boids model rules

  (a) Paths before the resolution algorithm (b) Paths after the resolution algorithm

Fig. 4 :

 4 Fig. 4: A portion of real eastbound traffic in 20 July 2012

TABLE I :

 I Results of applying our approach for different sets of flights

	Test (number of flights)		number of flights
		without delay	0 delay 10min	10min delay 20min
	Set 1 (368)	366	2	0
	Set 2 (617)	604	13	0
	Set 3 (572)	565	6	1
	Set 4 (649)	642	6	1

TABLE II :

 II Delays for different flight sets

	Test (number of flights)	Set 1 (368)	Set 2 (617)	Set 3 (572)	Set 4 (649)
	First quartile	0%	0%	0%	0%
	Second quartile	0%	0%	0%	0, 18%
	Third quartile	0, 009%	0, 05%	0, 005%	1, 18%
	Maximum extension	13, 8%	10%	13, 09%	17, 6%

TABLE III :

 III Evaluation of the distribution of extension path in comparison to direct route

The en-route phase of the flight is defined as the segment of flight from the arrival at the initial cruise altitude to the starting of the descent.