Lisa Medrouk
email: lmedrouk@ai.univ-paris8.fr

Anna Pappa

Jugurtha Hallou
email: jhallou@ai.univ-paris8.fr>

Review web pages collector tool for thematic corpus creation

.

The Web constitutes an ubiquitous, inescapable data collection source, providing a mine of inexhaustible informations in various languages and types. The interesting point for our method about creating corpora from the web resides on the fact that internet data could enrich existing corpora as well as giving accessibility to less viewed pages. Web pages are composed by large amount of unrelated material like navigational elements, advertisssements, and templates [START_REF] Kohlschütter | Boilerplate detection using shallow text features[END_REF] making the web collecting process a complex procedure, thus, creating a clean thematic corpus from the web, is still a challenging task [START_REF] Han | Data mining for web intelligence[END_REF]. The main objective of our research is to automatically create a thematic corpus from specific text data needed to develop further opinion analysis tools.

The concept of the tool is designed as a self-contained web application that could be deployed to any java web server. Before proceed with an explanation of our approach it will be helpful to define the problem and outline aspect and semantic assumptions. To simplify the problem we present the construction of our system by steps beginning by some definitions and terms disambiguations largely used in NLP domain, in order to set the theoretical background of our research.

• Definition 1 (thematic corpus) : for our system, a thematic corpus is a collection of raw text data gathered from web pages relatives to specific keywords request.

• Definition 2 (keywords) : the instance keyword used for the search engine could be viewed as a tuple composed by a synonym of reviews, comments, opinions followed by the term (product, item, person, place or other) for which we want to gather information for further analysis. The keyword has the same form in any requested language.

• Definition 3 (aspect-result) : the result presented in the final xml opinion document is an aspect instance, viewed also as a tuple composed by the url and the keyword used in the request.

The information provided by the web is complicated to extract due to the increasing complexity of the page layouts with menus, forms, sidebars, advertisements and all the unrelated material present in the pages. The RevScrap system is a tool able to consequently grap specific text data from website pages returned via web index to users requests. The applied method can be viewed as a set of sequential steps of process, each one giving access to user. The first step of the method allows the user to set the keywords which are the input to search engine request, for example return opinions + item. The second step is gathering URL(s) filtered by a parser excluding "noise" such as advertising and pages of formatting documents (pdf or ppt). The third step is the main process : it uses a specific DOM tree algorithm named ScrapRev for the detection and the identification of the comments nodes regardless the heterogeneity of the page structure and only keeping the most useful texts avoiding redundancy and noise. The ScrapRev technique is based on the top down tree-parsing algorithm, which it's easier to implement by manual programming. The results are collected to well structured xml documents named after the request's terms. The size of the xml documents varies on the quantity of comments present in the retrieved web page. Constructing specific web corpora using keywords via search engine queries is a prolific domain but we still lack a thematic reviews corpus ready to use for opinion mining, in this paper we will show that despite the heterogeneity and the complexity of the web pages, our targeted datas are mainly always located in the same repeated nodes regardless languages, allowing us to have a salient feature to automate this distinction and provide a ready to use thematic corpus.

Related work

Actual NLP tools offer a great deal of concordancers, search engines and text-analyzers, like BootCat [START_REF] Baroni | Bootcat: Bootstrapping corpora and terms from the web[END_REF], Webcorp Live [START_REF] Kehoe | WebCorp: Applying the Web to Linguistics and Linguistics to the Web[END_REF] or the Linguist's Search Engine (LSE) [START_REF] Philip | The linguist's search engine: An overview[END_REF] but they either use previously mostly hand-made corpora, or do not provide an easy downloadable results suitable for further use, or simply are much too expensive for academic budgets. The methods of information extraction (IE) applied to web information services, offer effective and efficient technologies to discover valuable and relevant knowledge in predefined set of concepts expressed by a corpus of texts put together mostly manually to form a specified information domain [START_REF] Piskorski | Information extraction: Past, present and future[END_REF]. Building specific Web corpora using automated search engine queries started in 2001 with CorpusBuilder of [START_REF] Ghani | Mining the web to create minority language corpora[END_REF] a tool for automatically generating Web-search queries tool to construct corpora for minority languages. Baroni [START_REF] Baroni | Bootcat: Bootstrapping corpora and terms from the web[END_REF] proposed a method for building domain specific Web corpora named BootCaT, using a characteristic domain small set of seed for automated queries, the results are then used to extend the corpus and so forth. [START_REF] Kilgarriff | A corpus factory for many languages[END_REF] used the same method to built a corpus factory of major world languages, by gathering a seed word list of hundred words and randomly select three of these words to create a search query, repeating several thousand times the operation in order to obtain a large corpus, the retrieved matching pages are then cleaned, tokenized, lemmatized, part of speech tagged before being load as the resulting corpus. Sharoff [START_REF] Sharoff | Creating general-purpose corpora using automated search engine queries[END_REF] also used the same approach with a 500 word seeds list.

Our research is targeted toward automatically creating thematic corpus, and is closer to previous works that showed that a web page can be partitioned into multiple blocks and prooving that eliminating irrelevant blocks from pages can facilitate data accessibility and data mining using DOM (Document Object Model). In our work the page partitioning provides the necessary elements of parsing and gathering relevant nodes for opinion mining. Noise detection based on DOM as level features of segments is already used by Yi [START_REF] Lan | Eliminating noisy information in web pages for data mining[END_REF] who introduced a simplified DOM data structure and a style tree to detect and eliminate noisy information in web pages and used web page clustering and classification as evaluation method showing that the method boosted dramaticaly data mining dataset. Menad [START_REF] Menad | Mesure de la similitude entre blocs de donnes pour lextraction automatique du contenu web. 21me Rencontre de la Socit Francophone de Classication[END_REF] used HTML hierarchy architecure and Levenshtein distance of retreived web pages to detect relevant data and exclude irrelevant content. Lin [START_REF] Shian | Discovering informative content blocks from web documents[END_REF] also tries to partition a Web page into blocks and identify content ones. Finally, BlogBuster [START_REF] Petasis | Blogbuster: A tool for extracting corpora from the blogosphere[END_REF], a tool for extracting a corpus from the blogosphere uses an engine that collect extracted required information from DOM nodes too.

The proposed technique architecture

Our thematic extraction algorithm is based on the following observation : The Web pages are segmented into atomic text blocks, while the review/comments in web pages follow different types of layout. We observed text types like boilerplate, content, as well as other classes like headline, user comments etc. We noticed that comments are mainly in specific redundant nodes. Therefore, we based the system on a specific DOM tree algorithm named DOMScrapRev for the detection and the identification of the comments nodes regardless the heterogeneity of the page structure and only keeping the most useful texts, excluding redundancy and keeping the most valuable reviews.

The system RevScrap

At a first place, our approach intend to provide a user-friendly and minimal effort environment.

In the first step we define a set of keywords : a set of terms semantically close to opinion (in our case), which are the input to search engine request, for example in french a keyword could be avis utilisateurs + item. For our tests, we defined equivalent keywords in three languages : english, french and greek and we used the google search engine and saved all the matching returned URLs. This lexical cross by using synonyms in the request avoids to get URLs only with a description of the item, without users reviews. A first parsing is taking place once the request is treated and the search engine returns matching URLs. A filter is applied to remove advertising or formatting type of pages for instance pdf or ppt format. This reduction is necessary to avoid useless or irrelevant links. Each returned page is processed by the RevSCrap DOM top down tree-parsing algorithm. By processed we mean partitioning the page in several content blocks according to W3Cs DOM architecture. Based on DOM (Document Object Model) which identify the logical structure of documents and the way it's handled in term of access and manipulation.

In a DOM, a Web page can be parsed and represented with a tree structure which models the parent-child relations between HTML tags, and in which leaf nodes contains content or anchor texts. Fig. 1 shows an example of a graphical representation of a DOM tree.

Figure 1: A graphical representation of a DOM tree example Our approach is based on the assumption that in a given HTML page divided in blocks, the comments are based in the repeated nodes of a sub block. Thus we process the page looking for the repeated nodes. the content of the nodes that are repeated more than six times with an average content superior to 250 characters are set as possible review content to be retrieved. A less important number of characters may lead to retrieve irrelevant content as links, images, etc. All the content of repeated leafs nodes are marked as possible reviews and saved for further processing after reduction of the potential appropriate nodes. We present the module that deals with the problem of filtering the web pages and summarizes the recursive nodes in the next section.

Filters

This module deals with the reduction of "noise" of the potential nodes containing relevant information to our request text data. Web Reviews are usually associated with scores, stars evaluation and most likely dates. The first tests performed on the filters tend to show that the Date node is the most common node associated with reviews. Therefore we set the Date node as the first filter associated with the matching retrieved comments, the algorithm jump up to the third ancestor looking for a date Node. A second filter is associated to the comments that have an URL who doesn't completely match the seed search word. For this purpose we proceed with a pattern matching parsing and a query matching to all the retrieved comments with non matching URL. For example, for a query of type : "avis samsung galaxy S4" it is possible to retrieve comments associated with an URL of a galaxy S5 as shown in the figure 2. Thus, this second pattern matching filter is set to avoid these mismatch cases. In the figure 3, we used the same keyword query for "samsung galaxy S4" in greek, another UTF-8 language, and as we expected, some URLs returned ok and some mismatched. We applied the filter in order to avoid activating mismatched web pages In addition to the previous listed filters, the system identifies the review URLs with multiples review pages and sink in theses pages to retrieve all the comments associated with this pages.

1

 1 The system RevScrap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 3.2 Filters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.3 the overall algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3.4 Aspect -Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Figure 2 :

 2 Figure 2: A URL mismatch with a seed word

Figure 3 :

 3 Figure 3: Example of query in Greek and some returned URLs

the overall algorithm

The overall algorithm is as follow : 1 : Set<S t r i n g > q u e r y R e s u l t s = g e t G o o g l e R e s u l t s ( r e q u e s t ) ; 2 : f o r ( S t r i n g r e s u l t : q u e r y R e s u l t s ) 3 :

u r l L i s t = c r a w l ( r e s u l t ) ; 4 : end f o r 5 : f o r (URL u r l : u r l L i s t ) 6 : treeDOM = treeDOMConstructor ( u r l ) ; g e t a l l nodes with t h e l e v e l 6 :

i f ( number o f upper than 5 ) 7 :

g e t t e x t o f a l l nodes ; 8 :

i f ( medium t e x t l e n g h t o f nodes > 3 0 0 ) 9 :

listeNodesOfComments . add ( nodes ) ; 1 0 : end i f 1 1 : end i f 1 2 : end f o r 1 3 : d a t e F i l t e r ( nodes . t e x t ) ; 1 4 : end i f ; Algorithm 4: commentsSearch

Aspect -Results

The resulting output is a collection of xml files with the following tags : idcomment, content, score, domain, path and URL, as shown in the following figures :

Conclusion

The goal of our work is to automatically create a user-friendly system able to build review corpora, in different languages, according to user's specific thematic query. The system provides an interactive interface working sequentially based on a step by step method. First of all, we set the terms standing for the opinion mining keywords. A small lexicon of synonyms is then created that will be used in search engine query in order to widely cover the query's semantic field. The search engine returns many URLs and a first filter is applied to remove advertisement and format type web pages like pdf. The links are activated after parsing and filtering the relevant html nodes. The nodes of opinion data are detected and parsed. The data is then gathered to xml documents highly reduced from noises. Thus, the first test batch was set to compare the RevSCrap system to a hand made one, both performing the same query search in order to evaluate the RevScrap capacity in retrieving only relevant comments, the idea was to query the same product review and compare the results, the selected queries are "avis Samsung S4" and "avis iphone 6". For tests purposes we set a test threshold fixed at the first 100 returned URLs.

The following tables showed the resulting results : According to this experiments, we can state that RevScrap returned greater results regarding, the number of relevant retrieved comments and relevant URLs. We can achieve high link coverage without a greedy time algorithm.


Mehdy Dref

Anna Pappa

An interaction approach between services for extracting relevant data from Tweets corpora

An interaction approach between services for extracting relevant data from Tweets corpora

Mehdy Dref, Anna

Introduction

Since the emergence of social networks and real-time public information in the Internet, the continuous changes of the web in the Era of the big data makes the data collection and processing harder by humans operators. It's the information monitoring, which characterizes all the implemented strategies that keep us informed about a special subject, in the least time possible and by using automated (signal) reporting processes, which is the most impacted.

Yet this domain is increasingly highlighted by the industry and politics to monitor their ecosystem and ensure the good image/reputation of their brand image or to monitor and adapt their communication strategy.

We consider that the analyst's work requires a special infrastructure adequate to software agents to operate, to compose and make sense from the contents of the Web resources. We demonstrate this need through the development of a multiagent system oriented services interactions.

Therefore, our contribution follows the different construction techniques and updates ontology proposed in the literature and in particular the socalled adaptive multiagent systems. These techniques aim to extract new terms and to integrate them into the ontology [START_REF] Maamar | Toward an agent-based and context-oriented approach for web services composition[END_REF].

The technique we propose is based on the detection phrases via the ontological database used as DBPedia [START_REF] Auer | Dbpedia: A nucleus for a web of open data[END_REF]. To achieve this, we have developed a prototype that incorporates part of the work done by the SMAC team LIFL by developing a multiscale model for the simulation oriented interactions [START_REF] Kubera | IODA: An interaction-oriented approach for Multi-Agent Based Simulations[END_REF] by moving towards the use of 'Agents acting as an interface between the system and an online service such as databases of Acronyms, Synonyms, Homonymes. At a global level, the system treats each syntactical groupe (nominal, verbal) extracted from the corpus of messages and verifies whether it is possible to associate them directly to a DBPedia knowledge. In case of failure, these service agents interact with each other in order to find the best possible answer to the problem, by operating directly in the phrase, trying to semantically modify it, until the association with ontological knowledge becomes possible [START_REF] Ottens | A Multi-Agent System for Dynamic Ontologies[END_REF], [START_REF] Picault | PADAWAN, un modèle multi-échelles pour la simulation orientée interactions[END_REF].

If the process doesn't succeed, the phrase is not extracted from the message and is considered irrelevant. The advantage of our approach is its modularity ; the possibility of interactions between services, it is both possible to add / modify / delete a service or define a new one, and then influence the outcome product.

Following the implementation of our prototype, we could compare the results extracted from a heterogeneous body of messages from the Twitter [START_REF] Kwak | What is twitter, a social network or a news media[END_REF] social network with Tagme method [START_REF] Ferragina | Tagme: On-the-fly annotation of short text fragments (by wikipedia entities)[END_REF], which approach is based mainly on storage and annotation of encyclopaedic corpus.

That may become disabling whether considering the changing aspect of Big Data and the needs of industry in order to benefit the realtime information from constantly updating databases as DBPedia.

TAGME the On-the-fly Annotation of Short Text Fragments tools

As mentionned in [START_REF] Ferragina | Tagme: On-the-fly annotation of short text fragments (by wikipedia entities)[END_REF] "In the domain of the fast annotation of short message in social network, TAGME is a powerful tool that is able to identify on-the-fly meaningful short-phrases (called "spots") in an unstructured text and link them to a pertinent Wikipedia page in a fast and effective way. This annotation process has implications which go far beyond the enrichment of the text with explanatory links because it concerns with the contextualization and, in some way, the understanding of the text."

Tagme uses a snapshot of Wikipedia, from the November 6, 2009. The datas are indexed locally. Anchors were drawn from Wikipedia pages, so they added the titles of redirect pages and some variants of the pagetitles.

"The idea is to manipulate the indexed data, by using for example statistical methods to find the most relevant keyword to enrich the initial short text."

As indicated, TAGME requires at first to recover data from an indexed knowledge database, which is problematic for us in terms of storage in a big data context and in a real-time context. This is why we implemented an approach using the full capacity of big data, by using services agents communicating, in order to find the best result, taking into account the context and databases that can evolve in real time, and also to provide new exploitable informations at any time, or news in real time, like it's the case with Twitter.

In this work, we will explain our ideas by using some examples, and we will compare our approach with Tagme only about the relevance of data. We are not concerned in the scope of the performance in this paper, although we don't forget this important aspect as you will see in the next parts of this paper.

The main interest of our approach is to provide a system capable of processing lexical ambiguities within a corpus of tweets in order to extract from a data stream relevant and useful messages to build a corpus. Therefore, the method is connected to different APIs developed to retrieve data from a stream on Twitter and allows to analyze, in real-time or not, a source message.

The selection of relevant messages is an important part of our system because it permits to filter a huge amount of data and select a subset of messages to analyze in the next step.

Automated building of a corpus of tweets

To introduce our work, it's necessary to define and explain what is Twitter and why this social network is really useful for our work. As mentionned in [START_REF] Kwak | What is twitter, a social network or a news media[END_REF] : "Twitter, a microblogging service less than three years old, commands more than 41 million users as of July 2009 and is growing fast. Twitter users tweet about any topic within the 140-character limit and follow others to receive their tweets."

• Number of monthly active users (MAU): 304 million; • Number of monthly active users who post tweets: 117 million; • Every minute 350,000 tweets are posted on Twitter, or 183.96 billion tweets per year.

So you understand now why Twitter is a good research study subject to retrieve a huge amount of data. Our system of fast annotation of short messages is also usable for the automated construction of a thematic corpus and we will see how we do that. But before that, we will explain how we retrieve data from the studied social network.

As mentionned below, Twitter developpers propose two mains APIs. For our work, we built a third API from scratch by using the Python programming language to retrieve more data without the limitation from the Twitter company.

So, in the case of Twitter, we have for now three types of APIs that we can compare :

• JSON API (limited but allows to retrieve published data);

• Streaming API (interesting to retrieve text in real time without limitation);

• From Scratch API (automatic scrapping that simulates a browser. Good compromise between the two approaches but it needs to be modified when the twitter structure evolves.

There is no time or query limitation with our API).

In this step, we can define three ways to retrieve messages. We combined the three APIs to build an Agent in order to retrieve a data stream.

The result produced by this Agent may also be used in others professional contexts, such as the real-time monitoring.

After building this Agent, it's necessary to find a good way to select relevant messages. For this, it's important to define what is "relevant". To illustrate this idea, we can make a real-time search from a hashtag (a keyword related to an event, for example) on Twitter and index in real-time all messages about this event.

If we study for example the extraction of messages mentioning the President of the United States of America, Barack Obama, the primary idea would be to list all the keywords that can refer to the U.S. President. After that, we just have to detect in the stream or in the feed of messages the presence or absence of these keywords.

Here is a part of this list :

• Barack Obama • Barack Hussein Obama • Obama • President Obama
• The president of the United States of America

• The president of the USA

• Brack Obma (mispelling case)

• @BarackObama (mention on Twitter)

• ...

The main difficulty of this simple approach is to list a complex set of elements relative to the President of the United States of America. So we implemented a system that has the ability to work without this complex list. We simply indicate that we want to use the Barack Obama's resource on DBPedia which correspond to the Barack Obama's page on Wikipedia. We can define a resource in DBPedia with a link like in the following table. Our system will be able to associate each type of name relative to Barack Obama with the knowledge database by using several services that we have to define previously.

Keywords

Resource Barack Obama http://dbpedia.org/page/Barack Obama Table 1: DBPedia Ontological Resource For example, if I'm interested in tweets of "Barack Obama", I will need agents for:

• messages with one or more spelling mistakes ;

• the message with relatives phrases: President Obama, Obama, President of the United States ... For this, after extraction of phrases that we want to analyze, a first comparison with data from Wikipedia is performed and if it fails, the problem is transmitted to others services that will try to solve it.

In the case of spelling errors, the system will use a service able to offer spelling corrections like it iss the case when performing a Google search. After this step, the corrected phrase will be resubmitted to Wikipedia. Other correction methods are also used in particular, thanks to the modularity of our system.

If that fails, we use a service based on a Google search result that allows to obtain results of an expression such as "President Obama" to retrieve a set of Bi-Grams on the search results that we sort by frequency. We can match via this method "President Obama" with "Barack Obama" that allows the final tweet validate and incorporate our corpus.

In addition, since knowledge databases of several Internet services are updated regularly, if a new name for the President of the United States of America appears, it will be associated to our main resource.

The effectiveness of the system will be determined by the number of services used, but also by the size of the interactions list, and by the order of priority assigned to each interaction.

Our corpus generation system uses other parameters such as the dates of beginning and end, relationships between a speaker and someone who interests us (i.e. people following each other), etc. Since this system is based on the Twitter's API, it is possible to use a certain number of parameters to target messages that can potentially interest us.

Twitter offers the following list of parameters :

• delimited

• stall warnings

• filter level • language • follow • track • locations • count • with • replies • stringify friend id
The progressive dimension of the system through flexible agents permits to adapt our tool for a lot of professionnal tasks.

Our initial approach

After retriving all the "good" messages, it is necessary to analysze each message to extract data from DPedia database (or Wikipedia).

Initially our method is divided into three stages. It takes as input a short message and gives in the output a text enriched by links to Wikipedia or DBPedia.

• Split the content (using POS tagging with a from scratch algorithm to split and order the content) ;

• Use knowledge databases to associate data. ;

• Extract data.

To split the content of a message, we use at first a service that produce morpho-syntax graph as known as part-of-speech tagging (POS tagging or POST). It consists in the identification of words as nouns, verbs, adjectives, adverbs, etc, in a message. Also, the part-of-speech tagging works with relationship with adjacent and related words in a phrase, sentence, or paragraph. There is a lot of POS tagging services on the Internet as http://mshang.ca/syntree/ or http://ironcreek.net/phpsyntaxtree/ In a multilingual context, it will be possible to define as much POS tagging agents as languages. For that, it will be necessary to build for each language a specific precondition as "is french(word) or is english(word). The precondition in the interactions list will guide the agent's choices toward the best method.

Description of a simple agent-based service

The smallest element of the system is called a reactive service agent. It is a simple agent that takes an input data as an argument and that connects to a service to retrieve information that will be returned. A simple agent takes as input between 1 and n n-grams and returns the output from 1 to n n-grams. For example, take the case of an acronym agent who takes an acronym parameter and returns a list from 0 to n possibilities. In addition to the simple agent, a complex agent has the ability to take decisions. For this, it has a list of interactions that allows it to choose who to contact first. Just like the simple agent, it takes as input between 1 and n n-grams and returns the output from 1 to n n-grams. It can internally have an algorithm for processing the data received by the online service to filter the results, for example. This agent may be reactive without limitation, cognitive or hybrid.

About the list of interactions, it is similar to the interaction matrix of the IODA methodology of the SMAC team of the Crystal laboratory of University of Lille 1.

We can define an interaction by a set composed of a target agent and a precondition (is an acronym() for example). Consequently, if FOO is an acronym, then we will call the single agent that we defined in the previous section. If necessary, a precondition may itself call a simple service or locally use an algorithm. The modularity of the system allows to compose a multi-agent system, taking into account the constraints of the system developer. About the interactions list, there is two common ways to build it : by building a complex agent with interactions to communicate with simple agents, or by building an agent that communicate with others complex agents. The main interest of the second approach is the modularity. Indeed, we can delegate several parts of the system and modelize sub-systems. The main interest of the last method is to wrap all acronym agents mentionned previously, in a specific agent.

Priority precondition

To explain how the system works, for each element, the agent will check if the n-gram is an acronym. If not, it will try to split the string to see if any of the items is an acronym.

If an acronym is found, the system will attempt to retrieve the equivalence. And if nothing is found, then the acronym agent will return None and the system will try to split again the string if it is possible. The interactions list will be called again.

We won't discuss more here about complex preconditions that need to introduce the concept of multi-scale oriented interactions multi-agent system but we refer you to [START_REF] Picault | PADAWAN, un modèle multi-échelles pour la simulation orientée interactions[END_REF] for an introduction to this important field about our future works.

A multi-agent-based model for service-oriented interaction

We consider that any Internet data present can become a service within our system. It can be a simple web service or a more complex service whose results are generated through the result produced, for example, by a search engine, according to algorithms that may be favorable to us. And this is the case for our agent that allows the modification by substitution using frequency algorithm on google search results. This agent takes into account the fact that Google results are often linked to current events. Therefore, relevant results dealing with current themes appear in the top of the search engine page, and may fill the entire first page.

It is from this observation that we have put in place an agent that can find "synonyms" of the searched term.

To be more specific, lets take the example of Barack Obama, who is the main object of our study in the context of this paper. As you know, there are lots of way to name the President of the United States. The idea is to understand that a search engine like Google will be able to provide reliable correspondence information (contextually), whatever the term used. This allows me to substitute the bi-gram "Barack Obama" to the bi-gram "President Obama". This resolves an ambiguity regarding DBPedia and validate the message.

In the same idea, it is possible to use Google as an agent spellchecker. As you know, Google is able to propose corrections via its suggestion module. Therefore, it is easy to retrieve a correction of a term and to associate it, collecting the proposed data.

Figure 5: Google as a service for fixing spelling mistakes As mentioned in the example, it is possible to find Barack Obama in the page search for "Brack Obma" and for every other research with a spelling mistake. We can then propose a spelling checker agent which is also based on Google.

To conclude this section, one should know that a web service can be understood broadly and that a web page is able to provide a multitude of exploitable services, in order to have relevant data, updated in real time.

We will take as an example a message posted by the President of the United States, Barack Obama, about the net neutrality and the FCC. In some cases, we have to remove some elements. It is the case, for example, when we have a stop word (a stop word can be found with a dedicated service). In this case, we remove "of" and "a" because there is a n-gram next to them. Also, we remove the "in" between "voted" and "favor", because "voted" is a verb. We can also remove "the", because it's a stop word and we have a mention next to it. That means that we have to treat the mention separately, because it is destinated to someone in particular. The link will be analyzed in the same way. We won't describe the algorithm for obvious reasons, but you can find in the next lines how we treated this kind of data. If the entity is a link, then our system will use an agent that will analyze the page. The agent will extract a set of data that will seem relevant by the system designer, which we define below:

FCC Voted Favor free and open internet

• content of the title tag

• content of the h1 tag

• content of the meta description tag

• content of the first h2 tag

• the link will be ignored In general, unlike TagMe, our approach permits to gain in quality. This quality is gained by three ways : either by proposing an identical extraction, either by proposing a more specific extraction, or by proposing a reduced extraction (by deleting non relevant elements, for example).

In term of performance, we are not able for now to evaluate our approach compared to TagMe, and as indicated in the beginning of this paper, this is not our goal.

Conclusion and outlook

To conclude, after the implementation of our prototype, we were able to compare the results extracted from a heterogeneous corpus of messages from the Twitter social network with the TagMe method. Remember that the Tagme approach is based primarily on storage and annotation with an encyclopaedic corpus, which can be outdated if we consider the changing aspect of Big data and the needs of the industry to get informations and knowledges in real time.

Additionally, about industrialistss needs, it will be quite possible to consider a system that will be linked with the companys products catalog, with customers, or suppliers, instead of a knowledge database as DBPedia. This system will be able to propose an extraction of relevant messages, that will be analyzed and exploited as part of a business intelligence. Therefore, the company will be able to adapt its supply and demands to the target market.

Finally, the strenght of our approach is based on its modularity, undoubtedly. By proposing an adjustable approach based on a multi-agents system, the system will be able to be adapted to several problematics, going beyond social networks. Moreover, comparative approaches will be lead to determine for every agent the perfect service and the perfect algorithm, depending on needs, and that will be the object of our future works.

First, one of our future works is to integrate a "feeling" agent for evaluate the sentiment expressed in a message and therefore extract, for example, only negative messages that allow to modelise a precise aspect of a brand's eco-system, for example. So it will be possible to retrieve in a stream only messages with positive opinion.

Next, as mentionned, we also work in a Multi-scale paradigm. In the futur, we will implement some ideas to improve our system.

And finally, as indicated at the beginning of this paper, we want to work with ontological knowledge database to produce a specific and thematic domain ontology from social network data included without limitation, opinion, relationship between users, influence. For that, we will define a ontological template to represent the social media communication on the Internet. Our system will be able to generate knowledges from social network extanded by DBPedia knowledge.

Figure 1 :

 1 Figure 1: A simple AcronymFinderAgent

Figure 2 :

 2 Figure 2: A first tweet from the US President

Figure 3 :Figure 4 :

 34 Figure 3: Google research for "President Obama"

Figure 6 :

 6 Figure 6: A second tweet from the US President

Figure 7 :

 7 Figure 7: A morpho-syntax graph from the tweet

Table 2 :

 2 Interactions list for an Agent that communicate with simple agents

	Target	website

Table 3 :

 3 Interactions list for an Agent that communicate with complex agents

	Priority	precondition	Target	website
	1	is an acronym AcronymFinderAgent http://www.acronymfinder.com/
	2	is an acronym AcronymSearchAgent http://www.acronymsearch.com/

Table 4 :

 4 Interactions list for a complex AcronymAgent

Table 5 :

 5 1st step of the analyze

	Free open internet
	Table 6: second step of the analyze

Table 7 :

 7 Comparison of results


Victor Lequay
email: victor.lequay@liris.cnrs.fr

Mathieu Lefort
email: mathieu.lefort@liris.cnrs.fr

Saber Mansour
email: saber.mansour@ubiant.com

Salima Hassas
email: salima.hassas@liris.cnrs.fr

Flexible Load Shedding using Gossip Communication in a Multi-Agents System

In order to balance production and consumption on the power grid, efforts are mostly made on the production side. Demand response is a classical solution consisting in harnessing electricity consumption to allow the introduction of renewable energy sources and self-production in the energy mix. In this context, the main problem is to coordinate the network nodes, considered here as agents, in order for them to be able to anticipate their need and also to adjust their contribution to the collective load-shedding effort. To tackle this last point we present an original bottom-up approach of distributed load-shedding with a decentralized algorithm based on gossip protocols. These protocols offer both reliability and scalability to be used on a large scale power grid. On this ground, we built an efficient decentralized control mechanism using a selfevaluation process improving the system performances. In this paper, we present our model and evaluate it using realistic simulated data. We then discuss current limitations and further improvements as part of future work.

Introduction

The energy sector undergoes dramatic changes as home electricity consumption raises steadily. Indeed, to satisfy the energy demand, new production units have to be plugged, adding complexity to the network as well as financial and environmental costs. Moreover these equipments are designed to sustain peaks in demand, which means that they are almost never operating at full capacity, thus generating additional costs. A simple solution to this problem would be to act on the demand side to spread or reduce the load peaks instead of increasing production to match them (see figure 1). This concept, named load shedding, allows to greatly reduce the environmental impact of electricity production while being way cheaper. Load shedding has been around for many years but was almost uniquely used in the industrial sector because consumption is controllable and highly demanding operations can be anticipated days ahead and easily postponed if necessary. A broader use of load shedding in network management needs to extend its principles to smaller, less predictable and distributed loads : homes. This idea, named distributed load shedding, may seem obvious at first glance, but a fair number of constraints must be satisfied to be integrated in the main power grid and accepted by the end user. This means that in addition to reactivity, reliability and capacity criteria, the system has to be strongly ergonomic and adaptive.

In this article, we present a solution which satisfies all these constraints. Our work is based on Hemis 1 , a smart building energy management system developed by Ubiant in collaboration with the LIRIS laboratory. Hemis is able to compute in real-time the load shedding capacity of a building with respect to the user's comfort. This information will be transmitted to the system we present in this article, whose decentralized architecture allows to precisely and adaptively control and shed the energy consumption of a large number of buildings. This architecture has been designed with scalability in mind, paving the way to manage thousands or even millions of homes with minimal need for an increasing processing power or any costly network infrastructure. We had two main goals. Firstly, to be able to operate in near real-time while maintaining the high quality of service needed for a smooth integration in the power grid. Secondly, to make our system as light as possible, allowing us to manage a possibly large amount of homes. These two competing objectives led us toward a fully decentralized approach that we explain here. We will first present an overview of the related work on 1. http://www.ubiant.com/hemis-ubiant/ distributed load shedding in section 2. We then introduce our model in section 3 and discuss our simulation results in section 4, before concluding and presenting some possible ways to improve our model as part of future work.

Distributed load shedding

Load shedding techniques have been used for long to balance consumption in the power grid, but until now it was mostly deployed to big consumers like factories or shopping centres. The adjective distributed refers to the integration of smaller loads into the system. In this paper, load shedding will always refer to distributed load shedding as we designed our system to allow any kind of load of any curtailment capacity. Load shedding raises many issues at different levels of abstraction, that could be summarized in 3 main points differentiating the existing approaches. The first one is the transmission media chosen to exchange orders and information between the operator and the end users. It represents an important part of the system costs and plays a major role on its scalability and reliability. A direct link permanently established between each client and the operator means a heavy and costly infrastructure in most cases, but also allows a nice reactivity. On the contrary, if connections are not permanent, the frequency of the connection becomes critical to the quality of the shedding. This is why most of the works on this topic use a permanent connection to the operator. The second main issue is the kind of control the system has over the loads to start a shedding. Usually, a price signal is used : the provider changes the energy price to encourage users to consume more or less, depending on the needs of the grid. This kind of incentive system is extremely easy to set up but suffers from bad reliability because the end user's reactivity to a change in electricity price is never guaranteed and even less predictable [START_REF] Callaway | Achieving Controllability of Electric Loads[END_REF]. Moreover, if the end user fails to manage his energy consumption correctly and continues to use his appliances normally when the price goes up, the impact on his electricity bill could be enough for him to withdraw completely from the system. These issues make this price based approach more adapted to less restrictive needs, like the global curtailing on daily peaks, where simple pricing schedules can be issued to consumers. Nevertheless, as a signal or incentive, the electricity price can be an interesting ground for building distributed load shedding systems [START_REF] Sarvapali | Agent-based control for decentralised demand side management in the smart grid[END_REF] [START_REF] Amir-Hamed Mohsenian-Rad | Autonomous Demand-Side Management Based on Game-Theoretic Energy Consumption Scheduling for the Future Smart Grid[END_REF]. More recently, the interest of the energy sector has been caught by more straightforward controlling solutions.

The third point is the algorithm that controls the connected loads. The challenge is to provide a quick and reliable answer on a given curtailment capacity, then maintain the stability of this curtailment until the end of the event, while making sure that the user's comfort is not altered and ensuring as much as possible a fair sharing of the effort between each concerned load. On this topic, existing approaches can be classified according to the degree of centralization of the decision process. On one end of the spectrum, a central server sends simple binary orders to connected appliances which respond immediately. On the other end, each load decides when to switch on and off, sometimes depending on external information.

Centralized algorithms applied to some real cases are mainly based on statistics. Historical systems, like the Centralized Remote Control by Musical Frequency ("Télécommande Centralisée à Fréquence Musicale") from EDF (historical French operator) [START_REF]Materiels emission et de reception de telecommande centralisee a frequence musicale[END_REF], allow the operator to remotely shut down some equipments like the water heater if the user subscribed to a dedicated contract. Also, as most of the consumption is basically delayed, such a method may later create an even higher peak than the one the operator wanted to reduce at first [START_REF] Callaway | Achieving Controllability of Electric Loads[END_REF]. This effect is naturally reduced by stochastic systems which randomly spread the loads curtailment and can be avoided in a centralized way only if loads are individually manageable, as in this case it is easy not to power on all appliances at once. More recent works on centralized load shedding systems sometimes use techniques coming from the field of artificial intelligence like artificial neural networks [START_REF] Hang | Application of Artificial Neural Network in Intelligent Building[END_REF] or reinforcement learning [START_REF] You | An intelligent adaptive load shedding scheme[END_REF] to automatically choose the most efficient strategies.

Some decentralized approaches use multi-agents systems. Often based on price incentives [START_REF] Sarvapali | Agent-based control for decentralised demand side management in the smart grid[END_REF][7], most of them use a stochastic approach to force spreading of the agent's actions in time, thus smoothing fluctuations or overshoots that could happen when using a simple hysteresis system [START_REF] Mohammad | Distributed Frequency Control in Smart Grids via Randomized Demand Response[END_REF] [START_REF] You | An intelligent adaptive load shedding scheme[END_REF]. Likewise, Beal and al. [START_REF] Vinayak | Distributed Control for Small Customer Energy Demand Management[END_REF][10] [START_REF] Beal | Fast Precise Distributed Control for Energy Demand Management[END_REF][8] suggest a stochastic algorithm called ColorPower which allows a distributed control of the energy demand. The idea is for the end user to set up a kind of connected plug that can switch off or on his devices. This plug switches randomly with a probability that is constantly updated according to a signal sent by a central server. This signal increases the probability of shutting down during a curtailment effort, and reduces it otherwise. These systems have one major drawback which is due to their probabilistic structure : they cannot be efficient unless a substantial amount of plugs are connected. Indeed, using this system, the available curtailment capacity is not the total one because every load does not automatically take part in the effort. That is why purely stochastic systems need a minimum number of partakers in order to ensure a sufficient load shedding capacity and are hard to set up incrementally [START_REF] Frey | A holonic control architecture for a heterogeneous multi-objective Smart Micro-Grid[END_REF].

Our model

To solve the different issues raised by the existing systems seen above in terms of user comfort, cost, adaptability and scalability, we chose to overturn the problem and to start from the user. Our bottom-up approach is to our knowledge the first one to focus In this section, we will start by presenting Hemis, the smart energy management solution over which we will build our system. We will then explain the goals our model has to achieve and also the constraints it has to comply with. We will also describe our decentralized model for a near real-time distributed loadshedding management.

Hemis: Home Energy Management Intelligent System

Developed by Ubiant in collaboration with the LIRIS laboratory, Hemis is a smart building energy management system. Based on a multi-agents system solving a multiconstraints optimisation problem, Hemis is able to maintain a desired level of comfort (meaning a correct temperature, lighting, air quality, etc... with respect to the user's habits and preferences) while automatically lowering the overall energy consumption. Connected appliances (heaters, lights, sensors, electrical roller shutter, etc...) are represented in the system by reactive agents collaborating on shared marking spaces to achieve the objectives of all environmental factors. The user simply sets theses objectives and the agents collaborate to find the best trade-off between comfort and energy consumption.

Hemis relies on two sources of information to determine the curtailment capacity of the building, that we call flexibility. The first one is a learning based on a local record of the user's habits and energy consumption, combined with realtime data from the sensors (if the weather is unusually cold, the electrical consumption will not be the same as the last days). The second one is the sum of individual anticipations from the agents themselves. The predicted flexibility takes into account every connected or known device, even if they are not currently on. Indeed, a load shedding can either be done by shutting down some equipments but also by not turning on an appliance when it was supposed to be, by advancing or postponing its use (for example by heating a room a little earlier while benefiting from the thermal inertia).

It is important to notice that the user stays in control of its equipments even during a load shedding. If an appliance is switched on despite a shedding being engaged, it will not be forced off by the system. The flexibility is then simply updated with this new piece of information.

The problem statement

In the following of the paper, we assume there exists an intelligent system as the one presented in the section 3.1 giving us the ability to know at each time t the flexibility f a of the building a, which is defined as the amount of energy the building can shed without diminishing the user's comfort. The reliability of this data is of course crucial to the efficiency of the system but our architecture is robust enough to tolerate a difference between the anticipated and the real value of the flexibility. Let N = {a 1 , a 2 , ..., a n } be the set of buildings equipped with this system. At each time, the total flexibility (or total shedding capacity) of the system is F = a∈N f a . To satisfy a request of a given curtailment capacity Q, each agent a will reduce its consumption by some amount x a . During the event, it is very likely that one or more buildings will have their flexibility updated, most of the time reduced or even brought down to zero. To ensure a stable curtailment, the system will have to update x a , ∀a ∈ N as quickly as possible so that a∈N x a = Q at almost all time. In the next section, we introduce our architecture that achieves these stability and reactivity requirements in a decentralized manner and without using any kind of price incentive.

Our distributed load shedding architecture

To answer the problems outlined in section 3.2, we propose a decentralized approach based on a multi-agents system inspired by gossiping algorithms. An agent represents a building that knows its flexibility in real time, as presented in section 3.1. Thanks to a gossip-based aggregate computation algorithm, that we will describe in section 3.3.2, each agent also knows at each time the value of various variables concerning the whole population. These variable are essential to the system as they are the core of the coordination between the agents. They will be described in section 3.3.1. The aim of the decentralized system is to determine for each load shedding event the amount of participation of each agent. For this purpose, each agent locally self-evaluates on various criteria and assigns itself a mark, representing its level of performance. When the agent receives a load shedding order, it will engage a certain amount of its total flexibility depending on its mark. Following the event, the agent will update its mark according to its performance. This process allows the system to improve the quality of the load shedding at each event (see section 3.3.3 for details).

Shared variables.

For the algorithm to work, agents need to know the value of some variables carrying information about or concerning the entire population.

•

The order O is a triplet O = {Q, t d , t f } with Q the amount of energy to shed between t d and t f . This order is initially sent to one or more agents by the energy producer in a fully reliable way.

•

The total participation agg is the sum of all the capacities the agents have committed themselves to be able to shed at every moment.

•

The best mark g max is the highest computed mark of any agent at a given time.

• Variable c max corresponds to the highest participation of an agent amongst the population during the m last events.

• Variable r min corresponds to the lowest failure average of an agent amongst the population. These variables are propagated and computed in a decentralized manner with the Push-Sum algorithm that we describe in the next section.

3.3.2.

The Push-Sum algorithm. The Push-Sum algorithm, presented by Kempe et al. [START_REF] Kempe | Gossip-based computation of aggregate information[END_REF], allows a group of agents to collectively process the value of an aggregate information (sum, mean, product, maximum, minimum value) in a completely decentralized way using what is called an epidemic or gossip propagation model. In their approach, each agent a possesses three variables : x a is the agent's value that will be aggregated with the other's (the agent's part in the shedding for instance), s a is a sum -initialized to x a -and the weight w a -initialized to 0 or 1 depending on the kind of calculation. If we want to compute a sum for example, w will be set to 0 except for one agent whose w will be set to 1. At t = 0, each agent sends the pair (s a , w a ) to itself. At each time step, a fraction α a,j of s a and w a is sent to a set of J agents so that j∈J α a,j = 1. Values of s a and w a are then updated by summing every pair (α j,a s j , α j,a w j ) received by a : s a = j∈J α j,a s j and w a = j∈J α j,a w j . The estimate value of the aggregate for one agent is agg a = s a w a . Kempe et al. show that, "given a γ and a δ, the relative error in the approximation of the real value agg is at most γ with probability at least 1 -δ in at most O(log n + log 1 γ + log 1 δ ) rounds". This logarithmic complexity allows for scalability. The topology of the network defines the choice of the neighbours to which an agent sends its messages. The number of neighbours J depends on the network topology and the connectivity constraints. Convergence speed will increase with the number of contacted agents at each step. This algorithm also only works if the network is a connected graph, meaning that there is a path between each pair of nodes. The nature of the Push-Sum algorithm allows us to add and remove agents in real-time without affecting the stability of the system, the only consequences being a small disturbance in the values of the shared variables as the information propagates and an obvious variation of the total flexibility in the system. This "plug-and-play" property of our model makes it fault tolerant regarding connectivity. In this article, in addition to a decentralized summing, we also need to compute minima and maxima (for the agents to be able to rank themselves amongst the population). Computing minima or maxima consists in simply keeping the minimum or the maximum of the received values and propagating it. In these cases, values are not weighted by α.

It is relevant to notice that this algorithm allows for a straightforward implementation of performance monitoring features for the use of an operator. Thus, we will be able to know the number of agents having a specific value for any given parameter (reliability, participation, etc...), or the average participation and other standard statistical tools.

3.3.3. Self-evaluation. The agent computes its mark according to three criteria :

• reliability, which is the ability to reduce its consumption of the amount it was committed to shed, and hold its consumption at the same level during the entire event,

• the average flexibility it possesses given by Hemis,

• its frequency of participation to the previous efforts. Each one of these three criteria is evaluated considering the history of the agent and gives a mark between 0 and 1. The final mark of the agent is computed as a weighted mean of these three values. More precisely, the history M a of an agent a is a list of triplets M a = {(r a 1 , c a 1 , t a 1 ), ..., (f a m , c a m , t a m )} over the last m events with • c a i the amount of energy shed by the agent a during the event i • r a i the standard deviation to the initial commitment of the agent during the event i • t a i equals 1 if the agent participated to the event i, 0 else

The agent's mark g a is computed from its reliability R a , its average capacity C a and its turnover T a , based on the history M a .

•

The reliability score of the agent a is given by This mark goes up if the agent does not participate often, increasing its chance to participate to the next events. An agent who participated to all the last m events will obtain T a = 0.

R a = rmin
At the end, we have

g a = k 1 F a + k 2 C a + k 3 T a with k 1 , k 2 and k 3 being weighting coefficients so that k 1 + k 2 + k 3 = 1 and k 1 , k 2 , k 3 ∈ [0, 1] 3 .
These coefficients are continuously and autonomously adjusted by each agent. The reliability coefficient k 1 is increased when the curtailment quality decreases, that is when the sum of the difference between the requested load reduction and the effective one over the event is higher than during the previous events. This aims to choose reliability over capacity when there is a poor quality of curtailment. The capacity coefficient k 2 increases with the amount of time needed by the population to reach a consensus when an order is received, relative to the requested variation magnitude. Indeed, if the aggregated value is already near the targeted one, the time needed to reach a consensus on this value will be shorter than for a bigger gap. The goal here is to improve the ranking of the agents providing the biggest shedding capacity, in order to speed up the consensus process. These coefficients are set to some default value at the starting of the system, but could potentially be optimised beforehand. This coefficient adjustment process allows the system to adapt itself to changes in the user's behaviour through time, which could hardly be anticipated as it depends on multiple factors as economical or weather conditions for example. [START_REF] Wuhib | A gossiping protocol for detecting global threshold crossings. Network and Service Management[END_REF] used the Push-Sum algorithm to design a decentralized threshold crossing detection algorithm. Adapted from some of their concepts (an hysteresis and a low-pass filter), we propose a new algorithm that allows each agent to adjust its share on a collective effort to quickly reach a global objective by summing their contributions. The first step is to detect a gap between the estimated sum of the contributions agg a and the global objective Q. It may seem like an easy task, but individual contributions are constantly changing. To avoid an oscillatory behaviour when agg a Q, two complementary mechanisms are used. The first one is the use of a ratio 0 ≤ H ≤ 1 implementing an hysteresis around the target Q, damping small variations at low frequency due to the continuous variations of the agent's flexibility (see figure 2). A threshold crossing is then detected if

Adjusting agent's participation. Wuhib et al

agg a Q -1 ≥ H.
The second mechanism allowing a reliable detection is a kind of low-pass filter erasing quick variations. It is implemented with a timer t wait . To be taken into account, a crossing must be observed for at least t wait time steps. These two systems are combined to lead to an accurate threshold crossing detection by each agent despite the frequent variations due to the convergence of the collectively computed aggregate. When an agent receives a shedding order, it first determines its maximal contribution x a lim regarding its flexibility f a and its mark g a following the formula x a lim = g a gmax f a , g max being the highest mark in the population (see section 3.3.1). This way, the agents with the higher marks contribute more than potentially less reliable agents or than those who participated more frequently. If an agent observes a gap between the estimated global effort and the objective as seen earlier, it adjust its own contribution x a with the formula x a = x a 1 + Q-agg a agg a . If the low-pass filter timer t wait is correctly defined, it allows the agents population to stabilize the new value of the collective effort agg a before adjusting again, preventing additional swinging that could be due to continuous adjustment of individual contributions. If during its adjustment an agent reaches its virtual contribution limit x a lim , it updates this limit with x a lim = min (x a lim + (f a t -x a lim ) * v; f a t ), v being a variation coefficient (v ≤ 1).

Pseudo-code

Algorithm 1 represents the program run by an agent a. Variables are initialized during step 1. One will notice that we set w to 0 in this code, which means that one of the other agents will have its w set to 1 for the aggregation computation to work as a sum, as we explained when describing the Push-Sum protocol (section 3.3.2). Apart from this difference, every agent runs the exact same program. Steps 2 to 9 contain the implementation of the Push-Sum protocol. The processing and the propagation of shedding orders are done in steps 10 through 15. The virtual limit x a lim is set on step 12.

Steps 16 to 28 correspond to the threshold crossing detection and the adjustment of the agent's contribution. The hysteresis is found at step 16 as well as the low-pass filtering with the timer t wait .

Steps 24 to 28 allow to update the virtual limit x a lim . At the beginning of the event (step 29), obj a memorizes the committed capacity. This variable will be used later to compute the reliability score of the agent. The state variable represents the different stages of a load shedding event. When state = 0, the agent is idle. Receiving an order puts the agent in state = 1 until the shedding starts and then goes to state = 2. While state = 2, the amount of flexibility the agent has engaged in the collective effort directly impacts the consumption in the user's home. This has not been shown in the pseudo-code for clarity. At the end of the event (step 34), the agent updates its history H a and its coefficients k 1 , k 2 and k 3 then switches to state = 3 where it waits for the shared variables to converge before computing its grade. Self-evaluation computations described in section 3.3.3 are not integrated in this pseudocode. Turnover score computation (step 35) can be done immediately, as opposed to the capacity score C a and the reliability score F a which depend on variables that are collectively computed and therefore need some time to converge. This is why the agent waits t wait time steps while in state = 3 before computing C a and F a (steps 42 and 43). The agent's mark g a can then be computed (step 44).

Algorithm 1 Pseudo-code for an agent

a t = 0 1: x ← f, s ← x, w ← 0, state ← 0 t > 0 2: Let M = {(s * , w * , g * max , c * min , c * max )} be all messages sent to a during round t -1 3: s ← x t -x t-1 + M s * , w ← M w * 4: g max ← max M (g * max ) 5: c min ← min M (c * min ), c max ← max M (c * max ) 6: Let J ⊆ N \{a} be a set of j agents randomly chosen 7: α a ← 1 j+1 8: send (α a s, α a w, g max , c min , c max ) to M ∪ {a} 9: agg ← s w 10: if O = {Q, t d , t f } is received then 11:
send O to j agents 12:

x lim ← g gmax f a 13:

x ← x lim 14:

state ← 1 15: end if 16: if agg Q ≥ H then 17: if t -cnt 1 ≥ t wait then 18: x ← x 1 + Q-agg
g a = k 1 R a + k 2 C a + k 3 T a 45: state ← 0 46: end if 47:
g max ← max(g, g max ) 48: end if 4. Experiments

Test protocol

We evaluated our algorithm on realistic simulated data. In the following, we will describe this protocol.

Each building is represented by an agent which possesses a fixed electricity consumption of 3500W at all time. It also has a flexibility (in Watts) randomly chosen in the set {100, 200, 400, 500, 2000, 3000} (100W represents a few connected light bulbs and 3000W represents a water heater) , meaning an average flexibility of 1033W for the population, corresponding to a heater switching off with a slight dimming of the global lighting.

To simulate a realistic behaviour of the inhabitant, each agent is given a failure probability drawn from an exponential distribution. This is to reflect the fact that a lot of people will have a relatively good reliability, while some of them will systematically cancel their participation in the load shedding.

Before each event, the simulation determines if the agent will fail according to this probability. Once again, to simulate a realistic behaviour, we spread the agents failure over the time of the event, following a polynomial curve. To show different kinds of failure, we created two different behaviours. The first corresponds to users noticing a difference in temperature that are willing to turn their heaters up again, reducing the flexibility of their home. This results in a progressive failure of a part of the population, growing faster as time passes. In the simulation this is implemented by a polynomial repartition of the failure point of the agents. We later reference this scenario as the "heater scenario". The second behaviour is a lighting one in which users notice a dimming in their lightning, and turn them back up immediately. This is implemented by the inverted polynomial function we use in the "heater scenario", as the amount of agents failing will be high at the beginning of the event and quickly stabilise. The main difference between these two scenarii is the time when the user reacts to the shedding. In the case of the lightning, the users either notices it quickly or does not react at all, as in the heater behaviour a small temperature change cannot be noticed that fast thus leading to a slowly growing proportion of the agents reacting. We also ran tests with both scenario combined, applying the lighting behaviour to the agents with the lowest flexibility (as lower flexibility mostly comes from dimming lights only) and the heater behaviour to the agents with the highest one (as heaters offer a bigger shedding capacity). The initial weighting coefficient of the reliability score k 1 is set to 0.5, the capacity one k 2 is at 0.4 and the turnover coefficient k 3 at 0.1. The agents start with a mark randomly chosen between 0 and 1 and their history is limited to 10 events. We set the hysteresis to H = 0.02, the delay t wait to one time step and the variation coefficient to v = 0.5. When not stated otherwise, each agent communicate with j = 10 other agents chosen uniformly at random at each step.

Results

Our simulations had two main objectives. First, to show the efficiency of a multi-agents system in maintaining the curtailment stability in a decentralized manner. Figure 3 shows the ability of our system to compensate for decreases in the agents flexibility in real-time. We see that as the total flexibility of the population plummet following the disengagement of a part of the population, the aggregated shedding capacity is maintained, suffering only from small variations.The different scenarii illustrate the robustness of the system with respect to the behaviour of the end users.

Our system is able to maintain a stable curtailment and does not rely on the user's behaviour (the total flexibility has to be higher than the requested shedding capacity). Moreover, this quality is obtained without any supervising entity.

Then, to show the effect of the self-evaluation process on the curtailment quality, we compared the results obtained with and without the self-evaluation. we ran longer tests to allow the agents to gather enough information in their history to assign themselves a relevant mark. On figure 4(a), the agents self-evaluation is disabled. At each event, the agents commit themselves to their full flexibility. We see that the amount of engaged energy impacted by the changes in the flexibility of the agents stays the same. On figure 4(b), the self-evaluation is enabled. The ratio trend of impacted capacity over total flexibility loss diminishes over time instead of staying high, showing the ability of the self-evaluation system to optimise each agent's share . Finally, we verified the efficiency of the propagation algorithm by trying different connectivity levels on the agent to ensure that the gossip consensus process worked in various condition, even with limited connections between the agents. Figure 5 shows the performances of the system when each agent communicates with 10, 5 or 2 neighbours at each step. We see that the impact of the connectivity constraint is barely noticeable, as it really only impacts the convergence speed when the target value is far from the current value.

Conclusions and perspectives

Distributed load shedding is prone to quickly develop in the upcoming years. As a straightforward solution to the biggest current problems of the energy sector without major drawbacks, it offers an ecological way to keep the network running while allowing consumers to save energy and money. The biggest obstacle faced by existing systems and ongoing work is to be able to deploy such a system while not affecting the user's comfort with a system simple enough to be reliable on a large scale. Yet, in a centralized system, taking the user's comfort into account implies a constant and heavy two-way communication between the server and the nodes, limiting the system's scalability and flexibility.

In this paper, we presented an original decentralized architecture to solve this problem. Following a bottom-up approach, the user is the starting point of the process and stays in control at all time. The home energy management system deduces the energy the building can shed and transmit it to the system we built on top of it. By doing so, we guarantee the user's comfort at all time, as opposed to more demanding system like price-based ones usually presented in the literature. We then use a gossip based communication protocol between the agents to transmit the information needed for the process to work. It provides a robust and scalable decentralized architecture allowing the agents to quickly reach a consensus on their respective participation to the effort. During an event, the simple reactive behaviour of the agents ensures a stable curtailment, as any failure of an agent is immediately absorbed by the adjustment of many others. This adaptability is then improved by a self-evaluation process which ensure the fair sharing of the effort between the agent, depending on their reliability, capacity, and frequency of participation. Event after event, the population regulates itself to improve the quality of the curtailment. This self-evaluation process is then fine-tuned by a local optimisation process that adjusts the weighting coefficients on the go, considering the latest performance of the whole system (always in a decentralized manner).

Moreover we let the on-site system take care of the user and independently determine its share on a load shedding effort, separating the complexity and efficiency of the process from the number of partakers. It allows a fully incremental deployment of the system, whereas a simple stochastic approach cannot work without a minimal number of connected users. In our system, a single user can curtail its load if needed, as any declared flexibility can immediately be used by the system.

Our simulations on realistic data confirm the resilience and the self-adaptation ability of our system to guarantee a stable curtailment even when any agents are disengaging at once. They also show the efficiency and relevance of the self-evaluation mechanism to improve the quality of the shedding over time, underlying the need of preliminary benchmarking to provide a high quality of service from the beginning.

These promising results pave the way to further works on this model. First, we have to test our system in real-life settings with more demanding situations, in terms of failure connectivity constraints, failure probability and scalability. It will help us determine the limitations of the model depending on the use cases. Second, we plan to add a local parameters optimisation process similar to the one used for k 1 , k 2 and k 3 that could be used by the agent to adjust the value of the hysteresis H or the timer t wait depending on their evaluation of the system efficiency. Too many crossing detection could slow down the system as well as irrelevant detections caused by a too small t wait . Third, it would be interesting to change the way the load shedding order is provided to the population. It is currently sent to one or more agents by a unique external source which is considered reliable. The entire system is therefore tied to this source (the energy provider in our case). We think that a learning mechanism coupled to a trust network could allows the agents to predict curtailment needs, to anticipate an order or to react autonomously without binding to an external operator. This would greatly enhance the system resilience.

Figure 1 :

 1 Figure 1: Example of the effect of load shedding on a demand peak.

.

  The value r min = min a∈N R a moy is a shared variable (see sections 3.3.1 and 3.3.2) and R a moy = m j=1r a j the sum of the standard deviation to the initial commitment over the last m events. The maximum mark will be obtained by agents having the smallest variations in their participation. being the sum of agent's capacity over the last m events, the capacity score of the agent a is C a = C a moy cmax , while c max = max a∈N C a moy a shared variable updated collectively as seen in sections 3.3.1 and 3.3.2. It is basically a global ranking rewarding agents with big shedding capacity.•The turnover is computed as follow T a = 1 -

Figure 2 :

 2 Figure2: Target crossing detection process. A crossing is confirmed when the aggregate value is above Q(1 + H) (grey areas) for a duration of t wait . The agent then starts adjusting its share to the effort.

Figure 3 :

 3 Figure3: These three charts show the performances of the system during three consecutive load shedding events. The red dotted line represents the total flexibility, most of the followed by the sum of the x lim of the agents (in yellow dots and dash line). The continuous green curve is the aggregate. The dashed blue curve shows the total consumption, brought down to the same scale for more readability.

Figure 4 :

 4 Figure 4: This chart shows the failure ratio between the total decrease of flexibility at each step and the total committed energy that this decrease impacted. Each peaks is a load shedding event.

j = 2 Figure 5 :

 25 Figure 5: These charts show the performance of the system with different connectivity constraints. The legend is the same as figure 3.

  lim ← x lim + (f a -x lim ) * v 26: end if 27: x lim ← min(x lim , f a ) 28: x a ← min(x a , x lim ) 29: if state = 1 and t ≤ t d then

		agg
	19:	cnt 1 ← t
	20:	end if
	21: else
	22:	cnt 1 ← t
	23: end if
	24: if x ≥ x lim then
	25:
	30:	obj a ← x a
	31:	state ← 2
	32: end if
	33: if state = 2 and t > t f then 34: update History H a
	35:	compute Turnover T a
	36:	update coefficients k 1 , k 2 and k 3
	37:	cnt 2 ← t
	38:	state ← 3
	39: end if
	40: if state = 3 then
	41: 42:	if t -cnt 2 ≥ t wait then compute Capacity C a
	43:	compute Reliability R a
	44:

x


Björn Richerzhagen
email: richerzhagen@kom.tu-darmstadt.de

Ralf Steinmetz
email: steinmetz@kom.tu-darmstadt.de

Towards an Adaptive Publish/Subscribe Approach Supporting Transitions

Keywords: Adaptive Pub/Sub, Transitions, Overlay, Ad hoc, Mobility

Communication in large-scale distributed systems is mostly based on the publish/subscribe (pub/sub) paradigm, where content creators and interested recipients are decoupled in space, time, and synchronization. With the rise of social applications and the wide distribution of mobile devices highly dynamic scenarios for pub/sub systems become increasingly interesting, requiring the system to be adaptive in order to react to environmental conditions. This paper identifies promising adaptations in pub/sub systems and proposes the novel concept of transitions between multiple pub/sub mechanisms. Transitions enable a pub/sub system to react to a wide range of conditions by switching to the mechanism that fits the current environmental conditions best. This concept leads to a range of interesting research questions, which are presented and addressed in this paper.

Introduction

The publish/subscribe (pub/sub) paradigm is the foundation for many applications deployed in the Internet, ranging from full-fledged commercial middleware to conceptional systems presented in the academic world [START_REF] Eugster | The many Faces of Publish/Subscribe[END_REF]. Prominent applications such as Facebook, Twitter, and Google+ distribute millions of -mostly user-created -content items to interested subscribers, making use of the pub/sub paradigm. At the same time, those platforms provide their services through dedicated applications to a wide range of end user devices, ranging from smartphones over tablets to desktop-PCs. Each of those devices has its own restrictions regarding computational power, energy supply, available network access technologies, and mobility. A pub/sub system needs to take those restrictions into account when forwarding content items and maintaining subscriptions.

Considering, e.g., mobility there exist a range of pub/sub systems that allow publishers and subscribers to be logically and physically mobile when connecting to a fixed broker network [START_REF] Sourlas | Mobility Support Through Caching in Content-Based Pub/Sub Networks[END_REF]. Those solutions, however, do not support mobile brokers, which are essential in the case of pure ad hoc connectivity between devices. Peer-to-peer-based solutions have been proposed for fully decentralized applications on a global scale [START_REF] Baldoni | Content-Based Publish-Subscribe over Structured Overlay Networks[END_REF], [START_REF] Bender | A Comparative Study of Pub/Sub Methods in Structured P2P Networks[END_REF]. Those systems have shown not to be able to deal with higher peer mobility, as they rely on structured overlay topologies. Systems that are specifically designed to support mobile brokers are mostly limited to a local scale and operate as an isolated application [START_REF] Meier | On Event-Based Middleware for Location-Aware Mobile Applications[END_REF], [START_REF] Pongthawornkamol | The Analysis of Pub/Subs Systems over Mobile Wireless Ad Hoc Networks[END_REF].

Each of the aforementioned approaches provides a viable solution to a limited set of environmental conditions, for example regarding peer mobility or scale of the overlay network. However, in a real-world application scenario, these requirements can vary significantly, rendering isolated solutions ineffective.

This paper proposes a novel approach towards a highly adaptive pub/sub system that supports heterogeneous devices as well as locality and mobility of publishers, subscribers, and brokers by allowing transitions between different pub/sub mechanisms. The goal is not to reinvent pub/sub, but to provide a methodology that allows existing mechanisms to be adapted and exchanged depending on the current -possibly local -situation, and to understand the impact of different such adaptations on the system. The novel approach of seamless transitions between pub/sub mechanisms rises a number of research questions:

-Between which pub/sub mechanisms can and should transitions occur? -What are the costs and benefits of these transitions? -How, when, and by whom are transitions triggered? -How is a stable system behavior ensured during and after a transition?

In order to tackle these questions, key transitions in a pub/sub system are identified and thoughts on their realization are given in Section 2. A conclusion and first results are presented in Section 3.

Transitions in Publish/Subscribe

As stated in the research questions, key transitions are to be identified and studied regarding their cost and benefits. Promising candidates are presented in this section, together with initial thoughts on their realization. Decentralized vs. Centralized Broker Networks. Current pub/sub broker networks are either decentralized as a peer-to-peer network or to some extend centralized, for example only on trusted machines in a cloud. For most applications, the load on the system can change significantly, depending on the time of day or on events in the real world. Therefore, adaptation possibilities between centralized broker networks and peer-to-peer approaches are to be investigated. A system might provide its service in the centralized manner as long as the workload remains below a certain threshold. As soon as this threshold is exceeded, the system adds additional peers to the broker network in a peer-to-peer manner. Finally, the whole system could adapt into a peer-to-peer overlay, thereby lowering the load on the service provider's infrastructure. A locally bounded topology transition could be of great interest in the dense presence of mobile devices. Such devices could then form an ad hoc overlay that deals especially well with mobile peers to relay messages [START_REF] Friedman | A Density-driven Publish Subscribe Service for Mobile Ad Hoc Networks[END_REF]. One promising approach regarding the construction of overlay networks with arbitrary neighborhood properties is T-Man, proposed by Jelasity et al. [START_REF] Jelasity | T-Man: Gossip-based fast Overlay Topology Construction[END_REF]. The author's work could serve as a starting point for an abstraction of overlay topology transitions.

Channel-based, Topic-based, or Content-based. The power of the pub/sub paradigm comes from its flexibility regarding subscription and publication semantics. There is a trade-off between filtering overhead for the broker network and expressiveness of the messages, which manifests in three categories systems: channel-based, topic-based, and content-based. Currently, application designers have to decide which category fits their scenario best. The system itself, however, should provide the abstraction and allow for a flexible filter language to support a wide range of applications. Internally, the system has to find a state that provides the best trade-off between message complexity and computational requirements. This leads to transitions between different kinds of content models with the goal of overall complexity reduction, depending on the current workload and the nature of subscriptions.

Exploiting Locality of Content and Interest. An emerging class of applications centers around location-based services. In such applications, interest in content is based on the physical position of a user. Exploiting this property has proven beneficial for the performance of distributed applications, as they are able to move content closer towards the user. There exist a range of spatial pub/sub solutions that address content based on its (logical) position [START_REF] Chen | An Efficient Spatial Publish/Subscribe System for Intelligent Location-based Services[END_REF]. These systems, however, are not intertwined with a global pub/sub solution and operate in a rather confined environment. Therefore, in our scenario, the system should locally adapt towards content-based pub/sub if, e.g., ad hoc communication can be utilized. In such a system, nearby users can benefit from each other if they have related interest. They can, for example, reduce their usage of the costly mobile network infrastructure by exchanging information locally in a peer-to-peer fashion. As a possible side effect, communication between nearby users can occur faster than via a centralized broker network, albeit the communication link might be less reliable. The resulting pub/sub system would, thus, be able to meet near real-time constraints on a local scale, while still being able to distribute messages to interested subscribers all over the world.

As presented, there exists a range of interesting research questions as to how pub/sub systems can support adaptivity through transitions. Starting with the mechanisms identified above, the costs and resulting benefits of transitions are to be studied in well-defined scenarios. To study the impact of locality and the decentralization of brokers as described beforehand, the scenario of a social application in a mobile ad hoc network is chosen. Additional to ad hoc communication, devices can use the cellular infrastructure, allowing for a detailed study of the resulting trade-offs. Furthermore, transitions between centralized brokers, i.e., brokers reachable via the link, and brokers distributed throughout the ad hoc network can be studied. One important research question in this context is to how, when, and by whom such transitions should be triggered. Answering this question requires a deep understanding as to how transitions affect the system and how stability of the overall system before, during, and after a transiton can be guaranteed. In an earlier work the authors studied the impact of transitions between scheduling mechanisms and overlay topologies in the context of P2P video streaming systems [START_REF] Richerzhagen | Supporting Transitions in P2P Video Streaming[END_REF]. The evaluation shows that transitions between mechanisms enable the system to work under a wider range of environmental conditions and retain desirable properties even in extreme scenarios.

The scenario of a mobile social application as described above needs to be modeled, and the impact of individual mechanisms and the transitions inbetween is to be evaluated. This should leed to a better understanding on when, how, and by whom transitions should be exectued to maintain a high service quality. While initial results are obtained by means of simulation, we later on plan to evaluate the system prototypically.

This work has been funded by the DFG as part of the CRC 1053 MAKI.

Preliminary Conclusions and Future WorkCurrent pub/sub systems are isolated applications specifically designed for a set of environmental conditions, based on a rather confined application scenario. In this work, we motivate the concept of transitions between different, well-known mechanisms in order to obtain a highly adaptive pub/sub system. Examples of such mechanisms and the resulting transitions are discussed, as well as potential starting points regarding their realization.


Matthias Wichtlhuber
email: mwichtlh|hausheer@ps.tu-darmstadt.de

David Hausheer

Towards a Mobility-Supporting Incentive Scheme for Peer-to-Peer Content Distribution

The distribution of bulk content such as video streams and system updates is becoming increasingly important on mobile devices. For this kind of data transfers, the application of the Peer-to-Peer (P2P) paradigm is attractive for content providers, as it allows to leverage clients' (peers') resources for the dissemination process. The contribution of resources can be encouraged by applying reciprocal incentives, which prevent a peer from consuming more resources than he contributed to the system. However, reciprocation has drawbacks, e.g., in terms of high energy consumption and low performance, when applied to mobile peers. This work substantiates these problems through measurements and discusses a virtual node concept as a possible solution.

Introduction

The widespread adoption of smartphones has led to a growing volume of mobile traffic. This increase in volume is driven by a few types of applications generating comparably high data volume, e.g., according to recent studies [START_REF]Fall 2012 Global Internet Phenomena Report[END_REF] more than 50% of mobile traffic is real-time entertainment traffic being caused mainly by audio/video streaming applications. In order to transfer such bulky data, content providers can utilize the Peer-to-Peer (P2P) approach to reduce their costs [START_REF] Abboud | On the Impact of Quality Adaptation in SVC-based P2P Video-on-Demand Systems[END_REF]. A P2P content distribution system requires clients (peers) to forward parts of the content (chunks) amongst each other, instead of retrieving the entire content from the central server. Thus, the consumption of resources like bandwidth, storage and CPU power is shifted from the content provider's data center to the peers.

The utilization of peers' resources implies the need for incentivation, as peers act rationally in the economic sense, resulting in a behavior that maximizes the service received from the network and minimizes the contribution of own resources. Researchers have proposed a number of incentive schemes to ensure contribution of peers in content distribution, where the most common form of incentive schemes applied today are reciprocal incentive schemes [3][4][5] very similar to BitTorrent's tit-for-tat approach. This class of schemes requires peers to provide other peers the same amount of resources, as they consume, e.g., in the case of bandwidth, by keeping the ratio between upload and download bandwidth close to 1.

Problem Description

Reciprocal schemes show weaknesses in heterogeneous environments, as they discriminate peers with poor resources, i.e., mobile peers. From a mobile user's perspective, reciprocation is an unattractive option, as sending data is more expensive in terms of energy consumption than just receiving data. The penalty of reciprocation can be quantified by measuring the energy consumption of a mobile P2P video on demand streaming application [START_REF] Abboud | On the Impact of Quality Adaptation in SVC-based P2P Video-on-Demand Systems[END_REF] running on an Android device using Wi-Fi (see Figure 1a). After a phase of aggressive scheduling (10s -55s), the measurement shows reciprocation to be about 100 mW more expensive than just downloading in steady state (55s -120s). This gap is caused by high peak values: plotting the counter cumulative distribution function of the peak power consumption (Figure 1b) shows a higher probability of high peak values in the case of reciprocation. It is reasonable to assume the gap to broaden with increased bitrates and for link types with a higher transmitting power such as HSDPA and LTE. Besides that, reciprocation is also expensive in the monetary sense for both, user and network provider.

A second field of problems is caused by the inherent properties of mobile links, namely varying data rates and frequent link loss. Trading partners cannot distinguish whether a mobile peer has bad link quality or tries to steal bandwidth. A strict enforcement of reciprocation under varying bandwidth constraints can even lead to a breakdown of cooperation, as partners start reducing service for each other in an alternating fashion [START_REF] Su | Incentive Mechanisms in P2P Media Streaming Systems[END_REF]. Moreover, with current schemes, frequent link loss looks like a peer failure followed by a new peer joining the network. This is problematic, as reciprocal incentive schemes rely on a grace period, in which new peers are served with the lowest possible priority only. Thereby, new peers can gain some bargaining power, as they do not have content to reciprocate, while the possibilities to steal resources are kept low. Thus, it takes some time for reciprocal incentive schemes to gain momentum, resulting in a bad perceived quality for mobile users after link failures.

Home Swarm A Home Swarm B Home Swarm C A 1 A 2 A 3 B 1 B 2 C 1 (a)
Although reciprocation is problematic with respect to mobility, dropping the incentive scheme for mobile users is not an option. On the one hand, there are practical considerations like the infeasibility of telling apart mobile from wired users by relying on their IP address only. On the other hand, an increased fraction of mobile users in a P2P network not participating in distributing content leads to a service degradation of the complete network, as the overall available upload bandwidth determines the overall available download bandwidth. Thus, there is a need for reciprocal incentive schemes supporting mobility in P2P content distribution.

Approach and Proposed Architecture

The approach proposed in this paper to address the problems discussed above is to utilize the variety of users' mobile and wired devices by clustering them. In the remainder, this cluster is referred to as the user's home swarm. The home swarm acts as a virtual node in a reciprocal incentive scheme. The main idea is to balance the load of reciprocation in a user's home swarm, thus allowing consumption and donation of resources to happen on different devices. An example of a random graph with clustered home swarms is given in Figure 2a. Assuming node B 1 to be a home access point and node B 2 to be a mobile device connected via a 3G cellular link, the proposed idea is that B 1 contributes resources by uploading content, while B 2 consumes the same amount of resources without reciprocating itself.

A conceptual architecture to provide this functionality is depicted in Figure 2b. It includes the P2P overlay functionality, which commonly consist of two main building blocks, one performing Neighborhood Selection using a Peer Sampling Service (e.g. a tracker server), the other performing Chunk Scheduling. Both consult the Incentive Component and take its suggestions (usually a priority list of peers to serve next) into account, when deciding on whom to serve which chunk of a file. In the following, the Incentive Component is decomposed into its subcomponents.

The basic component of the proposed incentive architecture is the Home Swarm Clustering Service. This service relies on the Peer Sampling Service for rendezvous and provides fraud proof means to tell apart which peers belong to the same home swarm and which do not. Atop, the Home Swarm Load Balancing component assumes a secure home swarm and can thus rely on all peers in the home swarm cluster to be reliable and to act in the interest of the user. The component implements the load balancing algorithm, using the Inbound/Outbound Accounting components to keep track of the home swarm's internal and external expenditures. The Mobility Support component is incorporated in the load balancing algorithm and deals with the special properties of mobile clients. The mobility support component will identify varying bandwidth/link-loss of mobile clients and care for initial credit to be generated even in absence of the mobile peer, thus caring for the non-energy related issues discussed in Section 2.

Preliminary Conclusions and Future Work

The contributions of this paper are twofold. Firstly, the problem of reciprocation on mobile clients is substantiated with measurements followed by a discussion. Secondly, the home swarm concept and a conceptual architecture are introduced to address the problem.

As a next step the proposed architecture will be detailed by clearly separating the building blocks via interfaces, and a prototype will be implemented to show that the proposed approach relieves the load of mobile devices with respect to energy consumption and bandwidth in P2P content distribution. The concept also implies algorithmic challenges with respect to resource allocation, trust and the general feasibility of the scheme which will be addressed in future work.

Fig. 1 :

 1 Fig. 1: Energy measurements comparing reciporcation and pure downloading.

Fig. 2 :

 2 Fig. 2: Random graph with clustered home swarms and architecture draft.