In recent years, the interest in the Internet of Things has been growing, and WSN is a promising technology that could be applied in many situations. Regardless of the nature of the application, WSNs are often used for data acquisition, to obtain information from an environment of interest, so it is essential to consider how this data will be made available to users. Over the last years, an increasing number of web services have been used to deal with databases and final users, providing familiar interfaces and multi-platform access to those data. To address this problem, our study proposes a web application based on MVC architecture to monitor, organize and manage devices and data in a wireless sensor network. Here, is presented a functional evaluation of the proposed system and a discussion regarding the test results.

Published in ICWS 2019

BibTeX

@inproceedings{SAFS19,
TITLE = {A Web-Service to Monitor a Wireless Sensor Network},
AUTHOR = {Rayanne Silveira and Francisco Alves and Allyx Fontaine and Ewaldo Santana},
BOOKTITLE = {Web Services - {ICWS} 2019 - 26th International Conference, Held as Part of the Services Conference Federation, {SCF} 2019, San Diego, CA, USA, June 25-30, 2019, Proceedings},
YEAR = {2019}
}

In the past few years, Internet of Things has become of common use in various areas, and especially in agriculture. There are many ways to increase the production using technology on agriculture. One of the most used is monitoring systems to follow characteristic properties and, in some cases, to control them by triggering a process that would correct an unwanted situation. Therefore, knowing the usefulness of this type of system, the present work proposes the monitoring of an environment using Internet of Things (IoT): Wireless Sensor Networks (WSN) are placed in strategic location in order to collect and send data to a web service. Currently, two topologies were tested to monitor the temperature and soil moisture of a soccer field. The samples were stored in a database and the next step is to integrate the system within the web application that we have already developed.

Published in INSCI 2019

BibTeX

@inproceedings{SDAFDFBS19,
TITLE = {Monitoring an Environment Using Wireless Sensor Network},
AUTHOR = {Rayanne Silveira and Thalyson Dutra and Francisco Alves and Allyx Fontaine and Thierry Desjardins and Raimundo Freire and Allan Barros and Ewaldo Santana},
BOOKTITLE = {Internet Science - 6th International Conference, {INSCI} 2019, Perpignan, France, December 2-5, 2019, Proceedings},
YEAR = {2019}
}

We consider dynamic and online variants of 2D pattern matching between an m*m pattern and an n*n text. All the algorithms we give are randomised and give correct outputs with at least constant probability.
For dynamic 2D exact matching where updates change individual symbols in the text, we show updates can be performed in O(log^2 n) time and queries in O(log^2 m) time.
We then consider a model where an update is a new 2D pattern and a query is a location in the text. For this setting we show that Hamming distance queries can be answered in O(log m + H) time, where H is the relevant Hamming distance.
Extending this work to allow approximation, we give an efficient algorithm which returns a (1+ \epsilon) approximation of the Hamming distance at a given location in O(\epsilon^−2 log^2 m log log n) time.
Finally, we consider a different setting inspired by previous work on locality sensitive hashing (LSH). Given a threshold k and after building the 2D text index and receiving a 2D query pattern, we must output a location where the Hamming distance is at most (1+\epsilon)k as long as there exists a location where the Hamming distance is at most k.
For our LSH inspired 2D indexing problem, the text can be preprocessed in O(n^{2(4/3+1/(1+\epsilon))}log^3 n)time into a data structure of size O(n^{2(1+1/(1+\epsilon))}) with query time O(n^{2(1/(1+\epsilon))}m^2).

Published in SPIRE 2016

BibTeX

@inproceedings{CFSV16,
TITLE = {Dynamic and Approximate Pattern Matching in 2D},
AUTHOR = {Rapha{\"{e}}l Clifford and Allyx Fontaine and Tatiana A. Starikovskaya and Hjalte Wedel Vildh{\o}j},
BOOKTITLE = {String Processing and Information Retrieval - 23rd International Symposium,{SPIRE} 2016, Beppu, Japan, October 18-20, 2016, Proceedings},
YEAR = {2016}
}

Randomised algorithms are generally simple to formulate. However, their analysis can become very complex, especially in the field of distributed computing. In this paper, we formally model in Coq a class of randomised distributed algorithms. We develop some tools to help proving impossibility results about classical problems and analysing this class of algorithms. As case studies, we examine the handshake and maximal matching problems. We show how to use our tools to formally prove properties about algorithms solving those problems.

Published in ICTAC 2016

BibTeX

@inproceedings{FZC16,
TITLE = {Certified Impossibility Results and Analyses in Coq of Some Randomised Distributed Algorithms},
AUTHOR = {Allyx Fontaine and Akka Zemmari},
BOOKTITLE = {Theoretical Aspects of Computing - {ICTAC} 2016 - 13th International Colloquium, Taipei, Taiwan, ROC, October 24-31, 2016, Proceedings},
YEAR = {2016}
}

Distributed systems have been studied thoroughly. Many applications are based on huge systems and one of the main property an algorithm running on such systems should verified is fault-tolerance. This paper presents a new randomized algorithm to solve the handshake problem in a distributed system. This algorithm is designed for an asynchronous distributed network of anonymous processes under the message passing communication protocol. In addition to its fault-tolerance, this algorithm is more effective than the existing ones thanks to its asynchronous aspect. To highlight its performance, we provide an experimental evaluation by comparing it to the most representative algorithm solving the handshake problem. The experimentation is done using Visidia, a tool for simulating and visualizing distributed algorithms.

Published in WAINA 2016

BibTeX

@inproceedings{FMTZ16,
TITLE = {A Fault-Tolerant Handshake Algorithm for Local Computations},
AUTHOR = {Allyx Fontaine and Mohamed Mosbah and Mohamed Tounsi and Akka Zemmari},
BOOKTITLE = {IEE AINA 2016 Workshop - The 30th IEEE International Conference on Advanced Information Networking and Applications, Le Régent Congress Centre, Crans-Montana, Switzerland, March 23 - 25, 2016},
YEAR = {2016}
}

We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming distance is at most k. Where the Hamming distance is greater than k at some alignment of the pattern and text, we simply output “No”. We study this problem in both the standard offline setting and also as a streaming problem. In the streaming k-mismatch problem the text arrives one symbol at a time and we must give an output before processing any future symbols. Our main results are as follows:
Our first result is a deterministic $O(nk²\; log\; k/m\; +\; n\; polylog\; m)$math> time offline algorithm for k-mismatch on a text of length n. This is a factor of k improvement over the fastest previous result of this form from SODA 2000.
We then give a randomised and online algorithm which runs in the same time complexity but requires only $O(k²\; polylog\; m)$ space in total.
Next we give a randomised (1 + ∊)-approximation algorithm for the streaming k-mismatch problem which uses $O(k²\; polylog\; m/∊²)$ space and runs in $O(polylog\; m/∊²)$ worst-case time per arriving symbol.
Finally we combine our new results to derive a randomised O(k2 polylog m) space algorithm for the streaming k-mismatch problem which runs in worst-case time per arriving symbol. This improves the best previous space complexity for streaming k-mismatch from FOCS 2009 by a factor of k. We also improve the time complexity of this previous result by an even greater factor to match the fastest known offline algorithm (up to logarithmic factors).

Published in SODA 2016

BibTeX

@inproceedings{CFPST16,
TITLE = {The \emph{k}-mismatch problem revisited},
AUTHOR = {Rapha{\"{e}}l Clifford and Allyx Fontaine and Ely Porat and Benjamin Sach and Tatiana A. Starikovskaya},
BOOKTITLE = {Proceedings of the Twenty-Seventh Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2016, Arlington, VA, USA, January 10-12, 2016},
PAGES = {2039--2052},
YEAR = {2016}
}

We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We present a randomised algorithm which takes $O(log\; log(k+m))$ time per arriving character and uses $O(k\; log\; m)$ words of space, where $k$ is the number of strings in the dictionary and m is the length of the longest string in the dictionary.

Published in ESA 2015

BibTeX

@inproceedings{CFPST15,
TITLE = {Dictionary Matching in a Stream},
AUTHOR = {Rapha{\"{e}}l Clifford and Allyx Fontaine and Ely Porat and Benjamin Sach and Tatiana A. Starikovskaya},
BOOKTITLE = {Algorithms - {ESA} 2015 - 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings},
PAGES = {361--372},
YEAR = {2015}
}

This paper concerns probabilistic distributed graph algorithms to solve classical graph problems such as colouring, maximal matching or maximal independent set. We consider anonymous networks (no unique identifiers are available) where vertices communicate by single bit messages. We present a general framework, based on coverings, for proving lower bounds for the bit complexity and thus the execution time to solve these problems. In this way we obtain new proofs of some well known results and some new ones. The last part gives impossibility results on the existence of Las Vegas distributed algorithms to break symmetries at distance $k$ for $k\ge 3$.

Published in SOFSEM 2014

BibTeX

@inproceedings{FMRZ14,
TITLE = {On Lower Bounds for the Time and the Bit Complexity of Some Probabilistic Distributed Graph Algorithms - (Extended Abstract)},
AUTHOR = {Allyx Fontaine and Yves M{\'{e}}tivier and John Michael Robson and Akka Zemmari},
BOOKTITLE = {{SOFSEM} 2014: Theory and Practice of Computer Science - 40th International Conference on Current Trends in Theory and Practice of Computer Science, Nov{\'{y}} Smokovec, Slovakia, January 26-29, 2014, Proceedings},
pages = {235--245},
year = {2014}
}