42739196
MAP: Medial axis based geometric routing in sensor networks
One of the challenging tasks in the deployment of dense wireless networks (like sensor networks) is in devising a routing scheme for node to node communication. Important consideration includes scalability, routing complexity, quality of communication paths and the load sharing of the routes. In this paper, we show that a compact and expressive abstraction of network connectivity by the medial axis enables efficient and localized routing. We propose MAP, a Medial Axis based naming and routing Protocol that does not require geographical locations, makes routing decisions locally, and achieves good load balancing. In its preprocessing phase, MAP constructs the medial axis of the sensor field, defined as the set of nodes with at least two closest boundary nodes. The medial axis of the network captures both the complex geometry and non-trivial topology of the sensor field. It can be represented succinctly by a graph whose size is in the order of the complexity of the geometric features (e.g., the number of holes). Each node is then given a name related to its position with respect to the medial axis. The routing scheme is derived through local decisions based on the names of the source and destination nodes and guarantees delivery with reasonable and natural routes. We show by both theoretical analysis and simulations that our medial axis based geometric routing scheme is scalable, produces short routes, achieves excellent load balancing, and is very robust to variations in the network model.
207794
Trade-Offs between Stretch Factor and Load-Balancing Ratio in Routing on Growth-Restricted Graphs
An unweighted graph has density rho and growth rate k if the number of nodes in every ball with radius r is bounded by rhork. The communication graphs of wireless networks and peer-to-peer networks often have constant bounded density and small growth rate. In this paper, we study the trade-off between two quality measures for routing in growth-restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load-balancing ratio, which measures the evenness of the traffic distribution. We show that if the routing algorithm is required to use paths with stretch factor c, then its load-balancing ratio is bounded by O(rho1/k(n/c)1-1/k), and the bound is tight in the worst case. We show the application and extension of the trade-off to the wireless network routing and VLSI layout design. We also present a load-balanced routing algorithm with the stretch factor constraint in an online setting, in which the routing requests come one by one.
2954526
Analysis of Incomplete Data and an Intrinsic-Dimension Helly Theorem
The analysis of incomplete data is a long-standing challenge in practical statistics. When, as is typical, data objects are represented by points in ℝd, incomplete data objects correspond to affine subspaces (lines or Δ-flats). With this motivation we study the problem of finding the minimum intersection radiusr(ℒ) of a set of lines or Δ-flats ℒ: the least r such that there is a ball of radius r intersecting every flat in ℒ. Known algorithms for finding the minimum enclosing ball for a point set (or clustering by several balls) do not easily extend to higher-dimensional flats, primarily because “distances” between flats do not satisfy the triangle inequality. In this paper we show how to restore geometry (i.e., a substitute for the triangle inequality) to the problem, through a new analog of Helly’s theorem. This “intrinsic-dimension” Helly theorem states: for any family ℒ of Δ-dimensional convex sets in a Hilbert space, there exist Δ+2 sets ℒ′⊆ℒ such that r(ℒ)≤2r(ℒ′). Based upon this we present an algorithm that computes a (1+ε)-core set ℒ′⊆ℒ, |ℒ′|=O(Δ4/ε), such that the ball centered at a point c with radius (1+ε)r(ℒ′) intersects every element of ℒ. The running time of the algorithm is O(nΔ+1dpoly (Δ/ε)). For the case of lines or line segments (Δ=1), the (expected) running time of the algorithm can be improved to O(ndpoly (1/ε)). We note that the size of the core set depends only on the dimension of the input objects and is independent of the input size n and the dimension d of the ambient space.
10628567
Shape Segmentation and Applications in Sensor Networks
Many sensor network protocols in the literature implicitly assume that sensor nodes are deployed uniformly inside a simple geometric region. When the real deployment deviates from that, we often observe degraded performance. It is desirable to have a generic approach to handle a sensor field with complex shape. In this paper, we propose a segmentation algorithm that partitions an irregular sensor field into nicely shaped pieces such that algorithms and protocols that assume a nice sensor field can be applied inside each piece. Across the segments, problem dependent structures specify how the segments and data collected in these segments are integrated. This unified topology-adaptive spatial partitioning would benefit many settings that currently assume a nicely shaped sensor field. Our segmentation algorithm does not require sensor locations and only uses network connectivity information. Each node is given a 'flow direction' that directs away from the network boundary. A node with no flow direction becomes a sink, and attracts other nodes in the same segment. We evaluate the performance improvements by integrating shape segmentation with applications such as distributed indices and random sampling.
45076012
Discrete Mobile Centers 


Abstract. We propose a new randomized algorithm for maintaining a set of clusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. This clustering algorithm is distributed in nature and can enable numerous applications in ad hoc wireless networks, where mobile devices must be interconnected to perform various tasks collaboratively.

1839876
Discrete mobile centers
\emph{We propose a new randomized algorithm for maintaining a set of c lusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. The algorithm can be implemented without exact knowledge of the node positions, if each node is able to sense its distance to other nodes up to the cluster radius. Such a kinetic clustering can be used in numerous applications where mobile devices must be interconnected into an ad-hoc network to collaboratively perform some task.}
14303513
A scalable peer-to-peer system for music content and information retrieval
Currently a large percentage of Internet traf£c consists of music £les, typically stored in MP3 compressed audio format, shared and exchanged over Peer-to-Peer (P2P) networks. Searching for music is performed by specifying keywords and naive string matching techniques. In the past years the emerging research area of Music Information Retrieval (MIR) has produced a variety of new ways of looking at the problem of music search. Such MIR techniques can signi£cantly enhance the ways user search for music over P2P networks. In order for that to happen there are two main challenges that need to be addressed: 1) scalability to large collections and number of peers, 2) richer set of search semantics that can support MIR especially when retrieval is content-based. In this paper, we describe a scalable P2P system that uses Rendezvous Points (RPs) for music metadata registration and query resolution, that supports attributevalue search semantics as well as content-based retrieval. The performance of the system has been evaluated in large scale usage scenarios using “real” automatically calculated musical content descriptors.
15355925
Customizable virtual private network service with QoS
Abstract In this paper, we propose and implement Virtual Network Service (VNS), a value-added network service for deploying virtual private networks (VPNs) in a managed wide-area IP network. The key feature of VNS is its capability of providing a customer with a VPN that is customizable with management capabilities and performance properties comparable to a dedicated physical network. In addition, VNS ensures confidentiality of data and principals through the use of IPSEC. The main technique underlying VNS is the virtualization of routers in both control and data planes. Virtualization of the control plane enables customizable routing and signaling per VPN. On the data plane, packet forwarding and link bandwidth are virtualized. Virtualization of the forwarding mechanism on the data plane enables forwarding of traffic according to each VPN's topology and policies. Virtualization of the link bandwidth enables each VPN to have guaranteed quality of service (QoS) and customized resource management policies. We have developed a VNS prototype for deployment on the CAIRN network. The VNS prototype implements several resource management mechanisms including packet scheduling, signaling and runtime monitoring. A graphical user interface enables service providers to manage, configure and deploy VPNs remotely.
17256385
A flocking based algorithm for document clustering analysis
Social animals or insects in nature often exhibit a form of emergent collective behavior known as flocking. In this paper, we present a novel Flocking based approach for document clustering analysis. Our Flocking clustering algorithm uses stochastic and heuristic principles discovered from observing bird flocks or fish schools. Unlike other partition clustering algorithm such as K-means, the Flocking based algorithm does not require initial partitional seeds. The algorithm generates a clustering of a given set of data through the embedding of the high-dimensional data items on a two-dimensional grid for easy clustering result retrieval and visualization. Inspired by the self-organized behavior of bird flocks, we represent each document object with a flock boid. The simple local rules followed by each flock boid result in the entire document flock generating complex global behaviors, which eventually result in a clustering of the documents. We evaluate the efficiency of our algorithm with both a synthetic dataset and a real document collection that includes 100 news articles collected from the Internet. Our results show that the Flocking clustering algorithm achieves better performance compared to the K- means and the Ant clustering algorithm for real document clustering.
8204298
Improved Source-Channel Models for Chinese Word Segmentation
This paper presents a Chinese word segmentation system that uses improved source-channel models of Chinese sentence generation. Chinese words are defined as one of the following four types: lexicon words, morphologically derived words, factoids, and named entities. Our system provides a unified approach to the four fundamental features of word-level Chinese language processing: (1) word segmentation, (2) morphological analysis, (3) factoid detection, and (4) named entity recognition. The performance of the system is evaluated on a manually annotated test set, and is also compared with several state-of-the-art systems, taking into account the fact that the definition of Chinese words often varies from system to system.
37200874
Some remarks on Kalman filters for the multisensor fusion
Abstract Multisensor data fusion has found widespread application in industry and commerce. The purpose of data fusion is to produce an improved model or estimate of a system from a set of independent data sources. There are various multisensor data fusion approaches, of which Kalman filtering is one of the most significant. Methods for Kalman filter based data fusion includes measurement fusion and state fusion. This paper gives first a simple a review of both measurement fusion and state fusion, and secondly proposes two new methods of state fusion based on fusion procedures at the prediction and update level, respectively, of the Kalman filter. The theoretical derivation for these algorithms are derived. To illustrate their application, a simple example is performed to evaluate the proposed methods and compare their performance with the conventional state fusion method and measurement fusion methods.