999307
A counterexample in congestion control of wireless networks
One of the triumphs of wireline network research of the last decade has been the casting of the Internet congestion control problem within an optimization framework based on utility functions. Such an approach provides a sound understanding of the underlying stability and fairness issues, as well as a post-facto justification of TCP-like additive-increase multiplicative-decrease (AIMD) algorithms. This paper provides a counter-example showing that the same result cannot be extended to wireless networks, at least not in a straightforward manner.The fundamental difference is that wireless networks are of a broadcast nature. There is no strict notion of a "link," since transmissions from nearby nodes interfere with each other. Using a simple model of interference in wireless networks, a counter-example of a wireless network is presented in which the congestion control mechanism has an unstable equilibrium point at the desired fair solution. Further, ns-2 simulations of this counter-example manifest an oscillatory behavior. Surprisingly, this oscillatory behavior appears to be fairly typical in wireless networks, with most randomly chosen network examples manifesting it. This loss of stability suggests a possible need for the re-design of wireless TCP and wireless queue management to explicitly account for the wireless nature of the effects of interference. wireless interference can make this mechanism unstable. We present counter-example wireless graphs and flow patterns in which the congestion control mechanism fails to remain stable. ns-2 simulations indicate that this loss of stability manifests in practice as oscillatory behavior. Moreover, this oscillatory behavior is fairly typical in wireless networks. This loss of stability suggests a need for the re-design of wireless TCP and wireless queue management to explicitly account for the effects of interference.
17708128
Extended message passing algorithm for inference in loopy Gaussian graphical models
Abstract We consider message passing for probabilistic inference in undirected Gaussian graphical models. We show that for singly connected graphs, message passing yields an algorithm that is equivalent to the application of Gaussian elimination to the solution of a particular system of equations. This relation provides a natural way of extending message passing to arbitrary graphs with loops by first studying the operations required by Gaussian elimination. We thus obtain a finite time convergent algorithm that solves the inference problem exactly and whose complexity grows gradually with the “distance” of the graph to a tree. This algorithm can be implemented in a distributed fashion at nodes through message passing, as for example in sensor networks.
7286364
Capacity bounds for ad hoc and hybrid wireless networks
We study the capacity of static wireless networks, both ad hoc and hybrid, under the Protocol and Physical Models of communication, proposed in [1]. For ad hoc networks with <i>n</i> nodes, we show that under the Physical Model, where signal power is assumed to attenuate as 1/r<sup>α</sup>, α > 2, the transport capacity scales as Θ(√<i>n</i>) bit-meters/sec. The same bound holds even when the nodes are allowed to approach arbitrarily close to each other and even under a more generalized notion of the Physical Model wherein the data rate is Shannon's logarithmic function of the SINR at the receiver. This result is sharp since it closes the gap that existed between the previous best known upper bound of O(<i>n</i><sup>α-1/α</sup>) and lower bound of Ω(√n).
 We also show that any spatio-temporal scheduling of transmissions and their ranges that is feasible under the Protocol Model can also be realized under the Physical Model by an appropriate choice of power levels for appropriate thresholds. This allows the generalization of various lower bound constructions from the Protocol Model to the Physical Model. In particular, this provides a better lower bound on the best case transport capacity than in [1].
 For hybrid networks, we consider an overlay of μ<i>n</i> randomly placed wired base stations. It has previously been shown in [6] that if all nodes adopt a common power level, then each node can be provided a throughput of at most Θ(1/log <i>n</i>) to randomly chosen destinations. Here we show that by allowing nodes to perform power control and properly choosing ν(1/log <i>n</i>), it is further possible to provide a throughput of Θ(1) to any fraction <i>f</i>, 0 < <i>f</i> < 1, of nodes. This result holds under both the Protocol and Physical models of communication. On the one hand, it shows that that the aggregate throughput capacity, measured as the sum of individual throughputs, can scale linearly in the number of nodes. On the other hand, the result underscores the importance of choosing minimum power levels for communication and suggests that simply communicating with the closest node or base station could yield good capacity even for multihop hybrid wireless networks.
8476709
On the /spl theta/-coverage and connectivity of large random networks
Wireless planar networks have been used to model wireless networks in a tradition that dates back to 1961 to the work of E. N. Gilbert. Indeed, the study of connected components in wireless networks was the motivation for his pioneering work that spawned the modern field of continuum percolation theory. Given that node locations in wireless networks are not known, random planar modeling can be used to provide preliminary assessments of important quantities such as range, number of neighbors, power consumption, and connectivity, and issues such as spatial reuse and capacity. In this paper, the problem of connectivity based on nearest neighbors is addressed. The exact threshold function for /spl theta/-coverage is found for wireless networks modeled as n points uniformly distributed in a unit square, with every node connecting to its /spl phi//sub n/ nearest neighbors. A network is called /spl theta/-covered if every node, except those near the boundary, can find one of its /spl phi//sub n/ nearest neighbors in any sector of angle /spl theta/. For all /spl theta//spl isin/(0,2/spl pi/), if /spl phi//sub n/=(1+/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, it is shown that the probability of /spl theta/-coverage goes to one as n goes to infinity, for any /spl delta/>0; on the other hand, if /spl phi//sub n/=(1-/spl delta/)log/sub 2/spl pi//2/spl pi/-/spl theta//n, the probability of /spl theta/-coverage goes to zero. This sharp characterization of /spl theta/-coverage is used to show, via further geometric arguments, that the network will be connected with probability approaching one if /spl phi//sub n/=(1+/spl delta/)log/sub 2/n. Connections between these results and the performance analysis of wireless networks, especially for routing and topology control algorithms, are discussed.
15090068
A simple provable algorithm for curve reconstruction
We present an algorithm that provably reconstructs a curve in the framework introduced by Amenta, Bern and Eppstein. The highlights of the algorithm are: (i) it is simple, (ii) it requires a sampling density better than previously known, (iii) it can be adapted for curve reconstruction in higher dimensions straightforwardly.
6513086
Hand Recognition Using Geometric Classifiers
We discuss the issues and challenges in the design of a hand outline based recognition system. Our system is easier to use, cheaper to build and more accurate than previous systems. Extensive tests on more than 700 images collected from 70 people are reported. Classification, verification and identification of the input images were done using two simple geometric classifiers. We describe a novel minimum enclosing ball classifier which performs well for hand recognition and could be of interest for other applications.
42584661
Minimal Vertex Separators of Chordal Graphs
Chordal graphs form an important and widely studied subclass of perfect graphs. The set of minimal vertex separators constitute an unique class of separators of a chordal graph and capture the structure of the graph. In this paper, we explore the connection between perfect elimination orderings of a chordal graph and its minimal vertex separators. Specifically, we prove a characterization of these separators in terms of the monotone adjacency sets of the vertices of the graph, numbered by the maximum cardinality search (MCS) scheme. This leads to a simple linear-time algorithm to identify the minimal vertex separators of a chordal graph using the MCS scheme. We also introduce the notion of multiplicity of a minimal vertex separator which indicates the number of different pairs of vertices separated by it. We prove a useful property of the lexicographic breadth first scheme (LBFS) that enables us to determine the multiplicities of minimal vertex separators of a chordal graph.
45262024
Some new bounds on the spectral radius of graphs
The eigenvalues of a graph are the eigenvalues of its adjacency matrix. This paper presents some upper and lower bounds on the greatest eigenvalue and a lower bound on the smallest eigenvalue.
15224609
Codes for Optical CDMA
There has been a recent upsurge of interest in applying Code Division Multiple Access (CDMA) techniques to optical networks. Conventional spreading codes for OCDMA, known as optical orthogonal codes (OOC) spread the signal in the time domain only, which often results in the requirement of a large chip rate. By spreading in both time and wavelength using two-dimensional OOCs, the chip rate can be reduced considerably. This paper presents an overview of 1-D and 2-D optical orthogonal codes as well as some new results relating to bounds on code size and code construction.