We present AcouBLE, the first system to significantly reduce the BLE tag’s RF front-end energy consumption while preserving standard BLE operation, backward compatibility, and one-to-one deployability. At its core is clock-seeding, a new paradigm that offloads the generation of the high-frequency MHz clock from the energy-constrained tag to the central (smartphone). The smartphone transmits a low-frequency audio signal that the tag transforms into a clean, ultra-low-jitter reference clock–eliminating the most energy-expensive component of a BLE connection event.Our design combines a novel digital-analog upconversion pipeline that converts a kHz audio tone into a stable 32 MHz clock with a lightweight feedback protocol to implement clock-seeding on commodity BLE chips without modifying the BLE stack or requiring privileged access on the central. A full prototype demonstrates up to 5.9X energy savings in Connected mode, while maintaining RF performance, seamless deployability, and backward compatibility.

Edge cloud technologies enable faster and more energy-efficient processing of user requests on servers located at the network’s edge. However, when compared to the cloud, edge resources are significantly more limited, prompting a critical question: as user requests arrive, how to determine which ones to allocate to the edge and which ones to the cloud. Additionally, to ensure a quality of service that considers task priorities, it is essential to reserve available resources for potential high-priority requests. This introduces a fundamental trade-off: reserving excessive computing resources at the edge, in anticipation of high-priority requests, is incompatible with reducing energy consumption. Conversely, allocating all edge resources may push higher-priority, potentially more delay-sensitive tasks into the cloud.To tackle this intricate problem, we present a multi-objective reinforcement learning approach utilizing a modified Q-learning process. This approach facilitates intelligent resource allocation, striking a careful balance between fulfilling high-priority requests and minimizing unused processing capacity. While the multi-objective agent ensures the satisfaction of high-priority services, it optimally utilizes the edge resources. Additionally, we introduce a framework for adapting the two cost components to specific requirements, favoring one objective over the other, and examining their impact on relevant metrics. Results demonstrate that this specialized strategy outperforms a conventional First Come First Served baseline, as well as a myopic strategy, which represents the unmodified Q-learning process, across these metrics.

We propose ColorUAV, a genetic algorithm for UAV path planning under multiple constraints. Our solution enables drones to travel towards a destination point while avoiding obstacles and navigating as close as possible to base stations in order to maximize communication opportunities. ColorUAV learning phase creates UAVs able to interact with their environment and compute paths whose weight is within 17% of the optimal. More interestingly, our trained UAVs are capable of adapting to moderate changes in the environment without re-training and while remaining efficient in terms of the path quality.

We present SmartPhOx, a pure camera-and-flashlight smartphone-based pulse oximetry solution. We build on the ratio-of-ratios (RR) method and linear regression, an elegant approach resting on the Beer-Lambert law and landing itself to efficient smartphone implementations. However, its implementations without specialized hardware have so far proved to be unsuitable for clinical use, in particular due to the instability of the RR measurements. We use an empirical study to shed light on the reasons why and propose using the very RR measurements to filter RR measurements – a new paradigm we call the Meta-Region of interest (Meta-ROI). We design a complete-system architecture, including a novel data structure for storing and RR values in the time and space dimensions and an efficient algorithm for identifying Meta-ROI. Results from an Android implementation of SmartPhOx with the participation of 37 volunteers show that it is the first pure camera-and-flashlight solution to meet the FDA requirement for Root Mean Square Error (RMSE).

As part of its ongoing effort to standardize 5G and become a key enabler of the Internet of Things, 3GPP introduced NB-IoT – an LPWAN access technology for massive Machine Type Communications (mMTC) – in Release 13. Rooted in LTE, NB-IoT introduces several innovation aimed at meeting the 5G IoT requirements, especially in terms of capacity. Already a commercial success with 94 deployments in over 35 countries, the performance of NB-IoT remains, however, poorly understood.In this paper, we introduce a theoretical model based on M/D/1-PS queues for assessing the performance of NB-IoT as function of different network settings and protocol configurations. Our model is the first to accurately capture the random access procedure for connection establishment (the contention phase) and the entire communicate process, with signalling, connection release and uplink, downlink messages (the congestion phase).After using simulations to demonstrate its accuracy, we use our model to assess the performance of NB-IoT as function of its key parameters. Our analysis reveals a) the NPRACH/NPUSCH ratio has to be chosen carefully and take into account the traffic distribution, and b) for small packet sizes, the NB-IoT signalling becomes a significant bottleneck to the number of UEs that can be supported.

The Narrowband Internet Of Things, better known by the acronym NB-IoT, is spearheading 3GPP’s effort to address the massive Machine Type Communication (mMTC) segment of 5G. With 103 deployments in more than 40 countries, NB-IoT’s performance in terms of cell capacity and coverage is well established. However, the performance it can offer in terms of battery life, a foundational requirement of IoT, has received little attention. In this paper, we introduce the first theoretical model based on the M/D/H/K queues capable of evaluating the energy performance of NB-IoT in advanced cell scenarios defined by a coverage distribution, a payload uplink and downlink size, and an incoming communication rate. After using the values computed by 3GPP for single-terminal cells to demonstrate its accuracy, we use our model to evaluate the NB-IoT’s energy performance. Our analysis reveals that a) Early Data Transmission, originally designed for improving the latency and connection density, can also significantly improve the energy performance, and b) When the load in multi-terminal cell settings increases, the terminal battery lifetime collapses. Leveraging our model, we introduce a solution requiring no changes to the standard and show that it significantly improves the terminal battery life.

IEEE 802.11ad is the first standard capable of delivering Gigabit capacities in a WLAN setting by exploiting mmWave frequencies. Its key innovation is the Sector Level Sweep, a procedure for establishing directional links over mmWave by sweeping over a pre-computed set of phased-array antenna sectors. Crucial to the performance of IEEE 802.11ad networks and involving an exponentially-large search space, the sector design is left open to implementation. As a result, several sector designs have been introduced that are aimed at maximizing the SNR of a given direct link while ignoring the interference projected to other links. If highly competitive in small deployments, a sector design that does not take interference into account can lead to poor overall performance in multi-AP deployments.We present IASSEN, the first approach to Interference-Aware Sector deSign in IEEE 802.11ad Networks. Anchored in an intimate understanding of COTS 802.11ad hardware, IASSEN models the SINR for each network link as function of the low-level parameters driving the sector design. After modeling the problem of interference-aware sector design as an integer nonlinear programming problem, IASSEN introduces a heuristic carefully combining a quick convergence to a local optimum with an approach for avoiding poor local optimum points. A simulation study using measurement-based and realistic sector patterns shows that IASSEN improves overall network performance by as much as 100% when compared to state-of-the-art approaches that do not take interference into account.

We present HandRate, the first smartphone-based system using a standard sensor (accelerometer) for opportunistically computing heart rate while a user holds their phone. Fundamentally, HandRate revisits ballistocardiography (BCG), a century-old technique for monitoring heart activity by measuring the body movement caused by the cardiac cycle. Traditionally performed using custom hardware, attached to a subject's body, revisiting BCG for the smartphone, held in hand, faces several challenges. The hand is an external organ furthest from the aorta and subject to motion artifacts, leading to a weak and noisy signal, while the position the phone is held in can impact which accelerometer axis best captures BCG. HandRate addresses these challenges by introducing a design involving two modules operating in tandem: the first aimed at transforming the accelerometer readings into a single-dimensional signal oblivious to how the phone is held, while the second module making heartbeat predictions based on this signal. Results from testing HandRate using data collected from 18 subjects show that it can estimate heart rate with accuracy similar to or better than systems requiring special sensors and/or active user participation.

In the race for Gigabit wireless links, IEEE introduced 802.11ad, an amendment aimed at delivering Gbps capacities in a WLAN setting by leveraging the 60 GHz band. The key innovation of the standard is its beamforming training protocol. Executed periodically at the beginning of every beacon interval, it enables the formation of directional links. To address contention during the uplink part of beamforming training, 802.11ad introduced A-BFT (Association BeamForming Training), an Aloha-inspired, two-level backoff race. While central to the functionality of 802.11ad networks, the performance of A-BFT, however, remains poorly understood. In this article, we propose an analytical finite-population model for evaluating the performance of IEEE 802.11ad A-BFT under two channel models: loss-free, and a channel introducing a constant bit error rate. After using an open-source simulator to demonstrate its accuracy, we use our model to assess the performance of A-BFT. We find that a counter-intuitive, quit-easily/be-lazy approach by the stations leads to the best overall beamforming training performance.

The recent standardization by IEEE of Fine Timing Measurement (FTM), a time-of-flight based approach for ranging has the potential to be a turning point in bridging the gap between the rich literature on indoor localization and the so-far tepid market adoption. However, experiments with the first WiFi cards supporting FTM show that while it offers meter-level ranging in clear line-of-sight settings (LOS), its accuracy can collapse in non-line-of-sight (NLOS) scenarios. We present FUSIC, the first approach that extends FTM's LOS accuracy to NLOS settings, without requiring any changes to the standard. To accomplish this, FUSIC leverages the results from FTM and MUSIC - both erroneous in NLOS - into solving the double challenge of 1) detecting when FTM returns an inaccurate value and 2) correcting the errors as necessary. Experiments in 4 different physical locations reveal that a) FUSIC extends FTM's LOS ranging accuracy to NLOS settings - hence, achieving its stated goal; b) it significantly improves FTM's capability to offer room-level indoor positioning.

With the exponential increase in wireless data traffic risking to overwhelm the current networking infrastructures, mmWave networking is seen as on of the most promising paths out of the logjam. IEEE introduced a new standard recently, 802.11ad, that uses mmWave frequencies for delivering multi-Gigabit capacities in a WLAN setting. Such capacities, however, do not come for free: mmWave frequencies have poor propagation characteristics and suffer from blockage, whose consequences on the networking protocols are not fully understood.In this paper, we aim at in-depth understanding of two key primitives in 802.11ad networks in environments rich with blockage: user association and reliability. Using careful measurements on COTS hardware, we find that user association under blockage takes an unreasonably long time, and, after analyzing the causes, provide practical insights on how to reduce this time by an order of magnitude. Relying on a multi-layer tracing tool allowing unprecedented granularity in the analysis of 802.11ad networks, we find that the part of the new standard regarding reliability is underspecified leading to different interpretations in practice. Their potential impact on performance is then evaluated using trace-based simulations, which reveal an interesting throughput-reliability tradeoff. Finally, we find that TCP is poorly prepared for sudden changes in round-trip timeouts, as those induced by link blockage in mmWave networks, leading to an unnecessary increase in timeouts.

In this work, we present COLiDeR, the first practical system for two-path relaying using off-the-shelf half-duplex radios. While two-path relaying has been mostly studied from a theoretical perspective in the literature, our solution addresses the challenges of making it practical by introducing two key contributions. First, using a measurement-driven approach, we identify the best approach for a radio to handle two overlapping signals. Just as important, we carefully quantify its limits and introduce the concept of the decoding areas. Second, we introduce a cross-layer protocol that seamlessly navigates the decoding areas with the objective of maximizing throughput while minimizing decoding failures. Experiments on a 4-USRP testbed show that COLiDeR delivers between 80-95% of the relaying performance of an ideal full-duplex radio while incurring negligible decoding failures.

Physical-Layer Network Coding (PLNC) was first introduced as a solution to increase the throughput of a two-way relay channel communication. Unlike most wireless communication techniques which try to avoid collisions, PLNC allows two simultaneous transmissions to a common receiver. In basic topologies, this technique has been shown to significantly enhance the throughput performance compared to classical interference-free communications. However, quantifying the impact of PLNC in large multi-hop networks remains an open question. In this work, we introduce the first theoretical framework that, given a particular network topology and traffic matrix, can evaluate the optimal network throughput subject to a fairness constraint relative to the initial demand of each flow, when PLNC is adopted. Based on linear programming, our solution ensures to respect the particularities imposed by PLNC. We use this framework to evaluate three state-of-the-art PLNC schemes across a variety of topologies and traffic matrices. Our numerical analysis reveals that while in simple toy topologies PLNC can significantly increase the network throughput, in large topologies the verdict is mixed. For certain topologies and traffic patterns adopting PLNC can double the throughput while in others, depending on the scheme used for implementing PLNC, the gain can be as high as 60 percent or as low as 0 percent when compared to traditional interference-free transmissions.

Today, we can use our smartphones to drive from Los Angeles to New York, yet we can not use them to find our way around Charles de Gaulle Airport. GPS simply does not work indoors and while outside areas are mapped very well, the indoors of most buildings remain a mystery to our favorite navigation apps. While the problem of indoor localization has attracted a lot of attention, with several solutions with meter-level accuracy emerging as research prototypes, the problem of building accurate and detailed indoor maps has been neglected. We present InPReSS, a solution for dynamic indoor map construction without explicit user input. It leverages the sensors available on off-the-shelf smartphones and their ubiquity to construct floor plans as users go about their daily business. The InPReSS approach consists of four steps: 1. Collecting readings from five sensors, tagged with their location from smartphones available in the target building, and divide the floor plan into cells using a Voronoi diagram. 2. Clustering the cells into rooms based on the sensor readings. 3. Identifying doors and ways between adjacent rooms using the Voronoi diagram and user movement traces. 4. Building a two-level graph of the floor plan for navigation.

We present PCach, a smartphone application designed to relieve the congestion in cellular networks resulting from the exponential growth of mobile data traffic. The basic idea underlying PCach is simple: use Wi-Fi to proactively cache content on the smartphone's memory, which otherwise would have been delivered through the cellular network during the next Wi-Fi coverage time gap. However, it leads to several challenging questions, including how much mobile data actually flows through cellular networks, how much data can be precached, and when and what to pre-cache. By analysing the extensive MACACO measurement dataset, our analysis shows that the median smartphone user transfers 15% of her data via the cellular network and that up to 80% of it could be pre-cached via Wi-Fi. From our empirical observations, we introduce an algorithm that can run stand-alone on off-the-shelf smartphones and predict with good accuracy when and what to pre-cache.

We revisit Physical-Layer Network Coding (PLNC) and the reasons preventing it from becoming a staple in wireless networks. We identify its strong coupling to the Two-Way Relay Channel (TWRC) as key among them due to its requiring crossing traffic flows and two-hop node coordination. We introduce SE-PLNC, a Source-Encoded PLNC scheme that is traffic pattern independent and involves coordination only among one-hop neighbors, making it significantly more practical to adopt PLNC in multi-hop wireless networks. To accomplish this, SE-PLNC introduces three innovations: it combines bit-level with physical-level network coding, it shifts most of the coding burden from the relay to the source of the PLNC scheme, and it leverages multi-path relaying opportunities available to a particular traffic flow. We evaluate SE-PLNC using theoretical analysis, proof-of-concept implementation on a Universal Software Radio Peripherals (USRP) testbed, and simulations. The theoretical analysis shows the scalability of SE-PLNC and its efficiency in large ad-hoc networks while the testbed experiments its real-life feasibility. Large-scale simulations show that TWRC PLNC barely boosts network throughput while SE-PLNC improves it by over 30%.

We investigate the potential gains of Physical-Layer Network Coding (PLNC) in multi-hop wireless networks. Physical-Layer Network Coding was first introduced as a solution to increase the throughput of a two-way relay channel communication. Unlike most wireless communications techniques which try to avoid collisions, PLNC allows two simultaneous transmissions to a common receiver. Such transmitted messages are summed at signal level and then decoded at packet level. In basic topologies, Physical-Layer Network Coding has been shown to significantly enhance the throughput performance compared to classical communications. However, the impact of PLNC in large multi-hop networks remains an open question. We therefore exploit Linear Programming to evaluate the impact of this paradigm in large realistic radio deployments. Our numerical results show that PLNC can increase the throughput in large multi-hop topologies by 30%. Such gains set theoretical benchmarks for designing new access methods and routing protocols to efficiently exploit the Physical-Layer Network Coding concept.

Physical-Layer Network Coding (PLNC) was first introduced as a solution to increase the throughput in simple bidirectional communication schemes. Unlike most wireless communication techniques which try to avoid collisions, PLNC allows two simultaneous transmissions to a common receiver. In this work, we propose a MAC layer distributed and realistic scheduling policy targeting PLNC based networks. In order to easily operate in large ad-hoc networks, our solution is completely decentralized and runs in constant time. By basing the transmission priority of every node on the queue sizes of its local neighbors and PLNC opportunities, our solution ensures high throughput when compared to classical interference-free scheduling. Both our theoretical analysis corroborated by our simulation results highlight that the proposed algorithm outperforms existing scheduling policies with throughput gains of around 35%.

We present Acrux, the first indoor localization system to achieve meter level accuracy while relying exclusively on a single fix and the sensors commonly found in off-the-shelf smartphones. Acrux uses dead-reckoning, the approach that gives probably the best chance at a completely autonomous indoor localization system. Unfortunately, it has not been mastered on smartphones beyond a few dozen meters due to its inherent integration drift. As a result, all dead-reckoning based solutions in literature require periodic recalibration using input from outside -- attaching strings preventing indoor localization from becoming mainstream. While it is virtually impossible to completely eliminate integration drift, Acrux is the first solution to succeed in dead-reckoning with meter level accuracy for several hundred meters, enough to relax the requirement for periodic recalibration in most indoor scenarios. To accomplish this, Acrux replaces step-counting, the standard approach for measuring distance using sensors, with an approach that measures the speed of locomotion. Although a straightforward accurate estimation of motion speed using the erroneous sensors found on smartphones is infeasible, Acrux combines a novel approach with measurement based analysis to achieve that. Leveraging its excellent dead-reckoning capability, Acrux is shown to provide indoor localization with median error between SI0.7 meter and SI1.2 meter and 98% percentile error of SI3 meter in a dozen of scenarios in 4 different buildings -- without any recalibration.

Studies have shown that in places like New York City drivers often spend over 20 min looking for parking, contributing to as much as 30% of the total traffic. In response, cities like San Francisco have deployed systems capable of pointing drivers to the closest available parking spot. Unfortunately, such systems have gained little traction as they rely on specialized infrastructure that is expensive to build and maintain. We present SmartPark, a smartphone based system that relaxes the requirement for specialized infrastructure by relying on the smartphone's sensors and ubiquitous Wi-Fi and cellular infrastructure. To accomplish this, SmartPark addresses two major challenges, under the constraint of minimum impact on battery life: automatic transportation mode detection and location matching. Solved together, they enable SmartPark to automatically detect when a user pulls out of a parking spot, making it available again. It addresses each challenge using a combination of thorough statistical analysis of the sensor readings and a novel Random Forest based classification algorithm. Experimental results from 12 volunteers, using 7 different smartphones, in 3 different cities show that SmartPark can distinguish 9 different transportation modes with accuracy between 95.57-100%, enabling it to correctly detect unparking events virtually 100% of the time. This is accomplished with a minimum impact on battery life-running SmartPark on a fully charged LG Google Nexus 5 for 5 h straight caused the battery level to drop only about 4%.

With the world population becoming increasingly urban and the multiplication of mega cities, urban leaders have responded with plans calling for so called smart cities relying on instantaneous access to information using mobile devices for an intelligent management of resources. Coupled with the advent of the smartphone as the main platform for accessing the Internet, this has created the conditions for the looming wireless bandwidth crunch.

Recent years have seen the advent of energy conservation as a key engineering and scientific challenge of our time. At the same time, most IP networks are typically provisioned to 30%-40% average utilization, leading to a significant waste of energy. Current approaches for creating more frugal networks rely on instantaneous and global knowledge of the traffic matrix and network congestion levels - a requirement that can be impractical for many network operators. We introduce a new traffic-agnostic metric for quantifying the quality of a frugal topology, the Adequacy Index (ADI).We show that the problem of minimizing the power consumption of a network subject to a given ADI threshold is NP-hard and present two polynomial time heuristics - ABStAIn and CuTBAck. We perform extensive simulations using topologies and traffic matrices from 3 real networks. Our results show that ABStAIn and CuTBAck are as effective as an exponential time traffic based solution at creating frugal topologies and outperform a state of the art polynomial time traffic based solution by about 80%. Furthermore, the median link utilization observed with ABStAIn and CuTBAck is similar to that with traffic based solutions, with the maximum link utilization never exceeding 80%.

Transmission count, the number of transmissions required for delivering a data packet over a link, is part of almost all state-of-the-art routing metrics for wireless networks. In traditional networks, peer-to-peer interference and channel errors are what define its value for the most part. In cognitive radio networks, however, there is a third culprit that can impact the transmission count: primary user interference. It may be tempting to think of primary user interference as no different than interference caused by other peers. However, unlike peers, primary users do not follow the same protocol and have strict channel access priority over the secondary users. Motivated by this observation, we carry out an empirical study on a USRP testbed for analyzing the impact of primary users. Our measurements show that a primary user has a distinct impact on the transmission count, which the de facto standard approach, ETX, designed for traditional networks, fails to capture. To resolve this, we present COExiST (for COgnitive radio EXpected transmISsion counT): a link metric that accurately captures the expected transmission count over a wireless link subject to primary user interference. Extensive experiments on a five-node USRP testbed demonstrate that COExiST accurately captures the actual transmission count in the presence of primary users -- the 80th percentile of the error is less than 20%.

We address the problem of routing for extending the service life of satellites in Iridium-like LEO constellations. Satellites in LEO constellations can spend over 30% of their time under the earth's umbra, time during which they are powered by batteries. While the batteries are recharged by solar energy, the depth of discharge they reach during eclipse significantly affects their lifetime - and by extension, the service life of the satellites themselves. For batteries of the type that power Iridium satellites, a 15% increase to the depth of discharge can practically cut their service lives in half. We present two new routing metrics - LASER and SLIM - that try to strike a balance between performance and battery depth of discharge in LEO satellite constellations. Our basic approach is to leverage the deterministic movement of satellites for favoring routing traffic over satellites exposed to the sun as opposed to the eclipsed satellites, thereby decreasing the average battery depth of discharge - all without adversely affecting network performance. Simulations show that LASER and SLIM can reduce the depth of discharge by about 11% and 16%, respectively, which can lead to as much as 100% increase in the satellite batteries lifetime. This is accomplished by trading off very little in terms of end-to-end delay.

Energy efficiency has emerged as a defining scientific and engineering challenge of our time. Ethernet, as the dominant wireline technology, has been a focus of intense research and development efforts with the goal of significantly decreasing its energy consumption. In 2010 the IEEE Std 802.3az, which uses a Low Power Idle (LPI) mode to reduce the energy consumption of a link when there is no data traffic, was approved. Recently, the major manufacturers have brought to market the first switches the implement the new energy efficient standard. In this paper, we make use of the first generation of hardware that support the IEEE 802.3az to get a better understanding of the behavior of energy efficient mechanisms for ethernet. Based on measurement on DLINK switches that are IEEE 802.3az compliant, we build a power model that reflects more accurately the power used by real hardware in practice. We use the measurement-driven power model to analyze the behavior of Lazy Start, the state of the art algorithm for energy efficient ethernet, in the ns-3 simulator. Based on our analysis, we provide recommendations for improvements and potential directions for future work.

TDMA MAC protocols suffer from two draw-backs that have reduced its practical appeal, especially for infrastructure-less wireless networks: the need for time synchronization, and the use of Jrames. While there has been extensive research towards achieving the required time synchronization, the frames are assumed to be inherent in TDMA. In this paper we present a framework for frameless TDMA based on a new concept we refer to as a slot chain. A slot chain is a series of slots with a starting slot and inter-slot period that is chosen to match a given capacity request. The key challenge in using slot chains instead of frames is ensuring that slot chains representing arbitrary capacity requests are conflict free. We present an algorithm for interleaving slot chains in a conflict-free manner. The algorithm is optimal for a class of requests called geometric and is z-approximate for general requests, where z can be made arbitrarily small. We show that any TDMA MAC protocol can readily replace using frames with using slot chains. Our simulation analysis shows that using slot chains results in much better capacity utilization when traffic is heterogeneous - as much as 100% in some cases.

We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer transmissions (including retransmissions) in wireless mesh networks. Unlike previous efforts, such as the popular ETX, we account for the fact that MAC protocols (including the IEEE 802.11 MAC) incorporate a finite number of transmission attempts per packet. This in turn leads to our key observation: the performance of a path depends not only on the number of the links on the path and the quality of its links, but also, on the relative positions of the links on the path. Based on this observation, we propose ETOP, a path metric that accurately captures the expected number of link layer transmissions required for reliable end-to-end packet delivery. We analytically compute ETOP, which is not trivial, since ETOP is a noncommutative function of the link success probabilities. Although ETOP is a more involved metric, we show that the problem of computing paths with the minimum ETOP cost can be solved by a greedy algorithm. We implement and evaluate a routing approach based on ETOP on a 25-node indoor mesh network. Our experiments show that the path selection with ETOP consistently results in superior TCP goodput (by over 50 percent in many cases) compared to path selection based on ETX. We also perform an in-depth analysis of the measurements to better understand why the paths selected by ETOP improve the TCP performance.

In this paper, we propose a new metric that is applicable both to routing and rate adaptation in multi-rate wireless mesh networks. Unlike many previous efforts, our metric is comprehensive; it considers several factors that affect end-to-end performance such as the effect of the relative positions of the links on a path when choosing the rates of operation and the importance of avoiding congested areas. We call our metric ETM (for Expected Transmission cost in Multi-rate wireless networks). We analytically derive the ETM metric. We show that the ETM metric can be used (a) to determine the best end-to-end path with a greedy routing approach and (b) it can be used to dynamically select the best transmission rate for each link on the path via a dynamic programming approach. Based on ETM, we design and implement the ETM-framework on an indoor wireless mesh network and compare its performance with that of the popular ETT and the recently proposed ETOP metrics. Our experiments show that the ETM-framework yields throughput improvements of up to 253% and 368% as compared with the ETT and ETOP frameworks.

With fully directional communications, nodes must track the positions of their neighbors so that communication with these neighbors is feasible when needed. Tracking process introduces an overhead, which increases with the number of discovered neighbors. The overhead can be reduced if nodes maintain only a subset of their neighbors; however, this may increase the length of paths between node pairs in the network. In this work, we study the tradeoffs between node degree and path stretch. We first design a topology control algorithm to optimize this tradeoff. Assuming that nodes communicate with their directional neighbors using circular directional transmissions, we model the original graph as a unit disk graph (UDG). Given a UDG G, our algorithm finds a sparse subgraph G' with a maximum degree of 6, and connecting each node pair u,v by a path of length hopsG(u, v) = O(hopsG(u, v) + log Delta), where Delta is the maximum degree in G, hopsG'(u, v) denotes length of the shortest path between u, v in G. We show that this result is near-optimal. Based on the insights gained from this design, we next construct a simpler, more practical scheme that integrates fully-directional neighbor discovery and maintenance with topology control strategy. We simulate both algorithms and compare their performances.

We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer transmissions (including retransmissions) in wireless mesh networks. Unlike previous efforts, such as the popular ETX, we account for the fact that MAC protocols (including the IEEE 802.11 MAC) incorporate a finite number of transmission attempts per packet. This in turn leads to our key observation: the performance of a path depends not only on the number of the links on the path and the quality of its links, but also, on the relative positions of the links on the path. Based on this observation, we propose ETOP, a path metric that accurately captures the expected number of link layer transmissions required for reliable end-to-end packet delivery. We analytically compute ETOP, which is not trivial, since ETOP is a noncommutative function of the link success probabilities. Although ETOP is a more involved metric, we show that the problem of computing paths with the minimum ETOP cost can be solved by a greedy algorithm. We implement and evaluate a routing approach based on ETOP on a 25-node indoor mesh network. Our experiments show that the path selection with ETOP consistently results in superior TCP goodput (by over 50% in many cases) compared to path selection based on ETX. We also perform an in-depth analysis of the measurements to better understand why the paths selected by ETOP improve the TCP performance.

In this paper, we propose a new Medium Access Control (MAC) protocol for full exploitation of directional antennas in wireless networks. The protocol introduces a circular directional transmission of the Request To Send (RTS) control packet, spreading around a station information about the intended communication. The stations that receive the directional RTS, using a simple scheme of tracking the neighbors' directions, defer their transmission toward the beams that could harm the ongoing communication. In this way, the proposed protocol takes advantage of the benefits of directional transmissions as the increase of spatial reuse and of coverage range. Additionally, it reduces the hidden-terminal problem, as well as the deafness problem, two main factors for the decrease of the efficiency of directional transmissions in ad hoc networks. The performance evaluation of the protocol shows that it offers a significant improvement in static, as well as mobile, scenarios, as compared to the performance of the proposed protocols that use omnidirectional or directional transmissions.

We revisit the problem of computing the path with the minimum cost in terms of the expected number of link layer retransmissions in wireless mesh networks. Unlike previous efforts (such as the popular ETX) we account for the fact that link layer protocols (such as the IEEE 802.11 MAC) incorporate a non-zero but finite number of retransmission attempts per packet. A key observation that motivates this work is that the performance of a path depends not only on the number of links on the path and their qualities, but also on the relative positions of the links on the path. In particular, the closer a lossy link to the destination, the higher is its impact on the performance of that path. We design a new path metricthat captures all of the above factors and we call this metric ETOP. In this paper, we provide a synopsis of the analytical computation of ETOP. We also implement a routing strategy based on ETOP on a 25-node experimental testbed and provide sample results to showcase the performance with ETOP.

Cooperative diversity facilitates spatio-temporal communications without requiring the deployment of physical antenna arrays. While physical layer studies on cooperative diversity have been extensive, higher layer protocols which translate the achievable reduction in the SNR per bit for a given target BER, into system wide performance enhancements are yet to mature. The challenge is that appropriate higher layer functions are needed in order to enable cooperative diversity at the physical layer. We focus on network-wide broadcasting with the use of cooperative diversity in ad hoc networks. We design a novel distributed network-wide broadcasting protocol that takes into account the physical layer dependencies that arise with cooperative diversity. We perform extensive simulations that show that our protocol can outperform the best of the noncooperative broadcasting protocols by: (a) achieving up to a threefold increase in network coverage and, (b) by decreasing the latency incurred during the broadcast by about 50%. We also construct an analytical model that captures the behavior of our protocol. Furthermore, we show that computing the optimal solution to the cooperative broadcast problem is NP-complete and construct centralized approximation algorithms. Specifically, we construct an O(Nepsi)-approximation algorithm with a computational complexity of O(N4/epsi); we also construct a simpler greedy algorithm.. The costs incurred with these algorithms serve as benchmarks with which one can compare that achieved by any distributed protocol

Space-time communications can help combat fading and, hence, can significantly increase the capacity of ad hoc networks. Cooperative diversity or virtual antenna arrays facilitate spatio-temporal communications without actually requiring the deployment of physical antenna arrays. Virtual MISO entails the simultaneous transmission of appropriately encoded information by multiple nodes to effectively emulate a transmission on an antenna array. We present a novel multilayer approach for exploiting virtual MISO links in ad hoc networks. The approach spans the physical, medium access control and routing layers, and provides 1) a significant improvement in the end-to-end performance in terms of throughput and delay and 2) robustness to mobility and interference-induced link failures. The key physical layer property that we exploit is an increased transmission range due to achieved diversity gain. Except for space-time signal processing capabilities, our design does not require any additional hardware. We perform extensive simulations to quantify the benefits of our approach using virtual MISO links. As compared to using only SISO links, we achieve an increase of up to 150 percent in terms of the end-to-end throughput and a decrease of up to 75 percent in the incurred end-to-end delay. Our results also demonstrate a reduction in the route discovery attempts due to link failures by up to 60 percent, a direct consequence of the robustness that our approach provides to link failures

Many MAC sub-layer protocols for supporting the usage of directional antennas in ad hoc networks have been proposed in literature. However, there remain two open issues that are yet to be resolved completely. First, in order to fully exploit the spatial diversity gains possible due to the use of directional antennas, it is essential to shift to the exclusive usage of directional antennas for the transmission and reception of all the MAC layer frames. This would facilitate maximal spatial reuse and will efface the phenomena of asymmetry in gain. Second, in the presence of mobility the MAC protocol should incorporate mechanisms by which a node can efficiently discover and track its neighbors. In this paper we propose PMAC, a new MAC protocol that addresses both the issues in an integrated way. PMAC incorporates an efficient mechanism for neighbor discovery, and a scheduling based medium sharing that allows for exclusive directional transmissions and receptions. We perform analysis and simulations to understand the performance of our scheme. We find that each node, on average, can achieve a per node utilization of about 80% in static and about 45% in mobile scenarios. In terms of throughput, our protocol is seen to outperform both the traditional IEEE 802.11 and previously proposed MAC protocols for use with directional antennas in ad hoc networks

Space-time communications can help combat fading and hence can significantly increase the capacity of ad hoc networks. Cooperative diversity or virtual antenna arrays facilitate spatio-temporal communications without actually requiring the deployment of physical antenna arrays. Virtual MISO entails the simultaneous transmission of appropriately encoded information by multiple nodes to effectively emulate a transmission on an antenna array. We present a novel multi-layer approach for exploiting virtual MISO links in ad hoc networks. The approach spans the physical, medium access control and routing layers and provides: (a) a significant improvement in the end-to-end performance in terms of throughput and delay and, (b) robustness to mobility and interference induced link failures. The key physical layer property that we exploit is an increased transmission range due to achieved the diversity gain. Except for space-time signal processing capabilities, our design does not require any additional hardware. We perform extensive simulations to quantify the benefits of our approach using virtual MISO links. As compared to using only SISO links, we achieve an increase of up to 150% in terms of the end-to-end throughput and a decrease of up to 75% in the incurred end-to-end delay. Our results also demonstrate a reduction in the route discovery attempts due to link failures by up to 60%, a direct consequence of the robustness that our approach provides to link failures.

With directional antennas, it is extremely important that a node maintains information with regards to the positions of its neighbors. This would allow the node to "track" the neighbors as they move; otherwise, a node will have to resort to either omnidirectional or circular directional transmissions (or receptions) fairly often. This can be overhead intense and can reduce spatial reuse. Maintaining directional information with regards to a large number of neighbors can itself be expensive; therefore it is important to limit a node's degree. We propose a topology control scheme (Di-ATC) that works with fully directional communications and offers a low degree bound while preserving network connectivity. The key idea is to execute Di-ATC on the discovered neighbors to select and maintain connectivity with only a subset of these neighbors. The members of this subset are those with high angular separations. We perform extensive simulations and demonstrate that our scheme effectively limits node degree while at the same time, preserves network connectivity and achieves low path stretch

Efficient routing protocols can provide significant benefits to mobile ad hoc networks, in terms of both performance and reliability. Many routing protocols for such networks have been proposed so far. Amongst the most popular ones are dynamic source routing (DSR), ad hoc on-demand distance vector (AODV), temporally-ordered routing algorithm (TORA) and location-aided routing (LAR). Despite the popularity of those protocols, research efforts have not focused in evaluating their performance when applied to large-scale wireless networks. Such networks are comprised of hundreds of nodes, connected via long routes. This greatly affects the network efficiency, since it necessitates frequent exchange of routing information. In this paper we present our observations regarding the behavior of the above protocols, in large-scale mobile ad hoc networks (MANETs). We consider wireless mobile terminals spread over a large geographical area, and we perform extensive simulations, using the QualNet and NS-2 simulators. The results of the simulations yield some interesting conclusions: AODV suffers in terms of packet delivery fraction (PDF) but scales very well in terms of end-to-end delay. DSR on the other hand scales well in terms of packet delivery fraction but suffers an important increase of end-to-end delay, as compared to its performance achieved in small-scale topologies. Also, the effect of maximum connections is severe on TORA, which seems unable to route large amounts of traffic. LAR, seems to scale very well, in terms of all metrics employed

Our objective in this paper is to design topology control algorithms such that (i) nodes have low degree and (ii) paths in the network have few hops. Low node degree is desirable in networks equipped with smart antennas and to reduce access contention. Short paths are desirable for minimizing communication delays and for better robustness to channel impairments and to mobility. Given any arbitrary unit-disc graph G representing all feasible links, our algorithms find a sparse subgraph G' having a maximum node degree of six and, for each pair of vertices u, v, having hopsG'(u, v) = O(hopsG(u,v) + logDelta), where Delta is the maximum node degree in G and hopsG(u, v) denotes the shortest path length from u to v in G. This result is near-optimal: (i) there is a connected UDG G in which no connected subgraph has degree less than five, and (ii) for any graph G, any bounded-degree subgraph G' must have hopsG'(u, v) = Omega(hopsG(u, v) + logDelta) for some u, v. Our distributed algorithm scales, preserves link symmetry, does not need node synchronization, and requires only O(n) messages. We perform extensive simulations that quantify the performance of our algorithm in realistic scenarios

The deployment of traditional higher layer protocols (especially the IEEE 802.11 MAC protocol at the MAC layer) with directional antennae could lead to problems from an increased number of collisions; this effect is primarily seen due to three specific effects: (i) an increase in the number of hidden terminals; (ii) the problem of deafness and, (iii) a difficulty in determining the locations of neighbors. In this work we propose a new MAC protocol that incorporates circular RTS and CTS transmissions. We show that the circular transmission of the control messages helps avoid collisions of both DATA and ACK packets from hidden terminals. Our protocol intelligently determines the directions in which the control messages ought to be transmitted so as to eliminate redundant transmissions in any given direction. We perform extensive simulations and analyze the obtained results in order to compare our scheme with previously proposed protocols that have been proposed for use in directional antenna equipped ad hoc networks. Our simulation results clearly demonstrate the benefits of incorporating both circular RTS and CTS messages in terms of the achieved aggregate throughput.

Many MAC sub-layer protocols for supporting the use of directional antennas in ad hoc networks have been proposed. However, there remain two open issues that are yet to be resolved completely. First, in order to exploit fully the spatial diversity gains due to the use of directional antennas, it is essential to shift to the exclusive use of directional antennas for the transmission and reception of all the upper layers frames. This facilitates maximal spatial re-use and effaces the phenomenon of asymmetry in gain. Second, in the presence of mobility, the MAC protocol should incorporate mechanisms by which a node can efficiently locate and track its neighbors. We propose a new polling based MAC protocol that addresses both the issues in an integrated way. We perform analysis and extensive simulations to understand the performance of our scheme in terms of its ability to maintain connectivity, the achieved utilization efficiency, and throughput. We find that each node, on average, can achieve a per node utilization of about 80% in static and about 45% in mobile scenarios. Our protocol is seen to outperform both the traditional IEEE 802.11 MAC protocol and previously proposed protocols for use with directional antennas that provide partial solutions to solve the aforementioned problems. Finally, we also study the sensitivity of our protocol to various system parameters.

Directional antennas in ad hoc networks offer many benefits compared with classical omnidirectional antennas. The most important include significant increase of spatial reuse, coverage range and subsequently network capacity as a whole. On the other hand, the use of directional antennas requires new approach in the design of a MAC protocol to fully exploit these benefits. Unfortunately, directional transmissions increase the hidden terminal problem, the problem of deafness and the problem of determination of neighbors' location. In this paper we propose a new MAC protocol that deals effectively with these problems while it exploits in an efficient way the advantages of the directional antennas. We evaluate our work through simulation study. Numerical results show that our protocol offers significant improvement compared to the performance of omni transmissions.