Present quantum computers are constrained by limited qubit capacity and restricted physical connectivity, leading to challenges in large-scale quantum computations. Distributing quantum computations across a network of quantum computers is a promising way to circumvent these challenges and facilitate large quantum computations. However, distributed quantum computations require entanglements (to execute remote gates) which can incur significant generation latency and, thus, lead to decoherence of qubits. In this work, we consider the problem of distributing quantum circuits across a quantum network to minimize the execution time. The problem entails mapping the circuit qubits to network memories, including within each computer since limited connectivity within computers can affect the circuit execution time. We provide two-step solutions for the above problem: In the first step, we allocate qubits to memories to minimize the estimated execution time; for this step, we design an efficient algorithm based on an approximation algorithm for the max-quadratic-assignment problem. In the second step, we determine an efficient execution scheme, including generating required entanglements with minimum latency under the network resource and decoherence constraints; for this step, we develop two algorithms with appropriate performance guarantees under certain settings or assumptions. We consider multiple protocols for executing remote gates, viz., telegates and cat-entanglements. With extensive simulations over NetSquid, a quantum network simulator, we demonstrate the effectiveness of our developed techniques and show that they outperform a scheme based on prior work by 40 to 50% on average and up to 95% in some cases.

In this article, we consider a network of quantum sensors, where each sensor is a qubit detector that “fires,” i.e., its state changes when an event occurs close by. The change in state due to the firing of a detector is given by a unitary operator, which is the same for all sensors in the network. Such a network of detectors can be used to localize an event, using a protocol to determine the firing sensor, presumably the one closest to the event. The determination of the firing sensor can be posed as a Quantum State Discrimination problem, which incurs a probability of error depending on the initial state and the measurement operators used. In this article, we address the problem of determining the optimal initial global state of a network of detectors that incur a minimum probability of error in determining the firing sensor. For this problem, we derive necessary and sufficient conditions for the existence of an initial state that allows for perfect discrimination, i.e., zero probability of error. Using insights from this result, we derive a conjectured optimal solution for the initial state, provide a pathway to prove the conjecture, and validate the conjecture empirically using multiple search heuristics that seem to perform near-optimally.

The ultimate goal of virtual reality (VR) is to create an experience indistinguishable from actual reality. To provide such a "life-like" experience, (i) the VR headset (VRH) should be wireless so that the user can move around freely, and (ii) the wireless link, connecting the VRH to a high-performance renderer, should support high data rates (tens to hundreds of Gbps). Industry is already pushing towards such wireless VRHs; however, these wireless links can only support a few Gbps rates. In general, current radio-frequency (RF) links (including mmWave) are not able to provide desired data rates. In this paper, we build a system, we call Cyclops, which uses free-space optical (FSO) technology to create a high-bandwidth VR wireless link. FSO links are capable of very high data rates (up to Tbps) due to the high frequencies of light waves and narrow beams. The main challenges in developing an effective FSO link are: (i) designing a link with sufficient movement tolerance, and (ii) developing a viable tracking and pointing (TP) mechanism which maintains the link while the VRH moves. As traditional TP approaches seem infeasible in our context, we develop a novel TP approach based on learning techniques, leveraging the VRH's inbuilt tracking system. We build robust 10 Gbps and 25Gbps link prototypes from commodity components, demonstrate their viability for expected movement speeds of a VRH, and show that, with certain custom-built components, we can support much higher movement speeds and bandwidths.

We address the problem of localizing an (unauthorized) transmitter using a distributed set of sensors. Our focus is on developing techniques that perform the transmitter localization in an efficient manner, wherein the efficiency is defined in terms of the number of sensors used to localize. Localization of unauthorized transmitters is an important problem which arises in many important applications, e.g., in patrolling of shared spectrum systems for any unauthorized users. Localization of transmitters is generally done based on observations from a deployed set of sensors with limited resources, thus it is imperative to design techniques that minimize the sensors’ energy resources. In this paper, we design greedy approximation algorithms for the optimization problem of selecting a given number of sensors in order to maximize an appropriately defined objective function of localization accuracy. The obvious greedy algorithm delivers a constant-factor approximation only for the special case of two hypotheses (potential locations). For the general case of multiple hypotheses, we design a greedy algorithm based on an appropriate auxiliary objective function—and show that it delivers a provably approximate solution for the general case. We develop techniques to significantly reduce the time complexity of the designed algorithms by incorporating certain observations and reasonable assumptions. We evaluate our techniques over multiple simulation platforms, including an indoor as well as an outdoor testbed, and demonstrate the effectiveness of our designed techniques—our techniques easily outperform prior and other approaches by up to 50-60% in large-scale simulations and up to 16% in small-scale testbeds.

Quantum computing hardware is improving in robustness, but individual computers still have small number of qubits (for storing quantum information). Computations needing a large number of qubits can only be performed by distributing them over a network of smaller quantum computers. In this paper, we consider the problem of distributing a quantum computation, represented as a quantum circuit, over a homogeneous network of quantum computers, minimizing the number of communication operations needed to complete every step of the computation. We propose a two-step solution: dividing the given circuit’s qubits among the computers in the network, and scheduling communication operations, called migrations, to share quantum information among the computers to ensure that every operation can be performed locally. While the first step is an intractable problem, we present a polynomial-time solution for the second step in a special setting, and a O(log n)-approximate solution in the general setting. We provide empirical results which show that our two-step solution outperforms existing heuristic for this problem by a significant margin (up to 90%, in some cases).

In this paper, we address the problem of Multiple Transmitters Localization (MTL), i.e., to determine the locations of potential multiple transmitters in a field, based on readings from a distributed set of sensors. In contrast to the widely studied single transmitter localization problem, the MTL problem has only been studied recently in a few works. MTL problem is of great significance in many applications wherein intruders may be present. E.g., in shared spectrum systems, detection of unauthorized transmitters is imperative to efficient utilization of the shared spectrum.In this paper, we present DeepMTL, a novel deep-learning approach to address the MTL problem. In particular, we frame MTL as a sequence of two steps, each of which is a computer vision problem: image-to-image translation and object detection. The first step of image-to-image translation essentially maps an input image representing sensor readings to an image representing distribution of transmitter locations, and the second object detection step derives precise locations of transmitters from the image of transmitter distributions. For the first step, we design our learning model sen2peak, while for the second step, we customize a state-of-the-art object detection model YOLOv3-cust. We demonstrate the effectiveness of our approach via extensive large-scale simulations, and show that our approach outperforms the previous approaches significantly (by 50% or more) in accuracy performance metrics, and incurs an order of magnitude less latency compared to other prior works.

Circuit switched networks with high-bandwidth links are essential to handling ever increasing traffic demands in today's data centers. As these networks incur a non-trivial reconfiguration delay, they are mainly suited for bursty traffic or large flows. To address the reconfiguration delay vs. high-bandwidth tradeoff in circuit networks, an essential traffic scheduling problem is to determine a sequence of network configurations to optimally serve a given traffic. Recent works have addressed this scheduling problem for one-hop traffic in fully-connected circuit networks.

We address the problem of localizing an (illegal) transmitter using a distributed set of sensors. Our focus is on developing techniques that perform the transmitter localization in an efficient manner, wherein the efficiency is defined in terms of the number of sensors used to localize. Localization of illegal transmitters is an important problem which arises in many important applications, e.g., in patrolling of shared spectrum systems for any unauthorized users. Localization of transmitters is generally done based on observations from a deployed set of sensors with limited resources, thus it is imperative to design techniques that minimize the sensors' energy resources. In this paper, we design greedy approximation algorithms for the optimization problem of selecting a given number of sensors in order to maximize an appropriately defined objective function of localization accuracy. The obvious greedy algorithm delivers a constant-factor approximation only for the special case of two hypotheses (potential locations). For the general case of multiple hypotheses, we design a greedy algorithm based on an appropriate auxiliary objective function - and show that it delivers a provably approximate solution for the general case. We develop techniques to significantly reduce the time complexity of the designed algorithms, by incorporating certain observations and reasonable assumptions. We evaluate our techniques over multiple simulation platforms, including an indoor as well as an outdoor testbed, and demonstrate the effectiveness of our designed techniques - our techniques easily outperform prior and other approaches by up to 50-60% in large-scale simulations.

We address the problem of localizing multiple intruders (unauthorized transmitters) using a distributed set of sensors in the context of a shared spectrum system. In contrast to single transmitter localization, multiple transmitter localization (MTL) has not been thoroughly studied. In shared spectrum systems, it is important to be able to localize simultaneously present multiple intruders to effectively protect a shared spectrum from malware-based, jamming, or other multi-device unauthorized-usage attacks. The key challenge in solving the MTL problem comes from the need to "separate" an aggregated signal received from multiple intruders into separate signals from individual intruders. Furthermore, in a shared spectrum paradigm, presence of an evolving set of authorized users (e.g., primary and secondary users) adds to the challenge.In this paper, we propose an efficient algorithm for the MTL problem based on the hypothesis-based Bayesian approach called MAP. Direct application of the MAP approach to the MTL problem incurs prohibitive computational and training cost. In this work, we develop optimized techniques based on MAP with significantly improved computational and training costs. In particular, we develop a novel interpolation method, ILDW, which helps minimize the training cost. We generalize our techniques via online-learning to the setting wherein there may be a set of dynamically-changing authorized users present in the background. We evaluate our developed techniques on large-scale simulations as well as on small-scale indoor and outdoor testbeds. Our experiments demonstrate that our technique outperforms the prior approaches by significant margins, i.e., error up to 74% less in large-scale simulations and 30% less in real-world testbeds.

Shared spectrum systems is an emerging paradigm to improve spectrum utilization and thus address the unabated increase in mobile data consumption. The paradigm allows the “unused” spectrum bands of licensed Primary Users (PUs) to be shared with Secondary Users (SUs), without causing any harmful interference to the PUs. Allocation of spectrum to the SUs is done based on spectrum availability at the SUs' locations; such allocation of spectrum is greatly facilitated by spectrum occupancy maps. In this work, we address the problem of creating spectrum occupancy maps from spectrum occupancy data over a large number of instants, in the challenging scenario of dynamically (temporally) changing spectrum occupancy due to intermittent transmission of primary users. The problem is particularly challenging when the available occupancy data is very sparse spatially, i.e., only very few locations report sensing data at any particular instant. We design various techniques to create spectrum maps in the above context, including a promising correlation-based merging method that merges observation vectors iteratively in conjunction with careful interpolation. Using extensive simulation over data including real data from cellular and deployed WiFi settings, we show that the correlation-based method is very effective in generating high-accuracy spatiotemporal spectrum maps even with very sparse observation vectors (as long as the number of such vectors is large enough).

We use a crowdsourcing approach for RF spectrum patrolling, where heterogeneous, low-cost spectrum sensors are deployed widely and are tasked with detecting unauthorized transmissions in a collaborative fashion while consuming only a limited amount of resources. We pose this as a collaborative signal detection problem where the individual sensor's detection performance may vary widely based on their respective hardware or software configurations, but are hard to model using traditional approaches. Still an optimal subset of sensors and their configurations must be chosen to maximize the overall detection performance subject to given resource (cost) limitations. We present the challenges of this problem in crowdsourced settings and present a set of methods to address them. The proposed methods use data-driven approaches to model individual sensors and develops mechanisms for sensor selection and fusion while accounting for their correlated nature. We present performance results using examples of commodity-based spectrum sensors and show significant improvements relative to baseline approaches.

The virtual network embedding (VNE) problem of mapping virtual network (VN) requests to a substrate network is a key component of network virtualization in datacenters. In a bid to improve datacenter network's performance and cost, there has been recent interest in "reconfigurable" network architectures, wherein the network topology can be changed at runtime to better handle current traffic patterns. Such reconfigurable networks seem naturally well-suited for efficient network virtualization- as networks can be "tailored" to accommodate the incoming VN requests. Motivated by the above, in this paper, we address the problem of virtual network embedding in reconfigurable networks; to the best of our knowledge, this has not been addressed before. In particular, we address the VNE problem in reconfigurable networks under two different models of VN link demands: fixed-bandwidth and stochastic-bandwidth demands. The former is the traditional model, while we propose the the latter to improve network utilization and leverage the runtime reconfiguration capability of reconfigurable networks. For the stochastic demand model, we employ a novel concept of embedding with "runtime-binding", wherein the embedding of a VN link is "configured" at runtime (via network reconfiguration) depending on the prevailing network state and traffic. We evaluate the efficiency of our proposed models and techniques via simulation using real VN requests and traffic statistics from large datacenters, and show that our proposed models and techniques offer significant performance advantages (up to 30-40%) over traditional models.

We describe an end-to-end platform called SpecSense to support large scale spectrum monitoring. SpecSense crowdsources spectrum monitoring to low-cost, low-power commodity SDR/embedded platforms and provides necessary analytics support in a central spectrum server. In this work, we describe SpecSense and address specific challenges related to accurately estimate spectrum occupancy on demand with low overhead. To address the accuracy question, we augment state-of-the-art spatial interpolation techniques to accommodate scenarios where RF propagation characteristics change across space. To address the overhead question, we solve the sensor selection problem to select the minimum number of spectrum sensors that can best estimate the spectrum at the requested locations.

Expected increase in cellular demand has pushed recent interest in picocell networks which have reduced cell sizes (100-200m or less). For ease of deployment of such networks, a wireless backhaul network is highly desired. Since RF-based technologies are unlikely to provide the desired multi-gigabit data rates, we motivate and explore use of free space optics (FSO) for picocell backhaul. In particular, we present a novel network architecture based on steerable links and sufficiently many robust short-range links, to help circumvent the key challenge of outdoor effects in reliable operation of outdoor FSO links. Our architecture is motivated by the fact that, due to the high density of picocells, many short-range links will occur naturally in a picocell backhaul. Moreover, use of steerable FSO links facilitates networks with sufficient redundancy while using only a small number of interfaces per node. We address the key problems that arise in the context of such a backhaul architecture, viz., an FSO link design with desired characteristics, and related network design and management problems. We develop and evaluate a robust 100m FSO link prototype, and simulate the proposed architecture in many metro US cities while show its viability via evaluation of key performance metrics.

To overcome the shortcomings of traditional static (wired) data center architectures, we recently proposed FireFly, a fully-flexible and fully-wireless data center network fabric based on free space optical (FSO) links. To facilitate a clear line-of-sight between the FSO devices placed on racks, FireFly uses a full-ceiling mirror for beam redirection. Use of a full-ceiling mirror imposes significant operational and infrastructural challenge and expense. The focus of our paper is to propose and evaluate alternative schemes to provide line-of-sight for FSO links in FireFly. In particular, we propose two schemes: (i) strategically placed multiple but small overhead mirrors, and (2) “towers” on top of racks, on which FSOs can be placed at regular heights. We develop comprehensive techniques for the above suggested schemes, and demonstrate the viability of these schemes by evaluating their performance using simulations for various performance metrics of interest.

Conventional static datacenter (DC) network designs offer extreme cost vs. performance tradeoffs---simple leaf-spine networks are cost-effective but oversubscribed, while "fat tree"-like solutions offer good worst-case performance but are expensive. Recent results make a promising case for augmenting an oversubscribed network with reconfigurable inter-rack wireless or optical links. Inspired by the promise of reconfigurability, this paper presents FireFly, an inter-rack network solution that pushes DC network design to the extreme on three key fronts: (1) all links are reconfigurable; (2) all links are wireless; and (3) non top-of-rack switches are eliminated altogether. This vision, if realized, can offer significant benefits in terms of increased flexibility, reduced equipment cost, and minimal cabling complexity. In order to achieve this vision, we need to look beyond traditional RF wireless solutions due to their interference footprint which limits range and data rates. Thus, we make the case for using free-space optics (FSO). We demonstrate the viability of this architecture by (a) building a proof-of-concept prototype of a steerable small form factor FSO device using commodity components and (b) developing practical heuristics to address algorithmic and system-level challenges in network design and management.

In cellular networks, a recent trend in research is to make spectrum access dynamic in the spatial and temporal dimensions for the sake of efficient utilization of spectrum. In one such model, the spectrum is divided into channels and periodically allocated to competing base stations using an auction-based market mechanism. An “efficient” auction mechanism is essential to the success of such a dynamic spectrum access model. A key objective in designing an auction mechanism is “truthfulness.” Combining this objective with an optimization of some social choice function (such as the social-welfare or the generated revenue) is highly desirable. In this paper, we design polynomial-time spectrum auction mechanisms that are truthful and yield an allocation with O(1)-approximate social-welfare or revenue. Our mechanisms generalize to general interference models. To the best of our knowledge, ours is the first work to design polynomial-time truthful spectrum auction mechanisms with a constant-factor approximation of either the expected revenue or the social-welfare. We demonstrate the performance of our designed mechanism through simulations.

We explore the vision of an all-wireless inter-rack datacenter fabric. Such a fabric, if realized, can offer operator the ability to dynamically reconfigure the network topology to adapt to future traffic demands while eliminating concerns related to cabling complexity. A key enabler for our vision is the use of free space optical (FSO) technology which, in contrast to traditional wireless/RF technologies, has lower interference footprint, can support longer range, and offers higher bandwidths. While FSO is an enabler, there are several significant practical challenges that need to be addressed before this vision turns into reality. We demonstrate the early promise of addressing these challenges and the potential benefits that this offers in comparison to state-of-the-art datacenter architectures.

The volume of data in broadband cellular network is growing exponentially. However, studies have indicated the traffic load on the cellular base stations varies significantly over time. This gives an opportunity to accommodate additional traffic with the same network capacity if some of the traffic (e.g., p2p, cloud sync) can be amenable to `delayed scheduling' without hurting the user experience any significantly. In this paper, we study various algorithmic problems that can arise in this context. Using a model where all flows can have certain flexibility in scheduling (via use of a `deadline'), we develop optimal or near-optimal algorithms to determine the minimum network capacity for two different models. We also develop various semi-online and online algorithms for online scheduling of flows, and analyze their performance. In particular, even though the online scheduling problem is shown to be intractable, our proposed semi-online algorithm can schedule flows optimally if aided by historical data and slightly additional network capacity over the optimal. Finally, using flow level traffic traces collected at the core of a commercially operated cellular network, we evaluate the effectiveness of our techniques. Evaluations show that delayed scheduling, when done efficiently (using an offline optimal algorithm), can accommodate the same traffic with much lower network capacity (up to 50% less) with only modest delays. While such an optimal solution needs an offline approach, we demonstrate that online scheduling can be almost equally effective when historical traffic data can be exploited for estimation purposes.

Femtocells are short-range devices deployed to provide increased coverage and capacity in a small area. They offer a way to increase the capacity of a cellular network by relaying cellular traffic to the wired network. In this paper, we address the problem of optimizing the overall capacity of a femtocell network, as defined by Shannon's law and physical interference, by appropriate power and channel assignment to the femtocells. In particular, we design an approximation algorithm for the objective of maximizing the total network capacity, for large uniform networks with arbitrary coverage regions. We also consider the second objective of maximizing the minimum capacity at a femtocell in the network, and design an algorithm for arbitrary networks which has an appropriate performance guarantee if there is a lower-bound on the distance of any two femtocells. Through simulations, we demonstrate the performance of our designed algorithms by comparing them with a bound on the optimal values.

In this paper, we address the problem of preserving generated data in a sensor network in case of node failures. We focus on the type of node failures that have explicit spatial shapes such as circles or rectangles (e.g., modeling a bomb attack or a river overflow). We consider two different schemes for introducing redundancy in the network, by simply replicating data or by using erasure codes, with the objective to minimize the communication cost incurred to build such data redundancy. We prove that the problem is NP-hard using either replication or coding. We design Oα-approximation centralized and distributed algorithms for the two redundancy schemes, where α is the "fatness" of the potential node failure events. Using erasure codes, data distribution can be handled in an efficient distributed manner. Simulation results show that by exploiting the spatial properties of the node failure patterns, one can substantially reduce the communication cost compared to the resilient data storage schemes in the prior literature.

We analyze several new problems that arise from the use of rotating directional sensors. The coverage region of a rotating directional sensor is restricted to a certain direction, and its orientation varies at constant speed. For already placed rotating directional sensors, we consider three problems for which the goal is to minimize the dark time (i.e. uncovered time) of all point in the area. We also consider the problem of placement and orientation of the minimum number of sensors, so to reduce to zero the dark time of all points. In addition, we study barrier coverage problems, in which the goal is to detect all intruders (or the largest number of them) that are trying to cross the monitored area. We show that these problems are NP-hard and some of them also NP-hard to approximate. We provide approximations algorithms that are easy to decentralize, and hence allow the sensors to self organize themselves.

Developing powerful paradigms for programming sensor networks is critical to realize the full potential of sensor networks as collaborative data processing engines. In this article, we motivate and develop a deductive framework for programming sensor networks, extending the prior vision of viewing sensor network as a distributed database. The deductive programming approach is declarative, very expressive, and amenable to automatic optimizations. Such a framework allows users to program sensor network applications at a high-level without worrying about the low-level tedious details. Our system translates a given deductive program to efficient distributed code that runs on individual nodes. To facilitate the above translation, we develop techniques for distributed and asynchronous evaluation of deductive programs in sensor networks. Our techniques generalize to recursive programs without negations, arbitrary non- recursive programs with negations, and in general to arbitrary "locally non-recursive" programs with function symbols. We present performance results on TOSSIM, a network simulator, and a small network testbed.

Sensor nodes may be equipped with a "directional" sensing device (such as a camera) which senses a physical phenomenon in a certain direction depending on the chosen orientation. In this article, we address the problem of selection and orientation of such directional sensors with the objective of maximizing coverage area. Prior works on sensor coverage have largely focused on coverage with sensors that are associated with a unique sensing region. In contrast, directional sensors have multiple sensing regions associated with them, and the orientation of the sensor determines the actual sensing region. Thus, the coverage problems in the context of directional sensors entails selection as well as orientation of sensors needed to activate in order to maximize/ensure coverage. In this article, we address the problem of selecting a minimum number of sensors and assigning orientations such that the given area (or set of target points) is k-covered (i.e., each point is covered k times). The above problem is NP-complete, and even NP-hard to approximate. Thus, we design a simple greedy algorithm that delivers a solution that k-covers at least half of the target points using at most M log(k|C|) sensors, where |C| is the maximum number of target points covered by a sensor and M is the minimum number of sensor required to k-cover all the given points. The above result holds for almost arbitrary sensing regions. We design a distributed implementation of the above algorithm, and study its performance through simulations. In addition to the above problem, we also look at other related coverage problems in the context of directional sensors, and design similar approximation algorithms for them.

Sensor networks are multihop wireless networks of resource-constrained sensor nodes used to realize high-level collaborative sensing tasks. To query or access data generated by the sensor nodes, the sensor network can be viewed as a distributed database. In this paper, we develop algorithms for communication-efficient implementation of join of multiple (two or more) data streams in a sensor network. The distributed implementation of join in sensor networks is particularly challenging due to unique characteristics of the sensor networks such as limited memory and battery energy on individual nodes, arbitrary and dynamic network topology, multihop communication, and unreliable infrastructure. One of our proposed approaches, viz., the perpendicular approach (PA), is load balanced, and in fact, incurs near-optimal communication cost for the special case of binary joins in grid networks under the assumption of uniform generation of tuples across the network. We compare the performance of our designed approaches through extensive simulations on the ns2 simulator, and show that PA results in substantially prolonging the network lifetime compared to other approaches, especially for joins involving spatial constraints.

One of the useful approaches to exploit redundancy in a sensor network is to keep active only a small subset of sensors that are sufficient to cover the region required to be monitored. The set of active sensors should also form a connected communication graph, so that they can autonomously respond to application queries and/or tasks. Such a set of active sensors is known as a connected sensor cover, and the problem of selecting a minimum connected sensor cover has been well studied when the transmission radius and sensing radius of each sensor is fixed. In this article, we address the problem of selecting a minimum energy-cost connected sensor cover, when each sensor node can vary its sensing and transmission radius; larger sensing or transmission radius entails higher energy cost. For the aforesaid problem, we design various centralized and distributed algorithms, and compare their performance through extensive experiments. One of the designed centralized algorithms (called CGA) is shown to perform within an O (log n ) factor of the optimal solution, where n is the size of the network. We have also designed a localized algorithm based on Voronoi diagrams which is empirically shown to perform very close to CGA and, due to its communication-efficiency, results in significantly prolonging the network lifetime. We also extend the aforementioned algorithms to incorporate fault tolerance. In particular, we show how to extend the algorithms to address the minimum energy-cost connected sensor k -cover problem, in which every point in the query region needs to be covered by at least k distinct active sensors. The CGA preserves the approximation bound in this case. We also propose a localized topology control scheme to preserve k -connectivity, and use it to extend the Voronoi-based approach to computing a minimum energy-cost k 1 -connected k 2 -cover. We study the performance of our proposed algorithms through extensive simulations.

In this paper, we consider multihop wireless mesh networks, where each router node is equipped with multiple radio interfaces, and multiple channels are available for communication. We address the problem of assigning channels to communication links in the network with the objective of minimizing the overall network interference. Since the number of radios on any node can be less than the number of available channels, the channel assignment must obey the constraint that the number of different channels assigned to the links incident on any node is at most the number of radio interfaces on that node. The above optimization problem is known to be NP-hard. We design centralized and distributed algorithms for the above channel assignment problem. To evaluate the quality of the solutions obtained by our algorithms, we develop a semidefinite program and a linear program formulation of our optimization problem to obtain lower bounds on overall network interference. Empirical evaluations on randomly generated network graphs show that our algorithms perform close to the above established lower bounds, with the difference diminishing rapidly with increase in number of radios. Also, ns-2 simulations, as well as experimental studies on testbed, demonstrate the performance potential of our channel assignment algorithms in 802.11-based multiradio mesh networks.

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is nontrivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least 1/4 (1/2 for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2) and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [33]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios such as higher access frequency and smaller memory.

In this article, we design techniques that exploit data correlations in sensor data to minimize communication costs (and hence, energy costs) incurred during data gathering in a sensor network. Our proposed approach is to select a small subset of sensor nodes that may be sufficient to reconstruct data for the entire sensor network. Then, during data gathering only the selected sensors need to be involved in communication. The selected set of sensors must also be connected, since they need to relay data to the data-gathering node. We define the problem of selecting such a set of sensors as the connected correlation-dominating set problem, and formulate it in terms of an appropriately defined correlation structure that captures general data correlations in a sensor network. We develop a set of energy-efficient distributed algorithms and competitive centralized heuristics to select a connected correlation-dominating set of small size. The designed distributed algorithms can be implemented in an asynchronous communication model, and can tolerate message losses. We also design an exponential (but nonexhaustive) centralized approximation algorithm that returns a solution within O (log n ) of the optimal size. Based on the approximation algorithm, we design a class of centralized heuristics that are empirically shown to return near-optimal solutions. Simulation results over randomly generated sensor networks with both artificially and naturally generated data sets demonstrate the efficiency of the designed algorithms and the viability of our technique—even in dynamic conditions.

Manycast is a group communication primitive wherein the source is required to send data packets to a certain number of a given set of destinations. In this article, we design fault-tolerant protocols for manycast operations in sensor networks with mobile destinations. To develop efficient protocols, we propose a location management scheme, which manages information about the locations of mobile destinations in a distributed manner. Based upon that, we develop rectangle-based and GridTree-based fault-tolerant manycast routing protocols. Simulation results show that the GridTree approach achieves sufficiently high success ratio, while using minimal transmission cost.

Radio frequency identification (RFID) is a technology where a reader device can "sense" the presence of a close-by object by reading a tag device attached to the object. To improve coverage, multiple RFID readers can be deployed in the given region. In this paper, we consider the problem of slotted scheduled access of RFID tags in a multiple reader environment. In particular, we develop centralized algorithms in a slotted time model to read all the tags using near-optimal number of time slots. We consider two scenarios -one wherein the tag distribution in the physical space is unknown, and the other where tag distribution is known or can be estimated a priori. For each of these scenarios, we consider two cases depending on whether a single channel or multiple channels are available. All the above version of the problem are NP-hard. We design approximation algorithms for the single channel and heuristic algorithms for the multiple channel cases. Through extensive simulations, we show that for the single channel case, our heuristics perform close to the approximation algorithms. In general, our simulations show that our algorithms significantly outperform colorwave, an existing algorithm for similar problems.

The goal in this paper is to develop comprehensive protocol support in all layers to provide max-min fairness for multihop flows in a wireless mesh network. Our approach has three parts. First, we estimate the max-min fair rate of all multihop flows in the network using a distributed protocol. This estimation uses the knowledge of the flow contention graph that the network nodes learn by exchanging local information. Second, the nodes enforce this rate by controlling the rate at which a flow is scheduled to the link layer. Third, a back pressure flow control is used to reduce the transmission rate of a flow if it has been exceeding its fair rate. Finally, we argue that the fair rate estimation can at best be approximated in an 802.11 based MAC protocol. Thus, to complement our fair rate estimation and scheduling procedures, we develop a virtual time based MAC protocol. We demonstrate via extensive simulations the benefit of all these approaches for ensuring fairness relative to the base case that uses 802.11 MAC and FIFO scheduling.

Caching can significantly improve the efficiency of information access in networks by reducing the access latency and bandwidth usage. However, excessive caching can lead to prohibitive system cost and performance degradation. In this article, we consider the problem of caching a data item in a network wherein the data item is read as well as updated by other nodes and there is a limit on the number of cache nodes allowed. More formally, given a network graph, the read/write frequencies to the data item by each node, and the cost of caching the data item at each node, the problem addressed in this article is to select a set of P nodes to cache the data item such that the sum of the reading, writing (using an optimal Steiner tree), and storage cost is minimized. For networks with a tree topology, we design an optimal dynamic programming algorithm that runs in O(|V|3P2), where |V| is the size of the network and P is the allowed number of caches. For the general graph topology, where the problem is NP-complete, we present a centralized heuristic and its distributed implementation. Through extensive simulations in general graphs, we show that the centralized heuristic performs very close to the exponential optimal algorithm for small networks, and for larger networks, the distributed implementation and the dynamic programming algorithm on an appropriately extracted tree perform quite close to the centralized heuristic.

Directional antennas in wireless mesh networks can improve spatial reuse. However, using them effectively needs specialized protocol support at the MAC layer, which is always not practical. In this work, we present a topology control approach to effectively using directional antennas with legacy MAC layer protocols such as IEEE 802.11. The idea is to use multiple directional antennas on each node and orient them appropriately to create low interference topologies while maintatining network connectivity. Our approach is based on a well-known approximation algorithm to compute minimum degree spanning trees. We show via empirical studies that this approach can reduce interference significantly without increasing stretch factors to any appreciable extent. Detailed wireless network simulations also show that this approach improves end-to-end throughput of multihop flows relative to using omni-directional antennas. Three or four directional antennas per network node with only moderate beamwidths are sufficient to improve the saturation throughput of multihop flows by a factor of 3-4.

Data caching can significantly improve the efficiency of information access in a wireless ad hoc network by reducing the access latency and bandwidth usage. However, designing efficient distributed caching algorithms is non-trivial when network nodes have limited memory. In this article, we consider the cache placement problem of minimizing total data access cost in ad hoc networks with multiple data items and nodes with limited memory capacity. The above optimization problem is known to be NP-hard. Defining benefit as the reduction in total access cost, we present a polynomial-time centralized approximation algorithm that provably delivers a solution whose benefit is at least one-fourth (one-half for uniform-size data items) of the optimal benefit. The approximation algorithm is amenable to localized distributed implementation, which is shown via simulations to perform close to the approximation algorithm. Our distributed algorithm naturally extends to networks with mobile nodes. We simulate our distributed algorithm using a network simulator (ns2), and demonstrate that it significantly outperforms another existing caching technique (by Yin and Cao [30]) in all important performance metrics. The performance differential is particularly large in more challenging scenarios, such as higher access frequency and smaller memory.

In this paper, we propose two new MAC protocols for multichannel operation in wireless ad hoc and mesh networks. The first protocol, extended receiver directed transmission protocol (xRDT) is based on a previously known multichannel solution called receiver directed transmission (RDT) that uses a notion of quiescent channel. xRDT solves the problems faced by RDT, such as multichannel hidden terminal and deafness, by using an additional busy tone interface and few additional protocol operations. We also develop a novel single interface solution, called local coordination-based multichannel MAC (LCM MAC). LCM MAC performs coordinated channel negotiations and channel switching to provide multichannel support. We demonstrate the effectiveness of these two protocols over two other well-known multichannel protocols - MMAC and DCA - via extensive ns2 simulations

In this paper, we design techniques that exploit data correlations in sensor data to minimize communication costs (and hence, energy costs) incurred during data gathering in a sensor network. Our proposed approach is to select a small subset of sensor nodes that may be sufficient to reconstruct data for the entire sensor network. Then, during data gathering only the selected sensors need to be involved in communication. The selected set of sensors must also be connected, since they need to relay data to the data-gathering node. We define the problem of selecting such a set of sensors as the connected correlation-dominating set problem, and formulate it in terms of an appropriately defined correlation structure that captures general data correlations in a sensor network.We develop a set of energy-efficient distributed algorithms and competitive centralized heuristics to select a connected correlation-dominating set of small size. The designed distributed algorithms can be implemented in an asynchronous communication model, and can tolerate message losses. We also design an exponential (but non-exhaustive) centralized approximation algorithm that returns a solution within O(log n) of the optimal size. Based on the approximation algorithm, we design a class of efficient centralized heuristics that are empirically shown to return near-optimal solutions. Simulation results over randomly generated sensor networks with both artificially and naturally generated data sets demonstrate the efficiency of the designed algorithms and the viability of our technique -- even in dynamic conditions.

Abstract — Sensor networks are often deployed in a redundant fashion. In order to prolong the network lifetime, it is desired to choose only a subset of sensors to keep active and put the rest to sleep. In order to provide fault tolerance, this small subset of active sensors should also provide some degree of redundancy. In this paper, we consider the problem of choosing a minimum subset of sensors such that they maintain a required degree of coverage and also form a connected network with a required degree of fault tolerance. In addition, we consider a more general, variable radii sensor model, wherein every sensor can adjust both its sensing and transmission ranges to minimize overall energy consumption in the network. We call this thevariableradiik1-Connected, k2-Cover problem. To address this problem, we propose a distributed and localized Voronoibased algorithm. The approach extends the relative neighborhood graph (RNG) structure to preserve k-connectivity in a graph, and design a distributed technique to inactivate desirable nodes while preserving k-connectivity of the remaining active nodes. We show through extensive simulations that our proposed techniques result in overall energy savings in random sensor networks over a wide range of experimental parameters. I.

A data warehouse stores materialized views of data from one or more sources, with the purpose of efficiently implementing decision-support or OLAP queries. One of the most important decisions in designing a data warehouse is the selection of materialized views to be maintained at the warehouse. The goal is to select an appropriate set of views that minimizes total query response time and the cost of maintaining the selected views, given a limited amount of resource, e.g., materialization time, storage space, etc. In This work, we have developed a theoretical framework for the general problem of selection of views in a data warehouse. We present polynomial-time heuristics for a selection of views to optimize total query response time under a disk-space constraint, for some important special cases of the general data warehouse scenario, viz.: 1) an AND view graph, where each query/view has a unique evaluation, e.g., when a multiple-query optimizer can be used to general a global evaluation plan for the queries, and 2) an OR view graph, in which any view can be computed from any one of its related views, e.g., data cubes. We present proofs showing that the algorithms are guaranteed to provide a solution that is fairly close to (within a constant factor ratio of) the optimal solution. We extend our heuristic to the general AND-OR view graphs. Finally, we address in detail the view-selection problem under the maintenance cost constraint and present provably competitive heuristics.

In overdeployed sensor networks, one approach to conserve energy is to keep only a small subset of sensors active at any instant. We consider the problem of selecting a minimum size connected K-cover, which is defined as a set of sensors M such that each point in the sensor network is "covered" by at least K different sensors in M, and the communication graph induced by M is connected. For the above optimization problem, we design a centralized approximation algorithm that delivers a near-optimal (within a factor of O(lg n)) solution, and present a distributed version of the algorithm. We also present a communication-efficient localized distributed algorithm which is empirically shown to perform well.

One of the useful approaches to exploit redundancy in a sensor network is to actively keep only a small subset of sensors that are sufficient to cover the region required to be monitored. The set of active sensors should also form a connected communication graph, so that they can autonomously respond to application queries and/or tasks. Such a set of active sensors is known as a connected sensor cover, and the problem of selecting a minimum connected sensor cover has been well studied when the transmission radius and sensing radius of each sensor is fixed. In this article, we address the problem of selecting a minimum energy-cost connected sensor cover, when each sensor node can vary its sensing and transmission radius; larger sensing or transmission radius entails higher energy cost. For the above problem, we design various centralized and distributed algorithms, and compare their performance through extensive experiments. One of the designed centralized algorithms (called CGA) is shown to perform within an O(log n) factor of the optimal solution, where n is the size of the network. We have also designed a localized algorithm based on Voronoi diagrams which is empirically shown to perform very close to CGA, and due to its communication-efficiency, results in significantly prolonging the network lifetime.

Spatial query execution is an essential functionality of a sensor network, where a query gathers sensor data within a specific geographic region. Redundancy within a sensor network can be exploited to reduce the communication cost incurred in execution of such queries. Any reduction in communication cost would result in an efficient use of the battery energy, which is very limited in sensors. One approach to reduce the communication cost of a query is to self-organize the network, in response to a query, into a topology that involves only a small subset of the sensors sufficient to process the query. The query is then executed using only the sensors in the constructed topology.In this article, we design and analyze algorithms for such self-organization of a sensor network to reduce energy consumption. In particular, we develop the notion of a connected sensor cover and design a centralized approximation algorithm that constructs a topology involving a near-optimal connected sensor cover. We prove that the size of the constructed topology is within an log n factor of the optimal size, where n is the network size. We also develop a distributed self-organization version of our algorithm, and propose several optimizations to reduce the communication overhead of the algorithm. Finally, we evaluate the distributed algorithm using simulations and show that our approach results in significant communication cost reduction.

On-line analytical processing (OLAP) is a recent and important application of database systems. Typically, OLAP data is presented as a multidimensional "data cube." OLAP queries are complex and can take many hours or even days to run, if executed directly on the raw data. The most common method of reducing execution time is to precompute some of the queries into summary tables (subcubes of the data cube) and then to build indexes on these summary tables. In most commercial OLAP systems today, the summary tables that are to be precomputed are picked first, followed by the selection of the appropriate indexes on them. A trial-and-error approach is used to divide the space available between the summary tables and the indexes. This two-step process can perform very poorly. Since both summary tables and indexes consume the same resource-space-their selection should be done together for the most efficient use of space. The authors give algorithms that automate the selection of summary tables and indexes. In particular, they present a family of algorithms of increasing time complexities, and prove strong performance bounds for them. The algorithms with higher complexities have better performance bounds. However, the increase in the performance bound is diminishing, and they show that an algorithm of moderate complexity can perform fairly close to the optimal.

Summary form only given. The goal of the Whips project (WareHousing Information Project at Stanford) is to develop algorithms and tools for the creation and maintenance of a data warehouse (J. Wiener et al., 1996). In particular, we have developed an architecture and implemented a prototype for identifying data changes at distributed heterogeneous sources, transforming them and summarizing them in accordance with warehouse specifications, and incrementally integrating them into the warehouse. In effect, the warehouse stores materialized views of the source data. The Whips architecture is designed specifically to fulfil several important and interrelated goals: sources and warehouse views can be added and removed dynamically; it is scalable by adding more internal modules; changes at the sources are detected automatically; the warehouse may be updated continuously as the sources change, without requiring down time; and the warehouse is always kept consistent with the source data by the integration algorithms. The Whips system is composed of many distinct modules that potentially reside on different machines. Each module is implemented as a CORBA object. They communicate with each other using ILU, a COBRA compliant object library developed by Xerox PARC.

A data warehouse is a repository of integrated information from distributed, autonomous, and possibly heterogeneous, sources. In effect, the warehouse stores one or more materialized views of the source data. The data is then readily available to user applications for querying and analysis. Figure 1 shows the basic architecture of a warehouse: data is collected from each source, integrated with data from other sources, and stored at the warehouse. Users then access the data directly from the warehouse.