No abstract available.

We consider a wireless network of n nodes that communicate over a common wireless medium under some interference constraints. Our work is motivated by the need for an efficient and distributed algorithm to determine the n2 dimensional unicast capacity region of such a wireless network. Equivalently, given a vector of end-to-end rates between various source-destination pairs, we seek to determine if it can be supported by the network through a combination of routing and scheduling decisions. This question is known to be NP-hard and hard to even approximate within n1-o(1)factor for general graphs. In this paper, we first show that the whole n2dimensional unicast capacity region can be approximated to (1 plusmn epsiv) factor in polynomial time, and in a distributed manner, whenever the Max Weight Independent Set (MWIS) problem can be approximated in a similar fashion for the corresponding topology. We then consider wireless networks which are usually formed between nodes that are placed in a geographic area and come endowed with a certain geometry, and argue that such situations do lead to approximations to the MWIS problem (in fact, in a completely distributed manner, in a time that is essentially linear in n). Consequently, this gives us a polynomial algorithm to approximate the capacity of wireless networks to arbitrary accuracy. This result hence, is in sharp contrast with previous works that provide algorithms with at least a constant factor loss. An important ingredient in establishing our result is the transient analysis of the maximum weight scheduling algorithm, which can be of interest in its own right.

Rate allocation is a fundamental problem in the operation of a wireless network because of the necessity to schedule the operation of mutually interfering links between the nodes. Among the many reasons behind the importance of efficiently determining the membership of an arbitrary rate vector in the feasibility region, is its high relevance in optimal cross layer design. A key feature in a wireless network is that links without common nodes can also conflict (secondary interference constraints). While the node exclusive model problem has efficient algorithms, it has long been known that this is a hard problem with these additional secondary constraints. However, wireless networks are usually deployed in geographic areas that do not span the most general class of all graphs possible. This is the underlying theme of this paper, where we provide algorithms for two restricted instances of wireless network topologies. In the first tractable instance, we consider nodes placed arbitrarily in a region such that (a) the node density is bounded, and (b) a node can only transmit or interfere with other nodes that are within a certain limited radius. We obtain a simple (1 - epsi) polynomial-time approximation scheme for checking feasibility (for any epsi > 0). The second instance considers the membership problem of an arbitrary rate-vector in the feasible set, where the nodes are distributed within a slab of fixed width (there are no density assumptions). Specifically, the results in [13] are shown to extend to a much more general class of graphs, which we call the (dmin,dmax) class of graphs, and this generalization is used to obtain a strongly polynomial time algorithm that decides membership of a rate-vector where the hosts are distributed within an infinite corridor with fixed cross-section.

Fountain codes are designed for erasure channels, and are particularly well suited for broadcast applications from a single source to its one hop receivers. In this context, the problem of designing a rateless code in the network case for on-the-fly recoding is very important, as relaying the data over multiple nodes is fundamentally useful in a network. Clearly, fountain codes are unsuited for on-line recoding (and simply forwarding over subsequent hops is provably suboptimal). Random linear codes are throughput optimal, but they do not enjoy the low complexity that is a prime feature of fountain codes. Can we get the low complexity of say, LT codes, while maintaining on-the-fly recoding and being throughput optimal? This paper proposes a novel solution to the above question. We consider packet level coding on a line network of discrete memoryless erasure channels (with potentially unlimited nodes), and exhibhit a coding scheme with (1) tatelessness (2) logarithmic per-symbol coding complexity (3) throughput optimality (achieves rates equal the min cut capacity) and (4) avoids the delay of having to decode and then re-encode entire block lengths at intermediate nodes.

The ubiquity of 802.11 devices and networks enables anyone to track our every move with alarming ease. Each 802.11 device transmits a globally unique and persistent MAC address and thus is trivially identifiable. In response, recent research has proposed replacing such identifiers with pseudonyms (i.e., temporary, unlinkable names). In this paper, we demonstrate that pseudonyms are insufficient to prevent tracking of 802.11 devices because implicit identifiers, or identifying characteristics of 802.11 traffic, can identify many users with high accuracy. For example, even without unique names and addresses, we estimate that an adversary can identify 64 % of users with 90 % accuracy when they spend a day at a busy hot spot. We present an automated procedure based on four previously unrecognized implicit identifiers that can identify users in three real 802.11 traces even when pseudonyms and encryption are employed. We find that the majority of users can be identified using our techniques, but our ability to identify users is not uniform; some users are not easily identifiable. Nonetheless, we show that even a single implicit identifier is sufficient to distinguish many users. Therefore, we argue that design considerations beyond eliminating explicit identifiers (i.e., unique names and addresses), must be addressed in order to prevent user tracking in wireless networks. Categories and Subject Descriptors:

It is currently difficult to build practical and reliable programming systems out of distributed and resource-constrained sensor devices. The state of the art in today's sensornet programming is centered around a component-based language called nesC. nesC is a node-level language-a program is written for an individual node in the network-and nesC programs use the services of an operating system called TinyOS. We are pursuing an approach to programming sensor networks that significantly raises the level of abstraction over this practice. The critical change is one of perspective: rather than writing programs from the point of view of an individual node, programmers implement a central program that conceptually has access to the entire network. This approach pushes to the compiler the task of producing node-level programs that implement the desired behavio.

We study the impact on 802.11 networks of RF interference from devices such as Zigbee and cordless phones that increasingly crowd the 2.4GHz ISM band, and from devices such as wireless camera jammers and non-compliant 802.11 devices that seek to disrupt 802.11 operation. Our experiments show that commodity 802.11 equipment is surprisingly vulnerable to certain patterns of weak or narrow-band interference. This enables us to disrupt a link with an interfering signal whose power is 1000 times weaker than the victim's 802.11 signals, or to shut down a multiple AP, multiple channel managed network at a location with a single radio interferer. We identify several factors that lead to these vulnerabilities, ranging from MAC layer driver implementation strategies to PHY layer radio frequency implementation strategies. Our results further show that these factors are not overcome by simply changing 802.11 operational parameters (such as CCA threshold, rate and packet size) with the exception of frequency shifts. This leads us to explore rapid channel hopping as a strategy to withstand RF interference. We prototype a channel hopping design using PRISM NICs, and find that it can sustain throughput at levels of RF interference well above that needed to disrupt unmodified links, and at a reasonable cost in terms of switching overheads.

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.

Recent sensor networks research has produced a class of data storage and query processing techniques called data-centric storage that leverages locality-preserving distributed indexes to efficiently answer multi-dimensional range and range-aggregate queries. These distributed indexes offer a rich design space of a) logical decompositions of sensor relation schema into indexes, as well as b) physical mappings of these indexes onto sensors. In this paper, we explore this space for energy-efficient data organizations (logical and physical mappings of tuples and attributes to sensor nodes) and devise purely local query optimization techniques for processing queries that span such decomposed relations.

The recent trend of rapid increase in routing table sizes at routers comprising the Internet's core is posing a serious challenge to the current Internet's scalability, availability, and stability. Multihoming is a prime contributor to this table size explosion. This paper argues that it is possible to a) scale the Internet's routing table sub-linearly with degree of multihoming, and b) improve routing convergence times even under pervasive multihoming using simple and incrementally deployable extensions to today's routing protocols. We present an addressing and routing protocol called SIMPLER (scalable IP multihoming protocol leveraging routing), which is designed to minimize and contain the propagation in space and time of non-aggregatable routes. SIMPLER's prefix containment property results in lower lookup and route processing costs (promotes scalability), and faster convergence time (helps network availability and stability). SIMPLER vastly diminishes the number of non-aggregatable prefixes appearing in the Internet core due to multihoming (to zero in the absence of network faults, and O(number of faults) otherwise), and always leaks fewer non-aggregatable prefixes than today's dominant multihoming strategy of "hole punching". Additionally, SIMPLER provides transport-layer survivability (TLS) and better routing policy management, while offering the same routing robustness as today's multihoming. The main cost of SIMPLER is the increased use of address space (O(log(network size)) in the average case). SIMPLER is carefully designed to be useful to both multihomed transit providers and multihomed leaf sites.

Wireless sensor networks research has, till date, made impressive advances in platforms and software services. Research in the area has moved on to consider an essential piece of sensor network technology---support for programming wireless sensor network applications and systems components at a suitably high level of abstraction. Two broad classes of programming models are currently being investigated by the community. One class focuses on providing higher-level abstractions for specifying a node's local behavior in a distributed computation. Examples of this approach include the recent work on node-local or region-based abstractions. By contrast, a second and less-explored class of research considers programming a sensor network in the large called macroprogramming.

Recent sensor networks research has produced a class of data storage and query processing techniques called Data-Centric Storage that leverages locality-preserving distributed indexes like DIM, DIFS, and GHT to efficiently answer multi-dimensional range and range-aggregate queries. These distributed indexes offer a rich design space of a) logical decompositions of sensor relation schema into indexes, as well as b) physical mappings of these indexes onto sensors. In this poster, we explore this space for energy-efficient data organizations (logical and physical mappings of tuples and attributes to sensor nodes) and devise purely local query optimization techniques for processing queries that span such decomposed relations. We propose four design techniques: (a) fully decomposing the base sensor relation into distinct sub-relations, (b) spatially partitioning these sub-relations across the sensornet, (c) localized query planning and optimization to find fully decentralized optimal join orders, and (d) locally caching join results. Together, these optimizations reduce the overall network energy consumption by 4 times or more when compared against the standard single multi-dimensional distributed index on a variety of synthetic query workloads simulated over both synthetic and real-world datasets. We validate the feasibility of our approach by implementing a functional prototype of our data organizer and query processor on Mica2 motes and observing comparable message cost savings.

The various proposed DHT routing algorithms embody several different underlying routing geometries. These geometries include hypercubes, rings, tree-like structures, and butterfly networks. In this paper we focus on how these basic geometric approaches affect the resilience and proximity properties of DHTs. One factor that distinguishes these geometries is the degree of flexibility they provide in the selection of neighbors and routes. Flexibility is an important factor in achieving good static resilience and effective proximity neighbor and route selection. Our basic finding is that, despite our initial preference for more complex geometries, the ring geometry allows the greatest flexibility, and hence achieves the best resilience and proximity performance.

This paper presents and analyzes IPNL (for IP Next Layer), a NAT-extended Internet protocol architecture designed to scalably solve the address depletion problem of IPv4. A NAT-extended architecture is one where only hosts and NAT boxes are modified. IPv4 routers and support protocols remain untouched. IPNL attempts to maintain all of the original characteristics of IPv4, most notably address prefix location independence. IPNL provides true site isolation (no renumbering), and allows sites to be multi-homed without polluting the default-free routing zone with per-site prefixes. We discuss IPNL's architectural benefits and drawbacks, and show that it comes acceptably close to achieving its goals.

OceanStore is a utility infrastructure designed to span the globe and provide continuous access to persistent information. Since this infrastructure is comprised of untrusted servers, data is protected through redundancy and cryptographic techniques. To improve performance, data is allowed to be cached anywhere, anytime. Additionally, monitoring of usage patterns allows adaptation to regional outages and denial of service attacks; monitoring also enhances performance through pro-active movement of data. A prototype implementation is currently under development.