Vision-language models (VLMs) have achieved impressive progress in natural image reasoning, yet their potential in medical imaging remains underexplored. Medical vision-language tasks demand precise understanding and clinically coherent answers, which are difficult to achieve due to complexity of medical data and the scarcity of high-quality expert annotations. These challenges limit the effectiveness of conventional supervised fine-tuning (SFT) and Chain-of-Thought (CoT) strategies that work well in general domains. To address these challenges, we propose Med-R1, a reinforcement learning (RL)-enhanced VLM designed to improve generalization and reliability in medical reasoning. Med-R1 adopts Group Relative Policy Optimization (GRPO) to encourage reward-guided learning beyond static annotations. We comprehensively evaluate Med-R1 across eight distinct medical imaging modalities. Med-R1 achieves a 29.94% improvement in average accuracy over its base model Qwen2-VL-2B, and even outperforms Qwen2-VL-72B-a model with $36\times $ more parameters. To assess cross-task generalization, we further evaluate Med-R1 on five question types. Med-R1 outperforms Qwen2-VL-2B by 32.06% in question-type generalization, also surpassing Qwen2-VL-72B. We further explore the thinking process in Med-R1, a crucial component of Deepseek-R1. Our results show that omitting intermediate rationales (No-Thinking Med-R1) not only improves cross-domain generalization with less training, but also challenges the common assumption that more reasoning always helps. Nevertheless, we also find that the Think-After Med-R1 variant further improves performance while maintaining interpretability. These findings suggest that, in medical VQA, the mere presence of explicit reasoning does not guarantee better performance. Instead, performance depends on the quality of the reasoning and the position where the reasoning is generated.

Recent studies on large language models (LLMs) and large multimodal models (LMMs) have demonstrated promising skills in various domains including science and mathematics. However, their capability in more challenging and real-world related scenarios like engineering has not been systematically studied. To bridge this gap, we propose EEE-Bench, a multimodal benchmark aimed at assessing LMMs’ capabilities in solving practical engineering tasks, using electrical and electronics engineering (EEE) as the testbed. Our benchmark consists of 2860 hand-picked and carefully curated problems spanning 10 essential subdomains such as analog circuits, control systems, etc. Compared to other domains, engineering problems are intrinsically 1) more visually complex and versatile and 2) less deterministic in solutions. Successful solutions to these problems often demand more-than-usual rigorous integration of visual and textual information as models need to understand intricate images like abstract circuits and system diagrams while taking professional instructions. Alongside EEE-Bench, we provide extensive quantitative evaluations, fine-grained analysis, and improvement methods using 17 widely-used open-and closed-sourced LLMs and LMMs and 7 popular prompting techniques. Our results reveal notable deficiencies in current foundation models for EEE, including an average performance ranging from 19.48% to 46.78% and a tendency toward "laziness" in overlooking essential visual context. In summary, we believe EEE-Bench not only reveals some noteworthy limitations of LMMs but also provides a valuable resource for advancing research on their application in practical engineering tasks, driving future improvements in their capability to handle complex, real-world scenarios. The EEE-Bench is publicly released on this link.

Many companies, including Google, Amazon, and Apple, offer voice assistants as a convenient solution for answering general voice queries and accessing their services. These voice assistants have gained popularity and can be easily accessed through various smart devices such as smartphones, smart speakers, smartwatches, and an increasing array of other devices. However, this convenience comes with potential privacy risks. For instance, while companies vaguely mention in their privacy policies that they may use voice interactions for user profiling, it remains unclear to what extent this profiling occurs and whether voice interactions pose greater privacy risks compared to other interaction modalities. In this paper, we conduct 1171 experiments involving 24530 queries with different personas and interaction modalities during 20 months to characterize how the three most popular voice assistants profile their users. We analyze factors such as labels assigned to users, their accuracy, the time taken to assign these labels, differences between voice and web interactions, and the effectiveness of profiling remediation tools offered by each voice assistant. Our findings reveal that profiling can happen without interaction, can be incorrect and inconsistent at times, may take several days or weeks to change, and is affected by the interaction modality.

Specialized machine learning (ML) models tailored to users’ needs and requests are increasingly being deployed on smart devices with cameras, to provide personalized intelligent services taking advantage of camera data. However, two primary challenges hinder the training of such models: the lack of publicly available labeled data suitable for specialized tasks and the inaccessibility of labeled private data due to concerns about user privacy. To address these challenges, we propose a novel system SpinML, where the server generates customized Synthetic image data to Privately traIN a specialized ML model tailored to the user request, with the usage of only a few sanitized reference images from the user. SpinML offers users fine-grained, object-level control over the reference images, which allows user to trade between the privacy and utility of the generated synthetic data according to their privacy preferences. Through experiments on three specialized model training tasks, we demonstrate that our proposed system can enhance the perfor- mance of specialized models without compromising users’ privacy preferences.

Toxic content detection is crucial for online services to remove inappropriate content that violates community standards. To automate the detection process, prior works have proposed varieties of machine learning (ML) approaches to train Language Models (LMs) for toxic content detection. However, both their accuracy and transferability across datasets are limited. Recently, Large Language Models (LLMs) have shown promise in toxic content detection due to their superior zero-shot and few-shot in-context learning ability as well as broad transferability on ML tasks. However, efficiently designing prompts for LLMs remains challenging. Moreover, the high run-time cost of LLMs may hinder their deployments in production. To address these challenges, in this work, we propose BD-LLM, a novel and efficient approach to bootstrapping and distilling LLMs for toxic content detection. Specifically, we design a novel prompting method named Decision-Tree-of-Thought (DToT) to bootstrap LLMs' detection performance and extract high-quality rationales. DToT can automatically select more fine-grained context to re-prompt LLMs when their responses lack confidence. Additionally, we use the rationales extracted via DToT to fine-tune student LMs. Our experimental results on various datasets demonstrate that DToT can improve the accuracy of LLMs by up to 4.6%. Furthermore, student LMs fine-tuned with rationales extracted via DToT outperform baselines on all datasets with up to 16.9% accuracy improvement, while being more than 60x smaller than conventional LLMs. Finally, we observe that student LMs fine-tuned with rationales exhibit better cross-dataset transferability.

Signal maps are essential for the planning and operation of cellular networks. However, the measurements needed to create such maps are expensive, often biased, not always reflecting the performance metrics of interest, and posing privacy risks. In this paper, we develop a unified framework for predicting cellular performance maps from limited available measurements. Our framework builds on a state-of-the-art random-forest predictor, or any other base predictor. We propose and combine three mechanisms that deal with the fact that not all measurements are equally important for a particular prediction task. First, we designquality-of-service functions ($Q$Q), including signal strength (RSRP) but also other metrics of interest to operators, such as number of bars, coverage (improving recall by 76%-92%) and call drop probability (reducing error by as much as 32%). By implicitly altering the loss function employed in learning, quality functions can also improve prediction for RSRP itself where it matters (e.g., MSE reduction up to 27% in the low signal strength regime, where high accuracy is critical). Second, we introduceweight functions($W$) to specify the relative importance of prediction at different locations and other parts of the feature space. We propose re-weighting based on importance sampling to obtain unbiased estimators when the sampling and target distributions are different. This yields improvements up to 20% for targets based on spatially uniform loss or losses based on user population density. Third, we apply theData Shapleyframework for the first time in this context: to assign values ($\phi$) to individual measurement points, which capture the importance of their contribution to the prediction task. This can improve prediction (e.g., from 64% to 94% in recall for coverage loss) by removing points with negative values and storing only the remaining data points (i.e., as low as 30%), which also has the side-benefit of helping privacy. We evaluate our methods and demonstrate significant improvement in prediction performance, using several real-world datasets.

We consider the problem of predicting cellular network performance (signal maps) from measurements collected by several mobile devices. We formulate the problem within the online federated learning framework: (i) federated learning (FL) enables users to collaboratively train a model, while keeping their training data on their devices; (ii) measurements are collected as users move around over time and are used for local training in an online fashion. We consider an honest-but-curious server, who observes the updates from target users participating in FL and infers their location using a deep leakage from gradients (DLG) type of attack, originally developed to reconstruct training data of DNN image classifiers. We make the key observation that a DLG attack, applied to our setting, infers the average location of a batch of local data, and can thus be used to reconstruct the target users' trajectory at a coarse granularity. We build on this observation to protect location privacy, in our setting, by revisiting and designing mechanisms within the federated learning framework including: tuning the FL parameters for averaging, curating local batches so as to mislead the DLG attacker, and aggregating across multiple users with different trajectories. We evaluate the performance of our algorithms through both analysis and simulation based on real-world mobile datasets, and we show that they achieve a good privacy-utility tradeoff.

Federated learning (FL) has attracted growing interest for enabling privacy-preserving machine learning on data stored at multiple users while avoiding moving the data off-device. However, while data never leaves users’ devices, privacy still cannot be guaranteed since significant computations on users’ training data are shared in the form of trained local models. These local models have recently been shown to pose a substantial privacy threat through different privacy attacks such as model inversion attacks. As a remedy, Secure Aggregation (SA) has been developed as a framework to preserve privacy in FL, by guaranteeing the server can only learn the global aggregated model update but not the individual model updates.While SA ensures no additional information is leaked about the individual model update beyond the aggregated model update, there are no formal guarantees on how much privacy FL with SA can actually offer; as information about the individual dataset can still potentially leak through the aggregated model computed at the server. In this work, we perform a first analysis of the formal privacy guarantees for FL with SA. Specifically, we use Mutual Information (MI) as a quantification metric and derive upper bounds on how much information about each user's dataset can leak through the aggregated model update. When using the FedSGD aggregation algorithm, our theoretical bounds show that the amount of privacy leakage reduces linearly with the number of users participating in FL with SA. To validate our theoretical bounds, we use an MI Neural Estimator to empirically evaluate the privacy leakage under different FL setups on both the MNIST and CIFAR10 datasets. Our experiments verify our theoretical bounds for FedSGD, which show a reduction in privacy leakage as the number of users and local batch size grow, and an increase in privacy leakage as the number of training rounds increases. We also observe similar dependencies for the FedAvg and FedProx protocol.

Online content platforms optimize engagement by providing personalized recommendations to their users. These recommendation systems track and profile users to predict relevant content a user is likely interested in. While the personalized recommendations provide utility to users, the tracking and profiling that enables them poses a privacy issue because the platform might infer potentially sensitive user interests. There is increasing interest in building privacy-enhancing obfuscation approaches that do not rely on cooperation from online content platforms. However, existing obfuscation approaches primarily focus on enhancing privacy but at the same time they degrade the utility because obfuscation introduces unrelated recommendations. We design and implement DeHarpo, an obfuscation approach for YouTube's recommendation system that not only obfuscates a user's video watch history to protect privacy but then also denoises the video recommendations by YouTube to preserve their utility. In contrast to prior obfuscation approaches, DeHarpo adds a denoiser that makes use of a ``secret'' input (i.e., a user's actual watch history) as well as information that is also available to the adversarial recommendation system (i.e., obfuscated watch history and corresponding ``nois`` recommendations). Our large-scale evaluation of DeHarpo shows that it outperforms the state-of-the-art by a factor of 2x in terms of preserving utility for the same level of privacy, while maintaining stealthiness and robustness to de-obfuscation.

With the advent of 5G+ services, it has become increasingly convenient for mobile users to enjoy high-quality multimedia content from CDN driven streaming and catch-up TV services (Netflix, iPlayer) in the (post-) COVID over-the-top (OTT) content rush. To relieve ISP owned fixed-line networks from CDN streamed multimedia traffic, system ideas (e.g., Wi-Stitch in [ 45 ]) have been proposed to (a) leverage 5G services and enable consumers to share cached multimedia content at the edge, and (b) consequently, and more importantly, reduce IP traffic at the core network. Unfortunately, given that contemporary multimedia content might be a monetized asset, these ideas do not take this important fact into account for shared content. We present EdgeMart —a content provider (CP) federated, and computationally sustainable networked (graphical) market economy for paid-sharing of cached licensed (OTT) content with autonomous users of a wireless edge network (WEN). EdgeMart is a unique oligopoly multimedia market (economy) that comprises competing networked sub-markets of non-cooperative content sellers/buyers—each sub-market consisting of a single buyer connected (networked) to only a subset of sellers. We prove that for any WEN-supported supply-demand topology , a pure strategy EdgeMart equilibrium exists that is (a) nearly efficient (in a microeconomic sense) indicating economy sustainability, (b) robust to edge user entry/exit, and (c) can be reached in poly-time (indicating computational sustainability). In addition, we experimentally show that for physical WENs of varying densities, a rationally selfish EdgeMart economy induces similar orders of multimedia IP traffic savings when compared to the ideal (relatively less practical), altruistic , and non-monetized “economy” implemented atop the recently introduced Wi-Stitch WEN-based content trading architecture. Moreover, the EdgeMart concept helps envision a regulated edge economy of opportunistic (pay per licensed file) client services for commercial OTT platforms.

Autonomous vehicles use 3D sensors for perception. Cooperative perception enables vehicles to share sensor readings with each other to improve safety. Prior work in cooperative perception scales poorly even with infrastructure support. AUTOCAST1 enables scalable infrastructure-less cooperative perception using direct vehicle-to-vehicle communication. It carefully determines which objects to share based on positional relationships between traffic participants, and the time evolution of their trajectories. It coordinates vehicles and optimally schedules transmissions in a distributed fashion. Extensive evaluation results under different scenarios show that, unlike competing approaches, AUTOCAST can avoid crashes and near-misses which occur frequently without cooperative perception, its performance scales gracefully in dense traffic scenarios providing 2-4x visibility into safety critical objects compared to existing cooperative perception schemes, its transmission schedules can be completed on the real radio testbed, and its scheduling algorithm is near-optimal with negligible computation overhead.

In hybrid datacenter networks, wired connections are augmented with wireless links to facilitate data transfers between racks. The usage of mmWave/FSO wireless links enables dynamic bandwidth/capacity allocation with extremely small reconfiguration delay. Also, on-demand workload distribution, where the workload of a job is divided into multiple tasks that can be distributed/routed to different racks to be processed in parallel, allows better utilization of computational resources in data centers. In prior work, the dynamic wireless capacity augmentation and workload distribution decisions were mostly made independently and in a heuristic manner for serving distributed and parallel computing jobs. In this paper, we propose a novel analytical framework and algorithms to jointly optimize both the wireless capacity augmentation and the workload distribution, to minimize the job completion time. We consider workload that is not amenable to pipelining, fully amenable to pipelining, and partially amenable to pipelining. With extensive simulation studies, we show that the gain (in terms of the reduction in the job completion time) can be very substantial when allowing such joint optimization.

Location-based services have become extremely popular. As a result, indoor localization has received a lot of attention from both industry and academia. Despite the plethora of existing approaches, no method can achieve high accuracy without major, expensive changes to existing systems. For example, to achieve good accuracy, fingerprinting methods require many APs within range of a client, time-of-arrival methods require tight synchronization, client hardware changes and line-of-sight, and direction-of-arrival methods require expensive antenna front ends and line-of-sight. In this paper, we take advantage of inexpensive, off-the-shelf switched-beam antennas (SBAs) to increase the diversity of measurements used for fingerprint-based localization. We show using experiments that a single AP equipped with n SBAs may infer equally rich localization information as nAPs equipped with n omnidirectional antennas each, as long as the SBAs are properly configured. We then establish via extensive experiments that a single packet reception from a commodity client at a single AP equipped with a handful of SBAs (e.g., eight SBAs costing a couple of dollars more than omni antennas) achieves localization accuracy in the order of half a meter with or without line-of-sight, in any indoor environment, with zero airtime overhead and zero client support.

Spectrum regulators are pursuing centralized, dynamic sharing systems that will enable spectrum access for new wireless technologies. These sharing systems will leverage cognitive radio concepts to automatically identify suitable spectrum for users. Collected user information may be considered sensitive, and some incumbents are hesitant about spectrum sharing, citing privacy concerns. Privacy preserving strategies are needed to promote widespread spectrum sharing. However, privacy preserving techniques typically come at the expense of spectrum efficiency, resulting in reduced utility for the users. In this work we study this privacy-performance tradeoff. We develop a generalized spectrum sharing system architecture and formulate the multi-utility, user privacy optimization problem, where privacy is measured by exposure to potential adversary inference attacks. We derive the optimal solution for this spectrum sharing privacy problem and then formulate an efficient heuristic strategy that exploits the problem structure. Via numerical analysis, we demonstrate substantial improvement over the prevailing obfuscation strategies applied in the literature, with up to a 50% increase in privacy and negligible impact on spectrum efficiency for a real-world use case. To our knowledge, this is the first work to formally derive the optimal solution to the user privacy problem in a generalized spectrum sharing framework.

In large-scale cloud computing systems, a task is often divided into multiple subtasks which can be executed in parallel in different machines. As a result, the task completion time is constrained by the completion time of the slowest subtask. To reduce the task completion time, the strategy of replicating the straggling subtasks has been employed in cloud computing frameworks such as MapReduce and Hadoop. Analyzing mathematically the performance of such replication strategies has recently received great attention. However, most of the analytical work focuses on the case where the completion times of the subtasks are identically distributed. This assumption may not hold in practice due to the modularization and encapsulation of the computation of a task, resulting in different service requirements for different subtasks. In this paper, we consider the case where the completion times of the subtasks of a task are drawn from heterogeneous/empirical distributions. Furthermore, we consider the case where jobs consist of hierarchical tasks that are required to be executed in a specific order described by a task precedence graph. We propose a novel framework to investigate how to allocate replication resources among the subtasks such that the overall task completion time is minimized. Specifically, we devise a Lagrange multiplier-based method and a water-filling-like algorithm for integer programs. We show via analysis and simulations the optimality and efficiency of our proposed algorithms, and explore the tradeoff between cost and latency from introducing replications in a task graph.

To satisfy the increasing demand for additional bandwidth from the wireless sector, regulatory bodies are considering to allow commercial wireless systems to operate on spectrum bands that until recently were reserved exclusively for military radar. Such co-existence would require mechanisms for controlling interference. One such mechanism is to assign a precoder to the communication system, which is designed to minimize the communication system’s interference to the radar. This paper looks into whether the implicit radar information contained in such a precoder can be exploited by an adversary to infer the radar’s location. For two specific precoder schemes, we simulate a machine learning based location inference attack. We show that the system information leaked through the precoder can indeed pose various degrees of risk to the radar’s privacy, and further confirm this by computing the mutual information between the respective precoder and the radar location.

Signal strength maps are of great importance to cellular providers for network planning and operation, however they are expensive to obtain and possibly limited or inaccurate in some locations. In this paper, we develop a prediction framework based on random forests to improve signal strength maps from limited measurements. First, we propose a random forests (RFs)-based predictor, with a rich set of features including location as well as time, cell ID, device hardware and other features. We show that our RFs-based predictor can significantly improve the tradeoff between prediction error and number of measurements needed compared to state-of-the-art data-driven predictors, i.e., requiring 80% less measurements for the same prediction accuracy, or reduces the relative error by 17% for the same number of measurements. Second, we leverage two types of real-world LTE RSRP datasets to evaluate into the performance of different prediction methods: (i) a small but dense Campus dataset, collected on a university campus and (ii) several large but sparser NYC and LA datasets, provided by a mobile data analytics company.

Despite the promising potential of network risk management services (e.g., cyber-insurance) to improve information security, their deployment is relatively scarce, primarily due to such service companies being unable to guarantee profitability. As a novel approach to making cyber-insurance services more viable, we explore a symbiotic relationship between security vendors (e.g., Symantec) capable of price differentiating their clients, and cyber-insurance agencies having possession of information related to the security investments of their clients. The goal of this relationship is to (i) allow security vendors to price differentiate their clients based on security investment information from insurance agencies, (ii) allow the vendors to make more profit than in homogeneous pricing settings, and (iii) subsequently transfer some of the extra profit to cyber-insurance agencies to make insurance services more viable. In this paper, we perform a theoretical study of a market for differentiated security product pricing, primarily with a view to ensuring that security vendors (SVs) make more profit in the differentiated pricing case as compared to the case of non-differentiated pricing. In order to practically realize such pricing markets, we propose novel andcomputationally efficientconsumer differentiated pricing mechanisms for SVs based on (i) the market structure, (ii) the communication network structure of SV consumers captured via a consumer'sBonacich centralityin the network, and (iii) security investment amounts made by SV consumers. We validate our analytical model via extensive simulations conducted on practical SV client network topologies; main results show (through those simulations) that (a) amonopolySV could improve its profit margin by upto$\approx$25 percent (based on the simulation setting) by accounting for clients’ investment information and network locations, whereas in anoligopolysetting, SVs could improve their profit margins by upto$\approx$18 percent, and (b) differentiated security pricing mechanisms are fair among SV consumers with respect to the total investment made by a consumer. To the best of knowledge, the proposed differentiated pricing framework is the first of its kind in the security products domain, and is generally applicable to usecases beyond the one investigated in this work.

802.11ax introduces OFDMA to WiFi. It thus enables multiplexing users/user groups in the frequency domain. WiFi networks usually operate in a multipath environment which generates a frequency selective channel. Hence, the capacity of a user/user group changes over different subcarriers. A good scheduling and resource allocation scheme can maximize the sum rate by allocating users and user groups on subcarriers based on their CSI and other system considerations. In this paper we investigate how to optimally assign users and user groups to subcarriers with the goal of maximizing the user sum rate in the context of 802.11ax. We introduce a novel divide and conquer based algorithm which we prove to be optimal under the assumption that a user can be assigned to more than one resource unit (RU) which consists of one ore more subcarriers. This serves as a tight upper bound on the actual problem where users/user groups can be assigned to a single RU only per the 802.11ax standard. We then introduce two practical algorithms for the actual problem, a greedy one and a recursive one which jointly splits the bandwidth into RUs and schedules users on them. Extensive simulations comparing the performance of the aforementioned algorithms establish that our practical schemes achieve very good performance in all studied scenarios.

The demand for higher and higher wireless data rates is driven by the popularity of mobile video content delivery through wireless devices such as tablets and smartphones. To achieve unprecedented mobile content delivery speeds while reducing backhaul cost and delay, in this paper we propose a new system architecture that combines two recent ideas, distributed caching of content in small cells (FemtoCaching), and, cooperative transmissions from nearby base stations (Coordinated Multi-Point). A key characteristic of the proposed architecture is the interdependence between the caching strategy and the physical layer coordination. Specifically, the caching strategy may cache different content in nearby base stations (BSs) to maximize the cache hit ratio, or cache the same content in multiple nearby BSs such that the corresponding BSs can transmit concurrently, e.g., to multiple users using zero-forcing beamforming, and achieve multiplexing gains. Such interdependency allows a joint cross-layer optimization. Given the popularity distribution of the content, the available cache size, and the network topology, we devise near-optimal strategies of caching such that the system throughput is maximized or the system delay is minimized. Under realistic scenarios and assumptions, our analytical and simulation results show that our system yields significantly faster content delivery, which can be one order of magnitude faster than that of legacy systems.

In an effort to meet growing demands on the radio frequency spectrum, regulators are exploring methods to enable band sharing among a diverse set of user devices. Proposed spectrum access systems would dynamically assign spectrum resources to users, maintaining databases of spectrum use information. While these systems are anticipated to increase the efficiency of spectrum sharing, incumbent users have raised concerns about exposing details of their operations and have questioned whether their privacy can be protected. In this paper, we explore whether primary users can retain a critical level of privacy in a spectrum access system setting, where they must reveal some information to enable dynamic access to the spectrum by other users. Under a variety of operational scenarios and user models, we examine adversary techniques to exploit the spectrum access system and obfuscation strategies to protect user privacy. We develop analytical methods to quantify the resulting privacy and validate our results through simulation. To the best of our knowledge, this is the first paper that considers inference attacks on primary users in the setting of a highly dynamic spectrum access system. Privacy analysis of this kind will help to enable the adoption of shared spectrum access systems by allowing incumbent users to quantify and mitigate risks to their privacy.

Modern wireless devices such as smartphones are pushing the demand for higher wireless data rates. The ensuing increase in wireless traffic demand can be met by a denser deployment of access points, coupled with a coordinated deployment of advanced physical layer techniques to reduce inter-cell interference. Unfortunately, advanced physical layer techniques, e.g., multi-user (MU) MIMO found in 802.11ac and LTE-advanced, are not designed to operate efficiently in a coordinated fashion across multiple densely deployed transmitters. In this paper, we introduce a new coordination architecture, which can achieve high performance gains without the high overhead and deployment cost that usually comes with coordination, thus making the vision of high capacity wireless access via densely deployed transmitters practical. The basic idea is to loosely coordinate nearby transmitters using slow varying channel statistics, while keeping all the functionality which depends on fast varying channel state information and has tight time deadlines locally. We achieve this via a smart combination of analog and digital beamforming using inexpensive front ends, a provably efficient algorithm to select compatible users and analog beams across all transmitters, and backward compatible protocol extensions. Our performance results, which include analysis, simulations, and experiments with software defined radios and directional antennas, show that our approach can achieve the $10\times $ gains of the theoretically optimal coordinated MU-MIMO approach, without the need to either tightly coordinate the clocks of the remote transmitters or meet tight delay constraints.

Cellular base band units of the future are expected to reside in a cloud data center which provides computation resources, content storage and caching, and a natural place to perform multi-user precoding, thus addressing both cost and performance concerns of cellular systems. Multi-user precoding relies on efficient user grouping schemes to maximize multiplexing gains. However, traditional user grouping schemes are unaware of data center constraints, and may induce a large number of data transfers across racks when fetching requested data to a certain rack for precoding. When congestion occurs in the data center network, the delay of data transfers across racks may exceed the channel coherence time. This would kill multi-user MIMO transmissions as channel state information becomes outdated. In this paper, we design a novel data-locality-aware user grouping schemes which preferentially group users whose requested data are located under the same rack. We also design user grouping algorithms which adapt to the congestion level in the cloud data center. Specifically, a regularized spectral efficiency maximization problem is proposed where the number of data transfers across racks is introduced as a regularization term. By adjusting the weight of the regularization term according to the congestion level, we gradually suppress data transfers across racks in forming user groups when congestion occurs. We reduce the above problem to a soft-capacitated facility location problem, and we devise a 2-approximation user grouping algorithm. At last, we conduct simulations which show that our proposed algorithm performs close to the optimal in practical scenarios, and study the tradeoff between higher spectral efficiency and lower data transfer cost.

The demand for wireless bandwidth is rising to unprecedented levels. The industry has responded with the inclusion of advanced PHY techniques, most notably multi-user (MU) MIMO, in the most recent WiFi and LTE standards. However, despite the theoretical promise for large multiplexing gains, in practice the rate gains are modest due to a combination of large overhead to collect channel state information and not-so-well-conditioned channel matrices.

The constantly growing wireless bandwidth demand is pushing wireless networks to multi-tier architectures consisting of a macrocell tier and a number of dense small cell deployment tiers. In such a multi-tier multi-cell environment, the classic problem of associating users to base stations becomes both more challenging and more critical to the overall network performance. Most previous analytical work is focused on designing static user-cell association algorithms, which, to achieve optimality, are periodically applied whenever there are new user arrivals, thus potentially inducing a large number of re-associations for previously arrived users. On the other hand, practical online algorithms that do not allow any such user re-association are often based on heuristics and may not have any performance guarantees. In this paper, we propose online algorithms for the multi-tier multi-cell user association problem that have provable performance guarantees, which improve previously known bounds by a sizable amount. The proposed algorithms are motivated by online combinatorial auctions, while capturing and leveraging the relative sparsity of choices in wireless networks as compared with auction setups. Our champion algorithm is a 1/2-a-1approximation algorithm, where a is the maximum number of feasible associations for a user and is, in general, small due to path loss. Our analysis considers the state-of-the-art wireless technologies, such as massive and multiuser MIMO, and practical aspects of the system such as the fact that highly mobile users have a preference to connect to larger cell tiers to keep the signaling overhead low. In addition to establishing formal performance bounds, we also conduct simulations under realistic assumptions, which establish the superiority of the proposed algorithm over existing approaches under real-world scenarios.

Effective radio frequency spectrum sharing methods are crucial for sustaining growth and development in mobile wireless services. In this paper, we consider a real-world scenario involving spectrum sharing between mobile wireless and meteorological satellite services as motivation for examining the general problem of efficient resource scheduling in a shared spectrum environment. We formulate an optimization framework for maximizing network utility subject to stochastic interference protection constraints. We design and propose a novel solution inspired by analysis of the optimization problem, where the primary contribution is an efficient power allocation algorithm to manage interference between systems. Using theory and simulations, we show that our algorithm significantly outperforms alternative approaches by well approximating the optimal solution with low enough complexity for practical, real-time application to large networks.

In an effort to meet growing demands on the radio frequency spectrum, regulators are exploring methods to enable band sharing among a diverse set of user devices. Proposed spectrum access systems would dynamically assign spectrum resources to users, maintaining databases of spectrum use information. While these systems are anticipated to increase the efficiency of spectrum sharing, incumbent users have raised concerns about exposing details of their operations and have questioned whether their privacy can be protected. In this paper, we explore whether primary users can retain a critical level of privacy when a system uses their information to enable dynamic access to the spectrum by other users. Under a variety of operational scenarios and user models, we examine adversary techniques to exploit the spectrum access system and obfuscation strategies to protect user privacy. We also develop analytical methods to quantify the performance of both the adversary and obfuscation strategies. To our knowledge, this is the first work that considers the privacy of a primary user in the setting of a highly dynamic spectrum access system. Privacy analysis of this kind will help to enable adoption of shared spectrum access systems by allowing incumbent users to quantify and mitigate risks to their privacy.

The ever growing wireless bandwidth demand is pushing WiFi and cellular networks to dense multi-cell deployments, as well as to multi-tier architectures consisting of macrocells and small cells. In such a multi-tier multi-cell environment, the classic problem of associating users to base stations becomes both more challenging and more critical to the overall network performance. Most previous analytical work is focused on offline/static user-cell association, where the users' arrivals and their rates are assumed to be known in advance and thus has little practical relevance. On the other hand, practical online algorithms based on heuristics are often suboptimal and may not provide any performance guarantees. In this paper, we propose an online algorithm for the multi-tier multi-cell user association problem that has a provable performance guarantee which improves previously known bounds by a sizable amount. The proposed algorithm is motivated by online combinatorial auctions, while capturing and leveraging the relative sparsity of choices in wireless networks as compared to auction setups. Specifically, it is a 1/2−a−1 approximation algorithm, where a is the maximum number of feasible associations for a user and is, in general, small due to path loss. In addition to establishing formal performance bounds, we also conduct simulations under realistic assumptions which establish the superiority of the proposed algorithm over existing approaches under real-world scenarios.

The enormous success of advanced wireless devices is pushing the demand for higher wireless data rates. The industry is satisfying this increasing demand by densely deploying large numbers of access points (APs). Unfortunately, unicast rates, especially in crowded scenarios, remain very low due to severe interference and time-sharing. However, one may take advantage of the broadcasting nature of wireless transmissions to offer high multicast rates. Motivated by this, we present coordinated broadcasting (Co-BCast), a system which coordinates multiple APs to provide participants of big events with high multicast rates that can support multiple high definition video streams.

With limited opportunities to open up new unencumbered bands to mobile wireless services, interest in enhancing methods for sharing of spectrum between services is high. For example, the band 1695-1710 MHz is expected to be made available to 3GPP Long-Term Evolution cellular network uplinks by sharing with incumbent meteorological satellite services already in the band. The LTE networks are to be operated in a manner that ensures no loss of incumbent capability by adhering to protection requirements such as a limit on the aggregate interference power at fixed incumbent earth station locations. In this paper, we consider this specific spectrum sharing scenario as motivation and formulate an optimization framework for power control and time-frequency resource scheduling on the LTE uplink with an aggregate interference constraint. We design and propose a novel algorithm inspired by numerical solution and analysis of the optimization problem. Using theory and simulation, we show that our algorithm significantly outperforms more simplistic approaches, well approximates the optimal solution, and is of sufficient scope and complexity for practical implementation, even in relatively large LTE networks. Algorithms of this kind are necessary for mobile wireless networks to make the most of constrained spectrum resources in shared bands.

Modern wireless devices such as tablets and smartphones are pushing the demand for higher and higher wireless data rates. The vast majority of this demand comes from media content. In this paper we propose to combine two recent ideas, distributed caching of content in small cells, and, cooperative transmissions from nearby base stations/BSs (generally known as coordinated multi-point), to achieve unprecedented content delivery speeds while reducing backhaul cost and delay. A key characteristic of our architecture is the interdependence between the caching strategy and the PHY/MAC layer coordination. Specifically, the caching strategy may cache different content in nearby BSs to maximize the hit ratio, or cache the same content in multiple nearby BSs such that the corresponding BSs can transmit concurrently, e.g. to multiple users using zero force beamforming, and achieve multiplexing gains. With this in mind, given the popularity distribution of the content, the available cache size, and the network topology, we devise optimal strategies of caching such that the throughput of the system is maximized. Our analytical and simulation results show that our system yields significantly faster content delivery, which, under realistic scenarios and assumptions can be one order of magnitude faster than that of legacy systems.

Recent work in security has illustrated that solutions aimed at detection and elimination of security threats alone are unlikely to result in a robust cyberspace. As an orthogonal approach to mitigating security problems, some have pursued the use of cyber-insurance as a suitable risk management technique. Such an approach has the potential to jointly align with the incentives of security vendors (e.g., Symantec, Microsoft, etc.), cyber-insurers (e.g., ISPs, cloud providers, security vendors, etc.), regulatory agencies (e.g., government), and network users (individuals and organizations), in turn paving the way for comprehensive and robust cyber-security mechanisms. To this end, in this work, we are motivated by the following important question: can cyber-insurance really improve the security in a network? To address this question, we adopt a market-based approach. Specifically, we analyze regulated monopolistic and competitive cyber-insurance markets, where the market elements consist of risk-averse cyber-insurers, risk-averse network users, a regulatory agency, and security vendors. Our results show that (i) without contract discrimination amongst users, there always exists a unique market equilibrium for both market types, but the equilibrium is inefficient and does not improve network security, and (ii) in monopoly markets, contract discrimination amongst users results in a unique market equilibrium that is efficient, which in turn results in network security improvement - however, the cyber-insurer can make zero expected profits. The latter fact is often sufficient to de-incentivize the insurer to be a part of a market, and will eventually lead to its collapse. This fact also emphasizes the need for designing mechanisms that incentivize the insurer to permanently be part of the market.

In this paper, we consider Quality-of-Information (QoI) aware transmission policies for a dynamic environment. In particular, we focus on the time-varying nature of the observation quality of the environment in practical networks which leads to uncertainty in satisfying QoI requirements specified by end users. The goal of this paper is to meet QoI requests from end users with minimum resources. Specifically, power is allocated dynamically depending on observation accuracies and QoI requirements. We formulate a dynamic scheme for scheduling with the objective of minimizing the energy consumption at the network while satisfying constraints on outage probability for QoI. Lyapunov stability arguments are used to define a policy based on the instantaneous observation qualities and QoI requirement satisfaction levels. Numerical results demonstrate that significant improvements in delivered QoI are realized with identical power expenditure using our QoI-aware resource allocation algorithm compared with traditional maximum-rate schedulers.

Large-scale distributed Multiuser MIMO (MU-MIMO) is a promising wireless network architecture that combines the advantages of "massive MIMO" and "small cells." It consists of several Access Points (APs) connected to a central server via a wired backhaul network and acting as a large distributed antenna system. We focus on the downlink, which is both more demanding in terms of traffic and more challenging in terms of implementation than the uplink. In order to enable multiuser joint precoding of the downlink signals, channel state information at the transmitter side is required. We consider Time Division Duplex (TDD), where the downlink channels can be learned from the user uplink pilot signals, thanks to channel reciprocity. Furthermore, coherent multiuser joint precoding is possible only if the APs maintain a sufficiently accurate relative timing and phase synchronization. AP synchronization and TDD reciprocity calibration are two key problems to be solved in order to enable distributed MU-MIMO downlink. In this paper, we propose novel over-the-air synchronization and calibration protocols that scale well with the network size. The proposed schemes can be applied to networks formed by a large number of APs, each of which is driven by an inexpensive 802.11-grade clock and has a standard RF front-end, not explicitly designed to be reciprocal. Our protocols can incorporate, as a building block, any suitable timing and frequency estimator. Here we revisit the problem of joint ML timing and frequency estimation and use the corresponding Cramer-Rao bound to evaluate the performance of the synchronization protocol. Overall, the proposed synchronization and calibration schemes are shown to achieve sufficient accuracy for satisfactory distributed MU-MIMO performance.

The enormous success of advanced wireless devices is pushing the demand for higher wireless data rates. Denser spectrum reuse through the deployment of more access points (APs) per square mile has the potential to successfully meet such demand. In principle, distributed multiuser multiple-input-multiple-output (MU-MIMO) provides the best approach to infrastructure density increase since several access points are connected to a central server and operate as a large distributed multiantenna access point. This ensures that all transmitted signal power serves the purpose of data transmission, rather than creating interference. In practice, however, a number of implementation difficulties must be addressed, the most significant of which is aligning the phases of all jointly coordinated APs. In this paper, we propose AirSync, a novel scheme that provides timing and phase synchronization accurate enough to enable distributed MU-MIMO. AirSync detects the slot boundary such that all APs are time-synchronous within a cyclic prefix (CP) of the orthogonal frequency-division multiplexing (OFDM) modulation and predicts the instantaneous carrier phase correction along the transmit slot such that all transmitters maintain their coherence, which is necessary for multiuser beamforming. We have implemented AirSync as a digital circuit in the field programmable gate array (FPGA) of the WARP radio platform. Our experimental testbed, comprising four APs and four clients, shows that AirSync is able to achieve timing synchronization within the OFDM CP and carrier phase coherence within a few degrees. For the purpose of demonstration, we have implemented two MU-MIMO precoding schemes, Zero-Forcing Beamforming (ZFBF) and Tomlinson-Harashima Precoding (THP). In both cases, our system approaches the theoretical optimal multiplexing gains. We also discuss aspects related to the MAC and multiuser scheduling design, in relation to the distributed MU-MIMO architecture. To the best of our knowledge, AirSync offers the first realization of the full distributed MU-MIMO multiplexing gain, namely the ability to increase the number of active wireless clients per time-frequency slot linearly with the number of jointly coordinated APs, without reducing the per client rate.

This paper establishes that random access scheduling schemes, and more specifically CSMA-CA, yield exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms that grossly underutilize the available capacity that random access provides. To establish our thesis, we first compare the achievable rate region of CSMA-CA and optimal in a number of carefully constructed multihop topologies and find that CSMA-CA is always within 48% of the optimal. Motivated by this result, we next characterize the worst-case performance of CSMA-CA in neighborhood topologies representing the congested regions of larger multihop topologies by deriving the neighborhood topology that yields the worst-case throughput ratio for CSMA-CA and find that in neighborhood topologies with less than 20 edges: 1) CSMA-CA is never worse than 16% of the optimal when ignoring physical-layer constraints; and 2) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst-case bounds, CSMA-CA is surprisingly efficient.

In Delay Tolerant Networks (DTNs), end-to-end connectivity between nodes does not always occur due to limited radio coverage, node mobility and other factors. Remote communication may assist in guaranteeing delivery. However, it has a considerable cost, and consequently, minimizing it is an important task. For multicast routing, the problem is NP-hard, and naive approaches are infeasible on large problem instances. In this paper we define the problem of minimizing the remote communication cost for multicast in DTNs. Our formulation handles the realistic scenario in which a data source is continuously updated and nodes need to receive recent versions of data. We analyze the problem in the case of scheduled trajectories and known traffic demands, and propose a solution based on a novel graph indexing system. We also present an adaptive extension that can work with limited knowledge of node mobility. Our method reduces the search space significantly and finds an optimal solution in reasonable time. Extensive experimental analysis on large real and synthetic datasets shows that the proposed method completes in less than 10 seconds on datasets with millions of encounters, with an improvement of up to 100 times compared to a naive approach.

A distributed MIMO system consists of several access points connected to a central server and operating as a large distributed multi-antenna access point. In theory, such a system enjoys all the significant performance gains of a traditional MIMO system, and it may be deployed in an enterprise WiFi like setup. In this paper, we investigate the efficiency of such a system in practice. Specifically, we build upon our prior work on developing a distributed MIMO testbed, and study the performance of such a system when both full channel state information is available to the transmitters and when no channel state information is available. In the full channel state information scenario, we implement Zero-Forcing Beamforming (ZFBF) and Tomlinson-Harashima Precoding (THP) which is provably near-optimal in high SNR conditions. In the scenario where no channel information is available, we implement Blind Interference Alignment (BIA), which achieves a higher multiplexing gain (degrees of freedom) than conventional TDMA. Our experimental results show that the performance of our implementation is very close to the theoretically predicted performance and offers significant gains over optimal TDMA. We also discuss medium access layer issues in detail for both scenarios. To the best of our knowledge, this is the first time that the theoretical high data rates of multiuser MIMO systems have been showcased in a real world distributed MIMO testbed.

Estimating link capacity in a wireless network is a complex task because the available capacity at a link is a function of not only the current arrival rate at that link, but also of the arrival rate at links which interfere with that link as well as of the nature of interference between these links. Models which accurately characterize this dependence are either too computationally complex to be useful or lack accuracy. Further, they have a high implementation overhead and make restrictive assumptions, which makes them inapplicable to real networks. In this paper, we propose CapEst, a general, simple yet accurate, measurement-based approach to estimating link capacity in a wireless network. To be computationally light, CapEst allows inaccuracy in estimation; however, using measurements, it can correct this inaccuracy in an iterative fashion and converge to the correct estimate. Our evaluation shows that CapEst always converged to within 5 percent of the correct value in less than 18 iterations. CapEst is model-independent; hence, it is applicable to any MAC/PHY layer and works with autorate adaptation. Moreover, it has a low implementation overhead, can be used with any application which requires an estimate of residual capacity on a wireless link and can be implemented completely at the network layer without any support from the underlying chipset.

Complex interference in static multihop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this paper, we explore mechanisms for achieving fair and efficient congestion control for multihop wireless mesh networks. First, we design an AIMD-based rate-control protocol called Wireless Control Protocol (WCP), which recognizes that wireless congestion is a neighborhood phenomenon, not a node-local one, and appropriately reacts to such congestion. Second, we design a distributed rate controller that estimates the available capacity within each neighborhood and divides this capacity to contending flows, a scheme we call Wireless Control Protocol with Capacity estimation (WCPCap). Using analysis, simulations, and real deployments, we find that our designs yield rates that are both fair and efficient. WCP assigns rates inversely proportional to the number of bottlenecks a flow passes through while remaining extremely easy to implement. An idealized version of WCPCap is max-min fair, whereas a practical implementation of the scheme achieves rates within 15% of the max-min optimal rates while still being distributed and amenable to real implementation.

In this paper, we explore a simple yet effective technique for explicitly allocating airtime to each active pair of communicating neighbors in a wireless neighborhood so that TCP starvation in a wireless mesh network is avoided. Our explicit allocation is efficient, redistributing unused airtime and also accounting for airtime rendered unusable by external interference. Our technique requires no modifications to TCP/IP and the 802.11 MAC, and is responsive to short flows, MAClayer auto rate adaptation, and other dynamics, as we demonstate in extensive experiments on two indoor testbeds. Despite its simplicity, the technique is on average within 12% of the max-min optimal allocation on several canonical topologies. 1.

This paper formally establishes that random access scheduling schemes, and, more specifically CSMA-CA, yields exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms which grossly underutilize the available capacity that random access provides. To establish our thesis we compare the max-min rate allocation achieved by CSMA-CA and optimal in multi-hop topologies and find that: (i) CSMA-CA is never worse than 16% of the optimal when ignoring physical layer constraints, (ii) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst case bounds, CSMA-CA is surprisingly efficient.

The research community has been fascinated by the challenges posed by multi-hopping for over a decade, and has produced a number of interesting theoretical results and innovative solutions for many of these challenges. However, despite the plethora of envisioned applications for many multi-hop architectures, e.g. mesh, sensor, and ad-hoc, the reality is that there are only a few real-world success stories involving multi-hopping.

A large body of work has theoretically analyzed the performance of mobility-assisted routing schemes for intermittently connected mobile networks. But the vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even for sparse networks. In this paper, we analyze the performance of routing schemes under contention. First, we introduce a mathematical framework to model contention. This framework can be used to analyze any routing scheme with any mobility and channel model. Then, we use this framework to compute the expected delays for different representative mobility-assisted routing schemes under random direction, random waypoint and community-based mobility models. Finally, we use these delay expressions to optimize the design of routing schemes while demonstrating that designing and optimizing routing schemes using analytical expressions which ignore contention can lead to suboptimal or even erroneous behavior.

Complex interference in static multi-hop wireless mesh networks can adversely affect transport protocol performance. Since TCP does not explicitly account for this, starvation and unfairness can result from the use of TCP over such networks. In this paper, we explore mechanisms for achieving fair and efficient congestion control for multi-hop wireless mesh networks. First, we design an AIMD-based rate-control protocol called Wireless Control Protocol (WCP) which recognizes that wireless congestion is a neighborhood phenomenon, not a node-local one, and appropriately reacts to such congestion. Second, we design a distributed rate controller that estimates the available capacity within each neighborhood, and divides this capacity to contending flows, a scheme we call Wireless Control Protocol with Capacity estimation (WCPCap). Using analysis, simulations, and real deployments, we find that our designs yield rates that are both fair and efficient, and achieve near optimal goodputs for all the topologies that we study. WCP achieves this level of performance while being extremely easy to implement. Moreover, WCPCap achieves the max-min rates for our topologies, while still being distributed and amenable to real implementation.

Experimentation with mobile ad hoc network testbeds is preferred to simulations for performing high fidelity testing. But, at the same time, realistic experimentation with large-scale network testbeds is more difficult, time-consuming, and expensive. To side-step some of these problems several researchers, e.g. P. De et al. (2005), V. Naik et al. (2006), have recently suggested experimentation on scaled-down replicas and have managed to downscale some specific indoor network realizations with no mobility. However, the question of whether a scaled-down replica can reproduce the behavior of an arbitrary large-scale mobile ad hoc network, in a timely manner, and under realistic outdoor conditions, remains an interesting open problem. In this work we investigate ways of constructing suitably scaled-down replicas, both in space and time, that can predict the performance of large-scale mobile ad hoc networks with high accuracy. We consider both large- and small-scale fading effects. Further, we present necessary and sufficient conditions for the scaling to be possible, and identify some of the issues that may arise in practice. Finally, we argue that it is not possible to build arbitrarily smaller replicas, and that the factor by which one scales down the original network (in space) depends on the carrier frequency.

Realistic mobility models are important to understand the performance of routing protocols in wireless ad hoc networks, especially when mobility-assisted routing schemes are employed, which is the case, for example, in delay-tolerant networks (DTNs). In mobility-assisted routing, messages are stored in mobile nodes and carried across the network with nodal mobility. Hence, the delay involved in message delivery is tightly coupled with the properties of nodal mobility. Currently, commonly used mobility models are simplistic random i.i.d. model that do not reflect realistic mobility characteristics. In this paper we propose a novel time-variant community mobility model. In this model, we define communities that are visited often by the nodes to capture skewed location visiting preferences, and use time periods with different mobility parameters to create periodical re-appearance of nodes at the same location. We have clearly observed these two properties based on analysis of empirical WLAN traces. In addition to the proposal of a realistic mobility model, we derive analytical expressions to highlight the impact on the hitting time and meeting times if these mobility characteristics are incorporated. These quantities in turn determine the packet delivery delay in mobility-assisted routing settings. Simulation studies show our expressions have error always under 20%, and in 80% of studied cases under 10%.

Epidemic routing has been proposed as a robust transmission scheme for sparse mobile ad hoc networks. Under the assumption of no contention, epidemic routing has the minimum end-to-end delay amongst all the routing schemes proposed for such networks. The assumption of no contention was justified by arguing that since the network is sparse, there will be very few simultaneous transmissions. Some recent papers have shown through simulations that this argument is not correct and that contention cannot be ignored while analyzing the performance of routing schemes, even in sparse networks.Incorporating contention in the analysis has always been a hard problem and hence its effect has been studied mostly through simulations only. In this paper, we find analytical expressions for the delay performance of epidemic routing with contention. We include all the three main manifestations of contention, namely (i) the finite bandwidth of the link which limits the number of packets two nodes can exchange, (ii) the scheduling of transmissions between nearby nodes which is needed to avoid excessive interference, and (iii) the interference from transmissions outside the scheduling area. The accuracy of the analysis is verified via simulations.

Traditionally, ad hoc networks have been viewed as a connected graph over which end-to-end routing paths had to be established.Mobility was considered a necessary evil that invalidates paths and needs to be overcome in an intelligent way to allow for seamless ommunication between nodes.However, it has recently been recognized that mobility an be turned into a useful ally, by making nodes carry data around the network instead of transmitting them. This model of routing departs from the traditional paradigm and requires new theoretical tools to model its performance. A mobility-assisted protocol forwards data only when appropriate relays encounter each other, and thus the time between such encounters, called hitting or meeting time, is of high importance.In this paper, we derive accurate closed form expressions for the expected encounter time between different nodes, under ommonly used mobility models. We also propose a mobility model that can successfully capture some important real-world mobility haracteristics, often ignored in popular mobility models, and alculate hitting times for this model as well. Finally, we integrate this results with a general theoretical framework that can be used to analyze the performance of mobility-assisted routing schemes. We demonstrate that derivative results oncerning the delay of various routing s hemes are very accurate, under all the mobility models examined. Hence, this work helps in better under-standing the performance of various approaches in different settings, and an facilitate the design of new, improved protocols.

In a wireless sensor network of N nodes transmitting data to a single base station, possibly over multiple hops, what distributed mechanisms should be implemented in order to dynamically allocate fair and efficient transmission rates to each node? Our interferenceaware fair rate control (IFRC) detects incipient congestion at a node by monitoring the average queue length, communicates congestion state to exactly the set of potential interferers using a novel low-overhead congestion sharing mechanism, and converges to a fair and efficient rate using an AIMD control law. We evaluate IFRC extensively on a 40-node wireless sensor network testbed. IFRC achieves a fair and efficient rate allocation that is within 20-40% of the optimal fair rate allocation on some network topologies. Its rate adaptation mechanism is highly effective: we did not observe a single instance of queue overflow in our many experiments. Finally, IFRC can be extended easily to support situations where only a subset of the nodes transmit, where the network has multiple base stations, or where nodes are assigned different transmission weights.

The Internet is a large, heterogeneous system operating at very high speeds and consisting of a large number of users. Researchers use a suite of tools and techniques in order to understand the performance of complex networks like the Internet: measurements, simulations, and deployments on small to medium-scale testbeds. This work considers a novel addition to this suite: a class of methods to scale down the topology of the Internet that enables researchers to create and observe a smaller replica, and extrapolate its performance to the expected performance of the larger Internet. This is complementary to the work of Psounis, 2003, where the authors presented a way to scale down the Internet in time, by creating a slower replica of the original system. The key insight that we leverage in this work is that only the congested links along the path of each flow introduce sizable queueing delays and dependencies among flows. Hence, one might hope that the network properties can be captured by a topology that consists of the congested links only. Using extensive simulations with transmission control protocol (TCP) traffic and theoretical analysis, we show that it is possible to achieve this kind of performance scaling even on topologies the size of the CENIC backbone (that provides Internet access to higher education institutions in California). We also show that simulating a scaled topology can be up to two orders of magnitude faster than simulating the original topology

The physical phenomena monitored by sensor networks, for example, forest temperature or water contamination, usually yield sensed data that are strongly correlated in space. With this in mind, researchers have designed a large number of sensor network protocols and algorithms that attempt to exploit such correlations.There is an increasing need to synthetically generate large traces of spatially correlated data representing a wide range of conditions to carefully study the performance of these algorithms. Further, a mathematical model for generating synthetic traces would provide guidelines for designing more efficient algorithms. These reasons motivate us to obtain a simple and accurate model of spatially correlated sensor network data.The proposed model is Markovian in nature and can capture correlation in data irrespective of the node density, the number of source nodes, or the topology. We describe a rigorous mathematical procedure and a simple practical method to extract the model parameters from real traces. We also show how to efficiently generate synthetic traces on a given topology using these parameters. The correctness of the model is verified by statistically comparing synthetic and real data. Further, the model is validated by comparing the performance of algorithms whose behavior depends on the degree of spatial correlation in data, under real and synthetic traces. The real traces are obtained from remote sensing data, publicly available sensor data, and sensor networks that we deploy. We show that the proposed model is more general and accurate than the commonly used jointly Gaussian model. Finally, we create tools that can be easily used by researchers to synthetically generate traces of any size and degree of correlation.

The physical phenomena monitored by sensor net- works, e.g. forest temperature, usually yield sensed data that are strongly correlated in space. We have recently introduced a mathematical model for such data, and used it to generate synthetic traces and study the performance of algorithms whose behavior depends on this spatial correlation (1). That work studied sensor networks with grid topologies. This work extends our modeling methodology to sensor networks with irregular topologies. We describe a rigorous mathematical procedure and a simple practical method to extract the model parameters from real traces. We also show how to efficiently generate synthetic traces that correspond to sensor networks with arbitrary topologies using the proposed model. The correctness of the model is verified by statistically com- paring synthetic and real data. Further, the model is validated by comparing the performance of algorithms whose behavior depends on the degree of spatial correlation in data, under real and synthetic traces. The real traces are obtained from both publically available sensor data, and sensor networks that we deploy. Finally, we augment our existing trace-generation tool with new functionality suited for sensor networks with irregular topologies.

As the Internet grows, it is becoming increasingly difficult to collect performance measurements, to monitor its state, and to perform simulations efficiently. This is because the size and the heterogeneity of the Internet makes it time-consuming and difficult to devise traffic models and analytic tools which would allow us to work with summary statistics. We explore a method to side step these problems by combining sampling, modeling, and simulation. Our hypothesis is this: if we take a sample of the input traffic and feed it into a suitably scaled version of the system, we can extrapolate from the performance of the scaled system to that of the original. Our main findings are as follows. When we scale an IP network which is shared by short- and long-lived TCP-like and UDP flows and which is controlled by a variety of active queue management schemes, then performance measures such as queueing delay and drop probability are left virtually unchanged. We show this in theory and in simulations. This makes it possible to capture the performance of large networks quite faithfully using smaller scale replicas.

The physical phenomena monitored by sensor networks, e.g. forest temperature, water contamination, usually yield sensed data that are strongly correlated in space. With this in mind, researchers have designed a large number of sensor network protocols and algorithms that attempt to exploit such correlations. To carefully study the performance of these algorithms, there is an increasing need to synthetically generate large traces of spatially correlated data representing a wide range of conditions. Further, a mathematical model for generating synthetic traces would provide guidelines for designing more efficient algorithms. These reasons motivate us to obtain a simple and accurate model of spatially correlated sensor network data. The model can capture correlation in data irrespective of the node density, the number of source nodes or the topology. We describe a mathematical procedure to extract the model parameters from real traces and generate synthetic traces using these parameters. Then, we validate our model by statistically comparing synthetic data and experimental data, as well as by comparing the performance of various algorithms whose performance depends on the degree of spatial correlation. Finally, we create a tool that can be easily used by researchers to synthetically generate traces of any size and degree of correlation.

Intermittently connected mobile networks are wireless networks where most of the time there does not exist a complete path from source to destination, or such a path is highly unstable and may break soon after it has been discovered. In this context, conventional routing schemes would fail. To deal with such networks we propose the use of an opportunistic hop-by-hop routing model. According to the model, a series of independent, local forwarding decisions are made, based on current connectivity and predictions of future connectivity information diffused through nodes' mobility. The important issue here is how to choose an appropriate next hop. To this end, we propose and analyze via theory and simulations a number of routing algorithms. The champion algorithm turns out to be one that combines the simplicity of a simple random policy, which is efficient in finding good leads towards the destination, with the sophistication of utility-based policies that efficiently follow good leads. We also state and analyze the performance of an oracle-based optimal algorithm, and compare it to the online approaches. The metrics used in the comparison are the average message delivery delay and the number of transmissions per message delivered.

Wireless sensor networks are characterized by dense deployment of sensor nodes which collectively communicate sensed data to the sink. However, due to the spatial correlation between sensor observations, it is not necessary for every node to transmit its data. We propose a clustering method which exploits the above observation. We do not make any assumption on the nature of data, and hence the algorithm will be valid for a broad range of conditions. The paper shows how to calculate the optimal cluster size. We also discuss the structure of the complete architecture which is still under development.

In networks and in Web server farms, it is useful to collect performance measurements, to monitor the state of the system, and to perform simulations. However, the sheer volume of traffic in large high-speed network systems makes it hard to monitor their performance or to simulate them efficiently. And the heterogeneity of the Internet means it is time-consuming and difficult to devise the traffic models and analytic tools which would allow us to work with summary statistics. We explore a method to side-step these problems by combining sampling, modeling and simulation. Our hypothesis is this: if we take a sample of the input traffic, and feed it into a suitably scaled version of the system, we can extrapolate from the performance of the scaled system to that of the original. Our main findings are: When we scale an IP network which is shared by TCP-like, UDP and Web flows; and which is controlled by a variety of active queue management schemes, then performance measures such as queueing delay and drop probability are left virtually unchanged. We show this in theory and in simulations. This makes it possible to capture the performance of large networks quite faithfully using smaller scale replicas.

The problem of document replacement in Web caches has received much attention and it has been shown that the eviction rule "replace the least recently used document" performs poorly in Web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size and the cost of fetching a document, leads to a sizable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for approximating any existing Web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M

The problem of document replacement in Web caches has received much attention in the literature research, and it has been shown that the eviction rule "replace the least recently used document" performs poorly in Web caches. Instead, it has been shown that using a combination of several criteria, such as the recentness and frequency of use, the size, and the cost of fetching a document, leads to a sizeable improvement in hit rate and latency reduction. However, in order to implement these novel schemes, one needs to maintain complicated data structures. We propose randomized algorithms for approximating any existing Web-cache replacement scheme and thereby avoid the need for any data structures. At document-replacement times, the randomized algorithm samples N documents from the cache and replaces the least useful document from the sample, where usefulness is determined according to the criteria mentioned above. The next M

We investigate the problem of providing a fair bandwidth allocation to each of n flows that share the outgoing link of a congested router. The buffer at the outgoing link is a simple FIFO, shared by packets belonging to the n flows. We devise a simple packet dropping scheme, called CHOKe, that discriminates against the flows which submit more packets per second than is allowed by their fair share. By doing this, the scheme aims to approximate the fair queueing policy. Since it is stateless and easy to implement, CHOKe controls unresponsive or misbehaving flows with a minimum overhead.