|Service Infrastructure and Network Management|
MobiDesk: Mobile Virtual Desktop Computing,
Ricardo A. Baratto, Shaya Potter, Gong Su, Jason Nieh(Columbia University, USA)
We present MobiDesk, a mobile virtual desktop computing hosting infrastructure that leverages continued improvements in network speed, cost, and ubiquity to address the complexity, cost, and mobility limitations of today's personal computing infrastructure. MobiDesk transparently virtualizes a user's computing session by abstracting underlyingsystem resources in three key areas: display, operating system, and network. It provides a thin virtualization layer that decouples a user's computing session from any particular end-user device, and moves all application logic to hosting providers. The virtualization layer decouples a user's computing session from the underlying operating system and server instance, enabling high-availability service by transparently migrating sessions from one server to another during server maintenance or upgrades. We have implemented a prototype in Linux that works with existing unmodified applications and operating system kernels. Our experimental results demonstrate that MobiDesk has very low virtualization overhead, can provide a full featured desktop experience including full-motion video support, and is able to migrate users' sessions efficiently and reliably for high-availability, while maintaining existing network connections.
Using code collection to support large applications on mobile devices
Lucian Popa, Costin Raiciu, (Politechnica University Bucharest, Romania), Radu Teodorescu (Lehman Brothers, USA), Irina Athanasiu (Politehnica University Bucharest, Romania), Raju Pandey (University of California, Davis, USA)
The progress of mobile device technology unfolds a new spectrum of applications that challenges conventional infrastructure models. Most of these devices are perceived by their users as "appliances" rather than computers and accordingly the application management should be done transparently by the underlying system unlike classic applications managed explicitly by the user. Memory management on such devices should consider new types of mobile applications involving code mobility such as mobile agents, active networks and context aware applications. This paper describes a new code management technique, called "code collection" and proposes a specific code collection algorithm, the Adaptive Code Collection Algorithm (ACCAL). Code collection is a mechanism for transparently loading and discarding application components on mobile devices at runtime that is designed to permit very low memory usage and at the same time good performance by focusing memory usage on the hotspots of the application. To achieve these goals, ACCAL uses properties specific to executable code and enhances conventional data management methods such as garbage collection and caching. The results show that fine-grained code collection allows large applications to execute by using significantly less memory while inducing small execution time overhead.
Architecture and Techniques for Diagnosing Faults in IEEE 802.11 Infrastructure Networks
Atul Adya, Victor Bahl (Microsoft Research, USA), Ranveer Chandra (Cornell University, USA), Lili Qiu (Microsoft Research, USA)
The wide-scale deployment of IEEE 802.11 wireless networks has generated significant challenges for Information Technology (IT) departments in corporations. Users frequently complain about connectivity and performance problems, and network administrators are expected to diagnose these problems while managing corporate security and coverage. Their task is particularly difficult due to the unreliable nature of the wireless medium and a lack of intelligent diagnostic tools for determining the cause of these problems. This paper presents an architecture for detecting and diagnosing faults in IEEE 802.11 infrastructure wireless networks. To the best of our knowledge, ours is the first paper to address fault diagnostic issues for these networks. As part of our architecture, we propose and evaluate a novel technique called Client Conduit, which enables bootstrapping and fault diagnosis of disconnected clients. We describe techniques for analyzing performance problems faced in a wireless LAN deployment. We also present an approach for detecting unauthorized access points. We have built a prototype of our fault diagnostic architecture on the Windows operating system using off-the-shelf IEEE 802.11 cards. The initial results show that our mechanisms are effective; furthermore, they impose low overheads when clients are not experiencing problems.
Localization for Mobile Sensor Networks
Lingxuan Hu, David Evans (University of Virginia, USA)
Many sensor network applications require location awareness, but it is often too expensive to include a GPS receiver in a sensor network node. Hence, localization schemes for sensor networks typically use a small number of seed nodes that know their location and protocols whereby other nodes estimate their location from the messages they receive. Several such localization techniques have been proposed, but none of them consider mobile nodes and seeds. Although mobility would appear to make localization more difficult, in this paper we introduce the sequential Monte Carlo Localization method and argue that it can exploit mobility to improve the accuracy and precision of localization. Our approach does not require additional hardware on the nodes and works even when the movement of seeds and nodes is uncontrollable. We analyze the properties of our technique and report experimental results from simulations. Our scheme outperforms the best known static localization schemes under a wide range of conditions.
VOR BAsestations for Indoor 802.11 Positioning,
Dragos Niculescu, Badri Nath (Rutgers University, USA)
Angle of arrival (AOA) has previously been used for outdoor positioning in aircraft navigation and for services like E911. For indoor positioning, the best schemes to date rely either on extensive infrastructure, or on sampling of the signal strength on a dense grid, which is subject to changes in the environment, like furniture, elevators, or people. We present an indoor positioning architecture that does not require a signal strength map, simply requiring the placement of special VOR base stations (VORBA). While our incipient realization of the AOA using 802.11 uses a base station with a revolving directional antenna, a non mechanical implementation would yield comparable performance, even with quantized angles. Performance of positioning with VOR base stations is evaluated though experimentation, simulation, and theoretical analysis.
Practical Robust Localization over Large-Scale 802.11 Wireless Networks
Andreas Haeberlen, Eliot Flannery, Andrew Ladd, Algis Rudys, Dan Wallach, Lydia Kavraki (Rice University, USA)
We demonstrate a system built using probabilistic techniques that allows for remarkably accurate localization across our entire office building using nothing more than the built-in signal intensity meter supplied by standard 802.11 cards. While prior systems have required significant investments of human labor to build a detailed signal map, we can train our system by spending less than one minute per office or region, walking around with a laptop and recording the observed signal intensities of our building's unmodified base stations. We actually collected over two minutes of data per office or region, about 28 man-hours of effort. Using less than half of this data to train the localizer, we can localize a user to the precise, correct location in over 95% of our attempts, across the entire building. Even in the most pathological cases, we almost never localize a user any more distant than to the neighboring office. A user can obtain this level of accuracy with only two or three signal intensity measurements, allowing for a high frame rate of localization results. Furthermore, with a brief calibration period, our system can be adapted to work with previously unknown user hardware. We present results demonstrating the robustness of our system against a variety of untrained time-varying phenomena, including the presence or absence of people in the building across the day. Our system is sufficiently robust to enable a variety of locationaware applications without requiring special-purpose hardware or complicated training and calibration procedures.
|Algorithms for Multihop Networks I|
Revisiting the TTL-based Controlled Flooding Search: Optimality and Randomization,
Nicholas Chang, Mingyan Liu (University of Michigan, USA)
In this paper we consider the problem of searching for a node or an object (i.e., piece of data, le, etc.) in a large network. Applications of this problem include searching for a destination node in a mobile ad hoc network, querying for a piece of desired data in a wireless sensor network, and searching for a shared le in an unstructured peer-to-peer network. We limit our attention in this study to the class of controlled ooding search strategies where query/search packets are broadcast and propagated in the network until a preset TTL (time-to-live) value carried in the packet expires. Every unsuccessful search attempt results in an increased TTL value (i.e., larger search area) and the same process is repeated. The primary goal of this study is to derive search strategies (i.e., sequences of TTL values) that will minimize the cost of such searches associated with packet transmissions. The main results of this paper are as follows. When the probability distribution of the location of the object is known a priori, we present a dynamic programming formulation with which optimal search strategies can be derived that minimize the expected search cost. We also derive the necessary and supportingcient conditions for two very commonly used search strategies to be optimal. When the probability distribution of the location of the object is not known a priori and the object is to minimize the worst-case search cost, we show that the best strategies are randomized strategies, i.e., successive TTL values are chosen from certain probability distributions rather than deterministic values. We show that given any deterministic TTL sequence, there exists a randomized version that has a lower worst-case expected search cost. We also derive an asymptotically (as the network size increases) optimal strategy within a class of randomized strategies.
Network Deformation: Traffic-Aware Algorithms for Dynamically Reducing
End-to-end Delay in Multihop Wireless Networks,
Anindya Basu (Bell Laboratories, Lucent Technologies, USA), Brian Boshes (University of California, Berkeley, USA), Sayandev Mukherjee, Sharad Ramanathan (Bell Laboratories, Lucent Technologies, USA)
We present two centralized algorithms that dynamically deform the topology of a multi-hop wireless network in response to changing traffic conditions, so as to reduce the end-to-end packet delay. These algorithms operate by reducing an easily calculable traffic-and-topologydependent metric that has strong positive correlation to the mean endto- end network delay. This makes it possible to change the network topology in real time. The first algorithm involves moving existing nodes to create new links, while the second involves adding a new node to the existing network. The new links are added judiciously between nodes with the most traffic fluctuations, in a way that often decreases the total number of network links. Multiple simulations on the original and the deformed networks using the ns simulator demonstrate that the reductions in end-to-end delay are significantly higher than with the alternative approach of increasing the capacities of the most congested links.
Routing in multi-radio, multi-hop wireless mesh networks,
Jitendra Padhye, Richard Draves, Brian Zill (Microsoft Research, USA)
We present a new metric for routing in multi-radio, multihop wireless networks. We focus on wireless networks with stationary nodes, such as community wireless networks. The goal of the metric is to choose a high-throughput path between a source and a destination. Our metric assigns weights to individual links based on the Expected Transmission Time (ETT) of a packet over the link. The ETT is a function of the loss rate and the bandwidth of the link. The individual link weights are combined into a path metric called Weighted Cumulative ETT (WCETT) that explicitly accounts for the interference among links that use the same channel. The WCETT metric is incorporated into a routing protocol that we call Multi-Radio Link-Quality Source Routing.
We studied the performance of our metric by implementing it in a wireless testbed consisting of 23 nodes, each equipped with two 802.11 wireless cards. We find that in a multi-radio environment, our metric significantly outperforms previously-proposed routing metrics by making judicious use of the second radio.
Power Conservation and Quality of Surveillance in Target Tracking Sensor Networks,
Chao Gui, Prasant Mohapatra (University of California, Davis, USA)
Target tracking is an important application of wireless sensor networks. In this application, the sensor nodes collectively monitor and track the movement of an event or target object. The network operations have two states: the surveillance state during the absence of any event of interest, and the tracking state which is in response to any moving targets gets. Thus, the power saving operations, which is of critical importance for extending network lifetime, should be operative in two different modes as well. In this paper, we study the power saving operations in both states of network operations. During surveillance state, a set of novel metrics for quality of surveillance is proposed specifically for detecting moving objects. In the tracking state, we propose a collaborative messaging scheme that wakes up and shuts down the sensor nodes with spatial and temporal preciseness. This study, which is a combination of theoretical analysis and simulated evaluations, quantifies the trade-off between power conservation and quality of surveillance while presenting guidelines for efficient deployment of sensor nodes for target tracking application.
On k-Coverage in a Mostly Sleeping Sensor Network,
Santosh Kumar, Ten Hwang Lai, Jozsef Balogh (The Ohio State University, USA)
Sensor networks are often desired to last many times longer than the active lifetime of individual sensors. This is usually achieved by putting sensors to sleep for most of their lifetime. On the other hand, surveillance kind of applications require guaranteed k-coverage of the protected region at all times. As a result, determining the appropriate number of sensors to deploy that achieves both goals simultaneously becomes a challenging problem. In this paper, we consider three kinds of deployments for a sensor network on a unit square - a sqrt(n)*sqrt(n) grid, random uniform (for all n points), and Poisson (with density n). In all three deployments, each sensor is active with probability p, independently from the others. Then, we claim that the critical value of the function nppr2/ log(np) is 1 for the event of k-coverage of every point. We also provide an upper bound on the window of this phase transition. Although the conditions for the three deployments are similar, we obtain sharper bounds for the random deployments than the grid deployment, which occurs due to the boundary condition. In this paper, we also provide corrections to previously published results for the grid deployment model. Finally, we use simulation to show the usefulness of our analysis in real deployment scenarios.
|Experimental Testbeds and Data|
Performance Optimizations for Wireless Wide-area Networks: Comparative Study and Experimental Evaluation,
Rajiv Chakravorty (University of Cambridge, United Kingdom), Suman Banerjee (University of Wisconsin-Madison, USA), Pablo Rodriguez (Microsoft Research, Cambridge, United Kingdom), Julian Chesterfield, Ian Pratt (University of Cambridge, United Kingdom)
We present a comparative performance study of a wide selection of optimization techniques to enhance application performance in the context of wide-area wireless networks (WWANs). Unlike in traditional wired and wireless IP-based networks, applications running overWWAN cellular environments are significantly affected by the vagaries of the cellular wireless medium. Prior research has proposed and analyzed optimizations at individual layers of the protocol stack. In contrast, we introduce the first detailed experimentbased evaluation and comparison of all such optimization techniques in a commercial WWAN testbed. This paper, therefore, summarizes our experience in implementing and deploying an infrastructure to improve WWAN performance. The goals of this paper are: (1) to perform an accurate benchmark of application performance over such commercially deployed WWAN environments, (2) to implement and characterize the impact of various optimization techniques across different layers of the protocol stack, and (3) to quantify their interdependencies in realistic scenarios. Additionally, we also discuss measurement pitfalls that we experienced and provide guidelines that may be useful for future experimentation in WWAN environments.
Characterizing Flows in Large Wireless Data Networks,
Xiaoqiao Meng, Starsky H.Y. Wong, Yuan Yuan, Songwu Lu (University of California at Los Angeles, USA)
Several studies have recently been performed on wireless university campus networks, corporate and public networks. Yet little is known about the flow-level characterization in such networks. In this paper, we statistically characterize both static flows and roaming flows in a large campus wireless network using a recently-collected trace. For static flows, we take a two-tier approach to characterizing the flow arrivals, which results a Weibull regression model. We further discover that the static flow arrivals in spatial proximity show strong similarity. As for roaming flows, they can also be well characterized statistically. We explain the results by user behaviors and application demands, and further cross- validate the modeling results by three other traces. Finally, we use two examples to illustrate how to apply our models for performance evaluation in the wireless context.
The Changing Usage of a Mature Campus-wide Wireless Network,
Tristan Henderson, David Kotz, Ilya Abyzov (Dartmouth College, USA)
Wireless Local Area Networks (WLANs) are now commonplace on many academic and corporate campuses. As "Wi-Fi" technology becomes ubiquitous, it is increasingly important to understand trends in the usage of these networks. This paper analyzes an extensive network trace from a mature 802.11 WLAN, including more than 550 access points and 7000 users over seventeen weeks. We employ several measurement techniques, including syslogs, telephone records, SNMP polling and tcpdump packet sniffing. This is the largest WLAN study to date, and the first to look at a large, mature WLAN and consider geographic mobility. We compare this trace to a trace taken after the network's initial deployment two years ago. We found that the applications used on the WLAN changed dramatically. Initial WLAN usage was dominated by Web traffic; our new trace shows significant increases in peer-to-peer, streaming multimedia, and voice over IP (VoIP) traffic. On-campus traffic now exceeds off-campus traffic, a reversal of the situation at the WLAN's initial deployment. Our study indicates that VoIP has been used little on the wireless network thus far, and most VoIP calls are made on the wired network. Most calls last less than a minute.
We saw greater heterogeneity in the types of clients used, with more embedded wireless devices such as PDAs and mobile VoIP clients. We define a new metric for mobility, the "session diameter." We use this metric to show that embedded devices have different mobility characteristics than laptops, and travel further and roam to more access points. Overall, users were surprisingly non-mobile, with half remaining close to home about 98% of the time.
|Ad Hoc Networks|
Denial of Service Resilience in Ad Hoc Networks,
Imad Aad, Jean-Pierre Hubaux (EPFL, Switzerland), Edward W. Knightly (Rice University, USA)
Significant progress has been made towards making ad hoc networks secure and DoS resilient. However, little attention has been focused on quantifying DoS resilience: Do ad hoc networks have sufficiently redundant paths and counter-DoS mechanisms to make DoS attacks largely ineffective? Or are there attack and system factors that can lead to devastating effects? In this paper, we design and study DoS attacks in order to assess the damage that difficult-to- detect attackers can cause. The first attack we study, called the JellyFish attack, is targeted against closed-loop flows such as TCP; although protocol compliant, it has devastating effects. The second is the Black Hole attack, which has effects similar to the JellyFish, but on open-loop flows. We quantify via simulations and analytical modeling the scalability of DoS attacks as a function of key performance parameters such as mobility, system size, node density, and counter-DoS strategy. One perhaps surprising result is that such DoS attacks can increase the capacity of ad hoc networks, as they starve multi-hop flows and only allow one-hop communication, a capacity-maximizing, yet clearly undesirable situation.
SSCH: Slotted Seeded Channel Hopping for Capacity Improvement in IEEE 802.11 Ad-Hoc Wireless Networks,
Victor Bahl (Microsoft Research, USA), Ranveer Chandra (Cornell University, USA), John Dunagan (Microsoft Research, USA)
Capacity improvement is one of the principal challenges in wireless networking. We present a link-layer protocol called Slotted Seeded Channel Hopping, or SSCH, that increases the capacity of an IEEE 802.11 network by utilizing frequency diversity. SSCH can be implemented in software over an IEEE 802.11-compliant wireless card. Each node using SSCH switches across channels in such a manner that nodes desiring to communicate overlap, while disjoint communications mostly do not overlap, and hence do not interfere with each other. To achieve this, SSCH uses a novel scheme for distributed rendezvous and synchronization. Simulation results show that SSCH signi?cantly increases network capacity in several multi-hop and single-hop wireless networking scenarios.
Improving TCP Performance over Mobile Ad Hoc Networks by Exploiting Cross-Layer Information Awareness,
Xin Yu (New York University, USA)
TCP performance degrades significantly in mobile ad hoc networks because most of packet losses occur as a result of route failures. Prior work proposed to provide link failure feedback to TCP so that TCP can avoid responding to route failures as if congestion had occurred. However, after a link failure is detected, several packets will be dropped from the network interface queue; TCP will time out because of these losses. It will also time out for ACK losses caused by route failures. In this paper, we propose to make routing protocols aware of lost data packets and ACKs and help reduce TCP timeouts for mobility-induced losses. Toward this end, we present two mechanisms: early packet loss notification (EPLN) and best-effort ACK delivery (BEAD). EPLN seeks to notify TCP senders about lost data packets. For lost ACKs, BEAD attempts to retransmit ACKs at either intermediate nodes or TCP receivers. Both mechanisms extensively use cached routes, without initiating route discoveries at any intermediate node. We evaluate TCP-ELFN enhanced with the two mechanisms using two caching strategies for DSR, path caches and a distributed cache update algorithm proposed in our prior work. We show that TCP-ELFN with EPLN and BEAD significantly outperforms TCP-ELFN under both caching strategies. We conclude that cross-layer information awareness is key to making TCP efficient in the presence of mobility.
|Algorithms for Multihop Networks II|
Truthful Multicast Routing in Selfish Wireless Networks,
Weizhao Wang, Xiang-Yang Li (Illinois Institute of Technology, USA), Yu Wang (University of North Carolina at Charlotte, USA)
In wireless networks, it is often assumed that each individual wireless terminal will faithfully follow the prescribed protocols without any deviation- except, perhaps, for a few faulty or malicious ones. Wireless terminals, when owned by individual users, will likely do what is the most beneficial to their owners, i.e., act "selfishly". Therefore, an algorithm or protocol intended for selfish wireless networks must be designed. In this paper, we specifically study how to conduct efficient multicast routing in selfish wireless networks. We assume that each wireless terminal or communication link will incur a cost when it transits some data. Traditionally, the VCG mechanism has been the only method to design protocols so that each selfish agent will follow the protocols for its own interest to maximize its benefit. The main contributions of this paper are two-folds. First, for each of the widely used multicast structures, we show that the VCG based mechanism does not guarantee that the selfish terminals will follow the protocol. Second, we design the first multicast protocols without using VCG mechanism such that each agent maximizes its profit when it truthfully reports its cost. Extensive simulations are conducted to study the practical performances of the proposed protocols regarding the actual network cost and total payment.
Initializing Newly Deployed Ad Hoc and Sensor Networks,
Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer (ETH Zurich, Switzerland)
A newly deployed multi-hop radio network is unstructured and lacks a reliable and e?cient communication scheme. In this paper, we take a step towards analyzing the problems existing during the initialization phase of ad hoc and sensor networks. Particularly, we model the network as a multihop quasi unit disk graph and allow nodes to wake up asynchronously at any time. Further, nodes do not feature a reliable collision detection mechanism, and they have only limited knowledge about the network topology. We show that even for this restricted model, a good clustering can be computed e?ciently. Our algorithm e?ciently computes an asymptotically optimal clustering. Based on this algorithm, we describe a protocol for quickly establishing synchronized sleep and listen schedule between nodes within a cluster. Additionally, we provide simulation results in a variety of settings.
FLSS: A Fault-Tolerant Topology Control Algorithm for Wireless Networks,
Ning Li, Jennifer Hou (University of Illinois at Urbana Champaign, USA
Topology control algorithms usually reduce the number of links in a wireless network, which in turn decreases the degree of connectivity. The resulting network topology is more susceptible to system faults such as node failures and departures. In this paper, we consider k-vertex connectivity of a wireless network. We first present a centralized algorithm, Fault-tolerant Global Spanning Subgraph (FGSSk), which preserves k-vertex connectivity. FGSSk is minmax optimal, i.e., FGSSk minimizes the maximum transmission power used in the network, among all algorithms that preserve k- vertex connectivity. Based on FGSSk, we propose a localized algorithm, Fault-tolerant Local Spanning Subgraph (FLSSk). It is proved that FLSSk preserves k-vertex connectivity while maintaining bi-directionality of the network, and FLSSk is min-max optimal among all strictly localized algorithms. We then relax several widely used assumptions for topology control to enhance the practicality of FGSSk and FLSSk. Simulation results show that FLSSk is more power-efficient than other existing distributed/localized topology control algorithms.
|Fairness and Load Balancing|
End-to-End Performance and Fairness in Multihop Wireless Backhaul Networks
Violeta Gambiroza, Bahareh Sadeghi, Edward W. Knightly (Rice University, USA)
Wireless IEEE 802.11 networks in residences, small businesses, and public "hot spots" typically encounter the wireline access link (DSL, cable modem, T1, etc.) as the slowest and most expensive part of the end-to-end path. Consequently, network architectures have been proposed that employ multiple wireless hops in route to and from the wired Internet. Unfortunately, use of current media access and transport protocols for such systems can result in severe unfairness and even starvation for flows that are an increasing number of hops away from a wired Internet entry point. Our objective is to study fairness and end-to-end performance in multihop wireless backhaul networks via the following methodology. First, we develop a formal reference model that characterizes objectives such as removing spatial bias (i.e., providing performance that is independent of the number of wireless hops to a wire) and maximizing spatial reuse. Second, we perform an extensive set of simulation experiments to quantify the impact of the key performance factors towards achieving these goals. For example, we study the roles of the MAC protocol, end-to-end congestion control, antenna technology, and traffic types. Next, we develop and study a distributed layer 2 fairness algorithm which targets to achieve the fairness of the reference model without modification to TCP. Finally, we study the critical relationship between fairness and aggregate throughput and in particular study the fairness-constrained system capacity of multihop wireless backhaul networks.
Coordinated Load Balancing, Handoff/Cell-site Selection, and Scheduling in Multi-cell Packet Data Systems
Aimin Sang (NEC Laboratories America, USA), Xiaodong Wang (Columbia University, USA), Mohammad Madihian, Richard Gitlin (NEC Laboratories America, USA)
We investigate a wireless system of multiple cells, each having a downlink shared channel in support of high-speed packet data services. In practice, such a system consists of hierarchically organized entities including a central server, Base Stations (BSs), and Mobile Stations (MSs). Our goal is to improve global resource utilization and reduce regional congestion given asymmetric arrivals and departures ofmobile users. For this purpose, we propose a scalable cross-layer framework to coordinate packet-level scheduling, call-level cell-site selection and handoff, and system-level loading balancing based on load, throughput, and channel measurements at different layers. In this framework, an opportunistic scheduling algorithm--the weighted Alpha-Rule--exploits multiuser diversity gain in each cell independently, trading aggregate (mean) downlink throughput for fairness and minimum rate guarantees among MSs. Each MS adapts to its channel dynamics and the load fluctuations in neighboring cells, in accordance with MSs' mobility and their arrivals or departures, by initiating load-aware handoff and cellsite selection. The central server adjusts the scheduling parameters of each cell to coordinate cells' coverage, or cell breathing, by prompting distributed MS handoffs. Across the whole system, BSs and MSs constantly monitor their load, throughput, or channel quality in order to facilitate the overall system coordination. Our specific contributions in such a framework are highlighted by the minimum-rate guaranteedWeighted Alpha-Rule scheduling, the load-aware MS handoff/cell-site selection, and the Media Access Control (MAC)-layer cell breathing. Our evaluations show that the proposed framework can improve the global resource utilization and load balancing, which translates into a smaller blocking rate of MS arrivals without extra resources, while the aggregate throughput remains roughly the same or improved around the hotspots. Our tests also show that the coordinated system is robust to dynamic load fluctuations and is scalable to both system size and MS population.
Fairness and Load Balancing in Wireless LANs Using Association Control,
Yigal Bejerano, Seung-Jae Han, Li Li (Bell Labs, Lucent Technologies, USA)
Recent studies on operational wireless LANs (WLANs) have shown that user load is often unevenly distributed among wireless access points (APs). This unbalanced load results in unfair bandwidth allocation among users. We observe that the unbalanced load and unfair bandwidth allocation can be greatly alleviated by intelligently associating users to APs,te rmed association control,ra ther than having users greedily associate APs of best received signal strength. In this study,w e present an e?cient algorithmic solution to determine the user-AP associations that ensure max-min fair bandwidth allocation. We provide a rigorous formulation of the association control problem that considers bandwidth constraints of both the wireless and backhaul links. Our formulation indicates the strong correlation between fairness and load balancing,w hich enables us to use load balancing techniques for obtaining near optimal max-min fair bandwidth allocation. Since this problem is NP-hard, we present algorithms that achieve a constant-factor approximate max-min fair bandwidth allocation. First,we calculate a fractional load balancing solution,where users can be associated with multiple APs simultaneously. This solution guarantees the fairest bandwidth allocation in terms of max-min fairness. Then,b y utilizing a rounding method we obtain an e?cient integral association. In particular,w e provide a 2-approximation algorithm for unweighted greedy users and a 3-approximation algorithm for weighted and bounded-demand users. In addition to bandwidth fairness, we also consider time fairness and we show it can be solved optimally. We further extend our schemes for the on-line case where users may join and leave. Our simulations demonstrate that the proposed algorithms achieve close to optimal load balancing and max-min fairness and they outperform commonly used heuristic approaches.
|Medium Access Control|
A Scalable Model for Channel Access Protocols in Multihop Ad Hoc Networks,
Marcelo Carvalho, J. J. Garcia-Luna-Aceves (University of California, Santa Cruz, USA)
A new modeling framework is introduced for the analytical study of medium access control (MAC) protocols operating in multihop ad hoc networks. The model takes into account the ect of physical-layer parameters on the success of transmissions, the MAC protocol on the likelihood that nodes can access the channnel, and the connectivity of nodes in the network. A key feature of the model is that nodes can be modeled individually, i.e., it allows a per-node setup of many layer-specic parameters. Moreover, no spatial probability distribution or a particular arrangement of nodes is assumed; the model allows the computation of individual (per-node) performance metrics for any given network topology and radio channel model. To show the applicability of the modeling framework, we model multihop ad hoc networks using the IEEE 802.11 distributed coordination function and validate the results from the model with discrete- event simulations in Qualnet. The results show that our model predicts results that are very close to those attained by simulations, and requires seconds to complete compared to several hours of simulation time.
Exploiting Medium Access Diversity in Rate Adaptive Wireless LANs,
Zhengrong Ji, Yi Yang, Junlan Zhou, Mineo Takai, Rajive Bagrodia (University of California at Los Angeles, USA)
Recent years have seen the growing popularity of multi-rate wireless network devices (e.g., 802.11a cards) that can exploit variations in channel conditions and improve overall network throughput. Concurrently, rate adaptation schemes have been developed that selectively increase data transmissions on a link when it offers good channel quality. In this paper, we propose a Medium Access Diversity (MAD) scheme that leverages the benefits of rate adaptation schemes by aggressively exploiting multiuser diversity. The basic mechanism of MAD is to obtain instantaneous channel condition information from multiple receivers and selectively transmit data to a receiver that improves the overall throughput of the network, while maintaining temporal fairness among multiple data flows. We identify and address the challenges in the design and implementation of MAD's three phases: channel probing, data transmission, and receiver scheduling. We also use analytical models to examine the tradeoff between network performance improvement and overhead of channel probing, and derive an asymptotic performance bound for the receiver scheduling algorithms used by MAD. Results from the analysis and the extensive simulations demonstrate that, on average, MAD can improve the overall throughput of IEEE 802.11 wireless LANs by 50% as compared with the best existing rate adaptation scheme.
On Using Battery State for Medium Access Control in Ad hoc Wireless Networks,
Jayashree Subramanian, Manoj Bs, Siva Ram Murthy (Indian Institute of Technology, Madras, India)
One of the challenging issues in the energy-constrained ad hoc wireless networks is to nd ways that increase their lifetime. Squeezing maximum energy from the battery of the nodes of these networks requires the communication protocols to be designed such that they are aware of the state of the batteries. Traditional MAC protocols for ad hoc networks are designed without considering the battery state. Major contributions of this paper are: (a) a novel distributed Battery Aware Medium Access Control (BAMAC(k)) protocol that takes benet of the chemical properties of the batteries, to provide fair scheduling and increased network and node lifetime through uniform discharge of batteries, (b) a discrete time Markov chain analysis for batteries of the nodes of ad hoc wireless networks, and (c) a thorough comparative study of our protocol with IEEE 802.11 and DWOP (Distributed Wireless Ordering Protocol) MAC protocols. The key idea proposed in this paper is to piggy-back nodes' battery-state information with the packets sent by the nodes by means of which the nodes are scheduled to ensure a uniform battery discharge. We model the operation of the battery using a discrete time Markovian chain. Using the theoretical analysis, we calculate lifetime of the battery in terms of maximum number of packets that a node can transmit before its battery drains fully. Extensive simulations have shown that our protocol extends the battery lifetime consuming 96% and 60% less percentage nominal capacity spent per packet transmission compared to the IEEE 802.11 and the DWOP MAC protocols, respectively. In general, performance results show that BAMAC(k) outperforms IEEE 802.11 and DWOP MAC protocols, in terms of power consumption , fairness, and lifetime of the nodes. We have also analyzed the factors that in uence the uniform discharge of batteries and their lifetime.