Flow-level performance and capacity of wireless networks with user mobility

The performance evaluation of wireless networks is severely complicated by the specific features of radio communication, such as highly variable channel conditions, interference issues, and possible hand-offs among base stations. The latter elements have no natural counterparts in wireline scenarios, and create a need for novel performance models that account for the impact of these characteristics on the service rates of users. Motivated by the above issues, we review several models for characterizing the capacity and evaluating the flow-level performance of wireless networks carrying elastic data transfers. We first examine the flow-level performance and stability of a wide family of so-called α-fair channel-aware scheduling strategies. We establish that these disciplines provide maximum stability, and describe how the special case of the Proportional Fair policy gives rise to a Processor-Sharing model with a state-dependent service rate. Next we turn attention to a network of several base stations with inter-cell interference. We derive both necessary and sufficient stability conditions and construct lower and upper bounds for the flow-level performance measures. Lastly we investigate the impact of user mobility that occurs on a slow timescale and causes possible hand-offs of active sessions. We show that the mobility tends to increase the capacity region, both in the case of globally optimal scheduling and local α-fair scheduling. It is additionally demonstrated that the capacity and user throughput improve with lower values of the fairness index α.     

A station strategy to deter backoff attacks in IEEE 802.11 LANs

The IEEE 802.11 MAC protocol now prevailing in wireless LANs is vulnerable to selfish backoff attacks consisting in selection of short backoff times in the constituent CSMA/CA procedure. Administrative prevention of such attacks fails in ad hoc configurations, where stations' behavior cannot be mandated. In this paper we take an incentive-oriented game-theoretic approach whereby stations are allowed to maximize their payoffs (achieved success rates). Using a fairly accurate performance model we show that a noncooperative CSMA/CA game then arises with a payoff structure characteristic of a Prisoners' Dilemma. For a repeated CSMA/CA game, a novel SPELL strategy is proposed and shown to yield to simple algorithmic design. Assuming that the stations are rational players and wish to maximize a mean-value-type long-term utility, SPELL is further shown to deter a single attacker by providing a disincentive to deviate from SPELL.     

Planning wireless networks by shortest path

Transmitters and receivers are the basic elements of wireless networks and are characterized by a number of radio-electrical parameters. The generic planning problem consists of establishing suitable values for these parameters so as to optimize some network performance indicator. The version here addressed, namely the Power Assignment Problem (pap), is the problem of assigning transmission powers to the transmitters of a wireless network so as to maximize the satisfied demand. This problem has relevant practical applications both in radio-broadcasting and in mobile telephony. Typical solution approaches make use of mixed integer linear programs with huge coefficients in the constraint matrix yielding numerical inaccuracy and poor bounds, and so cannot be exploited to solve large instances of practical interest. In order to overcome these inconveniences, we developed a two-phase heuristic to solve large instances of pap, namely a constructive heuristic followed by an improving local search. Both phases are based on successive shortest path computations on suitable directed graphs. Computational tests on a number of instances arising in the design of the national Italian Digital Video Broadcasting (DVB) network are presented.     

Performance of CSMA in multi-channel wireless networks

We analyze the performance of CSMA in multi-channel wireless networks, accounting for the random nature of traffic. Specifically, we assess the ability of CSMA to fully utilize the radio resources and in turn to stabilize the network in a dynamic setting with flow arrivals and departures. We prove that CSMA is optimal in the ad-hoc mode, when each flow goes through a unique dedicated wireless link from a transmitter to a receiver. It is generally suboptimal in infrastructure mode, when all data flows originate from or are destined to the same set of access points, due to the inherent bias of CSMA against downlink traffic. We propose a slight modification of CSMA that we refer to as flow-aware CSMA, which corrects this bias and makes the algorithm optimal in all cases. The analysis is based on some time-scale separation assumption which is proved valid in the limit of large flow sizes.     

Minimum power multicasting problem in wireless networks

In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.     

Optimization of the capacity of wireless mesh networks

This is a summary of the authors PhD thesis supervised by Hervé Rivano and defended on 29 October 2009 at the Université de Nice-Sophia Antipolis. The thesis is written in French and is available from . This work deals with the optimization of the capacity of wireless mesh networks, defined as the throughput offered to each flow. We develop optimization models integrating the cross-layer characteristics of radio communications. The joint routing and scheduling is studied and solved using column generation. A linear formulation focusing on the transport capacity available on the network cuts is derived. We prove the equivalence of the models, and adapt the resolution method into a cross line and column generation process. Thorough tests, a contention area located around the gateways which constraints the capacity is highlighted. These results are applied to a quantitative study of the effects of acknowledgments on the capacity. Finally, a stability study of a protocol routing a traffic injected arbitrarily is investigated.     

Maximizing system lifetime in wireless sensor networks

One of the most critical issues in wireless sensor networks is represented by the limited availability of energy on network nodes; thus, making good use of energy is necessary to increase network lifetime. In this paper, we define network lifetime as the time spanning from the instant when the network starts functioning properly, i.e., satisfying the target level of coverage of the area of interest, until the same level of coverage cannot be guaranteed any more due to lack of energy in sensors. To maximize system lifetime, we propose to exploit sensor spatial redundancy by defining subsets of sensors active in different time periods, to allow sensors to save energy when inactive. Two approaches are presented to maximize network lifetime: the first one, based on column generation, must run in a centralized way, whereas the second one is based on a heuristic algorithm aiming at a distributed implementation. To assess their performance and provide guidance to network design, the two approaches are compared by varying several network parameters. The column generation based approach typically yields better solutions, but it may be difficult to implement in practice. Nevertheless it provides both a good benchmark against which heuristics may be compared and a modeling framework which can be extended to deal with additional features, such as reliability.     

Modeling environmental effects on directionality in wireless networks

One method for improving wireless network throughput involves using directional antennas to increase signal gain and/or decrease interference. The physical layer models used in current networking simulators only minimally address the interaction of directional antennas and radio propagation. This paper compares the models found in popular simulation tools with measurements taken across a variety of links in multiple environments. We find that the effects of antenna direction are significantly different from those predicted by the models used in the common wireless network simulators. We propose a parametric model that better captures the effects of different propagation environments on directional antenna systems; we also show that the derived models are sensitive to both the direction of signal gain and the environment in which the antenna is used.     

Connectivity guarantees for wireless networks with directional antennas

We study a combinatorial geometric problem related to the design of wireless networks with directional antennas. Specifically, we are interested in necessary and sufficient conditions on such antennas that enable one to build a connected communication network, and in efficient algorithms for building such networks when possible.We formulate the problem by a set P of n points in the plane, indicating the positions of n transceivers. Each point is equipped with an α-degree directional antenna, and one needs to adjust the antennas (represented as wedges), by specifying their directions, so that the resulting (undirected) communication graph G is connected. (Two points p,q∈P are connected by an edge in G, if and only if q lies in p?s wedge and p lies in q?s wedge.) We prove that if α=60°, then it is always possible to adjust the wedges so that G is connected, and that α?60° is sometimes necessary to achieve this. Our proof is constructive and yields an time algorithm for adjusting the wedges, where k is the size of the convex hull of P.Sometimes it is desirable that the communication graph G contain a Hamiltonian path. By a result of Fekete and Woeginger (1997) [8], if α=90°, then it is always possible to adjust the wedges so that G contains a Hamiltonian path. We give an alternative proof to this, which is interesting, since it produces paths of a different nature than those produced by the construction of Fekete and Woeginger. We also show that for any n and ε>0, there exist sets of points such that G cannot contain a Hamiltonian path if α=90°−ε.     

Fast broadcasting and gossiping in radio networks

We establish an O(nlog²n) upper bound on the time for deterministic distributed broadcasting in multi-hop radio networks with unknown topology. This nearly matches the known lower bound of Ω(nlogn). The fastest previously known algorithm for this problem works in time O(n^3/2). Using our broadcasting algorithm, we develop an O(n^3/2log²n) algorithm for gossiping in the same network model.     

Fast paths in large-scale dynamic road networks

Efficiently computing fast paths in large-scale dynamic road networks (where dynamic traffic information is known over a part of the network) is a practical problem faced by traffic information service providers who wish to offer a realistic fast path computation to GPS terminal enabled vehicles. The heuristic solution method we propose is based on a highway hierarchy-based shortest path algorithm for static large-scale networks; we maintain a static highway hierarchy and perform each query on the dynamically evaluated network, using a simple algorithm to propagate available dynamic traffic information over a larger part of the road network. We provide computational results that show the efficacy of our approach.     

Bounded-hops power assignment in ad hoc wireless networks

Motivated by topology control in ad hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). The input consists of a directed complete weighted digraph G=(V,c) (that is, ). The power of a vertex u in a directed spanning subgraph H is given by , and corresponds to the energy consumption required for node u to transmit to all nodes v with uv∈E(H). The power of H is given by . Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r∈V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) and power at most O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥^κ (here ∥u,v∥ is the Euclidean distance and κ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)^κ) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u,v)=c(v,u)=∥u,v∥^κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case.     

Controlled mobility in stochastic and dynamic wireless networks

We consider the use of controlled mobility in wireless networks where messages arriving randomly in time and space are collected by mobile receivers (collectors). The collectors are responsible for receiving these messages via wireless transmission by dynamically adjusting their position in the network. Our goal is to utilize a combination of wireless transmission and controlled mobility to improve the throughput and delay performance in such networks. First, we consider a system with a single collector. We show that the necessary and sufficient stability condition for such a system is given by ρ<1 where ρ is the expected system load. We derive lower bounds for the expected message waiting time in the system and develop policies that are stable for all loads ρ<1 and have asymptotically optimal delay scaling. We show that the combination of mobility and wireless transmission results in a delay scaling of $\varTheta(\frac{1}{1-\rho})$ with the system load ρ, in contrast to the $\varTheta(\frac{1}{(1-\rho)^{2}})$ delay scaling in the corresponding system without wireless transmission, where the collector visits each message location. Next, we consider the system with multiple collectors. In the case where simultaneous transmissions to different collectors do not interfere with each other, we show that both the stability condition and the delay scaling extend from the single collector case. In the case where simultaneous transmissions to different collectors interfere with each other, we characterize the stability region of the system and show that a frame-based version of the well-known Max-Weight policy stabilizes the system asymptotically in the frame length.     

Automated antenna positioning algorithms for wireless fixed-access networks

This article addresses a real-life problem - obtaining communication links between multiple base station sites, by positioning a minimal set of fixed-access relay antenna sites on a given terrain. Reducing the number of relay antenna sites is considered critical due to substantial installation and maintenance costs. Despite the significant cost saved by eliminating even a single antenna site, an inefficient manual approach is employed due to the computational complexity of the problem. From the theoretical point of view we show that this problem is not only NP hard, but also does not have a constant approximation. In this paper we suggest several alternative automated heuristics, relying on terrain preprocessing to find educated potential points for positioning relay stations. A large-scale computer-based experiment consisting of approximately 7,000 different scenarios was conducted. The quality of alternative solutions was compared by isolating and displaying factors that were found to affect the standard deviation of the solutions supplied by the tested heuristics. The results of the simulation based experiments show that the saving potential increases when more base stations are needed to be interconnected. The designs of a human expert were compared to the automatically generated solutions for a small subset of the experiment scenarios. Our studies indicate that for small networks (e.g., connecting up to ten base stations), the results obtained by human experts are adequate although they rarely exceed the quality of automated alternatives. However, the process of obtaining these results in comparison to automated heuristics is longer. In addition, when more base station sites need to be interconnected, the human approach is easily outperformed by our heuristics, both in terms of better results (fewer antennas) and in significant shorter calculation times.     

Layouts for mobility management in wireless ATM networks

In this paper, we present a new model that combines quality of service and mobility aspects in wireless ATM networks. Namely, besides the hop count and load parameters of the basic ATM layouts, we introduce a new notion of distance that estimates the time needed to reconstruct the virtual channel of a wireless user when he moves through the network. Quality of service guarantee dictates that the rerouting phase must be imperceptible, that is, the maximum distance between two virtual channels must be maintained as low as possible. Therefore, a natural combinatorial problem arises in which suitable trade-offs must be determined between the different performance measures. We first show that establishing the existence of a layout with maximum hop count h, load l and distance d is NP-complete, even in the very restricted case h=2, l=1 and d=1. We then provide optimal layout constructions for basic interconnection networks, such as chains and rings.     

On approximation of dominating tree in wireless sensor networks

We study the following problem: Given a weighted graph G = (V, E, w) with \({w: E \rightarrow \mathbb{Z}^+}\) , the dominating tree (DT) problem asks us to find a minimum total edge weight tree T such that for every \({v \in V}\) , v is either in T or adjacent to a vertex in T. To the best of our knowledge, this problem has not been addressed in the literature. Solving the DT problem can yield a routing backbone for broadcast protocols since (1) each node does not have to construct their own broadcast tree, (2) utilize the virtual backbone to reduce the message overhead, and (3) the weight of backbone representing the energy consumption is minimized. We prove the hardness of this problem, including the inapproximability result and present an approximation algorithm together with an efficient heuristic. Finally, we verify the effectiveness of our proposal through simulation.