The problem of data privacy preservation is of central importance in ride-sharing applications, because in order to efficiently match passengers with vehicles, these services rely on exact location information. Yet, transportation and location data can reveal personal habits, preferences and behaviors, and users may prefer not to share their exact location. Masking location data in order to avoid the identification of users in case of data leakage, and/or misusage would help protect user privacy, but could also lead to poorer system performance, in terms of efficiency and quality of service as perceived by users.In this paper, we compare classic data masking techniques, namely obfuscation, k-anonymity, and l-diversity, applied to users’ location data, before sending it to a carpooling system. While the first two techniques use randomly generated points to mask the actual location, l-diversity uses actual points of interest, having the additional benefit of ensuring that the disclosed location is always an accessible and safe pickup or drop-off location. Given that users in a real ride-sharing system could choose to protect or not protect their location data when using the system, we also evaluate the effect of privacy preservation penetration rate, by varying the percentage of users choosing to have their location data protected. The results show that l-diversity performance is better than the others’ even when the privacy penetration rate is high, suggesting that this technique has the potential to meet both users’ and system’s needs, and thus being a better option to provide privacy within carpooling systems.

Trip matching algorithms used in ride-sharing and carpooling systems share the common goal of optimizing the number of used vehicles to satisfy a set of trips according to their temporal and spatial constraints, in order to better allocate resources and reduce traffic and congestion. However, each matching algorithm could be designed to pursue a different objective like, for instance, reducing users' waiting time for quality of service, reducing the total amount of traveled distance within the system to reduce carbon footprint, or maximizing the time two trips are shared to favor user interaction. Changing the final system objective could significantly change the performance of the system itself. In this paper, we compare the performance of matching algorithms with different objectives and show whether potential tradeoffs exist in pursuing these objectives, taking into consideration all the actors in play in a mobility sharing application. In particular, by applying the matching algorithms to two sets of daily trips performed in the cities of Pisa, Italy, and Cambridge, USA, our analysis shows that there is a matching algorithm among the ones we tested able to provide a good compromise between different optimization objectives.

Periodic exchange of situational information (beacons) is at the basis of most active safety applications in vehicular environments, and understanding its performance in real-world situations is very important. However, existing studies are focused on measuring the packet delivery rate (PDR), while disregarding the packet inter-reception (PIR) time which has recently been shown to be more relevant than PDR to characterize active safety application performance. In this paper, we fill this gap by presenting an extensive study of the PIR times observed in real-world highway scenarios. We start by showing that PIR cannot be reliably estimated from PDR, since the two metrics are only weakly correlated. Motivated by this finding, we present a thorough characterization of the PIR time distribution, which is shown to be a power law in a variety of configurations. The shape of the PIR time distribution indicates that potentially dangerous “situational awareness” blackouts are relatively frequent and positively time correlated. We then evaluate the effect of vehicle configuration and line-of-sight conditions on the PIR time, and show that relatively simple multi-hop beaconing techniques can substantially improve PIR statistics and, hence, safety. A final contribution of this paper is promoting the Gilbert–Elliot model, previously proposed to model bit-error bursts in packet switched networks, as a very accurate model of beacon reception behavior observed in real-world scenarios.

In this paper, we study the performance of the beaconing mechanism underlying active safety vehicular applications in presence of different levels of channel congestion. The importance of this study lies in the fact that channel congestion is considered a major factor influencing communication performance in vehicular networks, and that ours is the first investigation of the effects of congestion based on extensive, real-world measurements. We present a set of measurement-based models of the packet inter-reception time, and we show how these models can be used to estimate the application-level benefits, expressed in terms of increased reliability, of congestion control and of multi-hop propagation of situational information.

Active safety applications for vehicular networks aims at improving safety conditions on the road by raising the level of “situation awareness” onboard vehicles. Situation awareness is achieved through exchange of beacons reporting positional and kinematic data. Two important performance parameters influence the level of situation awareness available to the active safety application: the beacon (packet) delivery rate (PDR), and the packet inter-reception (PIR) time. While measurement-based evaluations of the former metric recently appeared in the literature, the latter metric has not been studied so far. In this paper, for the first time, we estimate the PIR time and its correlation with PDR and other environmental parameters through an extensive measurement campaign based on IEEE 802.11p technology. Our study discloses several interesting insights on PIR times that can be expected in a real-world scenarios, which should be carefully considered by the active safety application designers. A major insight is that the packet inter reception time distribution is a power-law and that long situation awareness black-outs are likely to occur in batch, implying that situation awareness can be severely impaired even when the average beacon delivery rate is relatively high. Furthermore, our analysis shows that PIR and PDR are only loosely (negatively) correlated, and that the PIR time is almost independent of speed and distance between vehicles. A third major contribution of this paper is promoting the Gilbert-Elliot model, previously proposed to model bit error bursts in packet switched networks, as a very accurate model of beacon reception behavior observed in real-world data.

This paper studies, for the first time to our best knowledge, VoIP performance over V2V IEEE 802.11p links. VoIP performance is evaluated in terms of both throughput and jitter through on-the-road measurements, investigating also the effects of inter-vehicle distance and speed on VoIP performance. Results of our study show that VoIP performance is quite poor, especially due to an excessively large number of lost packets under all investigated scenarios. In-lab experiments performed to investigate possible causes of this poor performance reveal that throughput degradation is likely to be due to inefficiencies in implementation of the vehicular networking stack, rather than to poor communication quality.

BACKGROUND: Tandem repetitions within protein amino acid sequences often correspond to regular secondary structures and form multi-repeat 3D assemblies of varied size and function. Developing internal repetitions is one of the evolutionary mechanisms that proteins employ to adapt their structure and function under evolutionary pressure. While there is keen interest in understanding such phenomena, detection of repeating structures based only on sequence analysis is considered an arduous task, since structure and function is often preserved even under considerable sequence divergence (fuzzy tandem repeats). RESULTS: In this paper we present PTRStalker, a new algorithm for ab-initio detection of fuzzy tandem repeats in protein amino acid sequences. In the reported results we show that by feeding PTRStalker with amino acid sequences from the UniProtKB/Swiss-Prot database we detect novel tandemly repeated structures not captured by other state-of-the-art tools. Experiments with membrane proteins indicate that PTRStalker can detect global symmetries in the primary structure which are then reflected in the tertiary structure. CONCLUSIONS: PTRStalker is able to detect fuzzy tandem repeating structures in protein sequences, with performance beyond the current state-of-the art. Such a tool may be a valuable support to investigating protein structural properties when tertiary X-ray data is not available.

BACKGROUND: Tandem repeats are multiple duplications of substrings in the DNA that occur contiguously, or at a short distance, and may involve some mutations (such as substitutions, insertions, and deletions). Tandem repeats have been extensively studied also for their association with the class of repeat expansion diseases (mostly affecting the nervous system). Comparative studies on the output of different tools for finding tandem repeats highlighted significant differences among the sets of detected tandem repeats, while many authors pointed up how critical it is the right choice of parameters. RESULTS: In this paper we present TReaDS - Tandem Repeats Discovery Service, a tandem repeat meta search engine. TReaDS forwards user requests to several state of the art tools for finding tandem repeats and merges their outcome into a single report, providing a global, synthetic, and comparative view of the results. In particular, TReaDS allows the user to (i) simultaneously run different algorithms on the same data set, (ii) choose for each algorithm a different setting of parameters, and (iii) obtain a report that can be downloaded for further, off-line, investigations. We used TReaDS to investigate sequences associated with repeat expansion diseases. CONCLUSIONS: By using the tool TReaDS we discover that, for 27 repeat expansion diseases out of a currently known set of 29, long fuzzy tandem repeats are covering the expansion loci. Tests with control sets confirm the specificity of this association. This finding suggests that long fuzzy tandem repeats can be a new class of cis-acting elements involved in the mechanisms leading to the expansion instability.We strongly believe that biologists can be interested in a tool that, not only gives them the possibility of using multiple search algorithm at the same time, with the same effort exerted in using just one of the systems, but also simplifies the burden of comparing and merging the results, thus expanding our capabilities in detecting important phenomena related to tandem repeats.

In this paper, we address the problem of balancing the network traffic load when the data generated in a wireless sensor network is stored on the sensor node themselves, and accessed through querying a geographic hash table. Existing approaches allow balancing network load by changing the georouting protocol used to forward queries in the geographic hash table. However, this comes at the expense of considerably complicating the routing process, which no longer occurs along (near) straight-line trajectories, but requires computing complex geometric transformations. In this paper, we demonstrate that it is possible to balance network traffic load in a geographic hash table without changing the underlying georouting protocol. Instead of changing the (near) straight-line georouting protocol used to send a query from the node issuing the query (the source) to the node managing the queried key (the destination), we propose to “reverse engineer” the hash function used to store data in the network, implementing a sort of “load-aware” assignment of key ranges to wireless sensor nodes. This innovative methodology is instantiated into two specific approaches: an analytical one, in which the destination density function yielding quasiperfect load balancing is analytically characterized under uniformity assumptions for what concerns location of nodes and query sources; and an iterative, heuristic approach that can be used whenever these uniformity assumptions are not fulfilled. In order to prove practicality of our load balancing methodology, we have performed extensive simulations resembling realistic wireless sensor network deployments showing the effectiveness of the two proposed approaches in considerably improving load balancing and extending network lifetime. Simulation results also show that our proposed technique achieves better load balancing than an existing approach based on modifying georouting.

In this paper, we present a measurement study of application layer performance in IEEE 802.11p vehicular net works. More specifically, our focus is on active safety applications, which are based on the exchange of beacon messages containing status information between close-by vehicles. We consider two performance metrics relevant to active safety applications: the first is application-layer goodput, which can be used to optimize congestion control techniques aimed at limiting the beaconing load on the wireless channel; the second is the beacon reception rate, which is useful to estimate the level of situation awareness achievable onboard vehicles. Our measurements were conducted using a prototypal, 802.11p compliant communication device developed by NEC, in both stationary and mobile V2V scenarios, and disclosed several useful insights on 802.11p application-level performance. To the best of our knowledge, the ones presented in this paper are the first application-level measurements of IEEE 802.11p based vehicular networks reported in the literature.

MOTIVATION: Genomes in higher eukaryotic organisms contain a substantial amount of repeated sequences. Tandem Repeats (TRs) constitute a large class of repetitive sequences that are originated via phenomena such as replication slippage and are characterized by close spatial contiguity. They play an important role in several molecular regulatory mechanisms, and also in several diseases (e.g. in the group of trinucleotide repeat disorders). While for TRs with a low or medium level of divergence the current methods are rather effective, the problem of detecting TRs with higher divergence (fuzzy TRs) is still open. The detection of fuzzy TRs is propaedeutic to enriching our view of their role in regulatory mechanisms and diseases. Fuzzy TRs are also important as tools to shed light on the evolutionary history of the genome, where higher divergence correlates with more remote duplication events. RESULTS: We have developed an algorithm (christened TRStalker) with the aim of detecting efficiently TRs that are hard to detect because of their inherent fuzziness, due to high levels of base substitutions, insertions and deletions. To attain this goal, we developed heuristics to solve a Steiner version of the problem for which the fuzziness is measured with respect to a motif string not necessarily present in the input string. This problem is akin to the 'generalized median string' that is known to be an NP-hard problem. Experiments with both synthetic and biological sequences demonstrate that our method performs better than current state of the art for fuzzy TRs and that the fuzzy TRs of the type we detect are indeed present in important biological sequences. AVAILABILITY: TRStalker will be integrated in the web-based TRs Discovery Service (TReaDS) at bioalgo.iit.cnr.it. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Wireless mesh networks are a promising area for the deployment of new wireless communication and networking technologies. In this paper, we address the problem of enabling effective peer-to-peer resource sharing in this type of networks. Starting from the well-known Chord protocol for resource sharing in wired networks, we propose a specialization that accounts for peculiar features of wireless mesh networks: namely, the availability of a wireless infrastructure, and the 1-hop broadcast nature of wireless communication, which bring to the notions of location awareness and MAC layer cross-layering. Through extensive packet-level simulations, we investigate the separate effects of location awareness and MAC layer cross-layering, and of their combination, on the performance of the P2P application. The combined protocol, MeshChord, reduces message overhead of as much as 40 percent with respect to the basic Chord design, while at the same time improving the information retrieval performance. Notably, differently from the basic Chord design, our proposed MeshChord specialization displays information retrieval performance resilient to the presence of both CBR and TCP background traffic. Overall, the results of our study suggest that MeshChord can be successfully utilized for implementing file/resource sharing applications in wireless mesh networks.

The detection of an over-represented sub-sequence in a set of (carefully chosen) DNA sequences is often the main clue leading to the investigation of a possible functional role for such a subsequence. Over-represented substrings (with possibly local mutations) in a biological string are termed motifs. A typical functional unit that can be modeled by a motif is a Transcription Factor Binding Site (TFBS), a portion of the DNA sequence apt to the binding of a protein that participates in complex transcriptomic biochemical reactions. In the literature it has been proposed a simplified combinatorial problem called the planted (l-d)-motif problem (known also as the (l-d) Challenge Problem) that captures the essential combinatorial nature of the motif finding problem. In this paper we propose a novel graph-based algorithm for solving a refinement of the (l-d) Challenge Problem. Experimental results show that instances of the (l-d) Challenge Problem considered difficult for competing state of the art methods in literature can be solved efficiently in our framework.

Wireless mesh networks are a promising area for the deployment of new wireless communication and networking technologies. In this paper, we address the problem of enabling effective peer-to-peer resource sharing in this type of networks. In particular, we consider the well-known Chord protocol for resource sharing in wired networks and the recently proposed MeshChord specialization for wireless mesh networks, and compare their performance under various network settings for what concerns total generated traffic and load balancing. Both iterative and recursive key lookup implementation in Chord/MeshChord are considered in our extensive performance evaluation. The results confirm superiority of MeshChord with respect to Chord, and show that recursive key lookup is to be preferred when considering communication overhead, while similar degree of load unbalancing is observed. However, recursive lookup implementation reduces the efficacy of MeshChord cross-layer design with respect to the original Chord algorithm. MeshChord has also the advantage of reducing load unbalancing with respect to Chord, although a moderate degree of load unbalancing is still observed, leaving room for further improvement of the MeshChord design.

Wireless mesh networks are a promising area for the deployment of new wireless communication and networking technologies. In this paper, we address the problem of enabling effective peer-to-peer resource sharing in this type of networks. Starting from the well-known Chord protocol for resource sharing in wired networks, we propose a specialization (called MESHCHORD) that accounts for peculiar features of wireless mesh networks: namely, the availability of a wireless infrastructure, and the 1-hop broadcast nature of wireless communication. Through extensive packet-level simulations, we show that MESHCHORD reduces message overhead of as much as 40% with respect to the basic Chord design, while at the same time improving the information retrieval performance.

Hierarchical peer to peer networks with multiple directory services are an important architecture for large-scale file sharing due to their effectiveness and efficiency. Recent research argues that they are also an effective method of providing large-scale content-based federated search of text-based digital libraries. In both cases the directory services are critical resources that are subject to attack or failure, but the latter architecture may be particularly vulnerable because content is less likely to be replicated throughout the network.