Search

Shared mobility is widely recognized for its contribution in reducing carbon footprint, traffic congestion, parking needs and transportation-related costs in urban and suburban areas. In this context, the use of carpooling in home-work commute is particularly appealing for its potential of lessening the number of cars and kilometers traveled, consequently reducing major causes of traffic in cities. Accord- ingly, most of the carpooling algorithms are optimized for reducing total travel time, cost, and other transportation-related metrics. In this paper, we analyze carpooling from a new perspective, investigating the question of whether it can be used also as a tool to favor social integration, and to what extent social benefits should be traded off with transportation efficiency. By incorporating traveler's social character- istics into a recently introduced network-based approach to model ride-sharing opportunities, we define two social-related carpooling problems: how to maximize the number of rides shared between people belonging to different social groups, and how to maximize the amount of time people spend together along the ride. For each of the problems, we provide corresponding optimal and computationally effi- cient solutions. We then demonstrate our approach on two datasets collected in the city of Pisa, Italy, and Cambridge, US, and quantify the potential social benefits of carpooling, and how they can be traded off with traditional transportation-related metrics. When collectively considered, the models, algorithms, and results presented in this paper broaden the perspective from which carpooling problems are typically analyzed to encompass multiple disciplines including urban planning, public policy, and social sciences.

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 novel locality 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 (~10^6) performed in two different urban areas, namely Manhattan (NYC) and Singapore. Our experiments show that our approach achieves a 5x speed-up, or even more during so-called ``rush times'', and it is robust under different traffic conditions.

Information and communication technologies have opened the way to new solutions for urban mobility that provide better ways to match individuals with on-demand vehicles. However, a fundamental unsolved problem is how best to size and operate a fleet of vehicles, given a certain demand for personal mobility. Previous studies(1-5) either do not provide a scalable solution or require changes in human attitudes towards mobility. Here we provide a network-based solution to the following 'minimum fleet problem', given a collection of trips (specified by origin, destination and start time), of how to determine the minimum number of vehicles needed to serve all the trips without incurring any delay to the passengers. By introducing the notion of a 'vehicle-sharing network', we present an optimal computationally efficient solution to the problem, as well as a nearly optimal solution amenable to real-time implementation. We test both solutions on a dataset of 150 million taxi trips taken in the city of New York over one year(6). The real-time implementation of the method with near-optimal service levels allows a 30 per cent reduction in fleet size compared to current taxi operation. Although constraints on driver availability and the existence of abnormal trip demands may lead to a relatively larger optimal value for the fleet size than that predicted here, the fleet size remains robust for a wide range of variations in historical trip demand. These predicted reductions in fleet size follow directly from a reorganization of taxi dispatching that could be implemented with a simple urban app; they do not assume ride sharing(7-9), nor require changes to regulations, business models, or human attitudes towards mobility to become effective. Our results could become even more relevant in the years ahead as fleets of networked, self-driving cars become commonplace(10-14).

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.

Taxi services are a vital part of urban transportation, and a considerable contributor to traffic congestion and air pollution causing substantial adverse effects on human health. Sharing taxi trips is a possible way of reducing the negative impact of taxi services on cities, but this comes at the expense of passenger discomfort quantifiable in terms of a longer travel time. Due to computational challenges, taxi sharing has traditionally been approached on small scales, such as within airport perimeters, or with dynamical ad-hoc heuristics. However, a mathematical framework for the systematic understanding of the tradeoff between collective benefits of sharing and individual passenger discomfort is lacking. Here we introduce the notion of shareability network which allows us to model the collective benefits of sharing as a function of passenger inconvenience, and to efficiently compute optimal sharing strategies on massive datasets. We apply this framework to a dataset of millions of taxi trips taken in New York City, showing that with increasing but still relatively low passenger discomfort, cumulative trip length can be cut by 40% or more. This benefit comes with reductions in service cost, emissions, and with split fares, hinting towards a wide passenger acceptance of such a shared service. Simulation of a realistic online system demonstrates the feasibility of a shareable taxi service in New York City. Shareability as a function of trip density saturates fast, suggesting effectiveness of the taxi sharing system also in cities with much sparser taxi fleets or when willingness to share is low., Main text: 6 pages, 3 figures, SI: 24 pages

Sharing rides could drastically improve the efficiency of car and taxi transportation. Unleashing such potential, however, requires understanding how urban parameters affect the fraction of individual trips that can be shared, a quantity that we call shareability. Using data on millions of taxi trips in New York City, San Francisco, Singapore, and Vienna, we compute the shareability curves for each city, and find that a natural rescaling collapses them onto a single, universal curve. We explain this scaling law theoretically with a simple model that predicts the potential for ride sharing in any city, using a few basic urban quantities and no adjustable parameters. Accurate extrapolations of this type will help planners, transportation companies, and society at large to shape a sustainable path for urban growth., National Science Foundation (U.S.) (DMS-1513179), National Science Foundation (U.S.) (CCF-1522054)

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: (i) a node is always better off participating in the protocol execution (individual rationality), (ii) a node is always better off behaving according to the protocol specification (truthfulness), (iii) messages are routed along the most energy-efficient (least cost) path, and (iv) 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 to reduce its message complexity. On the other hand, our investigation of the routing problem in presence of selfish nodes disclosed a new metric under which topology control protocols can be evaluated: the cost of cooperation.

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

The random waypoint model is a commonly used mobility model in the simulation of ad hoc networks. It is known that the spatial distribution of network nodes moving according to this model is, in general, nonuniform. However, a closed-form expression of this distribution and an in-depth investigation is still missing. This fact impairs the accuracy of the current simulation methodology of ad hoc networks and makes it impossible to relate simulation-based performance results to corresponding analytical results. To overcome these problems, we present a detailed analytical study of the spatial node distribution generated by random waypoint mobility. More specifically, we consider a generalization of the model in which the pause time of the mobile nodes is chosen arbitrarily in each waypoint and a fraction of nodes may remain static for the entire simulation time. We show that the structure of the resulting distribution is the weighted sum of three independent components: the static, pause, and mobility component. This division enables us to understand how the model's parameters influence the distribution. We derive an exact equation of the asymptotically stationary distribution for movement on a line segment and an accurate approximation for a square area. The good quality of this approximation is validated through simulations using various settings of the mobility parameters. In summary, this article gives a fundamental understanding of the behavior of the random waypoint model.

This paper describes nagging, a technique for parallelizing search in a heterogeneous distributed computing environment. Nagging exploits the speedup anomaly often observed when parallelizing problems by playing multiple reformulations of the problem or portions of the problem against each other. Nagging is both fault tolerant and robust to long message latencies. In this paper, we show how nagging can be used to parallelize several different algorithms drawn from the artificial intelligence literature, and describe how nagging can be combined with partitioning, the more traditional search parallelization strategy. We present a theoretical analysis of the advantage of nagging with respect to partitioning, and give empirical results obtained on a cluster of 64 processors that demonstrate nagging's effectiveness and scalability as applied to A∗ search, αβ minimax game tree search, and the Davis–Putnam algorithm.

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 inter-contact 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 inter-contact 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. 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 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 inter\-ference-aware STDMA time-based proportional fairness ($i$-STPF), and compare it to ordinary STDMA time-based proportional fairness (STPF). We present the $\epsilon i$-STPF scheduling algorithm, and prove that it approximates the time-based fair bandwidth allocation (up to a small positive constant $\epsilon$), 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 achieves excellent aggregate throughput while maintaining a close approximation to time-based fairness without interference.

International audience; 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.

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 measurementbased 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.

In this paper, we investigate the fundamental properties of broadcasting in {em 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 {sc 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 {sc 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 $Theta((log n)^{1+frac{2}{alpha}})$ factor from optimal, where $n$ is the number of mobile nodes and $alpha>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.

In this paper, we present a framework for analyzing routing performance in delay tolerant networks. Differently from previous work, our framework is aimed at characterizing the exact {\em 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 {\em packet delivery delay}, and {\em 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, spray and wait, etc. 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. \noindent 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, non-cooperative, and probabilistic cooperative scenarios, and derive nearly exact expressions of the packet delivery rate 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.

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.

One way in which wireless nodes can organize themselves into an ad hoc network is to execute a topology control protocol, which is designed to build a network satisfying specific properties. A number of basic topology control protocols exist and have been extensively analyzed. Unfortunately, most of these protocols are designed primarily for static networks and the protocol designers simply advise that the protocols should be repeated periodically to deal with failures, mobility, and other sources of dynamism. However, continuously maintaining a network topology with basic connectivity properties is a fundamental requirement for overall network dependability. Current approaches consider failures only as an afterthought or take a static fault tolerance approach, which results in extremely high energy usage and low throughput. In addition, most of the existing topology control protocols assume that transmission power is a continuous variable and, therefore, nodes can choose an arbitrary power value between some minimum and maximum powers. However, wireless network interfaces with dynamic transmission power control permit the power to be set to one of a discrete number of possible values. This simple restriction complicates the design of the topology control protocol substantially. In this paper, we present a set of topology control protocols, which work with discrete power levels and for which we specify a version that deals specifically with dynamic networks that experience failures, mobility, and other dynamic conditions. Our protocols are also novel in the sense that they are the first to consider explicit coordination between neighboring nodes, which results in more efficient power settings. In this paper, we present the design of these topology control protocols, and we report on extensive simulations to evaluate them and compare their performance against existing protocols. The results demonstrate that our protocols produce very similar topologies as the best protocols that assume power is a continuous variable, while having very low communication cost and seamlessly handling failures and mobility.

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 de- pends on the signa-to-interference-plus-noise ratio (SINR). While most previous work on wireless networks has addressed the sched- uling problem using simplistic graph-based or distance-based interference models, a few recent papers have investigated sched- uling 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 following problem: we are given a certain one- or two-dimensional 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 point 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 best performing strategy among a certain set of grid-like strategies that reflect the (one- or two-dimensional) symmetry of the region to be monitored. The best performing deployment strategy is such that: (1) the DoC requirement is fulfilled and (2) 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 centered at the drop point. The main contribution of this paper is an in-depth study of the inter-relationships between environmental conditions, DoC requirement, and cost of the deployment.

In this talk, 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, called RippleCast, that simultaneously achieves asymptotically optimal broadcast capacity and latency, subject to a weak upper bound on the maximum node velocity. 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 $Theta((log n)^{1+frac{2}{alpha}})$ factor from optimal, where $n$ is the number of mobile nodes and $alpha>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. To the best of our knowledge, our is the first paper investigating the effects of node mobility on the fundamental properties of broadcasting, and showing that, while optimal broadcasting in a mobile network is in principle possible, the coordination efforts related to the selection of broadcast relay nodes lead to sub-optimal broadcasting performance.

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.

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 of the 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.

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.

We study the problem of building and maintaining a network topology with certain desirable features in a wireless multi-hop network where nodes behave as selfish agents. We first provide examples showing that existing topology control approaches are not resilient to strategic node behavior, indicating the need to consider possible selfish node behavior at the design stage. To this end, we propose a general framework that can be used as a guideline in the design of incentive compatible topology control protocols. As an example of how to apply our framework to specific topology control protocols, we present an incentive compatible distributed algorithm for building the minimum spanning tree (MST), which is a very well-known topology control approach. We test the economic validity of our protocol through simulation of wireless networks under various advanced signal loss models on the physical layer. To the best of our knowledge, this is the first incentive compatible realization of topology control presented in the literature.

It is known that finding a Nash equilibrium for win-lose bimatrix games, i.e., two-player games where the players' payoffs are zero and one, is complete for the class PPAD. We describe a linear time algorithm which computes a Nash equilibrium for win-lose bimatrix games where the number of winning positions per strategy of each of the players is at most two. The algorithm acts on the directed graph that represents the zero-one pattern of the payoff matrices describing the game. It is based upon the efficient detection of certain subgraphs which enable us to determine the support of a Nash equilibrium.

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: (i) a node is always better off participating in the protocol execution (individual rationality), (ii) a node is always better off behaving according to the protocol specification (truthfulness), (iii) messages are routed along the most energy-efficient path, and (iv) 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 to reduce its message complexity. On the other hand, our investigation of the routing problem in presence of selfish nodes disclosed a new metric under which topology control protocols can be evaluated: the cost of cooperation.

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.

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 as sumption. In order to test this hypothesis, we performed extensive simulations using two well-known mobility models: the random waypoint model, which resembles intentional movement, and a Brownian-like model, which resembles non-intentional movement. Our analysis has shown that in the Brownian-like motion the uniformity assumption does hold,and that the intensity of the concentration of nodes in the center of the deployment region that occurs in the ran dom waypoint model heavily depends on the choice of some mobility parameters. For extreme values of these parameters,the uniformity assumption is impaired.

In this paper we consider a constrained version of the range assignment problem for wireless ad hoc networks, where the value the node transmitting ranges must be assigned in such a way that the resulting communication graph is strongly connected and the energy cost is minimum. We impose the further requirement of symmetry on the resulting communication graph. We also consider a weaker notion of symmetry, in which only the existence of a set of symmetric edges that renders the communication graph connected is required. Our interest in these problems is motivated by the fact that a (weakly) symmetric range assignment can be more easily integrated with existing higher and lower-level protocols for ad hoc networks, which assume that all the nodes have the same transmitting range. We show that imposing symmetry does not change the complexity of the problem, which remains NP-hard in two and three-dimensional networks. We also show that a weakly symmetric range assignment can reduce the energy cost considerably with respect to the homogeneous case, in which all the nodes have the same transmitting range, and that no further (asymptotic) benefit is expected from the asymmetric range assignment. Hence, the results presented in this paper indicate that weak symmetry is a desirable property of the range assignment.

The application of a discontinuous finite element method to the solution of the full Navier-Stokes equations, implemented in a code called MIGALE, has been validated by the execution of a series of well known benchmark tests for compressible subsonic, transonic, and supersonic flows in 2D geometries. The method combines some favorable properties of the finite volume and the finite element methods. It appears to be a potentially good candidate for the implementation on parallel computing machines. In fact, a discontinuous approximation of the unknowns implies a limited exchange of information among elements. It has been verified during the migration of MIGALE on a CRAY T3D computer that all elements that share a node—whose number may be strongly variable—have to exchange information. The result also shows that only those discontinuous elements that share a side (in 2D) or a face (in 3D) do communicate. Their number only depends on the nature of the element employed, which is usually small. Selection of methods, implementation of the same, and results infer that the program Split, developed essentially for testing purposes, can be easily integrated or substituted by more sophisticated tools. Even if the domain partition provided by Split is probably far from optimal, nevertheless the parallel program enjoys good scalability properties

This paper analyzes the cost of performing broadcast, product and prefix computation on the ideal fat-tree, a model proposed here to capture distance and bandwidth properties common to a variety of fat-tree networks. Algorithms are developed and analyzed in terms of the capacity of channels at different levels of the fat-tree. Non trivial lower bounds are derived establishing the optimality of our algorithms for a wide range of channel capacities.

In this paper we introduce two different techniques, clustering and perturbation, which use global information on TSP instances to speed-up and improve the quality of the tours found by heuristic methods. This global information is related to two correspondent features of any instance, namely distribution and sensitivity. The performance of our techniques has been tested and compared with known methods. To this end, we performed a number of experiments both on test instances, for which the optimal tour length is known, and on uniformly distributed instances, for which the comparison is done with the Held-Karp lower bound. The experimental results show that our techniques are competitive with the most efficient known methods. It turns out that the viewpoint used in this paper is very satisfactory and deserves further examination.

Given a n×n nonsingular linear system Ax=b, we prove that the solution x can be computed in parallel time ranging from Ω(log n) to O(log2n), provided that the condition number, μ(A), of A is bounded by a polynomial in n. In particular, if μ(A) =O(1), a time bound O(log n) is achieved. To obtain this result, we reduce the computation of x to repeated matrix squaring and prove that a number of steps independent of n is sufficient to approximate x up to a relative error 2−d, d=O(1). This algorithm has both theoretical and practical interest, achieving the same bound of previously published parallel solvers, but being far more simple.

We present an algorithm based on a method belonging to the class of Abaffy-Broyden-Spedicato [3]. The linear system to be solved can be sparse and in this situation must have a row-polychromatic structure.

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.