7456112
Efficient and guaranteed service coverage in partitionable mobile ad-hoc networks
In wireless ad-hoc networks, the network topology changes dynamically and unpredictably due to node mobility. Such topological dynamics are further exacerbated by the natural grouping behavior in the mobile user's movement, which leads to frequent network partitioning. Network partitioning poses significant challenges to the provisioning of centralized services in ad-hoc networks, since partitioning disconnects many mobile users from the central server. We propose a collection of novel run-time algorithms that adaptively ensure the centralized service is available to all mobile nodes during network partitioning, while minimizing the number of servers required. The network-wide service coverage is achieved by partition prediction and service replication on the servers, and assisted by distributed service selection on regular mobile nodes. Simulation results show that our algorithm efficiently achieves guaranteed service coverage to all nodes. To the best of our knowledge, there have been no similar approaches that use partition prediction to provision centralized services adaptively in partitionable mobile ad-hoc networks.
584351
Efficient peer-to-peer data dissemination in mobile ad-hoc networks
Without infrastructural support from base stations, mobile nodes in an ad hoc network communicate with each other in a peer-to-peer fashion. This poses a challenge in data dissemination among the mobile peers, each having limited transmission range and unpredictable mobility. We first propose a novel mobility model to characterize user mobility in a civilian environment, such as a college campus. We then propose the application of Tornado coding as an efficient solution to the challenge of ad hoc peer-to-peer data dissemination. A mobile node is able to download coded file segments from different peers-at different times and in different locations. When it receives sufficient segments, it will be able to re-construct the original file. Although Tornado coding itself is not new, we for the first time propose its application to mobile ad hoc data dissemination. Furthermore, we show how Tornado coding parameters affect the performance of peer-to-peer data dissemination.
2274256
Overlay Networks with Linear Capacity Constraints
Overlay networks are virtual networks residing over the IP network; consequently, overlay links may share hidden lower level bottlenecks. Previous work has assumed an independent overlay model: a graph with independent link capacities. We introduce a model of overlays that incorporates correlated link capacities and linear capacity constraints (LCC) to formulate hidden shared bottlenecks; we refer to these as LCC-overlays. We define metrics to qualitatively measure overlay quality in terms of its accuracy (in representing the true network topology) and efficiency (that is, performance). Through analysis and simulations, we show that LCC-overlay is perfectly accurate and, hence, enjoys much higher efficiency than the inaccurate independent overlay. We discover that even a highly restricted LCC class-node-based LCC-yields near-optimal accuracy and significantly higher efficiency. We study two network flow problems in the context of LCC-graphs: widest path and maximum flow. We prove that Widest Path with LCC is NP-complete. We formulate Maximum Flow with LCC as a linear program and propose an efficient distributed algorithm to solve it. Based on the LCC model, we further study the problem of optimizing delay while still maintaining optimal or near-optimal bandwidth. We also outline a distributed algorithm to efficiently construct an overlay with node-based LCC.
5921080
Dynamic reconfiguration for complex multimedia applications
Current state-of-the-art distributed multimedia applications require an environment that provides stable quality of service (QoS). However, these applications typically run on best-effort heterogeneous platforms, and compete with other applications or connections for end system and network resources, hence suffer from instability and dynamic variations with regards to QoS. We present a dynamically reconfigurable middleware control architecture to enhance adaptation awareness of these applications. Our middleware architecture allows for detecting QoS fluctuations in the surrounding environment and signaling optimal control actions to the application. Furthermore, we discuss the design of a core component, the Configurator, that adopts a fuzzy control approach to compute optimal control actions. Preliminary experimental results with a distributed visual tracking application show that our approach is viable and effective in controlling adaptive applications.
1974741
Strategyproof Mechanisms towards Dynamic Topology Formation in Autonomous Networks
In autonomous networks, cooperations among nodes cannot be assumed, since each node is capable of making independent decisions based on their personal preferences. In particular, when a node needs the help of intermediate nodes to relay messages to other nodes, these intermediaries may be reluctant to contribute their network resource for the benefit of others. Ideally, the right amount of incentives should be provided to motivate cooperations among autonomous nodes so that a mutually beneficial network results. In this paper, we leverage the power of mechanism design in microeconomics to design a distributed incentive mechanism that motivates each node towards a more desirable network topology. Since network parameters and constraints change dynamically in reality, the desirable topology can vary over time. Our solution presented in this paper has successfully encompassed such a dynamic nature of the network topology. In addition, we have transformed our solution to an easy-to-implement distributed algorithm, that converges towards the globally optimal topology.
8043231
QoS-Aware Adaptive Services in Mobile Ad-Hoc Networks
Ad-hoc wireless networks consist of mobile nodes interconnected by multi-hop wireless paths. Unlike conventional wireless networks, ad-hoc networks have no fixed network infrastructure or administrative support. Because of the dynamic nature of the network topology and limited bandwidth of wireless channels, Quality-of-Service (QoS) provisioning is an inherently complex and difficult issue. In this paper, we propose a fully distributed and adaptive algorithm to provide statistical QoS guarantees with respect to accessibility of services in an ad-hoc network. In this algorithm, we focus on the optimization of a new QoS parameter of interest, service efficiency, while keeping protocol overheads to the minimum. To achieve this goal, we first theoretically derive the lower and upper bounds of service efficiency based on a novel model for group mobility, followed by extensive simulation results to verify the effectiveness of our algorithm.
14151705
An adaptive k-nearest neighbor text categorization strategy
k is the most important parameter in a text categorization system based on the k-nearest neighbor algorithm (kNN). To classify a new document, the k-nearest documents in the training set are determined first. The prediction of categories for this document can then be made according to the category distribution among the k nearest neighbors. Generally speaking, the class distribution in a training set is not even; some classes may have more samples than others. The system's performance is very sensitive to the choice of the parameter k. And it is very likely that a fixed k value will result in a bias for large categories, and will not make full use of the information in the training set. To deal with these problems, an improved kNN strategy, in which different numbers of nearest neighbors for different categories are used instead of a fixed number across all categories, is proposed in this article. More samples (nearest neighbors) will be used to decide whether a test document should be classified in a category that has more samples in the training set. The numbers of nearest neighbors selected for different categories are adaptive to their sample size in the training set. Experiments on two different datasets show that our methods are less sensitive to the parameter k than the traditional ones, and can properly classify documents belonging to smaller classes with a large k. The strategy is especially applicable and promising for cases where estimating the parameter k via cross-validation is not possible and the class distribution of a training set is skewed.
5536365
Simulation of Diabetic Retinopathy Neovascularization in Color Digital Fundus Images
Diabetic retinopathy (DR) has been identified as a leading cause of blindness. One type of lesion, neovascularization (NV), indicates that the disease has entered a vision-threatening phase. Early detection of NV is thus clinically significant. Efforts have been devoted to use computer-aided analyses of digital retina images to detect DR. However, developing reliable NV detection algorithms requires large numbers of digital retinal images to test and refine approaches. Computer simulation of NV offers the potential of developing lesion detection algorithms without the need for large image databases of real pathology. In this paper, we propose a systematic approach to simulating NV. Specifically, we propose two algorithms based on fractal models to simulate the main structure of NV and an adaptive color generation method to assign photorealistic pixel values to the structure. Moreover, we develop an interactive system that provides instant visual feedback to support NV simulation guided by an ophthalmologist. This enables us to combine the low level algorithms with high-level human feedback to simulate realistic lesions. Experiments suggest that our method is able to produce simulated NVs that are indistinguishable from real lesions.
3580064
Bit section instruction set extension of ARM for embedded applications
Programs that manipulate data at subword level, i.e. bit sections within a word, are common place in the embedded domain. Examples of such applications include media processing as well as network processing codes. These applications spend significant amounts of time packing and unpacking narrow width data into memory words. The execution time and memory overhead of packing and unpacking operations can be greatly reduced by providing direct instruction set support for manipulating bit sections.In this paper we present the Bit Section eXtension (BSX) to the ARM instruction set. We selected the ARM processor for this research because it is one of the most popular embedded processor which is also being used as the basis of building many commercial network processing architectures. We present the design of BSX instructions and their encoding into the ARM instruction set. We have incorporated the implementation of BSX into the Simplescalar ARM simulator from Michigan. Results of experiments with programs from various benchmark suites show that by using BSX instructions the total number of instructions executed at runtime by many transformed functions are reduced by 4.26% to 27.27% and their code sizes are reduced by `1.27% to 21.05%.
12626074
Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks
Blocking probability has been one of the key performance indexes in the design of wavelength-routed all-optical WDM networks. Existing research has demonstrated that an effective Routing and Wavelength Assignment (RWA) algorithm and wavelength conversion are two primary vehicles for improving the blocking performance. However, these two issues have largely been investigated separately; in particular the existing RWA algorithms have seldom considered the presence of wavelength conversion. In this paper, we firstly demonstrate that the existing dynamic RWA algorithms do not work well in the presence of wavelength conversion as they usually only take into account the current traffic, and do not explicitly consider the route lengths. We then propose a weighted least-congestion routing and first-fit wavelength assignment (WLCR-FF) algorithm that considers both the current traffic load and the route lengths jointly. We further introduce an analytical model that can evaluate the blocking performance for WLCR algorithm. We carry out extensive numerical studies over typical topologies including ring, mesh-torus, and the 14-node NSFNET; and compare the performance of WLCR-FF with a wide variety of existing routing algorithms including static routing, fixed-alternate routing and least-loaded routing. The results conclusively demonstrate that the proposed WLCR-FF algorithm can achieve much better blocking performance in the presence of sparse or/and full wavelength conversion.
15445828
Analysis of a class of nonconforming finite elements for crystalline microstructures
An analysis is given for a class of nonconforming Lagrange-type finite elements which have been successfully utilized to approximate the solution of a variational problem modeling the deformation of martensitic crystals with microstructure. These elements were first proposed and analyzed in 1992 by Rannacher and Turek for the Stokes equation. Our analysis highlights the features of these elements which make them effective for the computation of microstructure. New results for superconvergence and numerical quadrature are also given.