Long-distance multi-hop wireless networks have been used in recent years to provide connectivity to rural areas. The salient features of such networks include TDMA channel access, nodes with multiple radios, and point-to-point long-distance wireless links established using high-gain directional antennas mounted on high towers. It has been demonstrated previously that in such network architectures, nodes can transmit concurrently on multiple radios, as well as receive concurrently on multiple radios. However, concurrent transmission on one radio, and reception on another radio causes interference. Under this scheduling constraint, given a set of source-destination demand rates, we consider the problem of satisfying the maximum fraction of each demand (also called the maximum concurrent flow problem). We give a novel joint routing and scheduling scheme for this problem, based on linear programming and graph coloring. We analyze our algorithm theoretically and prove that at least 50% of a satisfiable set of demands is satisfied by our algorithm for most practical networks (with maximum node degree at most 5).

Dense deployments of WLANs suffer from increased interference and, as a result, reduced capacity. There are three main functions used to improve the overall network capacity: 1) intelligent frequency allocation across access points (APs); 2) load-balancing of user affiliations across APs; and 3) adaptive power control for each AP. Several algorithms have been proposed in each category, but so far, their evaluation has been limited to: a) each approach in isolation; and b) simulations or small-scale testbeds. In this paper, we ask the question: What is the best way to combine these different functions? Our focus is to fully explore the interdependencies between the three functions in order to understand when and how to deploy them on a network. We follow a measurement-driven study to quantify the effects of three previously proposed optimization schemes (one for each category) on a relatively large testbed and in many different scenarios. Surprisingly, we find that blindly applying all the three optimization schemes is not always preferable; it can sometimes degrade the performance by as much as 24% compared to using only two of the schemes. We discover that there are explicit conditions that are conducive for applying specific combinations of the optimization schemes. We capture these conditions within a comprehensive framework, which we call measurement-driven guidelines (MDG). While we derive such guidelines based on measurements on one experimental testbed, we test their applicability and efficacy on a second testbed in a different location. We show that our framework improves network capacity consistently across both testbeds, with improvements ranging from 22% to 142% with 802.11a, and 103% to 274% with 802.11g.

We consider the problem of determining asymptotic bounds on the capacity of a randomadhocnetwork. Previous approaches assumed a link layer model in which if a transmitter-receiver pair can communicate with each other, i.e., the signal to interference and noise ratio (SINR) is above a certain threshold, then the transmitted packet is received error-free by the receiver thereby. Using this model, the per node capacity of the network was shown to be Theta(radic(nlogn)/1). In reality, for any finite link SINR, there is a nonzero probability of erroneous reception of the packet. We show that in a large network, as the packet travels an asymptotically large number of hops from source to destination, the cumulative impact of packet losses over intermediate links results in a per-node throughput of onlyO(radic(n)/1) under the previously proposed routing and scheduling strategy. We then propose a new scheduling scheme to counter this effect. The proposed scheme provides tight guarantees on end-to-end packet loss probability, and improves the per-node throughput to Omega(radic(n)(logn)/12(alpha-2)/alpha+2) wherealpha>2is the path loss exponent.

We study the problem of scheduling in OFDMA-based relay networks with emphasis on IEEE 802.16j based WiMAX relay networks. In such networks, in addition to a base station, multiple relay stations are used for enhancing the throughput, and/or improving the range of the base station. We solve the problem of MAC scheduling in such networks so as to serve the mobiles in a fair manner while exploiting the multiuser diversity, as well as the frequency selectivity of the wireless channel. The scheduling resources consist of tiles in a two-dimensional scheduling frame with time slots along one axis, and frequency bands or sub-channels along the other axis. The resource allocation problem has to be solved once every scheduling frame which is about 5 - 10 ms long. While the original scheduling problem is computationally complex, we provide an easy-to-compute upper bound on the optimum. We also propose three fast heuristic algorithms that perform close to the optimum (within 99.5%), and outperform other algorithms such as OFDM2A proposed in the past. Through extensive simulation results, we demonstrate the benefits of relaying in throughput enhancement (an improvement in the median throughput of about 25%), and feasibility of range extension (for e.g., 7 relays can be used to extend the cell-radius by 60% but mean throughput reduces by 36%). Our algorithms are easy to implement, and have an average running time of less than 0.05 ms making them appropriate for WiMAX relay networks.

Past approaches to routing in mesh networks either (i) do not account for the MAC-layer interactions between the links in a tractable manner, or (ii) are agnostic to load-balancing across gateways. Our answer to these problems is MaLB (MAC-aware and Load Balanced routing algorithm), a greedy, tractable, and distributed mesh routing algorithm. Since the underlying objective function has high combinatorial complexity, MaLB uses a greedy approach. MaLB finds an optimum routing forest (union of trees rooted at the gateways) by taking into account MAC-layer interaction between links, as well as optimum multi-hop association of mesh nodes to gateways. MaLB builds on top of ETP (Expected Through-Put), a recently proposed MAC-aware routing metric. We also propose a low complexity variant of MaLB called LB (Load Balanced routing algorithm) which performs load balancing in a MAC-agnostic manner. MaLB performs especially well in networks with skewed topologies that result from unplanned mesh network deployment, as well as in the presence of gateway failures. Simulations with an enhanced version of ns-2 show that MaLB results in up to 60% higher throughput than a shortest path algorithm with ETX (Expected Transmission Count). Furthermore, MaLB results in up to 30% improvement over the LB algorithm, as well as a shortest path algorithm with ETT (Expected Transmission Time).

The popularity of IEEE 802.11 WLANs has led to dense deployments in urban areas. High density leads to sub-optimal performance unless the interfering networks learn how to optimally use and share the spectrum. This paper proposes two fully distributed algorithms that allow (i) multiple interfering 802.11 access points to select their operating frequency in order to minimize interference, and (ii) users to choose the access point they attach to, in order to get their fair share of the whole network bandwidth. The proposed algorithms rely on Gibbs sampler, and do not require explicit coordination among the wireless devices. They only require the participating wireless nodes to measure local quantities such as interference and transmission delay. The algorithms are shown to lead to optimal bandwidth sharing, where optimality is defined according to the minimal potential delay. We analytically prove the convergence of the proposed algorithms, and study their performance by simulation.

The low cost and the ease of deployment of WiFi devices, as well as the need to support high bandwidth applications over 802.11 WLANs has led to the emergence of high density 802.11 networks in urban areas and enterprises. High density wireless networks, by design, face significant challenges due to increased interference resulting from the close proximity of co-channel cells. We demonstrate that power control can be used to mitigate interference in such an environment. It is well-known that variable transmit powers result in asymmetric links in the network, and can potentially lead to throughput starvation of some nodes. We first show that in order to perform starvation-free power control in 802.11 networks, across-layerapproach is required, whereby the transmit powers and the carrier sensing parameter of the MAC layer of the nodes should bejointlytuned. We then propose a framework that determines optimum settings for these parameters with the objective of maximizing the network-wide throughput for elastic traffic. Within this framework, we devise a distributed power control algorithm that uses a Gibbs sampler. OPNET simulations and experiments over a proof of concept testbed demonstrate that in a dense network the proposed power control algorithm yields significant improvement in client throughput.

Dense deployments of WLANs suffer from increased interference and as a result, reduced capacity. There are three main functions used to improve the overall network capacity: a) intelligent frequency allocation across APs, b) load-balancing of user affiliations across APs, and c) adaptive power-control for each AP. Several algorithms have been proposed in each category, but so far, their evaluation has been limited to: (a) each approach in isolation and, (b)simulations or small-scale testbeds. In this paper, we ask the question: what is the best way to combine these different functions? Our focus is to fully explore the interdependencies between the three functions in order to understand when and how to deploy them on a network. We follow a measurement-driven study to quantify the effects of three previously proposed optimization schemes (one for each category) on a relatively large testbed and in many different scenarios. Surprisingly, we find that blindly applying all the three optimization schemes is not always preferable; it can sometimes degrade the performance by as much as 24% compared to using only two of the schemes. We discover that there are explicit conditions that are conducive for applying specific combinations of the optimization schemes. We capture those conditions within a comprehensive framework, which we call MDG (Measurement-Driven Guidelines). While we derive suchguidelines based on measurements on one experimental testbed, we test their applicability and efficacy on a second testbed in a different location. We show that our framework improves network capacity consistently acrossboth testbeds, with improvements ranging from 22% to 142% with 802.11a, and 103% to 274% with 802.11g.

The provisioning of high throughput performance infrastructure wireless networks necessitates the deployment of a high density of Access Points. While the latter improves wireless link quality to the clients, it can also introduce additional interference unless the network is carefully planned and tuned. It has been shown that the reaction of CSMA/CA protocol to interference is unnecessarily conservative in high density environments. In this work, we study the problem of infrastructure wireless network design, and the interaction between high density and MAC parameter tuning. Through analysis and numerical results, we provide recommendations on (i) optimum dimensioning of high density networks, and (ii) optimum tuning of their MAC parameters. We demonstrate that 802.11a networks are inherently noise-dominated, while 802.11g networks are interference-dominated, thus requiring different network design approaches. In sharp contrast to previous work, we establish that MAC parameter tuning has limited benefit in properly planned 802.11a networks. On the other hand, analytical results on the optimal tuning of MAC parameters in interference-dominated 802.11g deployments show substantial throughput improvements. Using the insight gained through our analysis, we propose an algorithm for the optimal tuning of MAC parameters in unstructured high density environments. Opnet simulations show that the proposed algorithm results in up to 260% improvement in network throughput.

The problem of determining asymptotic bounds on the capacity of a random ad hoc network is considered. Previous approaches assumed a threshold-based link layer model in which a packet transmission is successful if the SINR at the receiver is greater than a fixed threshold. In reality, the mapping from SINR to packet success probability is continuous. Hence, over each hop, for every finite SINR, there is a non-zero probability of packet loss. With this more realistic link model, it is shown that for a broad class of routing and scheduling schemes, a fixed fraction of hops on each route have a fixed non-zero packet loss probability. In a large network, a packet travels an asymptotically large number of hops from source to destination. Consequently, it is shown that the cumulative effect of per-hop packet loss results in a per-node throughput of only O (1/n) (instead of thetas[1/radic(n log n)] as shown previously for the threshold-based link model)

The handoff algorithms in the current generation of 802.11 networks are primarily reactive in nature, because they wait until the link quality degrades substantially to trigger a handoff. They further rely on instantaneous signal strength measurements when choosing the best AP. This approach leads to handoff delays on the order of 1-2 seconds that are unacceptable for delay sensitive applications such as VoIP. We propose a fundamentally new approach to handoffs that is based on continuous monitoring of wireless links. In our approach, a client measures the beacon strengths of all the APs operating on the current, and the overlapping channels, and makes its handoff decisions based on the long-term, and short-term trends in these signals. We show through experiments in a campus wireless network that our proposed algorithms result in more than 50% reduction in average handoff delays, while having the potential to improve overall user performance. Our algorithms have been implemented in today's hardware, and unlike other proposed roaming algorithms in the literature, need no infrastructure support.

We study the impact of network load in the neighboring sectors on the inter-cell interference in a cellular data network. The signal received by a user over the forward link in such a system contains interference from the neighboring base stations. We note that the strength of this interference is a function of the network load in the neighboring cells. We obtain an expression for the received SINR (signal to interference and noise ratio) as a function of the traffic load in the interfering cells. Using this result, we propose an improvement to the conservative pilot-based SINR estimation scheme that is implemented in the current cellular data networks. The proposed scheme provides a more accurate estimate of the user SINR by taking better account of the contribution of inter-cell interference. It builds on top of the current SINR measurement scheme by using a combination of pilot measurement and traffic load measurement. With the proposed scheme, a terminal reports a less conservative data rate, and hence it receives a higher throughput. The scheme especially benefits the "poor" users, i.e., the users that receive low throughput because they are located far from the base station. For example, when the network load in the neighboring sectors is 0.5, with the proposed scheme, the throughput received by a single vehicular user located about three-fourth of the way between the serving base station and the cell boundary, is about 35% higher than the throughput obtained using the scheme that is used in current practice

We consider a heterogeneous sensor network in which nodes are to be deployed over a unit area for the purpose of surveillance. An aircraft visits the area periodically and gathers data about the activity in the area from the sensor nodes. There are two types of nodes that are distributed over the area using two-dimensional homogeneous Poisson point processes; type 0 nodes with intensity (average number per unit area) /spl lambda//sub 0/ and battery energy E/sub 0/; and type 1 nodes with intensity /spl lambda//sub 1/ and battery energy E/sub 1/. Type 0 nodes do the sensing while type 1 nodes act as the cluster heads besides doing the sensing. Nodes use multihopping to communicate with their closest cluster heads. We determine them optimum node intensities (/spl lambda//sub 0/, /spl lambda//sub 1/) and node energies (E/sub 0/, E/sub 1/) that guarantee a lifetime of at least T units, while ensuring connectivity and coverage of the surveillance area with a high probability. We minimize the overall cost of the network under these constraints. Lifetime is defined as the number of successful data gathering trips (or cycles) that are possible until connectivity and/or coverage are lost. Conditions for a sharp cutoff are also taken into account, i.e., we ensure that almost all the nodes run out of energy at about the same time so that there is very little energy waste due to residual energy. We compare the results for random deployment with those of a grid deployment in which nodes are placed deterministically along grid points. We observe that in both cases /spl lambda//sub 1/ scales approximately as /spl radic/(/spl lambda//sub 0/). Our results can be directly extended to take into account unreliable nodes.

This paper presents a cost based comparative study of homogeneous and heterogeneous clustered sensor networks. We focus on the case where the base station is remotely located and the sensor nodes are not mobile. Since we are concerned with the overall network dimensioning problem, we take into account the manufacturing cost of the hardware as well as the battery energy of the nodes. A homogeneous sensor network consists of identical nodes, while a heterogeneous sensor network consists of two or more types of nodes (organized into hierarchical clusters). We first consider single hop clustered sensor networks (nodes use single hopping to reach the cluster heads). We use LEACH as the representative single hop homogeneous network, and a sensor network with two types of nodes as a representative single hop heterogeneous network. For multihop homogeneous networks (nodes use multihopping to reach the cluster head), we propose and analyze a multihop variant of LEACH that we call M-LEACH. We show that M-LEACH has better energy efficiency than LEACH in many cases. We then compare the cost of multihop clustered sensor networks with M-LEACH as the representative homogeneous network, and a sensor network with two types of nodes (that use in-cluster multi-hopping) as the representative heterogeneous network.