Francesca Frontini
email: francesca.frontini@lip6.fr

Carmen Brando
email: carmen.brando@lip6.fr

Jean-Gabriel Ganascia
email: jean-gabriel.ganascia@lip6.fr

Semantic Web Based Named Entity Linking for Digital Humanities and Heritage Texts

Keywords: named-entity linking, linked data, digital humanities

This paper proposes a graph based methodology for automatically disambiguating authors' mentions in a corpus of French literary criticism. Candidate referents are identified and evaluated using a graph based named entity linking algorithm, which exploits a knowledge-base built out of two different resources (DBpedia and the BnF linked data). The algorithm expands previous ones applied for word sense disambiguation and entity linking, with good results. Its novelty resides in the fact that it successfully combines a generic knowledge base such as DBpedia with a domain specific one, thus enabling the efficient annotation of minor authors. This will help specialists to follow mentions of the same author in different works of literary criticism, and thus to investigate their literary appreciation over time.

Introduction

Named Entities (NE) are linguistic expressions that stand like rigid designators for referents; such entities normally include names of persons, geographical places, organizations, but also temporal references such as dates. Enriching mentions with a link to its referent by means of a unique identifier is crucial for the semantic annotation of texts. This is done by pointing to an external resource, such as a Universal Resource Identifier (URI) in the Linked Open Data (LOD) cloud. Segments in text referring to a Named Entity are known as entity mentions.

Named Entity Linking (NEL) [START_REF] Rao | Entity linking: Finding extracted entities in a knowledge base[END_REF] is a sub task of Named Entity Recognition and Disambiguation (NERD). NERD algorithms automatically detect entities in texts and assign them to a given class 3 . The NEL module assigns a unique identifier to the detected entities, thus disambiguating them by pointing to their referent. Linking is crucial since the same mention can represent different entities in different contexts and at the same time one entity can be mentioned in the text in different forms. So for instance the mention "Goncourt" can refer to any of the two Goncourt brothers, Edmond or Jules. At the same time Jules de Goncourt can be referred to in the text as "Goncourt", "J. Goncourt", "J. de Goncourt", ... This means that, in order to automatically retrieve all passages in a text where Jules de Goncourt is mentioned, it is necessary not only to annotate all these mentions as a Named Entity of the class person, but to provide them with a unique key that distinguishes them from those of other people, in this case those of Edmond. The bibliographic identifier "Goncourt, Jules de (1830-1870)", as well as the links <http://www.idref.fr/027835995> and <http://fr.dbpedia.org/page/Jules de Goncourt> are examples of such an identifier.

Besides ensuring disambiguation, linking also performs an important additional task, namely textual enrichment, in that it connects the mention with sources of additional information -such as DBpedia in the previous examplethat needs not be stored in the text but can be accessed when required. In the case of Edmond de Goncourt, additional information from DBpedia can tell us what books he authored, where he was born, ....

The main issue with NEL in digital humanities is that mentions of persons often refer to individuals that are not listed in general ontologies such as Yago or DBpedia, that constitute the typical knowledge base for linking in other domains. Such individuals are often present in other knowledge bases, notably bibliographical linked data repositories (such as the French National Library BnF linked data repository). On the other hand, linking requires access to ontological knowledge, in that choosing between two individuals having the same name may requires comparing the context of the mention with a priori knowledge. In this respect, knowledge bases such as DBpedia remain an important source of general knowledge of the World. Thus the ideal linking algorithm for literary criticism texts combines general and domain specific sources. The experiment here described goes in this direction.

The paper will first present previous approaches to NEL, then the proposed graph based disambiguation algorithm based on the notion of centrality, finally describe the experiment carried out on the corpus and the results. Some conclusions and suggestions for further improvement of the algorithm are finally given.

Previous approaches

Previous approaches for NEL can be divided in two main families. Those using text similarity and those using graph based methods. Both these methods are unsupervised, and they do not rely on pre-annotated corpora for training.

The best known tool of the first group is DBpedia Spotlight [START_REF] Mendes | Dbpedia spotlight: shedding light on the web of documents[END_REF], that performs NER and DBpedia linking at the same time. Spotlight identifies the candidates for each mention by performing string similarity between the mention and the DBpedia labels, then it decides which entry is the most likely by comparing the text surrounding the mention with the textual description of each candidate. The referent whose description is more similar to the context of the mention in terms of TF/IDF is chosen. This method is known to be very efficient, but it can only provide linking towards resources such as DBpedia, whose entries come with a description in the form of unstructured text. Other knowledge bases do not provide a textual description for their entries, such is the case of the bibliographical databases that constitute the ideal linking for mentions of authors.

Graph-based approaches rely on formalised knowledge described in graph form that is built from a Knowledge Base (KB) (e.g. the Wikipedia article network, Freebase, DBpedia, etc.). Reasoning can be performed through graph analysis operations. It is thereby possible to at least partially reproduce the actual decision process with which humans disambiguate mentions. A reader may decide that the mention "James" refers to philosopher "William James" and not to writer "Henry James" because it occurs in the same context as "Hume" and "Kant". In the same way such algorithms build a graph out of the candidates available for each possible referent in a given context and use the relative position of each referent within the graph to choose the correct referent for each mention. The graph is built for a context (such as a paragraph) containing possibly more than one mention, so that the disambiguation of one mention is helped by the other ones.

This kind of approach is similar to the one used in Word Sense Disambiguation [START_REF] Sinha | Unsupervised graph-basedword sense disambiguation using measures of word semantic similarity[END_REF], where a set of words in a given sentence needs to be labeled with the appropriate sense label by using the information contained in a lexical database such as WordNet. The key idea of this approach is that for all ambiguous words in the context, senses that belong to the same semantic space should be selected, and that in this way two ambiguous words can mutually disambiguate each other. More specifically, a subgraph is built, constituted only of the relevant links between the possible senses of the different words, and then for each alternative sense labeling, the most central is chosen. This procedure, when applied to such context specific subgraphs, ensures that in the end the chosen senses for each word will be the one better connected to each other.

Centrality is an abstract concept, and it can be calculated by using different algorithms 4 . In [START_REF] Sinha | Unsupervised graph-basedword sense disambiguation using measures of word semantic similarity[END_REF] the experiment was carried out using the following algorithms: Indegree, Betweenness, Closeness, PageRank, as well as with a combination of all these metrics using a voting system. Results showed the advantage of using centrality with respect to other similarity measures. While the combination of all centrality algorithms scores the best, Indegree centrality seems to be the better performing when compared to the other ones in terms of precision.

This graph based approach has been applied to NEL, where mentions take the place of words and Wikipedia articles that of WordNet synsets. Here too centrality measures are performed on the Wikipedia structure in order to use the rich set of relations to disambiguate mentions. More specifically in [START_REF] Hachey | Graph-based named entity linking with wikipedia[END_REF] English texts were disambiguated using a graph that relies only on English Wikipedia, and was constituted of the links and of the categories found in Wikipedia articles. So for instance the edges of the graph represent whether ArticleA links to ArticleB or whether ArticleA has CategoryC. Here too "local" centrality is then used to assign the correct link to the ambiguous mention. We have chosen a graph-based approach to NEL that will be described in the next section.

Our approach

Our approach to disambiguate NE mentions is a graph-based one. Vertices are represented by URIs of mention candidates (e.g. dbpedia:Victor Hugo) as well as URIs of concepts (e.g. foaf:Person) or individuals connected to at least two different candidates. Edges are semantic relations defined explicitly between URIs (e.g. "type"). The graph is undirected and their vertices and edges are a priori unweighted. We take advantage of the notion of centrality in Graph Theory to link a NE mention with the URI of the most probable candidate for that mention. In other words, we want to find the subset of vertices of different candidates having the greatest number of edges among them. The edges and vertices of the graph are built leveraging knowledge from different LOD sources whose nature is graph-based.

We illustrate the proposed approach with an example. Let us consider the following phrase of a French text of literary criticism written by Albert Thibaudet (1936) :

Quant au rythme, si Victor Hugo a dépassé Lamartine, il n'a pas été plus loin que Vigny.

In bold there are three mentions automatically recognized by a NER algorithm, that need now be linked to an identifier.

For each mention, the NEL algorithm selects possible candidates by exact string matching of the current mention and dictionary entries (e.g. Hugo, M. Hugo) and retrieves the corresponding URIs of the listed LOD sources. An excerpt of the candidates of the three named-entities from the example is listed below by distinguishable personal information instead of URI for readability sake.

Candidates (Victor Hugo) = Hugo, Victor (1802-1885) Candidates (Lamartine) = Lamartine, Alix de (1766-1829), Lamartine, Alphonse de (1790-1869), Lamartine, Elisa de (1790-1863)

Candidates (Vigny) = Vigny, Joseph Pierre de (1742-1812), Vigny, Benno (1889-1965), Vigny, Alfred de (1797-1863) Thanks to the URIs, it is possible to retrieve from the Web of Data the associated RDF graph for each candidate and combine them into a single graph. It should contain only those predicates involving at least two candidates of different mentions because we only want the predicates that play an important role in the disambiguation process. Calculating the centrality for every candidate will then give us the best candidates for the three mentions. Figure 1 shows an excerpt of the resulting graph where the chosen mention candidates are marked in bold. We can notice that the vertex yago:RomanticPoets is the one that influences the centrality measure the most because it is shared by the three chosen candidates. Likewise, other vertices connected to the chosen nodes, such as dbpedia:romanticisme and dbpedia:Alexandru Macedonski, are influential. Named Entities are disambiguated and referenced within the context of a paragraph, so in principle two (identical) mentions of the same author within one paragraph will always receive the same link, while the same mention in different paragraphs might be assigned a different referent, depending on the other mentions it occurs with.

The NEL task is commonly defined in such a way that it does not assume the existence of the correct referent among the candidates in the knowledge base [START_REF] Hachey | Evaluating entity linking with wikipedia[END_REF]. This is due to the fact that Wikipedia/DBpedia can hardly be a complete knowledge base even for textual genres such as contemporary newspapers articles. This seems even less true for the corpus that constitutes the object of our experiment. French literary criticism texts contain references not only to famous authors, but also to other minor figures that are not listed in Wikipedia. Therefore our proposal is to aim for a quasi complete reference base for the task of referencing authors.

Our approach relies importantly on a lookup dictionary; this is the subject of the following section.

LOD-based lookup dictionary

Linked data [START_REF] Bizer | Linked data -the story so far[END_REF] is an important way of publishing knowledge in the Semantic Web. Such data is easily available via web services; LOD is composed of triplets of the form (subject, predicate, object) where subjects designate URIs, objects may be URIs or data-typed literals, and predicates represents binary relations. Queries can be run in the SPARQL language and data is provided with a dereferenciable and persistent identifier called URI (Uniform Resource Identifier). Many of the available linked data are of great interest for digital humanities [START_REF] Van Hooland | Exploring entity recognition and disambiguation for cultural heritage collections[END_REF], and for the domain of literary criticism in particular. More specifically, information on authors for French texts can be found in the French version of DBpedia on the one hand, and in the catalogue of the Bibliothque Nationale de France (BnF) on the other.

The French DBpedia is constituted of the articles of the French version of Wikipedia. In DBpedia entries are classified one or more of the types of the DBpedia ontology. So for instance the author known as Stendhal5 is classified as Person, Artist, Writer, and at the top level, as Thing. Moreover, authors are linked to each other by horizontal relations such as InfluencedBy, and, indirectly, by being linked to the same concept, such as Romanticism. BnF entries list all authors of books ever published in France; their entries contain information on date of birth and death, gender, alternative names, works authored. For instance the BnF entry for Voltaire 6 gives several alternative names such as Franois-Marie Arouet (Voltaire's real name), Wolter, Good Naturd Wellwisher, ... Most crucially, BnF links its entry to the DBpedia one when existing, thus making it very easy to connect the two resources in one knowledge graph. Moreover, BnF entries also list the author's Idref, which is the official identification system used by French universities and higher education establishments to identify, track and manage the documents in their possession. The combination of these two sources was considered able to grant a sufficient coverage for a corpus of French literary criticism, thus the BnF and the DBpedia SPARQL endpoints were queried for all authors, retrieving their biographic information (name, surname, alternative names, dates of birth and death, title, ...) in structured form.

In order to be able to retrieve all possible mentions of an author, this information was processed into a dictionary of authors, that contains all alternative names of an author, plus a series of alternative forms automatically generated, with the links to BnF and DBpedia entries. Automatically generated alternative names are of the form:

surname only (Rousseau) initials + surname (J.J. Rousseau, JJ Rousseau, ...) title + surname (M. Rousseau, M Rousseau) -... Given the domain (French literature) this procedure ensures that the retrieval of at least one candidate URI for most mentions. At the same time, the mass of information present in the BnF repository will generate several homonyms and make most mentions ambiguous; thus good disambiguation becomes crucial.

Implementation of the NEL algorithm

The NEL algorithm processes a file in XML-TEI format 7 ; NE mentions are annotated with NER annotations (e.g. tag <persName>) for every paragraph; the algorithm is devised to processes one single class at a time (here Person). It uses a lookup dictionary per class listing superficial forms and their associated URIs from LOD sources, as described in the previous section. The algorithm produces an enriched version of the input file indicating the chosen candidate for each mention. We developed our implementation in Java ; RDF data is processed thanks to the Jena API8 ; graphs are manipulated by the JgraphT API9 and implementation of centrality measures are available in the Social Network analysis tool, JgraphT-SNA 10 . In particular, the algorithm performs the following steps for every paragraph of the XML-TEI file:

1. look for URIs of mention candidates in the dictionary 2. retrieve the RDF graphs of those URIs 3. simplify and combine graphs then compute the selected centrality measure 4. choose URI of candidate with the higher score per mention then write results in TEI file

The algorithm searches for (1) possible candidates of mentions by exact string matching the mentions of the current paragraph and superficial forms in the dictionary; there must be at least one ambiguous mention to continue. It retrieves URIs (BnF, DBpedia) of mention candidates from dictionary entries. Next, the RDF graph is retrieved (2) for every URI and converted to a JgraphT-compatible graph, where RDF objects and subjects are vertices and RDF predicates are edges. Irrelevant edges and vertices are removed from graphs. We keep edges which involve at least two vertices representing URIs candidates. Information coming from different sources is combined into a single graph (3); the way we combine graphs is straightforward. The fusion is implicitly done thanks to one of the main LOD principles which consists of reusing vocabularies published in the LOD vocabulary cloud. In other words, edges (predicates) and vertices (URI nodes) should be shared by at least two graphs associated to candidates of different mentions. The selected centrality measure (e.g. closeness) is calculated for the resulting graph. Finally, the algorithm chooses (4) the URI of the mention candidate with the higher centrality score and annotates the input XML-TEI file with this information.

Furthermore, simplification of graphs and calculation of centrality measures in the combined graph are crucial parts of the algorithm (3). This step is detailed in the Algorithm 1. It essentially removes edges which are irrelevant to calculate a centrality measure, in other words, it deletes those edges which involve at most one vertex of a non-candidate URI.

Experiments and results

This section describes the experiments settings used to test our proposal as well as preliminary results which are encouraging. In this experiment, in order to person entities. We measure the precision of the proposed NEL approach in terms of the attribution of the right URI to a mention with respect to the URI manually assigned by humans. The authors lookup dictionary was automatically built in advance thanks to the BnF LOD source which is rich in SameAs predicates pointing to DBpedia and Idref URIs. The resulting lookup dictionary is composed of 4,218,798 author names including their alternative names (e.g. M. Lamartine, Monsieur Lamartine, etc.). We chose 3 centrality measures commonly used in social network analysis and the word-sens disambiguation problem, these are: DegreeCentrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF], BrandesBetweennessCentrality [START_REF] Brandes | A faster algorithm for betweenness centrality[END_REF], Free-manClosenessCentrality [START_REF] Freeman | A set of measures of centrality based on betweenness[END_REF], as implemented in the JgraphT-SNA tool.

Results and Analysis

The test results with the three algorithm are shown in table 1 Precision is calculated comparing the number of correctly assigned links over the total of manually annotated entities of authors. The best result is obtained with BrandesBetweennessCentrality, with a precision of 0.74. DegreeCentrality has a comparable performance, FreemanCloseness centrality seems to heavily underperform with respect to the other centrality measures. The last column of table 1 shows the number of empty links over the total.

These first results are satisfying: though far from the 85% accuracy that is normally achieved by similar algorithms on the news domain, such levels of precision are nevertheless remarkable, considering that in many cases the text discusses minor authors, today unknown, that are not necessarily listed in DBpedia. Moreover, the use of BnF makes the number of candidates (and thus the possibility of error) explode, with sometimes as much as 20 or more possible candidate for a mention.

To quantify authors incompleteness in both the DBpedia and BnF data sets used in this experiment, we count the number of mentions in which the algorithm (using DegreeCentrality measure) does not find any corresponding URI in the chosen KB. In this manner, there are 160 author mentions, out of 1021 mentions identified in the corpus by the algorithm, that have no match in DBpedia, that is around 16%. Remarkably, there are only 23 mentions (i.e. 2%) that have no match in either BnF or DBpedia. Notice that all authors in this test set that are in DBpedia are also in BnF.

The most frequent mistakes considering DegreeCentrality and BrandesBe-tweennessCentrality measures (the most similar and precise ones) concern the following authors: Vielé-Griffin, Francis (1864-1937); Boileau, Nicolas (1636-1711); Barrès, Maurice (1862-1923); Payen, Fernand (1872-1946); Lefranc, Abel (1863-1952); Shakespeare, William (1564-1616); Spencer, Herbert (1820-1903); Goncourt, Edmond de (1822-1896) and brother Goncourt, Jules de (1830-1870); Mentré, Franois (1877-1950). The algorithm makes three types of mistakes.

MISSING CANDIDATES -In 23 cases the algorithm is unable to retrieve any candidate from the lookup dictionary, since the author is not present in any knowledge base. This is the case of author Francis Vielé-Griffin. In other cases the correct entity is present but not associated with the required pseudonym. This is the case of William Shakespeare's alleged alter ego William Stanley13 . This alias is not listed in the dictionary for Shakespeare, therefore, it is not possible to assign both mentions to the same person (and thus the same URI).

MISSING CONTEXT -In some rare cases only one ambiguous author's mention is present in a single paragraph, thus the algorithm resorts to a fall back strategy, choosing the entity with more links in absolute. Sometimes this strategy causes errors, as in the case of "Vigny", for whom, in isolation, the wrong link to Auriane Vigny is chosen.

INCOMPLETE INFORMATION -In some cases the context of the sentence should be sufficient to produce a correct disambiguation but the NEL algorithm makes mistakes due to lack of links in the knowledge base, which prevents the centrality measure to produce the desired result. For instance, "Shakespeare", when mentioned in the context of Shakespearian critic Abel Lefranc, should produce the correct linking to William, but Nicolas is chosen instead. Clearly explicit links between Abel Lefranc and the object of his studies are missing in the knowledge bases. Ancient authors also tend to cause problems due to lack of information, e.g. the Greek author Lysias is mistaken for an homonymous French revolutionary collective.

WRONG, MISLEADING INFORMATION -Sometimes the knowledge bases contain wrong or misleading information. For instance there exist a BnF entry for the "Ronsard family", classified as foaf:Person, which is chosen instead the correct assignment, namely one of its members, Pierre de Ronsard. The opposite is also true, so some mentions refer to both Goncourt brothers as a collective noun, but the algorithm chooses one of the two. Finally, wrong or misleading pseudonyms are sometimes listed in BnF for an author, causing wrong candidates to be injected in the graph and sometimes selected. So for instance "Descartes" is listed as a pseudonym for novelist Horace Walpole and thus sometimes Walpole is wrongly chosen as the link for philosopher Descartes.

Error analysis also shows that sometimes relevant information that is present in the knowledge base is not used in the decision process because it cannot be encoded in the graph in the form of links. A typical example is temporal information which is encoded in the form of dates (data-typed literals). In other words the fact that -for a given context -two candidate referents lived in the same period of time cannot be taken into account.

To evaluate the impact of the temporal dimension, we chose to evaluate against an index from which we removed authors born after the date of publishing of the work. The results show a slight improvement with DegreeCentrality reaching precision 0.78 and BrandesBetweennessCentrality 0.77. A greater improvement may be obtained using a more sophisticated graph building algorithm, that transforms information about dates of birth and death in links that can connect authors in a measurable way.

Conclusion and future work

We presented an algorithm to perform NEL on a corpus of 19th century literary criticism, with the specific goal of disambiguating and referencing author mentions for research purposes. The NEL module is meant to be used in combination with a NER module, and will help researchers in the creation of digital literary editions enriched with information about authors. The main purpose of this work is to help scholars in history of literature to perform complex queries in order to study the literary appreciation of authors over time, and investigate the history of literary criticism in French literature. More specifically the enrichment of the aforementioned "Corpus critique" is meant to enhance ongoing research in the history of scientific ideas, and to provide a way to follow the dissemination of theories and concepts defined by Charles Darwin, Claude Bernard, Henri Bergson in non scientific texts of their time.

The reported experiment shows how combining different sources can be useful to perform linking on a domain specific corpus with satisfying results. While the precision is not yet state of the art, it is nevertheless remarkable, considering that it is the first time graph that centrality algorithms have been used for NEL combining DBpedia with a domain specific source. Tests showed significant differences between one implementation of centrality and the other two. Error analysis suggests possible improvements of the algorithm, including the ad hoc transformation of temporal information -present in the knowledge base in the form of literals -into links of the context graph. Another possible evolution of the algorithm would be to assign different weights to the edges so that for instance sharing the same literary circle becomes a more important relation than being born in the same town. Weights would be learned from manually annotated data. Further experiments will be carried out with different corpora and on different categories of entities, notably places.

Experimenting with the size of the context will also be necessary, in order to find the best trade-off between efficiency and informativeness. A more ample context (ideally a whole chapter) may produce a better graph of candidates, such that all mentions can disambiguate each other correctly. But at the same time this may introduce noise, and also generate a graph so big that its construction and the calculation of centrality may require too much time.

Another possible evolution of the algorithm could be to improve the graph fusion procedure. So far, our strategy does not handle the proper fusion of individuals which are described heterogeneously by the different sources (e.g. Victor Hugo as described by BnF, as described by DBpedia, and so on). In this study we chose to study the problem from a quantitative point-of-view and thus to consider existent knowledge as it is without a pre-processing step. In the future, we foresee to make use of strategies commonly applied in Conceptual Graphs for information fusion [START_REF] Laudy | Information fusion using conceptual graphs: a tv programs case study[END_REF]. In this way, the resulting graph would better concentrate domain knowledge (i.e. avoid redundancy and conflicts) and thus calculate a more accurate centrality measure.

Fig. 1 .

 1 Fig. 1. Excerpt of the chosen URIs (in bold) for three candidates; a color designates all candidates of a single mention.

Table 1 .

 1 , Results with different centrality measures on test corpus.

	Centrality Measure Used	Precision Unassigned Links
	DegreeCentrality	0.73	23
	BrandesBetweennessCentrality 0.74	23
	FreemanClosenessCentrality 0.43	23

See[START_REF] Nadeau | A survey of named entity recognition and classification[END_REF] for a survey on NER.

For a discussion of the notion of centrality see also[START_REF] Rochat | Character Networks and Centrality[END_REF]

http://fr.dbpedia.org/page/Stendhal

http://data.bnf.fr/11928669/voltaire/

http://www.tei-c.org/index.xml

https://jena.apache.org/

http://jgrapht.org

https://bitbucket.org/sorend/jgrapht-sna

http://obvil.paris-sorbonne.fr/corpus/critique/

www.idref.fr

Stanley is believed by some to be the real author behind Shakespeare's works.

Acknowledgements

This work was supported by French state funds managed by the ANR within the Investissements d'Avenir programme under reference ANR-11-IDEX-0004-02 and by an IFER Fernand Braudel Scholarship awarded by FMSH.

evaluate the performance of the algorithm, the linking is performed on correctly identified and classified authors.

Experiment settings

The test corpus consists of a French text of literary criticism titled "Une thése sur le symbolisme" (A thesis about Symbolism) and it is the first volume of the work named "Réflexions sur la littrature" (Reflexions on literature) published by Albert Thibaudet in 1938.

The text is drawn from a larger "Corpus critique" 11 , published in TEI by the Labex OBVIL and containing a large collection of critical essays by different authors.

The chosen text in particular presents a high density of authors' mentions, so that each paragraph generally contains an average of 2-3 mentions that are treated at the same time by the algorithm. Mentions concerning authors were manually annotated by two experts in French literature; URIs assigned to mentions are those from Idref 12 . Guidelines to manual annotation were those proposed by the MUC7 conferences as well as those defined by the XML/TEI standard. The resulting test corpus contains 1021 manually annotated mentions of


Mr Utkarsh Jindal

PhD David Guiraud

I am very grateful to Dr. Shubhajit Roy Chowdhury, Assistant Professor at the International Institute of Information Technology, Hyderabad, India and a collaborator under Franco-Indian INRIA-DST funding for providing me an opportunity to travel to France and complete the project that I started in India under his guidance. The project consumed hard work, lot of research and dedication, and wouldn't have been possible without the support of all my supervisors and organizations I worked with.

My thanks and appreciations also go to my colleague, Ms. Mehak Sood, who willingly helped me out with her abilities throughout the project.

I attribute the completion of this research study to the blessings, moral support, love and affection of my parents and family members. They have always been a major source of motivation and strength.

Finally, I would like to express my recondite thanks to all those who have rendered their much needed services in the realization of this work.

Chapter 1: Introduction

All of us are exposed to optical (i.e., visible and near-infrared) radiation from the sun and other sources throughout our lives. Assuming our eyes are shielded from excessive intensity, and our skin is protected from the ultraviolet content of sunlight, we accept this exposure in the knowledge that it is perfectly safe. Unlike x-rays, optical photons are insufficiently energetic to produce ionisation, and unless light is concentrated to such a high degree that it causes burning to the skin, optical radiation offers no significant hazard. The diagnostic potential of optical methods has been widely known since Jöbsis [START_REF] Jöbsis | Noninvasive, infrared monitoring of cerebral and myocardial oxygen sufficiency and circulatory parameters[END_REF] first demonstrated that transmittance measurements of near-infrared (NIR) radiation could be used to monitor the degree of oxygenation of certain metabolites. This led to the development and increasingly widespread use of clinical near-infrared spectroscopy (NIRS), which offers a safe, non-invasive means of monitoring cerebral function at the bedside without the use of radioisotopes or other contrast agents [START_REF] Cope | System for long-term measurement of cerebral blood and tissue oxygenation on newborn infants by near infra-red transillumination[END_REF].

Human tissues contain a variety of substances whose absorption spectra at NIR wavelengths are well defined, and which are present in sufficient quantities to contribute significant attenuation to measurements of transmitted light. The concentration of some absorbers, such as water, melanin, and bilirubin, remain virtually constant with time. However, some absorbing compounds, such as oxygenated haemoglobin (HbO 2 ), deoxyhaemoglobin (Hb), and oxidised cytochrome oxidase (CtOx), have concentrations in tissue which are strongly linked to tissue oxygenation and metabolism. Increasingly dominant absorption by water at longer wavelengths limits spectroscopic studies to less than about 1000 nm. The lower limit on wavelength is dictated by the overwhelming absorption of Hb below about 650 nm. However, within the 650-1000 nm window, it is possible with sensitive instrumentation to detect light which has traversed up to 8 cm of tissue [START_REF] Lloyd-Fox | Illuminating the developing brain: the past, present and future of functional near infrared spectroscopy[END_REF].

Functional near infrared spectroscopy (fNIRS) is based on the optical measurement of changes in tissue oxy-(HbO2), and deoxy-(Hb) haemoglobin concentration whereas cerebral oximetry is cerebral oxygenation monitoring via near-infrared spectroscopy (NIRS) [START_REF] Lloyd-Fox | Illuminating the developing brain: the past, present and future of functional near infrared spectroscopy[END_REF]. One aspect of this response -the blood oxygen level dependent (BOLD) signal is the basis for functional magnetic resonance imaging (fMRI), a brain imaging modality closely related to fNIRS in terms of the underlying measurand. The responses measured during fNIRS are usually interpreted in terms of changes in HbO2 and Hb concentration --a somewhat richer set of variables than those available from basic fMRI. A third hemodynamic variable, Hbt, can be derived as the sum of HbO2 and Hb concentrations, which is considered a good indicator of the variations in the regional cerebral blood volume (CBV) [START_REF] Pellicer | Near-infrared spectroscopy: a methodology-focused review[END_REF].

NIR wavelengths can be selected such that the change in concentration of oxy-hemoglobin (HbO2) and deoxy-hemoglobin (Hb) in the brain tissue can be detected. Such a spectrophotometric determination is based on the absorption maximum of oxyhemoglobin and the isosbestic point of oxyhemoglobin and hemoglobin [START_REF] Tsao | Spectrophotometric determination of the oxygen saturation of whole blood[END_REF]. NIRS instrumentation works on various measuring principles, e.g., continuous wave (CW), frequency domain (FD), and time domain (TD). Absolute concentration measurements may be possible with more expensive TD and FD techniques [START_REF] Delpy | Estimation of optical pathlength through tissue from direct time of flight measurement[END_REF] but exact quantification was not a crucial factor in our application since we only wanted to detect a relative change in HbO2 and Hb rather than to quantify the hemodynamic response in absolute terms.

Chapter 2: fNIRS System Development

Functional Near Infrared Spectroscopy is used for the purpose of neuroimaging using Near Infrared spectrum. The scalp, skull, and surrounding tissues of the brain exhibit an optical window of tissue transparency in the near-infrared (NIR) range allowing interrogatory measurements of neurochemistry at the cortex. fNIRS is a noninvasive imaging method involving the quantification of chromophore concentration resolved from the measurement of near Infrared light attenuation. Using fNIRS, brain activity is measured through hemodynamic responses associated with neuron behavior. For this, we use a source-detector pair, where the detector measures the changes in intensity of NIR light provided by the source. From the changes in detected NIR light intensities, it is possible to calculate concentrations of absorbers (termed chromophores) in the tissue such as Hb and HbO. The differences in the absorption spectra of HbO and Hb allow us to measure the relative changes in hemoglobin concentration through use of light attenuation at multiple wavelengths. The next section explains the Beer Lambert law which relates the chromophore concentration change in the tissue to the absorption of light by the chromophore.

Beer Lambert law and its application

The relationship between light intensities and chromophore concentration is commonly expressed using the Beer-Lambert law.

o I A log C d I ε   ⋅     = ⋅ (1)
Attenuation (A) is the logarithmic ratio of two intensities, the intensity of the incident light (I0) and the transmitted light (I). ε is the molar extinction coefficient, as shown in Fig. 1, expressed in mM-1cm-1. C is the concentration of a chromophore and d is the direct path-length of the photon from the emitting to the receiving optode, i.e. the inter-optode or geometrical distance [START_REF] Hiraoka | A Monte Carlo investigation of optical pathlength in inhomogeneous tissue and its application to near-infrared spectroscopy[END_REF].

Considering that there are more chromophores in the tissue, the Beer-Lambert law can be written using that the absorption coefficient of each chromophore as additive [START_REF] Pellicer | Near-infrared spectroscopy: a methodology-focused review[END_REF], i.e. . [ ]

n n A C C C d ε ε ε ⋅ ⋅ ⋅ ⋅ = + + … + (2)
The typical application of the Beer-Lambert law is that A is experimentally measured (at n wavelengths for n chromophores of interest). Assuming that d is the inter-optode distance and ε1… εn has been found previously for each chromophore, the objective is to find C1…Cn [START_REF] Fishkin | Frequencydomain photon migration measurements of normal and malignant tissue optical properties in a human subject[END_REF]. Accurate estimation of chromophore concentration requires (at a minimum) the same number of wavelengths, as there is chromophores in the given tissue. A similar specific extinction coefficient of Hb and HbO2 in the near-infrared spectrum makes measuring at a single wavelength difficult and confounds the interpretation of changes in concentration of the chromophores. Simultaneous measurements of two wavelengths can be used to separate the changes for both Hb and HbO2 [START_REF] Strangman | Non-invasive neuroimaging using nearinfrared light[END_REF]. To increase the sensitivity of the estimation, two wavelengths should be chosen in order to distinguish between Hb and HbO2 molar extinction coefficients, such that HbO2 has the highest molar extinction coefficient at one wavelength and the lowest at the other.

However, if 'd' is not equal to the inter-optode distance, the hemoglobin changes cannot be quantified and comparisons between different subjects or NIRS regions cannot be made. d depends on subject's characteristics, the measured region, and the wavelength of the light. Due to scattering d will increase in an unknown manner. Approximately 80% of the total attenuation of near infrared light in tissue is due to scattering, and the remaining 20% to absorption [START_REF] Cope | System for long-term measurement of cerebral blood and tissue oxygenation on newborn infants by near infra-red transillumination[END_REF].

Scattering is thus the biggest problem when attempting quantitative measurements with NIRS. In a highly scattering medium, photons travel a mean distance that is far greater than d, which has been defined as the differential path-length (DP), i.e., the true optical distance between the optodes. Delpy et al. [START_REF] Delpy | Estimation of optical pathlength through tissue from direct time of flight measurement[END_REF] defined a scaling factor to correct for the path-length; the differential path-length factor (DPF). Therefore, the modified Beer-Lambert law incorporates the additions 0

I A log C d DPF G I ε = = ⋅ ⋅ ⋅     +   (3)
The attenuation and the specific extinction coefficient in the modified Beer-Lambert law are no longer strictly linearly related, the degree of non-linearity is a function of the scattering coefficients. The scattering coefficient of the tissue together with the geometry of the optodes are described in the term G. G is unknown and therefore an absolute calculation of chromophore concentration that cannot be derived from Eq. 3. This is a fundamental problem in tissue NIRS, making the determination of absolute concentrations of Hb and HbO2 problematic. Assuming that G has the same value for all chromophores in the medium, by using a differential equation between two chromophores, G is cleared. As a consequence, only changes in concentration of chromophores can be measured with NIRS [START_REF] Matcher | Absolute quantification of deoxyhaemoglobin concentration in tissue near infrared spectroscopy[END_REF]. Assuming that DPF and d remain constant during the measuring period, and d and DPF are known, quantitative data on changes in the concentration of chromophores can be derived.

( ) ( )

A C d DPF ε ∆ = ⋅ ∆ ⋅ ⋅ (4)
The changes in the concentration of chromophores can be calculated using a different wavelength for each chromophore, writing a Beer-Lambert equation for each, and solving the simultaneous equations through matrix inversion [START_REF] Delpy | Estimation of optical pathlength through tissue from direct time of flight measurement[END_REF]. The NIRS technique can still be applied as an oxygenation trend monitor if the DPF is unknown, such as the continuous wave NIRS. There are several techniques available that can be used to calculate the DPF, i.e., by time domain [START_REF] Matcher | Absolute quantification of deoxyhaemoglobin concentration in tissue near infrared spectroscopy[END_REF], frequency domain [START_REF] Fishkin | Frequencydomain photon migration measurements of normal and malignant tissue optical properties in a human subject[END_REF] or derivative spectroscopy [START_REF] Matcher | Absolute quantification of deoxyhaemoglobin concentration in tissue near infrared spectroscopy[END_REF], which allow for oxygenation changes to be measured. However, without the knowledge of the term G the absolute chromophore concentration cannot be measured.

Sensor implementation for continuous wave (CW) fNIRS

For hardware implementation of sensitive equipment, several factors are crucial for its performance and efficiency. As with any physiological measurement, the standardization of sensor placement, coupling, signal preprocessing, and conditioning together with a welldescribed experimental paradigm are essential elements in obtaining repeatable performance, optimized signal-to-noise ratio (SNR) and hence reduced workload on the DSP component. Measurement methods for NIRS are based around three distinct technologies:

• continuous wave (CW)

• frequency domain • time domain

We are using continuous wave (CW) NIRS in this work. This method generally employ either a multiple discrete wavelength source or a filtered white light source, they measure the light attenuation using either a photomultiplier, photodiode or an avalanche photodiode detector [START_REF] Matcher | Absolute quantification of deoxyhaemoglobin concentration in tissue near infrared spectroscopy[END_REF]. The main advantages of CW NIRS are the sampling rate, the size of the instrument, the weight, the simplicity and the cost, which makes CW NIRS ideal for bedside monitoring. However, CW NIRS has a few disadvantages, including the penetration depth and the difficulty to separate absorption and scattering effects. CW NIRS is therefore only fit to do oxygenation trend monitoring

The basic design of our NIRS probe along with the alignment of the light emitting diode (LED) and photo-detectors are shown in The analog signal obtained at the output of the low pass filter was converted to digital values using the 10 bit ADC present in Arduino Uno. The digital values were ported to the computer via USB with Arduino Uno serial USART port for processing in MATLAB. The sampling rate for ADC conversion was kept at 80Hz.

The Arduino was powered from USB port which was connected to the laptop. The 5V power output of the Arduino was used to power the entire circuit except the LED's. The LED's were powered using the digital output pins of the Arduino. The digital output pins of the Arduino were programmed for switching the LEDs ON/OFF systematically. The negative power (-5V) required For the experimental bench-testing, the NIRS probe was placed at the F3/F4 position (10-20 international system of scalp sites) -see Fig. To successfully interface the SomaSensor (Covidien, USA) with the low-cost DAQ (presented in Chapter 2), the maximum current that can go through the LED's in the SomaSensor had to be found out experimentally. This was done by varying the current through each LED in the SomaSensor and then looking at the radiant intensity changes along with the changes in the temperature of the SomaSensor. For this, we used a spectrometer Princeton Instrument SP2150 with a CCD Princeton device Pixis Excelon 400B. We also used a diffraction grating with 600

Bench testing SomaSensors for reusability

Two SomaSensors were selected out of which one was unused and unopened before the start of this experiment. The second SomaSensor however had been used for more than 20 times. The radiant intensity and the peak wavelength of both the sensors were compared. The graphs of both the sensors are shown below. We used a spectrometer Princeton Instrument SP2150 with a CCD Princeton Instrument Pixis Excelon 400B. We also used a diffraction grating with 600 grooves/mm blazed at 500nm. The exposition time was set at 3µs. It was found that even after more than 20 times of use, the SomaSensor provided consistent performance when compared to a new SomaSensor.

Human testing of SomaSensor interfaced with low-cost DAQ

To successfully interface the SomaSensor (Covidien, USA) with the low-cost DAQ (presented in Chapter 2), human testing of the Somasensors interfaced with the low-cost DAQ was required.

The following tests were performed:

1. Testing of SomaSensors: The protocol followed for data collection was 1 minute of Pre-tDCS, 1 minute during tDCS and 1 min post-tDCS. 1.5mA current was maintained during tDCS. This was done on 1 subject and done for a total of 3 times. The data showed a slight change in oxygen saturation after ensemble averaging. We need to collect more trials (>=15) to find significant changes.

2. Testing of low-cost custom-made NIRS sensors: The protocol followed for data collection was 1 minute of Pre-tDCS, 1 minute during tDCS and 1 min post-tDCS. 1.5mA current was maintained during tDCS. This was done on 1 subject and done for a total of 4 times. The data showed very small change in oxygen saturation after ensemble averaging. We need to collect more trials (>=15) to find significant changes.

3. Testing of Somasensors with the INVOS 5100 oximeter: This was done with 2 subjects. We saw slight change in oxygen saturation on the monitor during the experiment. However, we need the serial port data transfer function for collecting data for analysis in the PC. For this experiment, 1400mL human blood phantom was prepared. Out of this 1400mL, 28mL was human blood and 14mL was intralipid. It is important to mention here that the blood was donated by a volunteer on the day 1 of the experiment and a part of the same blood sample was used on the day 2 of the experiment. The phantom setup was a dual layer dynamic phantom and the separation between each layer was 1.4cm which has been published by Ms. Almajidy [START_REF] Almajidy | Estimating the spatial resolution of fNIRS sensors for BCI purposes[END_REF]. This separation also included the thickness of the beaker. The second day of the experiment showed no results where the SomaSensor could not detect the changes in the oxygen saturation in the phantom as shown in Figures 4.12-4.14. We postulate that this was due to deterioration of the phantom as well as low SNR of the SomaSensor interfaced with the low-cost DAQ. The details are discussed in the next chapter that lends to my future work. is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. The phantom seems to have deteriorated so much that the SomaSensor could not detect the change in the oxygen saturation. 12. First trial of the second day of phantom testing: The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. The phantom seems to have deteriorated so much that the SomaSensor could not detect the change in the oxygen saturation. The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. The phantom seems to have deteriorated so much that the SomaSensor could not detect the change in the oxygen saturation.

Performance testing of SomaSensor interfaced with low-cost DAQ using phantom

Chapter 5: Discussion and Future work

The low-cost CW NIRS system presented in this report costs roughly $500 [START_REF] Sood | Continuous wave functional near infra-red spectroscopy combined with transcranial direct current stimulation for assessment of cerebral vascular status in patients with ischemic stroke[END_REF]. The significant contribution of this INRIA internship work based on that low-cost CW NIRS system were, 1. Experiment done to evaluate the optimum current setting of the SomaSensor: The experiment was successful and the optimum current was found out to be 56 mA. Beyond this limit the supplied current resulted in increasing the temperature of the sensor which will damage the sensor over time and will also result in a burn if the sensor is used on a subject.

2. Experiment done to evaluate the reusability of the SomaSensor: The experiment was successful. The radiant intensity curves of both the LED's in both the SomaSensors were studied. The curves for both the new and the used SomaSensor were similar. This led to the conclusion that the SomaSensors can be reused up to 20 times at least.

3. Experiment done to test the somasensor interfaced with DAQ on a phantom: The experiments conducted on day 1 showed the variation in the oxygen saturation to some extend could be captured with the SomaSensor interfaced with low-cost DAQ but the experiments conducted on the day 2 showed no variation in the oxygen saturation levels that could be captured with the SomaSensor interfaced with low-cost DAQ. It is important to mention that all the settings and the protocol was identical on both the days of the experiment. This indicated that the device is not sensitive enough to detect the changes in blood phantom that was more than a day old. Also, the readings obtained on day 1 indicate a very low signal to noise ratio which was due to the low-cost DAQ.

The future work for the current low-cost DAQ hardware to work better with the SomaSensor are, 1. The present device is equipped with a 10 bit ADC which is the bare minimum in biomedical applications. This needs to be changed and an ADC with a higher resolution needs to be used to offer a better acquisition of the NIRS signal. One of the alternative ADC's that can be used comes from Texas Instruments AD129x family. These devices are low-power, multichannel, simultaneous-sampling, 24-bit delta-sigma (∆Σ) analog-todigital converters (ADC's) with integrated programmable gain amplifiers (PGAs). These devices incorporate various ECG-specific functions that make them well-suited for scalable electrocardiogram (ECG), electroencephalography (EEG), and electromyography (EMG) applications. Due to their high performance, these devices can be used in multichannel data acquisition systems by powering down the EEG-specific circuitry. Additionally, these devices offer a highly programmable mux which allows any of the input electrodes to be programmed as the patient reference drive. The PGA gain can be chosen from one of seven settings: 1, 2, 3, 4, 6, 8, or 12. The ADCs in the device offer data rates from 250 SPS to 32 kSPS. These devices can be communicated by using an SPI-compatible interface. Additionally, the ADS129xR also provide options for an internal respiration modulator and a demodulator circuit in the signal path of channel 1 [Texas Instruments: ADS129x Low-Power, 8-Channel, 24-Bit Analog Front-End for Biopotential Measurements]. Therefore, the future work involved replacing the 10 bit ADC of Arduino microcontroller with the 24 bit AD129x. With this, the communication protocol needs to be modified for serially porting the values to the computer. With 10 bit ADC the I2C communication protocol was used. But, the 24 bit AD129 chip comes with only SPI communication protocol. Serial Peripheral Interface (SPI) is an interface bus commonly used to send data between microcontrollers and small peripherals such as shift registers, sensors, and SD cards. It uses separate clock and data lines, along with a select line to choose the device you wish to talk to. It's a "synchronous" data bus, which means that it uses separate lines for data and a "clock" that keeps both sides in perfect sync. For synchronization, there is an extra start bit and stop bit to help the receiver sync up to data as it arrives. So, the digital output from the AD129 will be sent to Arduino programmed with SPI communication, as shown in Fig. 5.1.

With Arduino, there are two ways to communicate with SPI devices: By using the shiftIn() and shiftOut() commands. These are software-based commands that will work on any group of pins, but will be somewhat slow. Also, by using the SPI Library, which takes advantage of the SPI hardware built into the microcontroller. This is vastly faster than the above commands, but it will only work on certain pins. For Interfacing the Arduino with AD129, the various setting that needs to be done are as follows:

The interface can send data with the most-significant bit (MSB) first, or least-significant bit (LSB) first. In the Arduino SPI library, this is controlled by the setBitOrder() function. The slave will read the data on either the rising edge or the falling edge of the clock pulse. Additionally, the clock can be considered "idle" when it is high or low. In the Arduino SPI library, both of these options are controlled by the setDataMode() function. SPI can operate at extremely high speeds (millions of bytes per second), which may be too fast for some devices. To accommodate such devices, one can adjust the data rate. In the Arduino SPI library, the speed is set by the setClockDivider() function, which divides the master clock (16MHz on most arduinos) down to a frequency between 8MHz (/2) and 125kHz (/128). From arduino, the digital output will be transferred to computer with a USB cable.

2. Quantitative EEG analysis has been used as a method of identifying subclinical brain injury during neurosurgical procedures, such as carotid endarterectomy, and for ischemia detection, global function assessment, medication titration, and prognostication [START_REF] Foreman | Quantitative EEG for the detection of brain ischemia[END_REF]. Furthermore, high multilevel reproducibility has been shown [START_REF] Sheorajpanday | Reproducibility and clinical relevance of quantitative EEG parameters in cerebral ischemia: a basic approach[END_REF] where EEG parameters reliably discriminated between stroke and transient ischaemic attack (TIA) patients or control subjects, and correlated significantly with clinical and radiological status.

Reliable EEG parameters can be evaluated in a general stroke population for clinically relevant state and outcome measures [START_REF] Foreman | Quantitative EEG for the detection of brain ischemia[END_REF]. There are several studies that investigated the relationship between EEG alpha rhythm variations (alpha rhythm lies in the range of 8 to 13 Hz) and baseline regional CBF differences [START_REF] Jann | Association of individual resting state EEG alpha frequency and cerebral blood flow[END_REF] where the hemodynamic responses associated with cortical neural activity, i.e., the relationship between local neural activity and cerebral blood flow is termed neurovascular coupling (NVC) [START_REF] Filosa | Vascular tone and neurovascular coupling: considerations toward an improved in vitro model[END_REF]. Therefore, EEG may provide a measure that is independent from fNIRS where EEG can be used to indirectly detect and monitor CBF. Here, simultaneous EEG-NIRS imaging during perturbation with tDCS may help us in understanding the NVC underlying neural and hemodynamic responses post-stroke [START_REF] Dutta | EEG-NIRS based low-cost screening and monitoring of cerebral microvessels functionality[END_REF]. Furthermore, EEG-NIRS joint imaging may improve the specificity by estimating NVC as a biomarker for post-stroke impaired cerebral microvessels functionality [START_REF] Dutta | EEG-NIRS based low-cost screening and monitoring of cerebral microvessels functionality[END_REF] where non-neuronal systemic physiological fluctuations often contaminate fNIRS signals [START_REF] Sood | Anterior temporal artery tap to identify systemic interference using short-separation NIRS measurements: a NIRS/EEG-tDCS study[END_REF]. Therefore it is important to develop and integrate an EEG hardware with the NIRS hardware so that the joint neuroimaging technology can be leveraged to objectively detect and monitor the brain status.

3. For multi-channel approaches required for whole head measurements, a custom-made CW NIRS system based on an off-the-shelf data acquisition (DAQ) device to interface between signal and computer provides the user with a robust, fast and flexible solution [START_REF] Soraghan | A 12-channel, real-time near-infrared spectroscopy instrument for brain-computer interface applications[END_REF]. A multifunction off-the-shelf DAQ device (National Instruments Corporation, USA) can be used to provide basic physical input/output channels to drive the light sources and/or acquire optical signals. If timing accuracy of DAQ is critical, then a realtime off-the-shelf DAQ system, such as CompactRIO or PXI (National Instruments Corporation, USA), is required. Usually, the number of analog output channels are limited in off-the-shelf DAQ devices (e.g., only 2 analog outputs in PCIe-6351 from National Instruments Corporation, USA) and therefore the time division multiplexing technique can be used to illuminate multiple light sources (light emitting diodes or laser diodes). For example, the NIR light sources can be amplitude-modulated at different carrier frequencies with a gap (viz. 2 to 4 KHz in steps of 200Hz) using a driving circuit that includes a multiplexer and driver for the laser diode (LD) or light emitting diode (LED) to emit NIR light in consecutive time slots. LED, which emits incoherent and uncollimated light, is preferred since it allows the emission of more NIR photons into the tissue than LD with the same maximum permissible exposure [START_REF] Soraghan | A 12-channel, real-time near-infrared spectroscopy instrument for brain-computer interface applications[END_REF]. Dual-wavelength LEDs can be used instead of two separate LEDs in a multi-channel high density whole head system. Moreover, an individual programmable current source for each LED can be used so that the emitted light can be automatically adapted to variable individual acquisition conditions (hair, skin color, different tissue types such as muscle, brain etc. as well as a possible effect of EEG gel on the optical properties of the light path) [START_REF] Safaie | Wireless distributed acquisition system for near infrared spectroscopy -wda-nirs[END_REF]. Then, the backscattered NIR light can be collected (collected light is usually 7 to 9 orders smaller in magnitude than that emitted at the source [START_REF] Lareau | Near infrared spectrometer combined with multichannel EEG for functional brain imaging[END_REF]) and converted into an electrical signal by photodiodes. Due to low signal to noise ratio (SNR) of the output signal from the photodiodes, the signal can be band-pass filtered and amplified to increase the SNR.

A programmable gain amplifier (e.g. PGA204, Texas Instruments Inc., USA) can be used to adapt the gain depending on source-detector distance, scalp thickness, and hair color and density [START_REF] Scholkmann | A review on continuous wave functional near-infrared spectroscopy and imaging instrumentation and methodology[END_REF] to match the voltage range of the analog input channel of the DAQ device.

  Development of a low-cost point of care device for near-infrared spectroscopy (NIRS) based online imaging during non-express my sincere thanks to Dr. David Guiraud, Senior Research Scientist INRIA and Head Team DEMAR, LIRMM INRIA Montpellier, for accepting me as an internee in his team, supporting me throughout the course of this internship program. I wish to express my deep gratitude to Dr. Anirban Dutta, INRIA starting research scientist, DEMAR team for giving me a chance to pursue such an interesting project under Franco-Indian INRIA-DST funding and for constantly guiding and supervising me in research areas which were new to me. I am grateful to Ms. Rand Almajidy, Research Associate, for helping me with the phantom testing (under Franco-German PHC PROCOPE funding) at the research laboratory of Prof. Dr. rer. nat. Ulrich G. Hofmann, Peter-Osypka-Professor for Neuroelectronic Systems, University Medical Center Freiburg, Department of Neurosurgery, Germany. I am grateful to Mr. Victor Vagne, Doctoral Student, for helping with the bench testing of SomaSensor (under CHRU Montpellier support) at the research unit of Dr. Emmanuelle Le Bars and Dr. Nicolas Menjot de Champfleur, Plateforme d'Imagerie Fonctionnelle Humaine, Centre Hospitalier Régional Universitaire (CHRU) de Montpellier, France.

Fig 1 . 1 .

 11 Fig 1.1. Complete spectral range

Fig 2 . 1 .

 21 Fig 2.1. Variation of spectral extinction coefficient

  Fig 2.3. Basic design of amplifier

Fig 2 . 5 .Fig 2 . 4 .

 2524 Fig 2.5. Block Diagram of NIRS setup

2 . 7 .

 27 NIRS data consisted of a series of timedependent voltage signals measured between individual light source and detector positions on a probe. The concentrations of oxygenated, deoxygenated and total hemoglobin were calculated for each source-detector pair. Differential oxy hemoglobin and de-oxy hemoglobin concentrations were then estimated using modified Beer Lambert's Law with the custom software written in MATLAB (The MathWorks, Inc., USA).The cost of the major components used in the POCT NIRS hardware are given below in Table1

Fig 2 . 7 .Chapter 3 :

 273 Fig 2.7. Left Panel: POCT NIRS hardware. Right Panel: 10-20 International system of scalp sites for the placement of the sensors.

Figure 3 . 1 .Chapter 4 :

 314 Figure 3.1. SomaSensor based low-cost NIRS data acquisition device to monitor hemodynamics during NIBS.

Fig 4 . 1 .Fig 4 . 3 .

 4143 Fig 4.1. The relative radiant intensity of the used 730nm LED at 56mA current

Fig 4 . 4 .

 44 Fig 4.4. The relative radiant intensity of the unused 810nm LED at 56mA current

Figure 4 .

 4 [START_REF] Tsao | Spectrophotometric determination of the oxygen saturation of whole blood[END_REF] shows the phantom as it is prepared. Both the layers and the separation between them is clearly visible in this figure.The experiments were carried out in a dark room.

Figure 4 .

 4 6 and figure 4.7 show the phantom placed inside a black box which helped in eliminating external light exposure. A magnetic stirrer was used to keep the composition of the phantom uniform. The RPM of the stirrer was maintained at 500. Figure4.6 shows the stirrer on which the phantom has been placed. For the first 35 minutes, nitrogen was flushed in the phantom to completely remove the oxygen from the phantom. This was followed by bubbling in oxygen at a constant rate for the next 10 minutes. NIRS readings were recorded for the entire duration of the experiments.

Figure 4 .

 4 8 shows the complete setup including the phantom and the NIRS device along with data acquisition laptop. The graphs for oxygen saturation obtained after analysis of NIRS data are also shown below.

Fig 4 . 5 .

 45 Fig 4.5. Phantom preparation

Fig 4 . 7 .Fig 4 . 6 .

 4746 Fig 4.7. Phantom placed inside a dark box to reduce external light exposure

  -4.11.

Fig 4 . 9 .

 49 Fig 4.9. First trial of the first day of phantom testing:The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins.

Fig 4 . 8 .

 48 Fig 4.8. The complete experimental setup

Fig 4 . 11 .

 411 Fig 4.11. Third trial of the first day of phantom testing:The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. This trial terminated early due to a software glitch.

Fig 4 . 10 . 2 Fig 4 . 13 .

 4102413 Fig 4.10. Second trial of the first day of phantom testing:The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. This trial terminated early due to a software glitch.

Fig 4 .

 4 Fig 4.12. First trial of the second day of phantom testing: The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. The phantom seems to have deteriorated so much that the SomaSensor could not detect the change in the oxygen saturation.

Fig 4 . 14 .

 414 Fig 4.14. Third trial of the second day of phantom testing:The initial period (first 25 mins) is when the nitrogen is pumped in the phantom to reduce oxygen saturation and the last part (~15 mins) is when the oxygen is pumped in the phantom (~10 mins) to increase oxygen saturation and then the oxygen saturation was maintained for another 5mins. The phantom seems to have deteriorated so much that the SomaSensor could not detect the change in the oxygen saturation.

Fig 5 . 1 .

 51 Fig 5.1. AD129x connected with a Microcontroller

Table 1

 1

	Component	Price (USD)
	OPA2277	9
	INA131	10
	AD129 (used later)	30
	ICL7660	< 1
	Arduino Uno	30
	Somasensor (used later)	~300

Fig 2.6. Pin connections with 7660 voltage converters


Salah-Eddine Belouanas
email: salah-eddine.belouanas@lip6.fr

Kim-Loan Thai
email: kim.thai@lip6.fr

Prométhée Spathis
email: promethee.spathis@lip6.fr

Marcelo Dias De Amorim

SCoD: Saving Cellular Resources by Delaying Transmissions of Popular Content

At a time when operators struggle with unprecedented mobile data growth, saving cellular resources is of utmost importance. The first traffic that we must get rid of is redundant traffic. This happens, for example, when popular data must be disseminated to a population of subscribers. We propose SCoD, a strategy that benefits from the delay-tolerance of some applications to defer transmissions to appropriate instants. The idea is to wait for nodes to gather around a minimum number of access points so that the total number of transmissions is reduced. SCoD leverages as much as possible node mobility for the sake of clustering; to this end, SCoD relies on different guiding functions that trigger, whenever appropriate, a transmission. We assess the performance of our strategy by running simulations on a realistic vehicular dataset and find out that it leads to significant improvements when compared with traditional (instantaneous) dissemination strategies.

I. INTRODUCTION

Cellular operators are struggling with the skyrocketing growth of mobile traffic these latest years [START_REF] Cisco | Cisco visual networking index: Forecast and methodology[END_REF]. In a near future, they will likely have no choice but to combine a wide range of techniques to save cellular resources. So far, the main efforts have focused on increasing the cellular capacity, by either adopting new standards (e.g., 3G→4G→5G), or deploying more antennas, or acquiring new licensed bands.

At the same time, operators also adopt other strategies to limit usage of cellular resources. For example, most operators implement a two-phase resource assignment strategy, where users see their bandwidth capped after some data consumption threshold (generally in the order of a few Gbytes) [START_REF]At&t accused of deceiving smartphone customers with unlimited data plans[END_REF], [START_REF]Mobile internet: How many gigabytes do you need[END_REF]. A more recent strategy consists in offloading traffic through either an alternative technology (e.g., from cellular to Wi-Fi), or in-band channels (e.g., using small cells) [START_REF] Rebecchi | Data offloading techniques in cellular networks: A survey[END_REF], or even device-to-device communications [START_REF] Asadi | A survey on device-to-device communication in cellular networks[END_REF]. Following such recent trends, we are convinced that any saving is welcome.

In this paper, we propose to reduce the consumption of wireless resources by better controlling the number of transmissions, whenever possible. In particular, we advocate that a simple policy such as when to transmit could lead to significant savings in situations where data is popular and tolerates some delay. Fortunately, these situations are not rare.

The infrastructure we consider consists of a set A of access points covering a population N of mobile users interested in a content c. In this paper, unless specified, we do not deal with any specific radio technology and will simply refer to a i ∈ A as a wireless access point (or base station) that covers a zone called cell. Full dissemination must be achieved before a deadline τ . Our goal is to determine, on the fly, the minimum subset of access points  ⊂ A that should transmit a copy of the content to cover the entire population N. The challenge is to compute the different instants when access points should transmit the content; this is difficult, as user mobility cannot be known in advance.

To address the abovementioned problem, we propose SCoD (Scheduled Content Delivery), a strategy to disseminate delaytolerant contents by planning their transmission whenever groups of users in the same cell are considered big enough to trigger a transmission. Deciding what "big enough" means is the role of SCoD. We assume that a single transmission by an access point is received by all users in the corresponding cell. We also assume that each access point knows the list of mobile users it covers at all times. The population of users is composed of two types of users: sane users (who have not yet received the content) and infected users (who have already obtained the content). The decision to transmit or not is taken based on a decision function (DF), whose goal is to determine the threshold above which a group of users is sufficiently big to trigger a transmission. In a nutshell, SCoD relies on decision functions whose aggressiveness decreases over time (i.e., the threshold to consider that a group is big enough is higher in the beginning of the period). At the end of the process, when the content reaches the deadline, a content copy is transmitted within every cell hosting at least one sane user, so that full coverage is guaranteed.

We illustrate the idea of SCoD in Fig. 1. By tracking where sane users are, the infrastructure can figure out which cells host a sufficiently large number of sane users to determine if the corresponding access point should transmit the content. This is to be compared with a baseline strategy (which does not spread transmissions over time) that would require, most of the time, more transmissions in the beginning of the period (we will see this kind of behavior in Section IV). We assess the performance of SCoD by investigating several decision functions. Simulation results were obtained for a realistic largescale vehicular trace of Bologna city (Italy). We observe that SCoD significantly reduces the number of transmissions when compared with the baseline approach. Furthermore, SCoD is very close to an oracle solution (unpractical, as it assumes the knowledge of future user displacements). Moreover, the number of satisfied users converges very quickly to the total population.

The remainder of this paper is organized as follows. In user waiting for content user having received content user not interested in content cellular transmission within a cell at the beginning, to cover all nodes, six transmissions would be needed, so the system decides to wait a bit after some time, one cell decides to transmit the content later, two other cells transmit the content, finally covering all remaining nodes Fig. 1: Instead of transmitting six copies of the content at the beginning, the idea behind SCoD is to determine the right instants to trigger a transmission. In the example of the figure, it is possible to cover all users with only three transmissions.

Although for a single content it might be negligible, accumulated savings can be huge on the long term.

Section II, we present the system model and state the problem we consider in this paper. We introduce SCoD in Section III and motivate the role of the different decision functions. In Section IV, we present the evaluation methodology and the results. We postpone some related work to Section V and conclude the paper in Section VI.

II. CONTEXT AND PROBLEM STATEMENT

Without loss of generality, we model our system as a cellular network with limited capacity on the wireless access channel. We consider a system defined by the tuple [c, N, A, t 0 , τ ], where c is the content to be disseminated, N is the set of users that are interested in receiving c, A is the set of access points, t 0 is the time when c becomes available at the infrastructure, and τ is the maximum delay that any user tolerates before receiving c. We assume that c is generated at t 0 . At a given time t ∈ [t 0 , t 0 + τ ], the set of users are organized into two classes: N san ai (t) (the set of sane users associated with access point a i ∈ A at time t) and N inf ai (t) (the set of infected users associated with access point a i ∈ A at time t). At t 0 , the distribution of users is as follows: N san ai (t 0 ) = N and N inf ai (t 0 ) = ∅, for all a i ∈ A.

All cells are supposed to be disjoint. Thus, each (mobile) user is associated with one and only one access point at all times. For the purposes of this paper, we also assume that the population N remains unchanged during [t 0 , t 0 +τ ] (i.e., churn is not considered).

As previously mentioned, content c becomes available at t 0 and must be delivered to sane users by t 0 + τ . We assume perfect transmissions, i.e., a single transmission is enough to reach all users in the cell. Whenever an access point decides to transmit c, all sane users under this access point become infected users. Our goal consists in minimizing the number of transmissions by leveraging the mobility of the users. We simplify the problem by discretizing the content lifetime in time steps, then we examine each cell independently of the others. As time goes by, users may move from cell to cell; thus, density within a cell changes over time. We call a given distribution of users throughout the cells a configuration.

Problem definition. Given the tuple [c, N, A, t 0 , τ ], find a strategy to determine a threshold for the number of users in a cell at some time t ∈ [t 0 , t 0 + τ ] so that the corresponding access point decides to transmit c.

Note that setting a small threshold may lead to too many transmissions, while a big threshold may refrain an access point from transmitting in appropriate occasions. Finding a good trade-off is challenging, especially because the mobility of the users cannot be known in advance.

III. SCOD: SPECIFICATION AND OPERATION

We design SCoD following the different issues and assumptions discussed in the previous section. The most important features of SCoD are illustrated in Fig. 2. At t 0 , content c becomes available and must be delivered to all target subscribers by t 0 + τ . Upon each configuration change, SCoD checks whether the content deadline has been reached or not; if so, the decision is to transmit c in every cell containing at least one sane user. If not, a specific function β(t) (called lateness factor) is used to decide whether an access point should transmit or not. Function β(t) changes over time as it determines the aggressiveness of the decision process. SCoD is more aggressive in the beginning of the period, i.e., it expects bigger groups of users in a cell. As time goes by, it relaxes by tolerating smaller groups, up to the deadline where all cell containing at least a sane user must transmit. This procedure is formalized as follows. Access point a i transmits c at time t if one of the two conditions hold:

|N san ai (t)| ≥ β(t) A j=1 |N san aj (t)| & β(t) = 0 OR |N san ai (t)| > 0 & β(t) = 0 (1)
where |N san ai (t)| is the number of sane users associated with a i at time t and β(t), the lateness factor is a time-based function (0 ≤ β(t) ≤ 1) whose main role is to delay the transmissions. In other terms, it defines whether the system should be conservative and keep the content longer. We detail this function hereafter. Whenever a transmission takes place in at least one cell (note that nothing prevents multiple access points from transmitting at the same time), the system updates the list of sane users before the next configuration. The system carries on at the same pace until the deadline is reached. However, while the time is running, β decreases, which causes, at a given time, one of the inequalities in (1) to be satisfied. As a consequence, one or multiple transmissions occur.

SCoD transmission decision functions. We tested different functions as possible expressions of β(t). As we want the aggressiveness to decrease over time, we pick functions that are monotonically decreasing. These functions are listed in Table I.

TABLE I: Lateness factor functions used for β(t).

Function Expression

Logarithmic

β(t) = ln( -t+τ τ + 1) Linear β(t) = -t τ + 1 Square-root β(t) = -t+τ t+τ Exponential β(t) = 1 -e t τ -1

IV. EVALUATION A. Evaluation setup

In order to evaluate SCoD, we use the Bologna vehicular dataset, which contains a significant number of mobile nodes [6]. The dataset covers 20.6 km 2 in the city center for a period of two hours, featuring the movement of 10333 vehicles. We compare SCoD with three reference strategies: full coverage, immediate transmission, and oracle. In full coverage, the infrastructure systematically distributes the content in every cell (even if the cell does not have any user). Of course, this strategy is too naive to be implemented, and serves only as a lower bound. In immediate transmission, the content is transmitted at t 0 in all cells hosting sane users. Finally, in oracle, the decision to transmit is based on the prior knowledge of all future configurations during the whole period. This strategy is non-causal (thus not realizable), but provides an upper bound for the expected performance. The previous three strategies are simulated for a starting value of the lateness factor of β(t = t 0 ) = 0.25. The value of β at t = t 0 gives the initial aggressiveness of SCoD. For example, when β(t = t 0 ) = 0.25, it means that 25% of the nodes must be associated with an access point to trigger a transmission. 1We focus on a specific area of the city of Bologna where we track the location of each vehicle for a period of two hours. To assign each vehicle to an access point, we emulate a deployment plan of a wireless infrastructure consisting of access points composing the set A. Each vehicle is assigned to the nearest access point by using a Voronoi diagram [START_REF] Aurenhammer | Voronoi diagramsa survey of a fundamental geometric data structure[END_REF]. Each cell of the Voronoi diagram contains exactly one access point. We depict in Fig. 3a the tessellation for 100 access points withing the central area of Bologna.

To give more confidence to our results, we iterate the process of partitioning the map of Bologna by emulating multiple random deployment plans following a uniform distribution. The various topologies are generated for 100 and 300 access points. We assume that a single transmission by an access point is received by all vehicles in the corresponding cell. The results we show are provided for 1,000 and 2,000 nodes (vehicles in our scenario). With regard to the content deadline, we consider two scenarios with the following values: 300 s and 1,200 s (realistic values when considering such content as: pollution indication, important event announcements, popular content in social media etc. The evaluation performance results we present in the next section reflect averages over 20 simulation runs for different generated topologies (spatial distribution of access points). We primarily focus on the average transmission gain of a given strategy, G avg strategy , defined as:

G avg strategy = N FC -N strategy N FC , (2)
where, N FC is the number of transmissions when applying the full coverage strategy, and N strategy is the number of transmissions of the evaluated strategy (oracle, immediate transmission, and SCoD). Another performance criterion is the user satisfaction degree, which refers to how fast a strategy satisfies all the users at the lowest possible cost.

B. Evaluation results

We will show that SCoD performs very well in saving cellular resources by decreasing the number of transmissions. In the following, we will show the results for only one lateness function (we pick the "square" function). As a matter of fact, we observed that all functions described in Table I led to results with a small differences. In other words, this means that the aggressiveness aspect is more important that the skewness of the curve. We will not delve into this point in this paper, and will leave this discussion for future work.

Average transmission gain. We consider "full coverage" as the baseline reference to assess the gains obtained by each of other strategies. We use the average transmission gain G avg strategy as defined in Section IV-A. We plot in Fig. 4 the average transmission gain for multiple combinations of N and τ . As expected, the longer the content lifetime, the more SCoD gains. This is inherently related to the philosophy behind SCoD, whose goal is to benefit as much as possible from the mobility of the nodes. An interesting observation is that we achieve almost the same performance level as the oracle, especially for longer τ . The main reason for this behavior is that users have more time to wave among cells, which allows SCoD having more freedom to select the most appropriate time to transmit the content. We observe that the population size also has a positive impact on the gains. In one particular case, SCoD even outperformed the oracle. Although the oracle has the advantage of knowing the whole mobility trace in advance, it is not optimal. In fact, implementing the oracle is equivalent to determining the minimum cover set of a graph, which is known to be a NP-complete problem [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. In this paper, we used the greedy strategy as the heuristic to compute the oracle, which gives some room for improvements (which happened, for example, in Fig. 4d) [START_REF]A greedy heuristic for the set-covering problem[END_REF].

User satisfaction. We are also interested in evaluating the evolution of the dissemination process. In Fig. 5, we plot the CDF of satisfied users in function of the transmissions. There are a few observations we can make here. First, we see again that SCoD covers the same amount of nodes as the immediate strategy, but with less transmissions. SCoD's and oracle's curves overlap when the content tolerates longer delays. Second, and more interestingly, SCoD shows a much more steep slope. This means that SCoD limits the number of transmissions in lowly-populated cells. As a consequence, SCoD is more robust to transmission failures when the dead-line approaches (failures that happen earlier are easier to recover as we have more time left).

V. RELATED WORK

The problem of disseminating content while alleviating the burden on the overloaded infrastructure has been well studied in the literature. First proposals in this sens have target at better understanding node mobility and delay tolerance of some types of content. Solazzo et al. propose TACO-DTN, a content dissemination system that uses the info-station model to manage the resources of an access point when disseminating information [START_REF] Sollazzo | Taco-dtn: a time-aware content-based dissemination system for delay tolerant networks[END_REF], [START_REF] Frenkiel | The infostations challenge: Balancing cost and ubiquity in delivering wireless data[END_REF]. In the area of vehicular networking, similar approaches have been considered. Luan et al. propose a practical and cost-effective approach to construct a fully distributed roadside communication infrastructure to facilitate localized content dissemination to vehicles in a urban scenario [START_REF] Luan | Engineering a distributed infrastructure for large-scale cost-effective content dissemination over urban vehicular networks[END_REF]. Also in a vehicular context, Ahn et al. leverage both infrastructure and peer-to-peer communications to save resources at the cellular infrastructure [START_REF] Ahn | Optimizing content dissemination in vehicular networks with radio heterogeneity[END_REF].

Some effort have been done to maximize content dissemination within a deadline, while minimizing the use of cellular resources. Most works fall under the umbrella of mobile data offloading, which is considered to be an inexpensive method to improve the capacity of mobile networks. Balasubramanian et al. were the first to propose to delay transmissions until a node reaches a Wi-Fi hotspot [START_REF] Balasubramanian | Augmenting mobile 3g using wifi[END_REF], whose cost is assumed to be negligible when compared with the one of the cellular infrastructure. Similarly, Lee et al. suggests significant savings in energy and traffic by also delaying traffic [START_REF] Lee | Mobile data offloading: how much can wifi deliver?[END_REF]. To this end, they perform extensive analyses of traces of pedestrian mobility collected in a real metropolitan environment. From a much more theoretical perspective, Mehmeti and Spyropoulos propose a queueing analytic model for delayed offloading, and derive the mean delay, offloading efficiency, and other metrics of interest, as a function of the delay tolerance as well as other network parameters [START_REF] Mehmeti | Is it worth to be patient? analysis and optimization of delayed mobile data offloading[END_REF]. Other offloading techniques rely on device-to-device communications. Rebecchi et al. [START_REF] Rebecchi | Droid: Adapting to individual mobility pays off in mobile data offloading[END_REF], Whitbeck et al. [START_REF] Whitbeck | Relieving the wireless infrastructure: When opportunistic networks meet guaranteed delays[END_REF], and Han et al. [START_REF] Han | Cellular traffic offloading through opportunistic communications: a case study[END_REF] have considered scenarios in which device-to-device and cellular connections are used to disseminate the content, considering the social ties and the geographical proximity.

More related to our work, an alternative approach has been the center of focus in current literature, depends on the in- stantaneous availability of resources to deliver content without wasting resources [START_REF] Lungaro | Context-aware rrm for opportunistic content delivery in cellular networks[END_REF]. Although these contributions do show interesting results, they assume that nodes can communicate in ad hoc mode, which is not the case of this paper.

To summarize, our proposal differs from the previous works as it deals with full dissemination guarantees under a very constraint capacity of a cellular infrastructure.

VI. SUMMARY AND OUTLOOK

We proposed SCoD, a new content dissemination strategy specifically designed for cellular networks that suffer from heavy capacity constraints at the wireless access channel. It leverages node mobility and delay-tolerance to determine the best possible instants at which an access point must transmit a copy of a given content to a multitude of receivers. In a nutshell, its goal is to let users gather within fewer cells to reduce the number of transmissions. Experiments using a realistic vehicular dataset in the city of Bologna reveal that SCoD manages to reduce the number of transmissions when compared with strategies that do not play with the mobility of the nodes, while achieving 100% content delivery.

Our work will continue in the following directions. Firstly, we will address the problem of handling multiple contents that achieve a deadline at the same time. This will require the proposal of prioritization strategies to balance the dissemination evolution of the different contents. Secondly, we will investigate churn, where the system would accept new arrivals and departures. Thirdly, we will investigate the sensibility of the system with regard to the lateness function and its initial value.

Fig. 2 :

 2 Fig. 2: High level operation of SCoD.

Fig. 3 :

 3 Fig. 3: (a): The Voronoi diagram for a set of 100 APs deployed in the city of Bologna. (b) The red cells are the one involved in the transmission process of a content.

Fig. 4 :

 4 Fig. 4: Average transmission gain for SCoD (using a "square" lateness function) and two baseline strategies (Oracle, Immediate). Different values of the content lifetime and the users population are presented. Confidence intervals of 95% are shown as well.

Fig. 5 :

 5 Fig. 5: CDF of the users satisfaction for each strategy vs the number of transmission and the gain, and A=300 for all the plots.

This value is quite aggressive, but still leads to good results as we will show later in Section IV-B.

ACKNOWLEDGMENT

This work was partially funded by the French National Research Agency (ANR) under project ANR DataTweet (ANR-13-INFR-0008).