The pervasive deployment of Internet of Things (IoT) devices is considered a fundamental brick in the transition towards the Smart City. Small, interconnected, battery-less transceivers, capable of harvesting energy from Radio Frequency (RF) communications are envisioned as a green solution to realize this transition. In this paper, we investigate the possibility of setting up an urban monitoring application through battery-less IoT sensors deployed alongside a road and capable of scavenging energy from mobile wireless sources like traveling vehicles. The proposed Energy Harvesting (EH) model has been derived from experimental measurements, and combined with a vehicular traffic simulator in order to obtain a realistic input power pattern, which takes into account the variable speed and the trajectory of the vehicles. On top of this, a low-energy wireless communication protocol, inspired by the Long Range (LoRa) stack, has been developed, which prescribes periodic data transmission to a remote Access Point (AP). Extensive simulations have been carried out to highlight the impact of several parameters, including storage capacity, load current, data rate, packet size, RF sources intensity and mobility, on the overall system throughput. The obtained results confirm the feasibility of the approach; furthermore, they show that while the peculiar nature of the energy source would make it advantageous to send small packets at higher pace, the opposite strategy (larger packets at lower pace) becomes preferable when the overhead cost is taken into account.

In this paper, we investigate the potential of exploiting Free Space Optical (FSO) transmissions over short links to relay data from vehicular communications to a dedicated Access Point (AP). In the envisioned scenario, a small device capable of Energy Harvesting ($\mathbf{E H}$) from radio frequency signals is placed alongside the road. Using the Simultaneous Wireless Information and Power Transfer (SWIPT) principle, the device obtains both data and energy from passing vehicles. The scavenged energy is then used to power a small optical transmitter and relay the received data to the AP. We address the problem of finding the optimal fraction of incoming energy to be reserved for $\mathbf{E H}$, taking into account the stochastic losses over the optical link. A theoretical expression is derived, and a suitable approximation for some parameters setup is shown. The results, obtained through extensive Monte Carlo simulations, confirm the validity of the analysis, and show how the optimal harvesting range depends on the vehicular traffic characteristics as well as on the implemented schemes for transmissions collision avoidance.

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.

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.

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.

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.

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.

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

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.

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.

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.

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.

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.

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.

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

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

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.

In this paper we introduce a technique for developing efficient iterated local search procedures and we apply it to solve very large instances of the Euclidean Traveling Salesman Problem (TSP). This technique, which we call perturbation, uses global information on TSP instances to speed-up the computation and to improve the quality of the tours found by heuristic methods. The main idea is to escape from local optima by introducing perturbations in the problem instance rather than in the solution. The performance of our algorithms has been tested and compared with known methods. To this end, we have executed a number of experiments both on available benchmarks, for which the optimal tour length is known, and on randomly generated instances, for which the comparison is done with the Held-Karp lower bound. The experimental results, performed on up to 100,000 cities, show that our algorithms outperform the known methods for iterating local search for very large instances.