Despite the rapid growth in cellular data traffic, we know very little about the (operational) cellular data service network (CDSN) infrastructure. A key step in the process of developing any such understanding is to first understand the locations and distribution of the basestations in the CDSN infrastructure that serve as physical access points for end users for communicating with the underlying network. Such knowledge not only can provide critical insight into the the CDSN infrastructure, but can also guide the development of innovative (e.g. location-aware) services and applications. In this paper we propose a novel approach for mapping the CDSN basestation infrastructure via (explicit) user geo-intent. The intuition behind the proposed approach is to exploit specific geo-locations (i.e. geo-intent) contained in user queries to location-based services, and correlate them with basestation id's to geo-map the CDSN infrastructure. To investigate the validity of our approach, we employ data (RADIUS/RADA data sessions and application sessions) collected at the core IP network inside a CDSN. We develop heuristics for identifying user geo-intent and for geo-mapping the CDSN infrastructure - in particular, the basestations - and evaluate their efficacy using a subset of basestations with ground-truth GPS locations.

Wireless mesh networks are popular as a cost- effective means to provide broadband connectivity to large user populations. A mesh network placement provides coverage, such that each target client location has a link to a deployed mesh node, and connectivity, such that each mesh node wirelessly connects directly to a gateway or via intermediate mesh nodes. Prior work on placement assumes wireless propagation to be uniform in all directions, i.e., an unrealistic assumption of circular communication regions. In this paper, we present approximation algorithms to solve the NP- hard mesh node placement problem for non-uniform propagation settings. The first key challenge is incorporating non-uniform propagation, which we address by formulating the problem input as a connectivity graph consisting of discrete target coverage locations and potential mesh node locations. This graph incorporates non-uniform propagation by specifying the estimated signal quality per link. Secondly, our algorithms are the first to minimize the number of deployed mesh nodes with constant-factor approximation ratio in the non-uniform propagation setting. To achieve this, we formulate the Degree-Constrained Terminal Steiner tree problem and present approximation algorithms which leverage prior results on the Steiner tree problem. Third, it is impractical to measure all possible potential mesh links, and therefore deployment planning must rely on estimations. To address this challenge, we extend our algorithm to iteratively measure the links in the solution Steiner tree, refining the graph input on a per-link basis in order to ensure the deployed network is not disconnected. Finally, we use propagation measurements at 35,000 locations in the deployed GoogleWiFi network to investigate placement in a realistic, non-uniform propagation environment. Under this measured propagation setting, our algorithms result in up to 80% fewer mesh nodes than current algorithms and only require an average of 3 measurements per deployed mesh node to ensure backhaul connectivity.

Wireless mesh network deployments are popular as a cost-effective means to provide broadband connectivity to large user populations. As the network usage grows, network planners need to evolve an existing mesh network to provide additional capacity. In this paper, we study the problem of adding new capacity points (e.g., gateway nodes) to an existing mesh network. We first present a new technique for calculating gateway-limited fair capacity as a function of the contention at each gateway. Then, we present two online gateway placement algorithms that use local search operations to maximize the capacity gain on an existing network. A key challenge is that each gateway's capacity depends on the locations of other gateways and cannot be known in advance of determining a gateway placement. We address this challenge with two placement algorithms with different approaches to estimating the unknown gateway capacities. Our first placement algorithm, MinHopCount, is adapted from a solution to the facility location problem. MinHopCount minimizes path lengths and iteratively estimates the wireless capacity of each gateway location. Our second algorithm, MinContention, is adapted from a solution to the uncapacitated k-median problem and minimizes average contention on mesh nodes, i.e. the number of links in contention range of a mesh node and the number of routes using each link. We show that our gateway placement algorithms outperform a greedy heuristic by up to 64% on realistic topologies. For an example topology, we study the set of all possible gateway placements and find that there is large capacity gain between near-optimal and optimal placements, but the near-optimal placements found by local search are similar in configuration to the optimal.

We present a measurement-parameterized performance study of deployment factors in wireless mesh networks using three performance metrics: client coverage area, backhaul tier connectivity, and fair mesh capacity. For each metric, we identify and study topology factors and architectural features which strongly influence mesh performance via an extensive set of Monte Carlo simulations capturing realistic physical layer behavior. Our findings include: (i) A random topology is unsuitable for a large-scale mesh deployment due to doubled node density requirements, yet a moderate level of perturbations from ideal grid placement has a minor impact on performance. (ii) Multiple backhaul radios per mesh node is a cost-effective deployment strategy as it leads to mesh deployments costing 50% less than with a single-radio architecture, (iii) Dividing access and backhaul connections onto two separate radios does not use the second radio efficiently as it only improves fair mesh capacity 40% to 80% for most users. This is in contrast to using the second radio to move half the user population to a new network operated on the second radio. This work adds to the understanding of mesh deployment factors and their general impact on performance, providing further insight into practical mesh deployments.

Multihop wireless mesh networks can provide Internet access over a wide area with minimal infrastructure expenditure. In this work, we present a measurement driven deployment strategy and a data-driven model to study the impact of design and topology decisions on network-wide performance and cost. We perform extensive measurements in a two-tier urban scenario to characterize the propagation environment and correlate received signal strength with application layer throughput. We find that well-known estimates for pathloss produce either heavily overprovisioned networks resulting in an order of magnitude increase in cost for high pathloss estimates or completely disconnected networks for low pathloss estimates. Modeling throughput with wireless interface manufacturer specifications similarly results in severely underprovisioned networks. Further, we measure competing, multihop flow traffic matrices to empirically define achievable throughputs of fully backlogged, rate limited, and web-emulated traffic. We find that while fully backlogged flows produce starving nodes, rate-controlling flows to a fixed value yields fairness and high aggregate throughput. Likewise, transmission gaps occurring in statistically multiplexed web traffic, even under high offered load, remove starvation and yield high performance. In comparison, we find that well-known noncompeting flow models for mesh networks over-estimate network-wide throughput by a factor of 2. Finally, our placement study shows that a regular grid topology achieves up to 50 percent greater throughput than random node placement.