We introduce seqBench, a parametrized benchmark for probing sequential reasoning limits in Large Language Models (LLMs) through precise, multi-dimensional control over several key complexity dimensions.seqBench allows systematic variation of (1) the logical depth, defined as the number of sequential actions required to solve the task; (2) the number of backtracking steps along the optimal path, quantifying how often the agent must revisit prior states to satisfy deferred preconditions (e.g., retrieving a key after encountering a locked door); and(3) the noise ratio, defined as the ratio between supporting and distracting facts about the environment.Our evaluations on state-of-the-art LLMs reveal a universal failure pattern: accuracy collapses exponentially beyond a modelspecific logical depth.Unlike existing benchmarks, seqBench's fine-grained control facilitates targeted analyses of these reasoning failures, illuminating universal scaling laws and statistical limits, as detailed in this paper alongside its generation methodology and evaluation metrics.We find that even top-performing models systematically fail on seqBench's structured reasoning tasks despite minimal search complexity, underscoring key limitations in their commonsense reasoning capabilities.Designed for future evolution to keep pace with advancing models, the seqBench datasets are publicly released to spur deeper scientific inquiry into LLM reasoning, aiming to establish a clearer understanding of their true potential and current boundaries for robust real-world application.

Recent booming successes of electric vehicles (EVs) motivate emerging exploration of spatio-temporal EV charging demand forecasting to inform policy making. Recent studies have contributed to remarkable accuracy improvement by developing deep learning methods. However, when they access massive amounts of data and frequently exchange data through the Internet of Things (IoT), data silos and inefficient training emerge as main challenges. To tackle these challenges, this study proposes an integrated approach for regional EV charging demand forecasting, named FMGCN, which consists of two modules, namely 1) Spatio-temporal Learning module, which introduces spatial and temporal attentions to capture the underlying charging patterns between different regions and cities effectively; and 2) Distributed Pretraining module, which incorporates Federated Learning and Meta-Learning to enhance the adaptivity and generalisability of the forecasting model. A comprehensive evaluation based on a real-world dataset of 25,246 public EV charging piles shows that the proposed model outperforms other representative models with 1) an average improvement of 29.9% in forecasting errors; 2) an acceleration of 65% in convergence speed; and 3) a sound adaptability to support varying charging demand.

Recent technological developments have shown significant potential for transforming urban mobility. Considering first- and last-mile travel and short trips, the rapid adoption of dockless bike-share systems showed the possibility of disruptive change, while simultaneously presenting new challenges, such as fleet management or the use of public spaces. In this paper, we evaluate the operational characteristics of a new class of shared vehicles that are being actively developed in the industry: scooters with self-repositioning capabilities. We do this by adapting the methodology of shareability networks to a large-scale dataset of dockless bike-share usage, giving us estimates of ideal fleet size under varying assumptions of fleet operations. We show that the availability of self-repositioning capabilities can help achieve up to 10 times higher utilization of vehicles than possible in current bike-share systems. We show that actual benefits will highly depend on the availability of dedicated infrastructure, a key issue for scooter and bicycle use. Based on our results, we envision that technological advances can present an opportunity to rethink urban infrastructures and how transportation can be effectively organized in cities.

Today, and probably for a long time to come, humans will remain an integral part of vehicles for driving tasks. Therefore, it is essential to understand how vehicles and drivers interact with each other and how drivers’ behavior and physical and mental states affect vehicle performance and traffic safety. This article explores the relationship between driver and vehicle in real-world driving conditions by analyzing large-scale naturalistic data collected from cars and drivers. Specifically, more than 800 hours of driving data from 16 drivers were collected using three different data sources (telematics data, video frames, and physiological data) and two types of analysis were done. The first one analyzes different types of driver-vehicle interactions during driving. The second one investigates the effect of different driving conditions on drivers’ stress and explores the relationship between driver and vehicle in different driving conditions. Our experimental results show that drivers’ physiological signals are correlated with some variables from vehicle kinematics and influenced by drivers’ behavior inside the vehicle. These findings could be used to help manage comfort-related in-vehicle intervention systems and could provide a continuous measure of how different external conditions (traffic, road, weather, etc.) affect drivers.

Ride sharing has a tremendous potential to reduce the number of vehicles needed to serve a certain mobility demand. However, although ride sourcing services have flourished in recent years and are widely available worldwide (e.g. Uber, Didi, Lyft, Via), known ride sharing techniques still suffer severe scalability limitations, especially if the goal is combining multiple on-demand ride requests into a single trip within a large urban area. In the context of on-demand mobility systems, a complete enumeration of all candidate trip requests is unfortunately not a practical approach to find the optimal ride sharing solution. An efficient filtering approach is therefore needed in order to avoid both the storage of quadratic shortest-path lookup tables, as well as the exhaustive pairwise comparison of all mobility requests, with their GPS coordinates and time constraints. In this paper we present a ride sharing algorithm, which combined with the shareability networks method, is able to substantially speed up known approaches while only minimally impacting on the quality of the computed solution. The key building block is a novellocality filter, which allows to build a pruned version of the shareability network more efficiently in time and space than previous works. We corroborate this novel proposal with a large set of experiments executed over a dataset consisting of one month of trip requests (~106) performed in two different urban areas, namely Manhattan (NYC) and Singapore. Our experiments show that our approach achieves a$5\times $speed-up, or even more during so-called “rush times”, and it is robust under different traffic conditions.

The challenging applications envisioned for the future Internet of Things networks are making it urgent to develop fast and scalable resource allocation algorithms able to meet the stringent reliability and latency constraints typical of the ultra-reliable, low-latency communications (URLLCs). However, there is an inherent tradeoff between complexity and performance to be addressed: sophisticated resource allocation methods providing optimized spectrum utilization are challenged by the scale of applications and the concomitant stringent latency constraints. Whether nontrivial resource allocation approaches can be successfully applied in large-scale network instances is still an open question that this article aims to address. More specifically, we consider a scenario in which channel-state information (CSI) is used to improve spectrum allocation in a radio environment that experiences channel time correlation. Channel correlation allows the usage of CSI for longer time before an update, thus lowering the overhead burden. Following this intuition, we propose a dynamic pilot transmission allocation scheme in order to adaptively tune the CSI age. We systematically analyze the improvement of this approach applied to a sophisticated, recently introduced graph-based resource allocation method that we extend here to account for CSI. The results show that even in very dense networks and accounting for the higher computational time of the graph-based approach, this algorithm is able to improve spectrum efficiency by over 12% as compared to a greedy heuristic, and that dynamic pilot transmissions allocation can further boost its performance in terms of fairness, while concomitantly further increase spectrum efficiency of 3%-5%.

Online product reviews have become increasingly important in digital consumer markets where they play a crucial role in making purchasing decisions by most consumers. Unfortunately, spammers often take advantage of online reviews by writing fake reviews to promote/demote certain products. Most of the previous studies have focused on detecting fake reviews and individual fake reviewer-ids. However, to target a particular product, fake reviewers work collaboratively in groups and/or create multiple fake ids to write reviews and control the sentiments of the product. This article addresses the problem of finding such fake reviewer groups. More specifically, we propose a top-down framework for candidate fake reviewer groups’ detection based on the DeepWalk approach on reviewers’ graph data and a (modified) semisupervised clustering method, which can incorporate partial background knowledge. We validate our proposed framework on a real review dataset from the Google Play Store, which has partial ground-truth information about 2207 fraud reviewer-ids out of all 38 123 reviewer-ids in the dataset. Our experimental results demonstrate that the proposed approach is able to identify the candidate spammer groups with reasonable accuracy. The proposed approach can also be extended to detect groups of opinion spammers in social media (e.g. fake comments or fake postings) with temporal affinity, semantic characteristics, and sentiment analysis.

The current development trend of wireless communications aims at coping with the very stringent reliability and latency requirements posed by several emerging Internet-of-Things (IoT) application scenarios. Since the problem of realizing ultrareliable low-latency communications (URLLCs) is becoming more and more important, it has attracted the attention of researchers, and new efficient resource allocation algorithms are necessary. In this article, we consider a challenging scenario where the available spectrum might be fragmented across nonadjacent portions of the band, and channels are differently affected by interference coming from surrounding networks. Furthermore, channel state information (CSI) is assumed to be unavailable, thus requiring an allocation of resources-based only on topology information and channel statistics. To address this challenge in a dense smart factory scenario, where devices periodically transmit their data to a common receiver, we present a novel resource allocation methodology based on a graph-theoretical approach originally designed to allocate mobility resources in on-demand, shared transportation. The proposed methodology is compared with two benchmark allocation strategies, showing its ability of increasing spectral efficiency of as much as 50% with respect to the best performing benchmark. Contrary to what happens in many resource allocation settings, this increase in spectrum efficiency does not come at the expense of fairness, which is also increased as compared to benchmark algorithms.

Mobility trajectories of users contain personal information that when analyzed may reveal relevant data usable as message-sharing condition, e.g., interests in common or similar mobility patterns. In particular, leveraging on mobility patterns, in [12] we designed and presented a Geo-casting routing protocol called LoSeRO for opportunistic networks, which uses knowledge of the locations most frequently visited by a user to route messages. LoSeRO forwards messages-in a multi-casting way-to all users who have a mobility profile that intersects the packet's destination zone. LoSeRO presented a relative good performance value, however, to improve its performances, in this paper our contribution is to propose an upgraded version of our earlier proposed protocol, termed as LoSeRO v2. In particular, it upgrades the traditional working fashion of LoSeRO by extending the knowledge of the most frequented locations to those users not only directly met, i.e., two-hops away. With this purpose, through simulations, we compare the performance of LoSeRO v2, with LoSeRO and other existing routing geo-casting protocols, and we illustrate how LoSeRO v2 achieves enhanced performances comparing precision, coverage and additional metrics.

Cars can nowadays record several thousands of signals through the controller area network (CAN) bus technology and potentially provide real-time information on the car, the driver, and the surrounding environment. This paper proposes a new methodology for near-real-time analysis and classification of driver behavior using a selected subset of CAN bus signals, specifically gas pedal position, brake pedal pressure, steering wheel angle, steering wheel momentum, velocity, RPM, longitudinal and lateral acceleration. Data have been collected in a completely uncontrolled experiment involving 54 people, where over 2000 trips have been recorded without any type of predetermined driving instruction on a wide variety of road scenarios. While only few works have analyzed the driving behavior of more than 50 drivers using CAN bus data, we propose an unsupervised learning technique that clusters drivers in different groups, and offers a validation method to test the robustness of clustering in a wide range of experimental settings. The minimal amount of data needed to preserve robust driver clustering is also computed, showing that by properly choosing a subsampling strategy it is possible to reduce the size of the database as much as 99% without impairing the clustering performance.

The increasing availability and adoption of shared vehicles as an alternative to personally owned cars presents ample opportunities for achieving more efficient transportation in cities. With private cars spending on the average over 95% of the time parked, one of the possible benefits of shared mobility is the reduced need for parking space. While widely discussed, a systematic quantification of these benefits as a function of mobility demand and sharing models is still mostly lacking in the literature. As a first step in this direction, this paper focuses on a type of private mobility which, although specific, is a major contributor to traffic congestion and parking needs, namely, home-work commuting. We develop a data-driven methodology for estimating commuter parking needs in different shared mobility models, including a model where self-driving vehicles are used to partially compensate flow imbalance typical of commuting, and further reduce parking infrastructure at the expense of the increased traveled kilometers. We consider the city of Singapore as a case study and produce very encouraging results showing that the gradual transition to shared mobility models will bring tangible reductions in parking infrastructure. In the future-looking, self-driving vehicle scenario, our analysis suggests that up to 50% reduction in parking needs can be achieved at the expense of the increasing total traveled kilometers of less than 2%.

Cities are encountering extensive deficits in infrastructure service while they are experiencing rapid technological advancements and overhauls in transportation systems. Standard bridge evaluation methods rely on visual inspections, which are infrequent and subjective, ultimately affecting the structural assessments on which maintenance plans are based. The operational behavior of a bridge must be observed more regularly and over an extended period in order to sufficiently track its condition and avoid unexpected rehabilitation. Mobile sensor networks are conducive to monitoring bridges vibrations routinely, with benefits that have been demonstrated in recent structural health monitoring (SHM) research. Though smartphone accelerometers are imperfect sensors, they can contribute valuable information to SHM, especially when aggregated, e.g., via crowdsourcing. In an application on the Harvard Bridge (Boston, MA), it is shown that acceleration data collected using smartphones in moving vehicles contained consistent and significant indicators of the first three modal frequencies of the bridge. In particular, the results became more precise when informatics from several smartphone datasets were combined. This evidence is the first to support the hypothesis that smartphone data, collected within vehicles passing over a bridge, can be used to detect several modal frequencies of the bridge. The result defines an opportunity for local governments to make partnerships that encourage the collection of low-cost bridge vibration data, which can contribute to more effective management and informed decision-making.

In recent years, cars have evolved from purely mechanical to veritable cyberphysical systems that generate large amounts of real-time data. These data are instrumental to the proper working of the vehicle itself, but make them amenable to a multitude of other uses. For instance, GPS information has recently been used for a large number of mobility studies in the academic community[1],[5], as well as to feed traffic apps such as Google Traffic and Waze. This use of vehicle data is already having a profound impact in science, industry, economy, and society at large. Now, imagine that instead of accessing one single source of vehicle-generated data (GPS), one can access the entire wealth of data exchanged on the controller area network (CAN) bus in near real timeamounting to over 4000 signals sampled at high frequency, corresponding to a few gigabytes of data per hour. What would be the implications, opportunities, and challenges sparked by this transition?

We consider the problem of maximizing performance in multihop wireless networks while achieving fairness among flows. While time-based fairness has been widely recognized as the appropriate fairness mechanism in single-hop wireless networks, no analogous notion has been developed for multihop wireless networks. We define the first general notion of time-based fairness for multihop networks by abstracting a network into a virtual single-hop network and applying the single-hop time-based fairness notion. This produces rate shares for each flow in the network, and we develop a constructive method for achieving these rate shares through physical-interference-aware scheduling. When combined with an appropriate link transmission policy, this scheduling approach preserves the time-based-fair rate shares for flows even with spatial reuse and the resulting rate reductions that occur among concurrent links. To our best knowledge, this is the first constructive approach for achieving fair rate shares in multihop wireless networks with or without interference consideration. We also prove that, with an appropriate scheduling algorithm, this approach produces an aggregate rate that is within a constant factor of the maximum aggregate rate subject to time-based fairness. Finally, we perform extensive simulations, which show that our approach as much as doubles the aggregate rate of a solution that approximates max-min fairness, while achieving a more natural fairness property.

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.

We tackle the problem of locality-aware message spreading in a network composed of smart mobile devices, without resorting to any backbone communication infrastructure. The motivations for our work are two-fold. First, recent smart mobile devices are capable of capturing and storing location information (at a significant granularity) by using, e.g., GPS service and storage capacity available in the devices. Second, recent studies have shown that mobility is positively correlated with the building of new social relationships, which are relatively more likely to occur for people who have visited common places in the past [2], [4], [3]. These two factors together show the importance of building proximity based communication networks, and the need of messages spreading among a targeted set of users in a network. We assume that the participating users move in a large geographic area, and a location inside the area can be uniquely identified by any user, for example, using GPS coordinates. Each user independently builds her mobility profile, called Moby Zone, considering her own past mobility traces. The Moby Zone of a user is the set of her most visited places.

Existing social-aware routing protocols for packet switched networks make use of the information about the social structure of the network deduced by state information of nodes (e.g., history of past encounters) to optimize routing. Although these approaches are shown to have superior performance to social-oblivious, stateless routing protocols (BinarySW, Epidemic), the improvement comes at the cost of considerable storage overhead required on the nodes. In this paper we present SANE, the first routing mechanism that combines the advantages of both social-aware and stateless approaches. SANE is based on the observation - that we validate on a real-world trace - that individuals with similar interests tend to meet more often. In SANE, individuals (network members) are characterized by their interest profile, a compact representation of their interests. By implementing a simple routing rule based on interest profile similarity, SANE is free of network state information, thus overcoming the storage capacity problem with existing social-aware approaches. Through thorough experiments, we show the superiority of SANE over existing approaches, both stateful, social-aware and stateless, social-oblivious. We discuss the statelessness of our approach in the supplementary file, which can be found on the Computer Society Digital Library at http://doi.ieeecomputersociety.org/10.1109/TPDS.2014.2307857, of this manuscript. Our interest-based approach easily enables innovative networking services, such as interest-casting. An interest-casting protocol is also introduced in this paper, and evaluated through experiments based on both real-world and synthetic mobility traces.

In this paper, we consider how proportional fairness in wireless networks is impacted by spatial reuse and the interference it produces. We observe that, in scenarios where spatial reuse is possible (e.g., in high-density WLAN environments), the classic notion of time-based proportional fairness can be severely impacted: some users might experience very large interference penalties while other users might get larger bandwidth proportions than what they would have received with time-based proportional fairness and no spatial reuse. To account for this, we introduce the concept of interference-aware STDMA time-based proportional fairness (i-STPF), and compare it to ordinary STDMA time-based proportional fairness (STPF). We present an εi-STPF scheduling algorithm, and prove that it approximates the time-based fair bandwidth allocation (up to a small positive constant ε), while providing an aggregate throughput that is within a constant factor from optimal. We also present a heuristic i-STPF scheduling algorithm and compare it through simulation to a similar heuristic STPF scheduler, and to an interference-aware, rate-based scheduler. The results show that the i-STPF scheduler: i) achieves excellent aggregate throughput about 35% higher than rate-based throughput; and ii) maintains a close approximation to time-based fairness without interference.

In this paper, we introduce the notion of mobility-cast in opportunistic networks, according to which a message sent by a node S is delivered to nodes with a mobility pattern similar to that of S - collectively named place-friends. The motivation for delivering a message to place-friends stems from the fact that current social acquaintances are likely to be place-friends. Most importantly, it has been recently found that a large fraction of new social contacts comes from place-friends.

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.

Many mobile social networking applications are based on a “friend proximity detection” step, according to which two mobile users try to jointly estimate whether they have friends in common, or share similar interests, etc. Performing “friend proximity detection” in a privacy-preserving way is fundamental to achieve widespread acceptance of mobile social networking applications. However, the need of privacy preservation is often at odds with application-level performance of the mobile social networking application, since only obfuscated information about the other user's profile is available for optimizing performance. In this paper, we study for the first time the fundamental tradeoff between privacy preservation and application-level performance in mobile social networks. More specifically, we consider a mobile social networking application for opportunistic networks called interest-casting. In the interest-casting model, a user wants to deliver a piece of information to other users sharing similar interests (“friends”), possibly through multi-hop forwarding. In this paper, we propose a privacy-preserving friend proximity detection scheme based on a protocol for solving the Yao's “Millionaire's Problem”, and we introduce three interest-casting protocols achieving different tradeoffs between privacy and accuracy of the information forwarding process. The privacy versus accuracy tradeoff is analyzed both theoretically, and through simulations based on a real-world mobility trace. The results of our study demonstrate for the first time that privacy preservation is at odds with forwarding accuracy, and that the best tradeoff between these two conflicting goals should be identified based on the application-level requirements.

The problem of multiple-input-multiple-output (MIMO) feasiblity refers to whether it is possible to support specified numbers of streams allocated to the links of an MIMO network while canceling all interference. In unilateral interference cancellation, nodes account only for interfering links that they have been assigned to cancel and ignore other interfering links. We present several different formulations of the unilateral MIMO feasibility problem and use these formulations to analyze the problem's complexity and develop heuristic feasibility algorithms. We first prove that the general unilateral feasibility problem is NP-complete. We then identify several special cases where the problem is solvable in polynomial time. These include when only receiver-side interference cancellation is performed, when all nodes have two antenna elements, and when the maximum degree of the network's interference graph is two. Finally, we present several heuristic feasibility algorithms derived from different problem formulations and evaluate their accuracies on randomly generated MIMO networks.

Performance bounds for opportunistic networks have been derived in a number of recent papers for several key quantities, such as the expected delivery time of a unicast message, or the flooding time (a measure of how fast information spreads). However, to the best of our knowledge, none of the existing results is derived under a mobility model which is able to reproduce the power law+exponential tail dichotomy of the pairwise node intercontact time distribution which has been observed in traces of several real opportunistic networks. The contributions of this paper are two-fold: first, we present a simple pairwise contact model—called the Home-MEG model—for opportunistic networks based on the observation made in previous work that pairs of nodes in the network tend to meet in very few, selected locations (home locations); this contact model is shown to be able to faithfully reproduce the power law+exponential tail dichotomy of intercontact time. Second, we use the Home-MEG model to analyze flooding time in opportunistic networks, presenting asymptotic bounds on flooding time that assume different initial conditions for the existence of opportunistic links. By comparing asymptotic bounds with the results of simulations performed using a realistic human mobility model, we demonstrate the capability of the proposed Home-MEG model to faithfully predict the speed of information spreading in large-scale opportunistic networks. Finally, our bounds provide some analytical evidences that the speed of information spreading in opportunistic networks can be much faster than that predicted by simple geometric mobility models.

In this paper, we tackle the problem of designing a random mobility model generating a target node spatial distribution. More specifically, we solve a long standing open problem by presenting two versions of the well-known random waypoint (RWP) mobility model in bounded regions generating a uniform steady-state node spatial distribution. In the first version, named temporal-RWP , we exploit the temporal dimension of node mobility and achieve uniformity by continuously changing the speed of a mobile node as a function of its location and of the density function of trajectories in the movement region R . In the second version, named spatial-RWP , we instead exploit the spatial dimension and achieve uniformity by selecting waypoints according to a suitably defined mix of probability density functions. Both proposed models can be easily incorporated in wireless network simulators, and are thus of practical use. The RWP models presented in this paper allow for the first time completely removing the well-known border effect causing possible inaccuracies in mobile network simulation, thus completing the picture of a “perfect” simulation methodology drawn in existing literature.

The long-standing problem of identifying the scattering mechanism that triggers the observance of a heavy-tailed power azimuth spectrum is undertaken using a geometry-based stochastic approach. More specifically, the unimodal power azimuth spectrum (PAS) and joint power angular scattering response (PASR) are derived under the 2-D Gaussian scattering model. At first, it is formally shown that, under free-space propagation, a Gaussian scatter distribution in 2-D space gives rise to an angular power spectrum that may be well modeled by the Gaussian function. Numerical results are presented for higher path-loss exponents, where it is shown that heavy-tailed functions such as the Lorentzian and Laplacian functions provide good fits to the derived spectrum. To complement earlier research works in this area, a recently introduced geometry-based stochastic model is extended in order to express the instantaneous multimodal PASR, which significantly contributes to the estimated correlation statistics as shown in the paper. The 2-D spatial channel model developed herein, allows the distance from the observation point to vary, which enhances the validity of the derived PAS and PASR. Statistical results are provided for various distances from the observation point in order to facilitate any potential practical use of the derived 2-D model. Finally, an analytical expression for the correlation experienced between two antenna patterns is derived under the proposed model.

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.

For this demo, we present an implementation of the FairPlay framework for secure two-party function computation on Android smartphones, which we call MobileFairPlay. MobileFairPlay allows high-level programming of several secure two-party protocols, including protocols for the Millionaire problem, set intersection, etc. All these functions are useful in the context of mobile social networks and opportunistic networks, where parties are often requested to exchange sensitive information (list of contacts, interest profiles, etc.) to optimise network operation.

In this paper, we present an implementation of the FairPlay framework for secure two-party function computation on Android smartphones, which we call MobileFairPlay. Mobile-FairPlay allows high-level programming of several secure two-party protocols, including protocols for the Millionaire problem, set intersection, computation of Jaccard similarity coefficient, etc. All these functions are useful in the context of mobile social networks and opportunistic networks, where parties are often requested to exchange sensitive information (list of contacts, interest profiles, etc.) to optimize network operation. To demonstrate the feasibility of MobileFairPlay, we present an application to privacy-preserving interest-casting in opportunistic networks, implementing a recently proposed protocol. We tested running times of the implemented protocol on several Android phones, obtaining very reasonable (up to 5sec) running times. These results clearly promote MobileFairPlay as a feasible security framework for mobile environments.

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.

Message forwarding is a fundamental brick to spread information among users in opportunistic networks. In this paper, we consider the recently proposed interest-casting networking primitive for opportunistic networks, according to which a packet generated by a sender should be delivered to all users in the network - potentially unknown to the sender - sharing similar interests. However, the current implementation of interest-casting assume users exchange their interest profiles to take forwarding decisions, thus revealing very sensitive information to strangers. In this work, we approach for the first time the problem of designing an interest-casting protocol while not revealing sensitive information during the forwarding and message delivery process. In particular, we present a privacy-preserving mechanism based on the well-known Millionaires' problem allowing users to discover whether they have similar interests without disclosing private information. Based on this mechanism, we propose four different privacy-preserving forwarding protocols to realise interest-casting in opportunistic networks, and we compare their performance on a real-world mobility trace.

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 framework for analyzing routing performance in delay tolerant networks (DTNs). Differently from previous work, our framework is aimed at characterizing the exact distribution of relevant performance metrics, which is a substantial improvement over existing studies characterizing either the expected value of the metric, or an asymptotic approximation of the actual distribution. In particular, the considered performance metrics are packet delivery delay, and communication cost, expressed as number of copies of a packet circulating in the network at the time of delivery. Our proposed framework is based on a characterization of the routing process as a stochastic coloring process and can be applied to model performance of most stateless delay tolerant routing protocols, such as epidemic, two-hops, and spray and wait. After introducing the framework, we present examples of its application to derive the packet delivery delay and communication cost distribution of two such protocols, namely epidemic and two-hops routing. Characterizing packet delivery delay and communication cost distribution is important to investigate fundamental properties of delay tolerant networks. As an example, we show how packet delivery delay distribution can be used to estimate how epidemic routing performance changes in presence of different degrees of node cooperation within the network. More specifically, we consider fully cooperative, noncooperative, and probabilistic cooperative scenarios, and derive nearly exact expressions of the packet delivery rate (PDR) under these scenarios based on our proposed framework. The comparison of the obtained packet delivery rate estimation in the various cooperation scenarios suggests that even a modest level of node cooperation (probabilistic cooperation with a low probability of cooperation) is sufficient to achieve 2-fold performance improvement with respect to the most pessimistic scenario in which all potential forwarders drop packets.

In this paper, the problem of deriving the power angular scattering response (PASR) resulting from a Gaussian scatterer distribution is undertaken. The scatter cluster can be located arbitrarily in the vicinity of the mobile unit. Furthermore, for the considered scatter geometry we derive both the angular and distance statistics at the observation point, allowing a theoretical characterization of the PASR. A major byproduct of this analysis is that the Gaussian scatterer hypothesis is formally shown to produce a Gaussian power angular spectrum in a macrocell environment, which is in accordance with existing measurements.

In this paper, the angular power spectrum exhibited under a three-dimensional (3-D) Gaussian scattering distribution at fixed observation points in space is investigated. Typically, these correspond to the mobile and base units, respectively. Unlike other spatial channel models, the derived model accounts for the distance to each scatterer from the observation point, and transforms distances into power values under the assumption of free-space propagation. The proposed 3-D spatial channel model follows a non-central approach in terms of the scatterer distribution in space, which means that the angular power field at the base unit need not be due to a scatterer distribution centered exactly at the mobile. Derivations are provided for the angular and power domains. As shown, by conditioning the distance, the angular field reduces to the von-Mises Fisher distribution. Most importantly, this work provides a theoretical backup to the Gaussian angular power spectrum observed in radio propagation channel measurements, introducing a formal theoretical framework consistent with the experimental investigations found in literature. More specifically, our findings show that a Gaussian scatterer distribution in space gives rise to a Gaussian-like angular power spectrum and a Gaussian angular power density in the azimuth and elevations fields. By introducing the notion of distance into the framework, the proposed 3-D spatial channel model can be used to evaluate performance of current and future multi-element wireless communication networks.

In this paper, we investigate the fundamental properties of broadcasting in mobile wireless networks. In particular, we characterize broadcast capacity and latency of a mobile network, subject to the condition that the stationary node spatial distribution generated by the mobility model is uniform. We first study the intrinsic properties of broadcasting, and present the RippleCast broadcasting scheme that simultaneously achieves asymptotically optimal broadcast capacity and latency, subject to a weak upper bound on maximum node velocity and under the assumption of static broadcast source. We then extend RippleCast with the novel notion of center-casting, and prove that asymptotically optimal broadcast capacity and latency can be achieved also when the broadcast source is mobile. This study intendedly ignores the burden related to the selection of broadcast relay nodes within the mobile network, and shows that optimal broadcasting in mobile networks is, in principle, possible. We then investigate the broadcasting problem when the relay selection burden is taken into account, and present a combined distributed leader election and broadcasting scheme achieving a broadcast capacity and latency which is within a $$\Uptheta((\log n)^{1+\frac{2}{\alpha}})$$ factor from optimal, where n is the number of mobile nodes and α > 2 is the path loss exponent. However, this result holds only under the assumption that the upper bound on node velocity converges to zero (although with a very slow, poly-logarithmic rate) as n grows to infinity.

The contribution of this position paper is twofold: the first one extends the use of social networking in the direction of allowing not only communications among persons but also human-machine interaction and machine to machine collaboration; the second contribution is the presentation of an experimental platform for large-scale testing of innovative mobile social networking applications, including the one described in the first part of the paper.

In this paper we describe SANE, the first forwarding mechanism that combines the advantages of both social-aware and stateless approaches in pocket switched network routing. SANE is based on the observation“that we validate on real-world traces”that individuals with similar interests tend to meet more often. In our approach, individuals (network members) are characterized by their interest profile, a compact representation of their interests. Through extensive experiments, we show the superiority of social-aware, stateless forwarding over existing stateful, social-aware and stateless, social-oblivious forwarding. An important byproduct of our interest-based approach is that it easily enables innovative routing primitives, such as interest-casting. An interest-casting protocol is also described, and extensively evaluated through experiments based on both real-world and synthetic mobility traces.

A MIMO network is a wireless network made up of individual MIMO links. The problem we consider is to maximize throughput in a multihop MIMO network with interference suppression. Our problem formulation accounts for variable rates on the MIMO links, which depend on the channel conditions of the link, and the manner in which the diversity-multiplexing trade-off is handled. We present an ILP formulation of the MIMO one-shot scheduling problem with variable rates, which is the first exact formulation of a MIMO network optimization problem that accounts for full interference suppression capabilities of MIMO links. We use CPLEX to evaluate the optimal solution based on the ILP formulation for wireless networks with up to 32 concurrently transmitting links. We also modify a heuristic algorithm from a related MIMO scheduling problem to work in our problem setting. Results show that the heuristic can scale to networks with 80 or more concurrent links, but is 10-20% from optimal in terms of throughput. We show that the heuristic scheduler is not able to fully exploit the diversity-multiplexing-interference suppression tradeoff, which is inherent in the problem. This shows that there is substantial room for developing improved scheduling algorithms for MIMO networks and provides some insight into promising directions to explore.

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.

Cooperative vehicular systems have been identified as a promising solution to overcome the current and future needs for increasing traffic safety and efficiency, while providing infotainment and added-value services on the move. To achieve their objectives, cooperative vehicular systems will be based on wireless communications between vehicles and with other infrastructure nodes, and will have to deal with highly dynamic nodes, challenging propagation conditions, and stringent application requirements. By looking at cooperative applications and their data traffic, as well as the current and foreseen spectrum allocations for cooperative vehicular systems, there is a risk that the corresponding radio channels could easily be saturated if no control algorithms are used. The saturation of the radio channels would result in unstable vehicular communications, and thus in an inefficient operation of cooperative systems. As a prime example of upcoming ubiquitous networks contributing to the vision of “a thousand radios per person,” cooperative vehicular systems need to be designed to scale to high densities of radios without centralized coordination, while at the same time guaranteeing the requirements of the implemented applications and services, for example the stringent needs of active traffic safety applications. In this paper, we survey and classify various decentralized methods to control the load on the radio channels and to ensure each vehicle's capacity to detect and communicate with the relevant neighboring vehicles, with a particular focus on approaches based on transmit power and rate control. Finally, we discuss the open research challenges that are imposed by different application requirements and potential existing contradictions.

This paper studies the fundamental properties of broadcasting in multihop wireless networks. Previous studies have shown that, as long as broadcast capacity is concerned, asymptotically optimal broadcasting is possible in wireless multihop networks under very general conditions. However, none of the existing work on broadcast capacity has considered latency in message delivery, which is simply assumed to be finite (but not explicitly bounded). In this paper, the issue of investigating the fundamental properties of broadcast communications for what concerns both capacity and latency using a realistic, SINR-based interference model is investigated. In particular, a novel topological notion of network connectivity is introduced, and it is shown that, if the network satisfies this property, asymptotically optimal broadcast capacity and latency can be achieved simultaneously. The above result holds in the general scenario in which an arbitrary number of broadcast sources arbitrarily share the available (optimal) network capacity. The result presented in this paper is in sharp contrast to similar results obtained for the case of unicast transmissions, where asymptotically optimal latency in message delivery can be achieved only at the expense of asymptotically reducing network capacity. Thus, the results presented in this paper show that scalable broadcasting in multihop wireless networks is, in principle, possible.

In this paper, we investigate the fundamental properties of broadcasting in mobile wireless networks. In particular, we characterize broadcast capacity and latency of a mobile network, subject to the condition that the stationary node spatial distribution generated by the mobility model is uniform. We first study the intrinsic properties of broadcasting, and present a broadcasting scheme that simultaneously achieves asymptotically optimal broadcast capacity and latency, subject to a weak upper bound on the maximum node velocity. We then investigate the broadcasting problem when the burden related to selecting relay nodes is taken into account, and present a combined distributed leader election and broadcasting scheme achieving a broadcast capacity and latency which is within a poly-logarithmic factor from optimal.

Vehicle-to-vehicle (V2V) or vehicle-to-infrastructure (V2I) communications are enabling technologies for a host of applications, ranging from infotainment and web browsing to cooperative driving for enhanced traffic safety and efficiency. The latter two application areas, traffic safety and efficiency, address the issue of sustainable mobility and are high on the political agendas around the world.

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.

In this paper, we consider the classical problem of link scheduling in wireless networks under an accurate interference model, in which correct packet reception at a receiver node depends on the signa-to-interference-plus-noise ratio (SINR). While most previous work on wireless networks has addressed the scheduling problem using simplistic graph-based or distance-based interference models, a few recent papers have investigated scheduling with SINR-based interference models. However, these papers have either used approximations to the SINR model or have ignored important aspects of the problem. We study the problem of wireless link scheduling under the exact SINR model and present the first known true approximation algorithms for transmission scheduling under the exact model. We also introduce an algorithm with a proven approximation bound with respect to the length of the optimal schedule under primary interference. As an aside, our study identifies a class of “difficult to schedule” links, which hinder the derivation of tighter approximation bounds. Furthermore, we characterize conditions under which scheduling under SINR-based interference is within a constant factor from optimal under primary interference, which implies that secondary interference only degrades performance by a constant factor in these situations.

In this paper, we study the fundamental properties of broadcasting in multi-hop wireless networks. Previous studies have shown that, as long as broadcast capacity is concerned, asymptotically optimal broadcasting is possible in wireless multi-hop networks under very general conditions. However, none of the existing work on broadcast capacity has considered latency in message delivery, which is simply assumed to be finite (but not explicitly bounded). In this paper, we address the issue of investigating the fundamental properties of broadcast communications for what concerns both capacity and latency using a realistic, SINR-based interference model. In particular, we introduce a novel topological notion of network connectivity, and show that, if the network satisfies this property, asymptotically optimal broadcast capacity and latency can be achieved simultaneously. This is in sharp contrast to similar results obtained for the case of unicast transmissions, where strictly bounded latency in message delivery can be achieved only at the expense of asymptotically reducing network capacity. Thus, the results presented in this paper show that scalable broadcasting in multi-hop wireless networks is, in principle, possible.

It is common practice in wireless multihop network evaluations to ignore interfering signals below a certain signal strength threshold. This paper investigates the thesis that this produces highly inaccurate evaluations in many cases. We start by defining a bounded version of the physical interference model, in which interference generated by transmitters located beyond a certain distance s from a receiver is ignored. We then derive a lower bound on neglected interference and show that it is approximately two orders of magnitude greater than the noise floor for typical parameter values and a surprisingly small number of nodes. We next evaluate the effect of neglected interference through extensive simulations done with a widely-used packet-level simulator (GTNetS), considering 802.11 MAC with both CBR and TCP traffic in networks of varying size and topology. The results of these simulations show very large evaluation errors when neglecting far-away interference: errors in evaluating aggregate throughput when using the default interference model reached up to 210% with 100 nodes, and errors in individual flow throughput were far greater.

In this paper, we analyze the effect of different degrees of node cooperation on the performance of routing protocols for delay tolerant networks. We first present an accurate analytical characterization of the performance of epidemic and two-hops routing in terms of expected packet delivery rate under the standard assumption of fully cooperative node behavior. This characterization is itself an interesting result, since it requires accurately approximating the distribution of the packet delivery delay. We then use the results derived in the first part of the paper to analytically characterize epidemic routing protocol performance in presence of different degrees of node cooperation. We also performed extensive simulations for a broader set of routing protocols and cooperation scenarios. The results of our simulations show that, while epidemic routing provides the better PDR performance under all investigated degrees of network cooperation, binary SW routing can achieve comparable performance, with the potential of significantly reducing message overhead. Binary SW routing shows also the better resilience to lower node cooperation levels amongst the considered routing protocols. Finally, our results suggest that even a modest level of node cooperation is sufficient to achieve 3-4-fold performance improvement with respect to the most pessimistic scenario in which all potential forwarders drop messages.

This paper considers the problem of scheduling the maximum number of streams in a single time slot under the MIMO degrees of freedom (DOF) model, when all links are in a single collision domain. In the DOF model, nodes can use degrees of freedom provided by their antenna arrays to multiplex multiple streams on a single link and/or cancel interference between concurrently transmitting links. Given a set of links with data to transmit that are free of primary interference, we provide optimal constructions for both the case where only spatial reuse (from interference cancellation) is allowed and the case where both spatial reuse and spatial multiplexing can be done simultaneously. Our analysis allows deriving clean throughput performance trends when the number of available DOFs is arbitrarily increased. These trends show that combining spatial multiplexing with spatial reuse can arbitrarily increase throughput compared to spatial reuse only, and that close to two-fold throughput increases can be achieved compared to spatial multiplexing only. Finally, we show how the approach can be extended to deal with primary interference and optimally solve the one-shot stream scheduling problem for an arbitrary set of MIMO links in a single collision domain.

It is known that CSMA/CA channel access schemes are not well suited to meet the high traffic demand of wireless mesh networks. One possible way to increase traffic carrying capacity is to use a spatial TDMA (STDMA) approach in conjunction with the physical interference model, which allows more aggressive scheduling than the protocol interference model on which CSMA/CA is based. While an efficient centralized solution for STDMA with physical interference has been recently proposed, no satisfactory distributed approaches have been introduced so far. In this paper, we first prove that no localized distributed algorithm can solve the problem of building a feasible schedule under the physical interference model. Motivated by this, we design a global primitive, called SCREAM, which is used to verify the feasibility of a schedule during an iterative distributed scheduling procedure. Based on this primitive, we present two distributed protocols for efficient, distributed scheduling under the physical interference model, and we prove an approximation bound for one of the protocols. We also present extensive packet-level simulation results, which show that our protocols achieve schedule lengths very close to those of the centralized algorithm and have running times that are practical for mesh networks.

Recently, interest has arisen in use of realistic interference models for transmission scheduling in wireless multihop networks, particularly in mesh networks where throughput is a major concern. In this work, we use the SINR-based physical interference model and develop a uniform framework for transmission scheduling when diverse wireless resources can be exploited. The factors considered are multiple (possibly overlapped) channels, directional antennas, and transmit power control. We develop an efficient heuristic for computing a diversity exploiting schedule based on a new network saturation metric. We prove that, under uniform random node distributions, the schedule produced by our heuristic is within a poly-log factor from optimal with a probability that approaches one as network size increases. Through simulation, we demonstrate the ability of our algorithm to achieve up to a 10-fold throughput improvement with respect to networks without diversity. Our analysis also reveals a number of insights on the ability of diversity exploitation to reduce or eliminate interference.

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.

Providing strong QoS guarantees for wireless multi-hop networks is very challenging, due to many factors such as use of a shared communication medium, variability in wireless link quality, and so on. However, wireless mesh technology gives the opportunity to alleviate some of these problems, due to lack of mobility in the wireless infrastructure, and presence of natural centralization points in the network. The main contribution of this paper is the definition of a simple framework that exploits these features to provide provable, strong QoS guarantees to network clients. In particular, admitted clients are guaranteed a certain minimum bandwidth and maximum delay on their connections. The framework is based on STDMA scheduling at the MAC layer, which is periodically executed at the network manager to adapt to changes in traffic demand. While scheduling computation is centralized, admission control is performed locally at the wireless backbone nodes, thus reducing signaling. We propose two bandwidth distribution and related admission control policies, which are at opposite ends of the network utilization/spatial fairness trade-off. Through extensive simulations, we show that the proposed framework achieves its design goals of providing strong QoS guarantees to VoIP clients while not sacrificing throughput in a realistic mesh network scenario, also in presence of highly unbalanced load at the backbone nodes. To the best of our knowledge, this is the first proposal with similar features for wireless mesh networks.

Dealing with interference is one of the primary challenges to solve in the design of protocols for wireless ad-hoc networks. Most of the work in the literature assumes localized or hop-based interference models in which the effect of interference is neglected beyond a certain range from the transmitter. However, interference is a more complex phenomenon that cannot, in general, be captured by localized models, implying that protocols based on such models are not guaranteed to work in practice. This paper is the first to present and rigorously analyze a distributed dominating set protocol for wireless ad-hoc networks with O(1) approximation bound based on the physical interference model, which accounts for interference generated by all nodes in the network. The proposed protocol is fully distributed, randomized, and extensively uses physical carrier sensing to reduce message overhead. It does not need node identifiers or any kind of prior information about the system, and all messages are of constant size (in bits). We prove that, by appropriately choosing the threshold for physical carrier sensing, the protocol stabilizes within a logarithmic number of communication rounds, w.h.p., which is faster than the runtime of any known distributed protocol without prior knowledge about the system under any wireless model that does not abstract away collisions.

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.

We consider the problem of establishing a route and sending packets between a source/destination pair in ad hoc networks composed of rational selfish nodes whose purpose is to maximize their own utility. In order to motivate nodes to follow the protocol specification, we use side payments that are made to the forwarding nodes. Our goal is to design a fully distributed algorithm such that (1) a node is always better off participating in the protocol execution (individual rationality), (2) a node is always better off behaving according to the protocol specification (truthfulness), (3) messages are routed along the most energy-efficient (least cost) path, and (4) the message complexity is reasonably low. We introduce the COMMIT protocol for individually rational, truthful, and energy-efficient routing in ad hoc networks. To the best of our knowledge, this is the first ad hoc routing protocol with these features. COMMIT is based on the VCG payment scheme in conjunction with a novel game-theoretic technique to achieve truthfulness for the sender node. By means of simulation, we show that the inevitable economic inefficiency is small. As an aside, our work demonstrates the advantage of using a cross-layer approach to solving problems: Leveraging the existence of an underlying topology control protocol, we are able to simplify the design and analysis of our routing protocol and reduce its message complexity. On the other hand, our investigation of the routing problem in the presence of selfish nodes disclosed a new metric under which topology control protocols can be evaluated: the cost of cooperation.

Modeling mobility and user behavior is of fundamental importance in testing the performance of protocols for wireless data networks. Although several models have been proposed in the literature, none of them can at the same time capture important features such as geographical mobility, user-generated traffic, and the wireless technology at hand. When collectively considered, these three aspects determine the user-perceived quality-of-service (QoS) level, which, in turn, might have an influence on the mobility of those users (we call them QoS-driven users) who do not display constrained mobility patterns, but they can decide to move to less congested areas of the network in case their perceived QoS level becomes unacceptable. In this paper, we introduce the Wireless QoS-aware Mobility (WiQoSM) model, which collectively considers all of the above mentioned aspects of wireless data networks. WiQoSM is composed of 1) a user mobility model, 2) a user traffic model, 3) a wireless technology model, and 4) a QoS model. Components 1,2, and 3 provide input to the QoS model, which, in turn, can influence the mobility behavior of QoS-driven users. WiQoSM is very simple to use and configure and can be used to generate user and traffic traces at the access points (APs) composing a wireless data network. WiQoSM is shown to be able to generate traces that resemble statistical features observed in traces extracted from real-world wireless local area network (WLAN) deployments. Furthermore, WiQoSM has the nice feature of allowing the fine tuning of a disjoint set of parameters in order to influence different statistical properties of the generated traces and of providing the network designer with a high degree of flexibility in choosing network parameters such as the number of users and APs, wireless channel technology, traffic mix, and so on. Given the above features, WiQoSM can be a valuable tool in the simulation of wireless data network protocols.

Vehicular Ad Hoc Networks (VANETs) are attracting the attention of researchers, industry, and governments for their potential of significantly increasing the safety level on the road. In order to understand whether VANETs can actually realize this goal, in this paper we analyze the dynamics of multi-hop emergency message dissemination in VANETs. Under a probabilistic wireless channel model that accounts for interference, we derive lower bounds on the probability that a car at distance d from the source ofthe emergency message correctly receives the message within time t. Besides d and t, this probability depends also on 1-hop channel reliability, which we model as a probability value p, and on the message dissemination strategy. Our bounds are derived for an idealized dissemination strategy which ignores interference, and for two provably near-optimal dissemination strategies under protocol interference. The bounds derived in the first part of the paper are used to carefully analyze the tradeoff between the safety level on the road (modeled by parameters d and t), and the value of 1-hop message reliability p. The analysis of this tradeoff discloses several interesting insights that can be very useful in the design of practical emergency message dissemination strategies.

Wireless mesh networks are expected to be widely used to provide Internet access in the near future. In order to fulfill the expectations, these networks should provide high throughput simultaneously to many users. Recent research has indicated that, due to its conservative CSMA/CA channel access scheme and RTS/CTS mechanism, 802.11 is not suitable to achieve this goal.In this paper, we investigate throughput improvements achievable by replacing CSMA/CA with an STDMA scheme where transmissions are scheduled according to the physical interference model. To this end, we present a computationally efficient heuristic for computing a feasible schedule under the physical interference model and we prove, under uniform random node distribution, an approximation factor for the length of this schedule relative to the shortest schedule possible with physical interference. This represents the first known polynomial-time algorithm for this problem with a proven approximation factor.We also evaluate the throughput and execution time of this algorithm on representative wireless mesh network scenarios through packet-level simulations. The results show that throughput with STDMA and physical-interference-based scheduling can be up to three times higher than 802.11 for the parameter values simulated. The results also show that our scheduling algorithm can schedule networks with 2000 nodes in about 2.5 minutes.

Congestion is expected to become a prominent problem to deal with as the popularity of wireless data networks continues to increase. However, this problem can in principle be mitigated if a fraction of the network users could decide to move to another location in case their perceived QoS degrades. To account for this, we propose an extension of the well-known RWP model called QoS-RWP, in which users are divided into mobile users displaying constrained movement patterns, and QoS-driven users who are mainly stationary, but they can decide to move to a better location to improve their QoS level. Another enhancement of QoS-RWP with respect to the original RWP model is that waypoints are chosen according to an access point (AP) popularity metric, which reflects the recently observed phenomenon that different APs in a wireless data network display very different degrees of popularity among users. The QoS-RWP model also accounts for different classes of load offered to the network by the users, and for different channel access methods. Based on QoS-RWP, we perform a simulation-based analysis of network usage under different combinations of network parameters such as the number of users, number of APs, relative fraction of QoS-driven users, and channel access method. Our investigation discloses interesting insights on network usage, and shows that our model is able to capture important properties observed in real-world network deployments.

Improving the safety of drivers and passengers by wirelessly exchanging information between vehicles represents a major driving force for the design of vehicular ad hoc networks. In a heavy loaded 802.11-based network, however, safety-related packets might collide frequently and cannot be decoded by a receiver, thus they might not be effective in increasing the safety level on the roads. In this paper, we propose to use transmit power control in order to reduce packet collisions, while taking into account the major design goal of vehicular ad hoc networks, i.e. increasing safety. While previous work has addressed the issue of power control primarily for optimizing network capacity and/or connectivity, the optimization criterion for improving safety has to be built upon the concept of fairness: a higher transmit power of a sender should not be selected at the expense of preventing other vehicles to send/receive their required amount of safety information. In this paper, we propose a fully distributed and localized algorithm called D-FPAV (distributed fair power adjustment for vehicular networks) for adaptive transmit power adjustment which is formally proven to achieve max-min fairness. Furthermore, we investigate the effectiveness and robustness of D-FPAV through extensive simulations based on a realistic highway scenario and different radio propagation models

Topology control, wherein nodes adjust their transmission ranges to conserve energy and reduce interference, is an important feature in wireless ad hoc networks. Contrary to most of the literature on topology control which focuses on reducing energy consumption, in this paper we tackle the topology control problem with the goal of limiting interference as much as possible, while keeping the communication graph connected with high probability. Our approach is based on the principle of maintaining the number of physical neighbors of every node equal to or slightly below a specific value k. As we will discuss in this paper, having a nontrivially bounded physical node degree allows a network topology with bounded interference to be generated. The proposed approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability both theoretically and through simulation. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that uses distance estimation. k-Neigh guarantees logarithmically bounded physical degree at every node, is the most efficient known protocol (requiring 2n messages in total, where n is the number of nodes in the network), and relies on simpler assumptions than existing protocols. Furthermore, we verify through simulation that the network topologies produced by k-Neigh show good performance in terms of node energy consumption and expected interference.

In a previous paper P. Santi and D. Blough (see ibid., vol.2, no.1, p.25-39, Jan.-Mar. 2003) presented a number of results concerning the asymptotic connectivity of wireless ad hoc networks. This comment includes fixes to several of that paper's results.

In this paper we study the following problem: we are given a certain region R to monitor and a requirement on the degree of coverage (DoC) of R to meet by a network of deployed sensors. The latter will be dropped by a moving vehicle, which can release sensors at arbitrary points within R. The node spatial distribution when sensors are dropped at a certain points is modeled by a certain probability density function F. The network designer is allowed to choose an arbitrary set of drop points, and to release an arbitrary number of sensors at each point. Given this setting, we consider the problem of determining the optimal deployment strategy, i.e., the drop strategy such that the DoC requirement is fulfilled and the total number of deployed nodes n is minimum. We study this problem both analytically and through simulation, under the assumption that F is the two-dimensional Normal distribution of parameter s (sigma) centered at the drop point. We show that, for given value of s (sigma) and DoC requirement, optimal deployment strategies can be easly identified. The sensor dropping problem studied in this paper is relvant whenever manual node deployment is impossible or overly expensive, and partially controlled deployment (the network designer can choose the drop points, but the final node deployment is random) is the only feasible choice.

Topology Control (TC) is a well-studied technique used in wireless ad hoc networks to find energy-efficient and/or low-interference subgraphs of the maxpower communication graph. However, existing work has the following limitations: (1) the energy model adopted is quite unrealistic - only transmit power is often considered and homogeneous decay of the radio signal with distance is assumed; (2) the interference measure does not account for multi-hop communications. In this paper, we show the dramatic effect of the underlying energy and interference model on TC. In particular, we demonstrate that by using more realistic energy models and considering the effects of multi-hop interference, radically different conclusions about TC can be drawn; namely that (1) energy efficient TC is essentially meaningless, since every link turns out to be "efficient", and that (2) topologies identified as "interference-optimal" in the current literature can be extremely bad from the viewpoint of multi-hop interference. Given these observations, we propose a new measure of link interference, extend it to deal with multi-hop interference, and design a corresponding optimal communication subgraph, called ATASP. We prove that, in the worst case, ATASP coincides with the maxpower communication graph, showing that in some unfortunate situations also performing multi-hop interference-based TC is pointless. However, the simulation results with random node deployments presented in this paper show that, on the average, ATASP is a sparse subgraph of the maxpower communication graph, and multi-hop interference-based TC is indeed possible. Since computing ATASP requires global knowledge, we experiment through simulation with known localized algorithms for energy-efficient TC and show that they perform well (on the average) with respect to multi-hop interference.

In this paper, we have investigated the critical transmitting range for connectivity in mobile ad hoc networks. We have proven that, in the presence of bounded and obstacle free mobility, the CTR in the mobile case is at least as large as the CTR in the case of uniformly distributed points (asymptotically). For the case of RWP mobility, we have proven a more accurate characterization of the CTR and shown that, if the pause time is 0, there is an asymptotic gap between the mobile and uniform scenario. We have verified the quality of our results through simulation. We have also presented a formula that, given the value of the CTR in the uniform case, provides a good approximation of the CTR in the most extreme case of RWP mobility, i.e., when the pause time is set to 0. We want to remark that the approach presented in this paper can be easily extended to other mobility models: If the expression of the pdf f/sub m/ that resembles the long-term node distribution is known and satisfies certain properties, it is sufficient to compute the minimum value of f/sub m/ on R to determine the value of the critical range for connectivity. We believe that the results presented in this paper provide a better understanding of the behavior of a fundamental network parameter in the presence of mobility and, in particular, of RWP mobility. From a practical point of view, our results can be used to improve the accuracy of RWP mobile ad hoc networks simulation, which is commonly used to evaluate the performance of ad hoc networking protocols.

Clustering sensor nodes increases the scalability and energy efficiency of communications among them. In hostile environments, unexpected failures or attacks on cluster heads (through which communication takes place) may partition the network or degrade application performance. In this work, we propose a new approach, REED (Robust Energy Efficient Distributed clustering), for clustering sensors deployed in hostile environments. Our primary objective is to construct a k (i.e., k-connected) network, where k is a constant determined by the application. Fault tolerance can be achieved by selecting k independent sets of cluster heads (i.e., cluster head overlays) on top of the physical network, so that each node can quickly switch to other cluster heads in case of failures or attacks on its current cluster head. The independent cluster head overlays also provide multiple vertex-disjoint routing paths for load balancing and security. Network lifetime is prolonged by selecting cluster heads with high residual energy and low communication cost, and periodically reclustering the network in order to distribute energy consumption among sensor nodes. We prove that REED can asymptotically achieve k tolerance if certain constraints on node density are satisfied. We also investigate via simulations the clustering properties of REED, and show that building multiple cluster head overlays does not consume significant energy.

We use a vertex-isoperimetric inequality to show that the number of test and repair iterations needed to perform sequential diagnosis of d-dimensional hypercubes is upper bounded by d-r, where r/spl epsi//spl Theta/(d). This result improves the best bound of d test and repair iterations previously known. Numerical evaluation has shown that the actual value of r ranges from 0.16d to 0.31d.

We propose an approach to topology control based on the principle of maintaining the number of neighbors of every node equal to or slightly below a specific value k. The approach enforces symmetry on the resulting communication graph, thereby easing the operation of higher layer protocols. To evaluate the performance of our approach, we estimate the value of k that guarantees connectivity of the communication graph with high probability. We then define k-Neigh, a fully distributed, asynchronous, and localized protocol that follows the above approach and uses distance estimation. We prove that k-Neigh terminates at every node after a total of 2n messages have been exchanged (with n nodes in the network) and within strictly bounded time. Finally, we present simulations results which show that our approach is about 20% more energy-efficient than a widely-studied existing protocol.

Abstract: The random waypoint model is a frequently used mobility model for simulation–based studies of wireless ad hoc networks. This paper inves-tigates the spatial node distribution that results from using this model. We show and interpret simulation results on a square and circular system area, derive an analytical expression of the expected node distribution in one di-mension, and give an approximation for the two–dimensional case. Finally, the concept of attraction areas and a modified random waypoint model, the random borderpoint model, is analyzed by simulation. 1

We analyze the critical transmitting range for connectivity in wireless ad hoc networks. More specifically, we consider the following problem: assume n nodes, each capable of communicating with nodes within a radius of r, are randomly and uniformly distributed in a d-dimensional region with a side of length l; how large must the transmitting range r be to ensure that the resulting network is connected with high probability? First, we consider this problem for stationary networks, and we provide tight upper and lower bounds on the critical transmitting range for one-dimensional networks and nontight bounds for two and three-dimensional networks. Due to the presence of the geometric parameter l in the model, our results can be applied to dense as well as sparse ad hoc networks, contrary to existing theoretical results that apply only to dense networks. We also investigate several related questions through extensive simulations. First, we evaluate the relationship between the critical transmitting range and the minimum transmitting range that ensures formation of a connected component containing a large fraction (e.g., 90 percent) of the nodes. Then, we consider the mobile version of the problem, in which nodes are allowed to move during a time interval and the value of r ensuring connectedness for a given fraction of the interval must be determined. These results yield insight into how mobility affects connectivity and they also reveal useful trade offs between communication capability and energy consumption.

We consider the following problem for wireless ad hoc networks: assume n nodes, each capable of communicating with nodes within a radius of r, are distributed in a d-dimensional region of side l; how large must the transmitting range r be to ensure that the resulting network is connected? We also consider the mobile version of the problem, in which nodes are allowed to move during a time interval and the value of r ensuring connectedness for a given fraction of the interval must be determined. For the stationary case, we give tight bounds on the relative magnitude of r, n and l yielding a connected graph with high probability in l-dimensional networks, thus solving an open problem. The mobile version of the problem when d=2 is investigated through extensive simulations, which give insight on how mobility affects connectivity and reveal a useful trade-off between communication capability and energy consumption.

Cooperative cell-based strategies have been recently proposed as a technique for extending the lifetime of wireless ad hoc networks, while only slightly impacting network performance. The effectiveness of this approach depends heavily on the node density: the higher it is, the more consistent energy savings can potentially be achieved. However, no general analyses of network lifetime have been done either for a base network (one without any energy conservation technique) or for one using cooperative energy conservation strategies. In this paper, we investigate the lifetime/density tradeoff under the hypothesis that nodes are distributed uniformly at random in a given region, and that the traffic is evenly distributed across the network. We also analyze the case where the node density is just sufficient to ensure that the network is connected with high probability. This analysis, which is supported by the results of extensive simulations, shows that even in this low density scenario, cell-based strategies can significantly extend network lifetime.

In this paper, we analyze the node spatial distribution of mobile wireless ad hoc networks. Characterizing this distribution is of fundamental importance in the analysis of many relevant properties of mobile ad hoc networks, such as connectivity, average route length, and network capacity. In particular, we have investigated under what conditions the node spatial distribution resulting after a large number of mobility steps resembles the uniform distribution. This is motivated by the fact that the existing theoretical results concerning mobile ad hoc networks are based on this assumption.

The problem of identifying the faulty units in regularly interconnected systems is addressed. The diagnosis is based on mutual tests of units, which are adjacent in the "system graph" describing the interconnection structure. This paper evaluates an algorithm named EDARS (Efficient Diagnosis Algorithm for Regular Structures). The diagnosis provided by this algorithm is provably correct and almost complete with high probability. Diagnosis correctness is guaranteed if the cardinality of the actual fault set is below a "syndrome-dependent bound," asserted by the algorithm itself along with the diagnosis. Evaluation of EDARS relies upon extensive simulation which covered grids, hypercubes, and cube-connected cycles (CCC). Simulation experiments showed that the degree of the system graph has a strong impact over diagnosis completeness and affects the "syndrome-dependent bound," ensuring correctness. Furthermore, a comparative analysis of the performance of EDARS, with hypercubes and CCCs on one side and grids of the same size and degree on the other side, showed that diameter and bisection width of the system graph also influence the diagnosis correctness and completeness.

In this paper we consider the following problem for ad hoc networks: assume that n nodes are distributed in a d-dimensional region, with 1≤d≤3, and assume that all the nodes have the same transmitting range r; how large must r be to ensure that the resulting network is strongly connected? We study this problem by means of a probabilistic approach, and we establish lower and upper bounds on the probability of connectedness. For the one-dimensional case, these bounds allow us to determine a suitable magnitude of r for a given number of nodes and displacement region size. In an alternate formulation, the bounds allow us to calculate how many nodes must be distributed should the transmitting range be fixed. Finally, we investigate the required magnitude of r in the two- and three-dimensional cases through simulation. Based on the bounds provided and on the simulation analysis, we conclude that, as compared to the deterministic case, a probabilistic solution to this range assignment problem achieves substantial energy savings. A number of other potential uses for our analyses are discussed as well

The problem of identifying faulty mobiles in ad-hoc networks is considered. Current diagnostic models were designed for wired networks, thus they do not take advantage of the shared nature of communication typical of ad-hoc networks. In this paper we introduce a new comparison-based diagnostic model based on the one-to-many communication paradigm. Two implementations of the model are presented. In the first implementation, we assume that the network topology does not change during diagnosis, and we show that both hard and soft faults can be easily, detected Based on this implementation, a diagnosis protocol is presented The evaluation of the communication and time complexity of the protocol indicates that efficient diagnosis protocols for ad-hoc networks based on our model can be designed In the second implementation we allow the system topology to change during diagnosis. As expected, the ability of diagnosing faults under this scenario is significantly reduced with respect to the stationary case.

The problem of multiple faults diagnosis in safety-critical systems is considered. Error propagation between system components is modeled as a directed graph, where the errors propagate instantaneously along the edges. Some of the system components are equipped with alarms, which ring when abnormal conditions are detected. A diagnosis algorithm identifies the set of potential failure sources based on the set of ringing alarms. The paper introduces the D-FAULTS algorithm, which diagnoses the system when at most two nodes can be failure sources at any time. The concept of sequential diagnosis is also introduced, to deal with an unknown number of faults. Sequential diagnosis is aimed at locating the smallest set of nodes containing at least one fault. Using this approach, a faulty system can be restored to normal condition by executing repeatedly the diagnosis and repair phases. To this purpose, we introduce the sequential diagnosis algorithm S-DIAG with optimal time complexity.

Introduces EDARS (Efficient Diagnosis Algorithm for Regular Structures). The algorithm provides a diagnosis which is correct, but possibly incomplete, if the cardinality of the actual fault set is below a "syndrome-dependent bound" asserted by the algorithm itself. The time complexity of EDARS is O(nt) when executed on t-regular structures of size n. The correctness and the completeness degree of EDARS were evaluated by means of simulation. Grids, hypercubes and cube-connected cycle (CCC) structures were considered. Simulation results with grid structures showed a strong influence of structure degree over diagnosis performance. Furthermore, comparisons of simulation results obtained with hypercubes, CCCs and grids of the same size and degree showed that diameter and bisection width also appear to influence the performance of EDARS, particularly with respect to diagnosis completeness.

A novel approach to the diagnosis of hypercubes, called self-validating diagnosis (SVD), is introduced. An algorithm bared on this approach, called the SVD algorithm, is presented and evaluated. Given any fault set and the resulting syndrome, the algorithm returns a diagnosis and a syndrome-dependent bound, T/sub /spl sigma//, with the property that the diagnosis is correct (although possibly incomplete) if the actual number of faulty units is less than T/sub /spl sigma//. The average of T/sub /spl sigma// is very large and the diagnosis is almost complete even when the percentage of faulty units in the system approaches 50%. Moreover, the diagnosis correctness can be validated deterministically by individually probing a very small number of units. These results suggest that the SVD algorithm is suitable for applications requiring a large degree of diagnosability, as is the case for wafer-scale testing of VLSI chips, where the percentage of faulty units may be as large us 50%.

This paper introduces a diagnosing algorithm for bidimensional processor arrays, where processors are interconnected in horizontal and vertical meshes. For the purpose of diagnosis, the array is considered to be partitioned in square clusters of processors. The algorithm is based on interprocessor tests, using a comparison model. The algorithm, which is divided in four steps, called intracluster diagnosis, interluster diagnosis, fault-free core identification and augmentation, identifies a set of non-faulty and a set of faulty units. The diagnosis is proved to be correct in the worst case, assuming that the actual number of faulty processors is no more that T(N), an increasing function of the number N of processors. It is shown that T(N) is O(N/sup 2/3/). Although correct, the diagnosis is generally incomplete. However, using probabilistic techniques, it is shown that the diagnosis is very likely to be complete under the same limitations which ensure correctness in the worst case.