Sitemap
 
 
IEEE Projects
>>
  Hiding Sensitive

>>
  Encouraging Persons

>>
  Truth Discovery

>>
  Reverse Nearest Neighbors

 
Search Projects
Project
Example keywords: image compression, B Sc, networking, etc
 
 
 
 
 
 
IEEE Category
 
    >> My Projects  
    >> Latest IEEE Projects  
    >> Image Processing  
    >> Networking  
    >> Network Security  
    >> Data Mining  
    >> Neural Network  
    >> Mobile Computing  
    >> Application Projects  
    >> Web Application Projects  
    >> Knowledge and Data Engineering  
    >> Parallel and Distributed Systems  
    >> Recently Downloaded  
 
 
 
 
Project Request
 
 
Name*
E-Mail*
Mobile*
Domain*
Comments*
 
 
 
Projects
 
Project Title
No. of Downloads
Action
Reverse Nearest Neighbors Search in Ad-hoc Subspaces
5
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Given an object q, modeled by a multidimensional point, a reverse nearest neighbors (RNN) query returns the set of objects in the database that have q as their nearest neighbor. In this paper, we study an interesting generalization of the RNN query, where not all dimensions are considered, but only an ad hoc subset thereof. The rationale is that 1) the dimensionality might be too high for the result of a regular RNN query to be useful, 2) missing values may implicitly define a meaningful subspace for RNN retrieval, and 3) analysts may be interested in the query results only for a set of (ad hoc) problem dimensions (i.e., object attributes). We consider a suitable storage scheme and develop appropriate algorithms for projected RNN queries, without relying on multidimensional indexes. Given the significant cost difference between random and sequential data accesses, our algorithms are based on applying sequential accesses only on the projected atomic values of the data at each dimension, to progressively derive a set of RNN candidates. Whether these candidates are actual RNN results is then validated via an optimized refinement step. In addition, we study variants of the projected RNN problem, including RkNN search, bichromatic RNN, and RNN retrieval for the case where sequential accesses are not possible. Our methods are experimentally evaluated with real and synthetic data
A Web Usage Mining Framework for Mining Evolving User Profiles
10
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we present a complete framework and findings in mining Web usage patterns from Web log files of a real Web site that has all the challenging aspects of real-life Web usage mining, including evolving user profiles and external data describing ontology of the Web content. Even though the Web site under study is part of a nonprofit organization that does not “sell” any products, it was crucial to understand “who” the users were, “what” they looked at, and “how their interests changed with time,” all of which are important questions in Customer Relationship Management (CRM). Hence, we present an approach for discovering and tracking evolving user profiles. We also describe how the discovered user profiles can be enriched with explicit information need that is inferred from search queries extracted from Web log data. Profiles are also enriched with other domain-specific information facets that give a panoramic view of the discovered mass usage modes. An objective validation strategy is also used to assess the quality of the mined profiles, in particular their adaptability in the face of evolving user behavior.
Truth Discovery with Multiple Conflicting Information Providers on the Web
25
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The World Wide Web has become the most important information source for most of us. Unfortunately, there is no guarantee for the correctness of information on the Web. Moreover, different websites often provide conflicting information on a subject, such as different specifications for the same product. In this paper, we propose a new problem, called Veracity, i.e., conformity to truth, which studies how to find true facts from a large amount of conflicting information on many subjects that, is provided by various websites. We design a general framework for the Veracity problem and invent an algorithm, called TRUTHFINDER, which utilizes the relationships between websites and their information, i.e., a website is trustworthy if it provides many pieces of true information, and a piece of information is likely to be true if it is provided by many trustworthy websites. An iterative method is used to infer the trustworthiness of websites and the correctness of information from each other. Our experiments show that TRUTHFINDER successfully finds true facts among conflicting information and identifies trustworthy websites better than the popular search engines.
Encouraging Persons with Hearing Problem to Learn Sign Language by Internet Websites
35
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Nowadays the Internet users are from different ages and groups. Disabled people are a group of the Internet users. Some Web sites are especially created for these people. One group of the disabled people are deaf persons. They have a special talking language which is named sign language. Here we present a method to encourage them, esp. children, to learn the sign language. In this method, when a deaf person wants to enter a Web site which is created for deaf persons, a word is shown as a movie using a sign language. The user should recognize the word and select it from a list. If the user understands the sign language and recognizes the word, he/she can enter the website. This project has been implemented by PHP scripting language.
Hiding Sensitive Association Rules with Limited Side Effects
8
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Data mining techniques have been widely used in various applications. However, the misuse of these techniques may lead to the disclosure of sensitive information. Researchers have recently made efforts at hiding sensitive association rules. Nevertheless, undesired side effects, e.g., nonsensitive rules falsely hidden and spurious rules falsely generated may be produced in the rule hiding process. In this paper, we present a novel approach that strategically modifies a few transactions in the transaction database to decrease the supports or confidences of sensitive rules without producing the side effects. Since the correlation among rules can make it impossible to achieve this goal, in this paper, we propose heuristic methods for increasing the number of hidden sensitive rules and reducing the number of modified entries. The experimental results show the effectiveness of our approach, i.e., undesired side effects are avoided in the rule hiding process. The results also report that in most cases, all the sensitive rules are hidden without spurious rules falsely generated. Moreover, the good scalability of our approach in terms of database size and the influence of the correlation among rules on rule hiding are observed.
Integrating Data Warehouses with Web Data: A Survey
10
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper surveys the most relevant research on combining Data Warehouse (DW) and Web data. It studies the XML technologies that are currently being used to integrate, store, query and retrieve web data, and their application to DWs. The paper reviews different DW distributed architectures and the use of XML languages as an integration tool in these systems. It also introduces the problem of dealing with semi-structured data in a DW. It studies Web data repositories, the design of multidimensional databases for XML data sources and the XML extensions of On-Line Analytical Processing techniques. The paper addresses the application of information retrieval technology in a DW to exploit text-rich documents collections. The authors hope that the paper will help to discover the main limitations and opportunities that offer the combination of the DW and the Web fields, as well as, to identify open research lines.
Detecting Word Substitutions in Text
45
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Searching for words on a watch list is one way in which large-scale surveillance of communication can be done, for example in intelligence and counterterrorism settings. One obvious defense is to replace words that might attract attention to a message with other, more innocuous, words. For example, the sentence the attack will be tomorrow" might be altered to the complex will be tomorrow", since 'complex' is a word whose frequency is close to that of 'attack'. Such substitutions are readily detectable by humans since they do not make sense. We address the problem of detecting such substitutions automatically, by looking for discrepancies between words and their contexts, and using only syntactic information. We define a set of measures, each of which is quite weak, but which together produce per-sentence detection rates around 90% with false positive rates around 10%. Rules for combining per sentence detection into per-message detection can reduce the false positive and false negative rates for messages to practical levels. We test the approach using sentences from the Enron email and Brown corpora, representing informal and formal text respectively.
Beyond single-page web search results
5
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Given a user keyword query, current Web search engines return a list of individual Web pages ranked by their "goodness" with respect to the query. Thus, the basic unit for search and retrieval is an individual page, even though information on a topic is often spread across multiple pages. This degrades the quality of search results, especially for long or uncorrelated (multitopic) queries (in which individual keywords rarely occur together in the same document), where a single page is unlikely to satisfy the user's information need. We propose a technique that, given a keyword query, on the fly generates new pages, called composed pages, which contain all query keywords. The composed pages are generated by extracting and stitching together relevant pieces from hyperlinked Web pages and retaining links to the original Web pages. To rank the composed pages, we consider both the hyperlink structure of the original pages and the associations between the keywords within each page. Furthermore, we present and experimentally evaluate heuristic algorithms to efficiently generate the top composed pages. The quality of our method is compared to current approaches by using user surveys. Finally, we also show how our techniques can be used to perform query-specific summarization of Web pages.
Automatic Website Summarization by Image Content: A Case Study with Logo and Trademark Images
21
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Image-based abstraction (or summarization) of a Web site is the process of extracting the most characteristic (or important) images from it. The criteria for measuring the importance of images in Web sites are based on their frequency of occurrence, characteristics of their content and Web link information. As a case study, this work focuses on logo and trademark images. These are important characteristic signs of corporate Web sites or of products presented there. The proposed method incorporates machine learning for distinguishing logo and trademarks from images of other categories (e.g., landscapes, faces). Because the same logo or trademark may appear many times in various forms within the same Web site, duplicates are detected and only unique logo and trademark images are extracted. These images are then ranked by importance taking frequency of occurrence, image content and Web link information into account. The most important logos and trademarks are finally selected to form the image-based summary of a Web site. Evaluation results of the method on real Web sites are also presented. The method has been implemented and integrated into a fully automated image-based summarization system which is accessible on the Web.
Distributional Features for Text Categorization
23
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Text categorization is the task of assigning predefined categories to natural language text. With the widely used 'bag of words' representation, previous researches usually assign a word with values such that whether this word appears in the document concerned or how frequently this word appears. Although these values are useful for text categorization, they have not fully expressed the abundant information contained in the document. This paper explores the effect of other types of values, which express the distribution of a word in the document. These novel values assigned to a word are called distributional features, which include the compactness of the appearances of the word and the position of the first appearance of the word. The proposed distributional features are exploited by a tf idf style equation and different features are combined using ensemble learning techniques. Experiments show that the distributional features are useful for text categorization. In contrast to using the traditional term frequency values solely, including the distributional features requires only a little additional cost, while the categorization performance can be significantly improved. Further analysis shows that the distributional features are especially useful when documents are long and the writing style is casual.
Gossip Trust for Fast Reputation Aggregation in Peer-to-Peer Networks
22
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In peer-to-peer (P2P) networks, reputation aggregation and peer ranking are the most time-consuming and space demanding operations. This paper proposes a gossip-based reputation system (Gossip Trust) for fast aggregation of global reputation scores. It leverages a Bloom filter based scheme for efficient score ranking. Gossip Trust does not require any secure hashing or fast lookup mechanism thus is applicable to both unstructured and structured P2P networks. Randomized gossiping with effective use of power nodes enables fast aggregation and fast dissemination of global scores in O (log2 n) time steps, where n is the network size. The gossip-based protocol is designed to tolerate dynamic peer joining and departure, as well as to avoid possible peer collusions. The scheme has a considerably low gossiping message overhead, i.e. O (nlog2 n) messages for n nodes. Bloom filters reduce the memory overhead per node to 512 KB for a 10,000-node network. We evaluate the performance of Gossip Trust with both P2P file-sharing and parameter-sweeping applications. The simulation results demonstrate that Gossip Trust has small aggregation time, low memory demand, and high ranking accuracy. These results suggest promising advantages of using the Gossip Trust system for trusted P2P computing.
Lazy Approach to Associative Classification
75
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Associative classification is a promising technique to build accurate classifiers. However, in large or correlated data sets, association rule mining may yield huge rule sets. Hence, several pruning techniques have been proposed to select a small subset of high-quality rules. Since the availability of a "rich" rule set may improve the accuracy of the classifier, we argue that rule pruning should be reduced to a minimum. The L3 associative classifier is built by means of a lazy pruning technique that discards exclusively rules that only misclassify training data. The classification of unlabeled data is performed in two steps. A small subset of high-quality rules is first considered. When this set is not able to classify the data, a larger rule set is exploited. This second set includes rules usually discarded by previous approaches. To cope with the need of mining large rule sets and to efficiently use them for classification, a compact form is proposed to represent a complete rule set in a space-efficient way and without information loss. An extensive experimental evaluation on real and synthetic data sets shows that L:i improves the classification accuracy with respect to previous approaches.
On Modularity Clustering
5
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Abstract: Modularity is a recently introduced quality measure for graph clusterings. It has immediately received considerable attention in several disciplines, particularly in the complex systems literature, although its properties are not well understood. We study the problem of finding clusterings with maximum modularity, thus providing theoretical foundations for past and present work based on this measure. More precisely, we prove the conjectured hardness of maximizing modularity both in the general case and with the restriction to cuts and give an Integer Linear Programming formulation. This is complemented by first insights into the behavior and performance of the commonly applied greedy agglomerative approach.
Learning a Maximum Margin Subspace for Image Retrieval
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Abstract: One of the fundamental problems in Content-Based Image Retrieval (CBIR) has been the gap between low-level visual features and high-level semantic concepts. To narrow down this gap, relevance feedback is introduced into image retrieval. With the user-provided information, a classifier can be learned to distinguish between positive and negative examples. However, in real-world applications, the number of user feedbacks is usually too small compared to the dimensionality of the image space. In order to cope with the high dimensionality, we propose a novel semisupervised method for dimensionality reduction called Maximum Margin Projection (MMP). MMP aims at maximizing the margin between positive and negative examples at each local neighborhood. Different from traditional dimensionality reduction algorithms such as Principal Component Analysis (PCA) and Linear Discriminant Analysis (LDA), which effectively see only the global euclidean structure, MMP is designed for discovering the local manifold structure. Therefore, MMP is likely to be more suitable for image retrieval, where nearest neighbor search is usually involved. After projecting the images into a lower dimensional subspace, the relevant images get closer to the query image; thus, the retrieval performance can be enhanced. The experimental results on Corel image database demonstrate the effectiveness of our proposed algorithm.
Incremental Maintenance of Online Summaries Over Multiple Streams
10
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We propose a novel approach based on predictive quantization (PQ) for online summarization of multiple time-varying data streams. A synopsis over a sliding window of most recent entries is computed in one pass and dynamically updated in constant time. The correlation between consecutive data elements is effectively taken into account without the need for preprocessing. We extend PQ to multiple streams and propose structures for real-time summarization and querying of a massive number of streams. Queries on any subsequence of a sliding window over multiple streams are processed in real time. We examine each component of the proposed approach, prediction, and quantization separately and investigate the space-accuracy trade-off for synopsis generation. Complementing the theoretical optimality of PQ-based approaches, we show that the proposed technique, even for very short prediction windows, significantly outperforms the current techniques for a wide variety of query types on both synthetic and real data sets.
A Cost-Based Approach to Adaptive Resource Management in Data Stream Systems
20
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Abstract: Data stream management systems need to adaptively control their resources, since stream characteristics and query workload may vary over time. In this paper, we investigate an approach to adaptive resource management for continuous sliding-window queries that adjusts window sizes and time granularities to keep resource usage within bounds. These two novel techniques differ from standard load shedding approaches based on sampling, as they ensure exact query answers for given user-defined quality of service specifications, even under query reoptimization. In order to quantify the effects of both techniques on the various operations in a query plan, we develop an appropriate cost model for estimating operator resource allocation in terms of memory usage and processing costs. A thorough experimental study not only validates the accuracy of our cost model but also demonstrates the efficacy and scalability of the proposed techniques.
Algorithms for Storytelling
20
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Abstract: We formulate a new data mining problem called storytelling as a generalization of redescription mining. In traditional redescription mining, we are given a set of objects and a collection of subsets defined over these objects. The goal is to view the set system as a vocabulary and identify two expressions in this vocabulary that induce the same set of objects. Storytelling, on the other hand, aims to explicitly relate object sets that are disjoint (and, hence, maximally dissimilar) by finding a chain of (approximate) redescriptions between the sets. This problem finds applications in bioinformatics, for instance, where the biologist is trying to relate a set of genes expressed in one experiment to another set, implicated in a different pathway. We outline an efficient storytelling implementation that embeds the CARTwheels redescription mining algorithm in an A* search procedure, using the former to supply next move operators on search branches to the latter. This approach is practical and effective for mining large data sets and, at the same time, exploits the structure of partitions imposed by the given vocabulary. Three application case studies are presented: a study of word overlaps in large English dictionaries, exploring connections between gene sets in a bioinformatics data set, and relating publications in the PubMed index of abstracts.
Improving Bayesian Network Structure Learning with mutual information
20
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We introduce a simple empirical order-based greedy heuristic for learning discriminative Bayesian network structures. We propose two metrics for establishing the ordering of N features. They are based on the conditional mutual information. Given an ordering, we can find the discriminative classifier structure with O (Nq) score evaluations (where constant q is the maximum number of parents per node). We present classification results on the UCI repository (Merz, Murphy, & Aha 1997), for a phonetic classification task using the TIMIT database (Lamel, Kassel, & Seneff 1986), and for the MNIST handwritten digit recognition task (Le-Cun et al. 1998). The discriminative structure found by our new procedures significantly outperforms generatively produced structures, and achieves classification accuracy on par with the best discriminative (naïve greedy) Bayesian network learning approach, but does so with a factor of ?10 speedup. We also show that the advantages of generative discriminatively structured Bayesian network classifiers still hold in the case of missing features.
Computing Iceberg Cubes by Top-Down and Bottom-Up Integration
47
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Data cube computation is one of the most essential but expensive operations in data warehousing. Previous studies have developed two major approaches, top-down versus bottom-up. The former, represented by the multiway array cube (called the multiway) algorithm, aggregates simultaneously on multiple dimensions; however, it cannot take advantage of a priori pruning when computing iceberg cubes (cubes that contain only aggregate cells whose measure values satisfy a threshold, called the iceberg condition). The latter, represented by BUC, computes the iceberg cube bottom-up and facilitates a priori pruning. BUC explores fast sorting and partitioning techniques; however, it does not fully explore multidimensional simultaneous aggregation. In this paper, we present a new method, star-cubing, that integrates the strengths of the previous two algorithms and performs aggregations on multiple dimensions simultaneously. It utilizes a star-tree structure, extends the simultaneous aggregation methods, and enables the pruning of the group-bys that do not satisfy the iceberg condition. Our performance study shows that star-cubing is highly efficient and outperforms the previous methods
Improved word-aligned binary compression for text indexing
21
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We present an improved compression mechanism for handling the compressed inverted indexes used in text retrieval systems, extending the word-aligned binary coding carry method. Experiments using two typical document collections show that the new method obtains superior compression to previous static codes, without penalty in terms of execution speed.
Markov Random Field Model-Based Edge-Directed Image Interpolation
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper presents an edge-directed image interpolation algorithm. In the proposed algorithm, the edge directions are implicitly estimated with a statistical-based approach. In opposite to explicit edge directions, the local edge directions are indicated by length-16 weighting vectors. Implicitly, the weighting vectors are used to formulate geometric regularity (GR) constraint (smoothness along edges and sharpness across edges) and the GR constraint is imposed on the interpolated image through the Markov random field (MRF) model. Furthermore, under the maximum a posteriori-MRF framework, the desired interpolated image corresponds to the minimal energy state of a 2-D random field given the low-resolution image. Simulated annealing methods are used to search for the minimal energy state from the state space. To lower the computational complexity of MRF, a single-pass implementation is designed, which performs nearly as well as the iterative optimization. Simulation results show that the proposed MRF model-based edge-directed interpolation method produces edges with strong geometric regularity. Compared to traditional methods and other edge-directed interpolation methods, the proposed method improves the subjective quality of the interpolated edges while maintaining a high PSNR level.
Texture Analysis and Classification with Linear Regression Model Based on Wavelet Transform
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The wavelet transform as an important multi resolution analysis tool has already been commonly applied to texture analysis and classification. Nevertheless, it ignores the structural information while capturing the spectral information of the texture image at different scales. In this paper, we propose a texture analysis and classification approach with the linear regression model based on the wavelet transform. This method is motivated by the observation that there exists a distinctive correlation between the sample images, belonging to the same kind of texture, at different frequency regions obtained by 2-D wavelet packet transform. Experimentally, it was observed that this correlation varies from texture to texture. The linear regression model is employed to analyze this correlation and extract texture features that characterize the samples. Therefore, our method considers not only the frequency regions but also the correlation between these regions. In contrast, the pyramid-structured wavelet transforms (PSWT) and the tree structured wavelet transform (TSWT) do not consider the correlation between different frequency regions. Experiments show that our method significantly improves the texture classification rate in comparison with the multi resolution methods, including PSWT, TSWT, the Gabor transform, and some recently proposed methods derived from these. Index Terms—Linear regression, texture analysis, texture classification, wavelet transform
A New Watermarking Scheme for Color Images Captured By Mobile Phone Cameras
10
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A new frequency domain based watermarking scheme for color images captured by mobile phone cameras is proposed. The proposed technique embeds personal mobile phone numbers inside the image. The aim of the scheme is to protect the copy right ownership of the image. Each bit of the decimal digits is inserted onto one low frequency coefficient of one of the DCT blocks of the host image. A DCT coefficient selection (DCS) process has been applied to increase the invisibility qualities, this process managed to find the coefficient with the maximum magnitude. Different embedding location depending on the spatial frequencies of the host image will be selected. The proposed algorithm achieves a high PSNR values and is found to be robust against JPEG compression and different image manipulation algorithms.
Authentication Using Graphical Passwords: Effects of Tolerance and Image Choice
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Graphical passwords are an alternative to alphanumeric passwords in which users click on images to authenticate themselves rather than type alphanumeric strings. We have developed one such system, called Pass Points, and evaluated it with human users. The results of the evaluation were promising with respect to memorability of the graphical password. In this study we expand our human factors testing by studying two issues: the effect of tolerance or margin of error, in clicking on the password points and the effect of the image used in the password system. In our tolerance study, results show that accurate memory for the password is strongly reduced when using a small tolerance (10 ? 10 pixels) around the user’s password points. This may occur because users fail to encode the password points in memory in the precise manner that is necessary to remember the password over a lapse of time. In our image study we compared user performance on four everyday images. The results indicate that there were few significant differences in performance of the images. This preliminary result suggests that many images may support memorability in graphical password systems.
Semantic Texton forests for image categorization and segmentation
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We propose semantic texton forests, efficient and powerful new low-level features. These are ensembles of decision trees that act directly on image pixels, and therefore do not need the expensive computation of filter-bank responses or local descriptors. They are extremely fast to both train and test, especially compared with k-means clustering and nearest-neighbor assignment of feature descriptors. The nodes in the trees provide (i) an implicit hierarchical clustering into semantic textons, and (ii) an explicit local classification estimate. Our second contribution, the bag of semantic textons, combines a histogram of semantic textons over an image region with a region prior category distribution. The bag of semantic textons is computed over the whole image for categorization, and over local rectangular regions for segmentation. Including both histogram and region prior allows our segmentation algorithm to exploit both textural and semantic context. Our third contribution is an image-level prior for segmentation that emphasizes those categories that the automatic categorization believes to be present. We evaluate on two datasets including the very challenging VOC 2007 segmentation dataset. Our results significantly advance the state-of-the-art in segmentation accuracy, and furthermore, our use of efficient decision forests gives at least a five-fold increase in execution speed.
Image Classification using Random Forests and Ferns
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We explore the problem of classifying images by the object categories they contain in the case of a large number of object categories. To this end we combine three ingredients: (i) shape and appearance representations that support spatial pyramid matching over a region of interest. This generalizes the representation of Lazebnik et al [16] from an image to a region of interest (ROI), and from appearance (visual words) alone to appearance and local shape (edge distributions). (ii) automatic selection of the regions of interest in training. This provides a method of inhibiting background clutter and adding invariance to the object instance’s position, and (iii) the use of random forests (and random ferns) as a multi-way classifier. The advantage of such classifiers (over multi-way SVM for example) is the ease of training and testing. Results are reported for classification of the Caltech-101 and Caltech-256 data sets. We compare the performance of the random forest/ferns classifier with a benchmark multiway SVM classifier. It is shown that selecting the ROI adds about 5% to the performance and, together with the other improvements; the result is about a 10% improvement over the state of the art for Caltech-256.
Blood Vessel Segmentation from Color Retinal Images using Unsupervised Texture Classification
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Automated blood vessel segmentation is an important issue for assessing retinal abnormalities and diagnoses of many diseases. The segmentation of vessels is complicated by huge variations in local contrast, particularly in case of the minor vessels. In this paper, we propose a new method of texture based vessel segmentation to overcome this problem. We use Gaussian and L*a*b* perceptually uniform color spaces with original RGB for texture feature extraction on retinal images. A bank of Gabor energy filters are used to analyze the texture features from which a feature vector is constructed for each pixel. The fuzzy C-means (FCM) clustering algorithm is used to classify the feature vectors into vessel or non-vessel based on the texture properties. From the FCM clustering output we attain the final output segmented image after a post processing step. We compare our method with hand-labeled ground truth segmentation of five images and achieve 84.37% sensitivity and 99.61% specificity.
Vision Processing for Real time 3-D Data Acquisition Based on Coded Structured Light
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Structured light vision systems have been successfully used for accurate measurement of 3D surfaces in computer vision. However, their applications are mainly limited to scanning stationary objects so far since tens of images have to be captured for recovering one 3D scene. This paper presents an idea for real-time acquisition of 3D surface data by a specially coded vision system. To achieve 3D measurement for a dynamic scene, the data acquisition must be performed with only a single image. A principle of uniquely color-encoded pattern projection is proposed to design a color matrix for improving the reconstruction efficiency. The matrix is produced by a special code sequence and a number of state transitions. A color projector is controlled by a computer to generate the desired color patterns in the scene. The unique indexing of the light codes is crucial here for color projection since it is essential that each light grid be uniquely identified by incorporating local neighborhoods so that 3D reconstruction can be performed with only local analysis of a single image. A scheme is presented to describe such a vision processing method for fast 3D data acquisition. Practical experimental performance is provided to analyze the efficiency of the proposed methods
Sub sampling Image Compression using Al-Alaoui Back propagation Algorithm
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
With the advances in wireless communications and embedded systems, efficient storage and transmission of images and video over limited bandwidth is required. Novel image compression techniques need to be investigated; artificial neural networks subsampling image compression method is presented using the Al - Alaoui back propagation algorithm is used [1-5]. The Al-Alaoui algorithm is a weighted mean-square-error (MSE) approach to pattern recognition. It employs cloning of the erroneously classified samples to increase the population of their corresponding classes. Using the Al-Alaoui back propagation, obtained simulation results show a faster convergence rate, zero misclassified pixels and an improvement in PSNR around 2 dB.
Semi-supervised SVM batch mode active learning for image retrieval
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Active learning has been shown as a key technique for improving content-based image retrieval (CBIR) performance. Among various methods, support vector machine (SVM) active learning is popular for its application to relevance feedback in CBIR. However, the regular SVM active learning has two main drawbacks when used for relevance feedback. First, SVM often suffers from learning with a small number of labeled examples, which is the case in relevance feedback. Second, SVM active learning usually does not take into account the redundancy among examples, and therefore could select multiple examples in relevance feedback that are similar (or even identical) to each other. In this paper, we propose a novel scheme that exploits both semi-supervised kernel learning and batch mode active learning for relevance feedback in CBIR. In particular, a kernel function is first learned from a mixture of labeled and unlabeled examples. The kernel will then be used to effectively identify the informative and diverse examples for active learning via a min-max framework. An empirical study with relevance feedback of CBIR showed that the proposed scheme is significantly more effective than other state-of-the-art approaches.
Feature based wavelet shrinking algorithm for image denoising
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A selective wavelet shrinkage algorithm for digital image denoising is presented. The performance of this method is an improvement upon other methods proposed in the literature and is algorithmically simple for large computational savings. The improved performance and computational speed of the proposed wavelet shrinkage algorithm is presented and experimentally compared with established methods. The denoising method incorporated in the proposed algorithm involves a two-threshold validation process for real-time selection of wavelet coefficients. The two-threshold criteria select wavelet coefficients based on their absolute value, spatial regularity, and regularity across multiresolution scales. The proposed algorithm takes image features into consideration in the selection process. Statistically, most images have regular features resulting in connected sub band coefficients. Therefore, the resulting sub bands of wavelet transformed images in large part do not contain isolated coefficients. In the proposed algorithm, coefficients are selected due to their magnitude, and only subsets of those selected coefficients which exhibit a spatially regular behavior remain for image reconstruction. Therefore, two thresholds are used in the coefficient selection process. The first threshold is used to distinguish coefficients of large magnitude and the second is used to distinguish coefficients of spatial regularity. The performance of the proposed wavelet denoising technique is an improvement upon several other established wavelets denoising techniques, as well as being computationally efficient to facilitate real-time image-processing applications.
Restoration of DWI Data Using a Rician LMMSE Estimator
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper introduces and analyzes a linear minimum mean square error (LMMSE) estimator using a Rician noise model and its recursive version (RLMMSE) for the restoration of diffusion weighted images. A method to estimate the noise level based on local estimations of mean or variance is used to automatically parameterize the estimator. The restoration performance is evaluated using quality indexes and compared to alternative estimation schemes. The overall scheme is simple, robust, fast, and improves estimations. Filtering diffusion weighted magnetic resonance imaging (DW-MRI) with the proposed methodology leads to more accurate tensor estimations. Real and synthetic datasets are analyzed.
Efficient Nonlocal Means for Denoising of Textural Patterns
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper contributes two novel techniques in the context of image restoration by nonlocal filtering. First, we introduce an efficient implementation of the nonlocal means filter based on arranging the data in a cluster tree. The structuring of data allows for a fast and accurate preselection of similar patches. In contrast to previous approaches, the preselection is based on the same distance measure as used by the filter itself. It allows for large speedups, especially when the search for similar patches covers the whole image domain, i.e., when the filter is truly nonlocal. However, also in the windowed version of the filter, the cluster tree approach compares favorably to previous techniques in respect of quality versus computational cost. Second, we suggest an iterative version of the filter that is derived from a variational principle and is designed to yield nontrivial steady states. It reveals to be particularly useful in order to restore regular, textured patterns.
Indexing of Satellite Images with Different Resolutions by Wavelet Features
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Space agencies are rapidly building up massive image databases. A particularity of these databases is that they are made of images with different, but known, resolutions. In this paper, we introduce a new scheme allowing us to compare and index images with different resolutions. This scheme relies on a simplified acquisition model of satellite images and uses continuous wavelet decompositions. We establish a correspondence between scales which permits us to compare wavelet decompositions of images having different resolutions. We validate the approach through several matching and classification experiments, and we show that taking the acquisition process into account yields better results than just using scaling properties of wavelet features.
Discriminative Analysis of Lip Motion Features for Speaker Identification and Speech-Reading
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
There have been several studies that jointly use audio, lip intensity, and lip geometry information for speaker identification and speech-reading applications. This paper proposes using explicit lip motion information, instead of or in addition to lip intensity and/or geometry information, for speaker identification and speech-reading within a unified feature selection and discrimination analysis framework, and addresses two important issues: 1) Is using explicit lip motion information useful, and, 2) if so, what are the best lip motion features for these two applications? The best lip motion features for speaker identification are considered to be those that result in the highest discrimination of individual speakers in a population, whereas for speech-reading, the best features are those providing the highest phoneme/word/phrase recognition rate. Several lip motion feature candidates have been considered including dense motion features within a bounding box about the lip, lip contour motion features, and combination of these with lip shape features. Furthermore, a novel two-stage, spatial, and temporal discrimination analysis is introduced to select the best lip motion features for speaker identification and speech-reading applications. Experimental results using a hidden-Markov-model-based recognition system indicate that using explicit lip motion information provides additional performance gains in both applications, and lip motion features prove more valuable in the case of speech-reading application.
Texture Analysis and Segmentation Using Modulation Features, Generative Models, and Weighted Curve Evolution
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this work we approach the analysis and segmentation of natural textured images by combining ideas from image analysis and probabilistic modeling. We rely on AM-FM texture models and specifically on the Dominant Component Analysis (DCA) paradigm for feature extraction. This method provides a low-dimensional, dense and smooth descriptor, capturing essential aspects of texture, namely scale, orientation, and contrast. Our contributions are at three levels of the texture analysis and segmentation problems: First, at the feature extraction stage we propose a regularized demodulation algorithm that provides more robust texture features and explore the merits of modifying the channel selection criterion of DCA. Second, we propose a probabilistic interpretation of DCA and Gabor filtering in general, in terms of Local Generative Models. Extending this point of view to edge detection facilitates the estimation of posterior probabilities for the edge and texture classes. Third, we propose the weighted curve evolution scheme that enhances the Region Competition/ Geodesic Active Regions methods by allowing for the locally adaptive fusion of heterogeneous cues. Our segmentation results are evaluated on the Berkeley Segmentation Benchmark, and compare favorably to current state-of-the-art methods.
Reversible Integer Color Transform
13
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this correspondence, we introduce a systematic algorithm that can convert any 3 times 3 color transform into a reversible integer-to-integer transform. We also discuss the ways to improve accuracy and reduce implementation complexity. We derive the integer RGB-to-KLA, IV1V2, YCbCr, DCT, YUV, and YIQ transforms that are optimal in accuracy.
Expansion Embedding Techniques for Reversible Watermarking
25
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Reversible watermarking enables the embedding of useful information in a host signal without any loss of host information. Tian's difference-expansion technique is a high-capacity, reversible method for data embedding. However, the method suffers from undesirable distortion at low embedding capacities and lack of capacity control due to the need for embedding a location map. We propose a histogram shifting technique as an alternative to embedding the location map. The proposed technique improves the distortion performance at low embedding capacities and mitigates the capacity control problem. We also propose a reversible data-embedding technique called prediction-error expansion. This new technique better exploits the correlation inherent in the neighborhood of a pixel than the difference-expansion scheme. Prediction-error expansion and histogram shifting combine to form an effective method for data embedding. The experimental results for many standard test images show that prediction-error expansion doubles the maximum embedding capacity when compared to difference expansion. There is also a significant improvement in the quality of the watermarked image, especially at moderate embedding capacities.
The Mathematical Theory of Dynamic Load Balancing in Cellular Networks
10
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
While many interesting dynamic load balancing schemes have been proposed for efficient use of limited bandwidth and to increase the capacity of congested or hot spots (or cells) in wireless networks, to date, a comprehensive mathematical framework which encompasses all of these schemes does not exist. In this paper, we provide a unified mathematical framework for dynamic load balancing, which leads to closed-form performance expressions for evaluating the performance of some of the most important dynamic load balancing strategies proposed in the literature. To the best of our knowledge, this is the first generic theoretical framework that can be used to evaluate the performance of many different dynamic load balancing schemes with simple closed-form results. The accuracy of the results predicted by these analytical expressions derived from the theoretical framework is checked by comparing these results with simulation results provided in the literature for well-known schemes.
A Flexible Privacy-Enhanced Location-Based Services System Framework and Practice
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Location based services (LBS) are becoming increasingly important to the success and attractiveness of next generation wireless systems. However, a natural tension arises between the need for user privacy and the flexible use of location information. In this paper we present a framework to support privacy enhanced location based services. We classify the services according to several basic criteria and we propose a hierarchical key distribution method to support these services. The key idea behind the system is to hierarchically encrypt location information under different keys, and distribute the appropriate keys only to group members with the necessary permission. Four methods are proposed to deliver hierarchical location information while maintaining privacy. We propose a key tree rebalancing algorithm to maintain the re-keying performance of the group key management. Furthermore, we present a practical LBS system implementation. Hierarchical location information coding offers flexible location information access which enables a rich set of location based services. Our load tests show such a system is highly practical with good efficiency and scalability.
IEEE Transactions on Mobile Computing Project Title: Minimizing recovery state in geographic ad hoc routing Abstract: Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use o
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone. We explain the problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, Node Elevation Ad-hoc Routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic adhoc routing solutions.
Contention-Aware performance analysis of Mobility-Assisted Routing
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A large body of work has theoretically analyzed the performance of mobility-assisted routing schemes for intermittently connected mobile networks. However, the vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even for sparse networks. In this paper, we analyze the performance of routing schemes under contention. First, we introduce a mathematical framework to model contention. This framework can be used to analyze any routing scheme with any mobility and channel model. Then, we use this framework to compute the expected delays for different representative mobility-assisted routing schemes under random direction, random waypoint and community-based mobility models. Finally, we use these delay expressions to optimize the design of routing schemes while demonstrating that designing and optimizing routing schemes using analytical expressions which ignore contention can lead to suboptimal or even erroneous behavior.
Contention-Aware performance analysis of Mobility-Assisted Routing
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A large body of work has theoretically analyzed the performance of mobility-assisted routing schemes for intermittently connected mobile networks. However, the vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even for sparse networks. In this paper, we analyze the performance of routing schemes under contention. First, we introduce a mathematical framework to model contention. This framework can be used to analyze any routing scheme with any mobility and channel model. Then, we use this framework to compute the expected delays for different representative mobility-assisted routing schemes under random direction, random waypoint and community-based mobility models. Finally, we use these delay expressions to optimize the design of routing schemes while demonstrating that designing and optimizing routing schemes using analytical expressions which ignore contention can lead to suboptimal or even erroneous behavior.
IEEE Transactions on Mobile Computing Project Title: Minimizing recovery state in geographic ad hoc routing Abstract: Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use o
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Geographic ad hoc networks use position information for routing. They often utilize stateless greedy forwarding and require the use of recovery algorithms when the greedy approach fails. We propose a novel idea based on virtual repositioning of nodes that allows to increase the efficiency of greedy routing and significantly increase the success of the recovery algorithm based on local information alone. We explain the problem of predicting dead ends which the greedy algorithm may reach and bypassing voids in the network, and introduce NEAR, Node Elevation Ad-hoc Routing, a solution that incorporates both virtual positioning and routing algorithms that improve performance in ad-hoc networks containing voids. We demonstrate by simulations the advantages of our algorithm over other geographic adhoc routing solutions.
Random Cast: An energy efficient communication scheme for Mobile Ad-hoc Networks
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In mobile ad hoc networks (MANETs), every node overhears every data transmission occurring in its vicinity and thus, consumes energy unnecessarily. In IEEE 802.11 Power Saving Mechanism (PSM), a packet must be advertised before it is actually transmitted. When a node receives an advertised packet that is not destined to it, it switches to a low power sleep state during the data transmission period, and thus, avoids overhearing and conserves energy. However, since some MANET routing protocols such as Dynamic Source Routing (DSR) collect route information via overhearing, they would suffer if they are used in combination with 802.11 PSM. Allowing no overhearing may critically deteriorate the performance of the underlying routing protocol, while unconditional overhearing may offset the advantage of using PSM. This paper proposes a new communication mechanism, called Random Cast, via which a sender can specify the desired level of overhearing, making a prudent balance between energy and routing performance. In addition, it reduces redundant rebroadcasts for a broadcast packet and thus saves more energy. Extensive simulation using ns-2 shows that Random Cast is highly energy-efficient compared to conventional 802.11 as well as 802.11 PSM-based schemes, in terms of total energy consumption, energy good put and energy balance.
Providing Location-Aware End-to-End Data Security in Wireless Sensor Networks
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Providing end-to-end data security, i.e., data confidentiality, authenticity, and availability, in wireless sensor networks (WSNs) is a non-trivial task. In addition to the large number and severe resource constraint of sensor nodes, a particular challenge comes from potential insider attacks due to possible node compromise, since a WSN is usually deployed in unattended/hostile environments. Existing security designs provide a hop-by-hop security paradigm only, which leaves the end-to-end data security at high stake. Data confidentiality and authenticity is highly vulnerable to insider attacks, and the multihop transmission of messages aggravates the situation. Moreover, data availability is not sufficiently addressed in existing security designs, many of which are highly vulnerable to many types of Denial of Service (DoS) attacks, such as report disruption attacks, selective forwarding attacks, etc. In this paper, we seek feasible solutions to overcome these vulnerabilities. Through exploiting the static and location-aware nature of WSNs, we come up with a location-aware end-to-end security framework in which each node only stores a few secret keys and those secret keys are bound to the node's geographic location. The property of the location-aware keys successfully limits the impact of compromised nodes to their vicinity. We also propose a multifunctional key management framework which ensures both node-to-sink and node-to-node authentication along report forwarding routes. Moreover, our novel one-to-many data delivery approach guarantees efficient en-route bogus data filtering and is highly robust against many known DoS attacks. We evaluate our design through extensive analysis, which demonstrates a high security resilience against an increasing number of compromised nodes at the cost of a moderate protocol overhead.
LEDS: Providing Location-Aware End-to-End Data Security in Wireless Sensor Networks
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Providing end-to-end data security, i.e., data confidentiality, authenticity, and availability, in wireless sensor networks (WSNs) is a non-trivial task. In addition to the large number and severe resource constraint of sensor nodes, a particular challenge comes from potential insider attacks due to possible node compromise, since a WSN is usually deployed in unattended/hostile environments. Existing security designs provide a hop-by-hop security paradigm only, which leaves the end-to-end data security at high stake. Data confidentiality and authenticity is highly vulnerable to insider attacks, and the multihop transmission of messages aggravates the situation. Moreover, data availability is not sufficiently addressed in existing security designs, many of which are highly vulnerable to many types of Denial of Service (DoS) attacks, such as report disruption attacks, selective forwarding attacks, etc. In this paper, we seek feasible solutions to overcome these vulnerabilities. Through exploiting the static and location-aware nature of WSNs, we come up with a location-aware end-to-end security framework in which each node only stores a few secret keys and those secret keys are bound to the node's geographic location. The property of the location-aware keys successfully limits the impact of compromised nodes to their vicinity. We also propose a multifunctional key management framework which ensures both node-to-sink and node-to-node authentication along report forwarding routes. Moreover, our novel one-to-many data delivery approach guarantees efficient en-route bogus data filtering and is highly robust against many known DoS attacks. We evaluate our design through extensive analysis, which demonstrates a high security
Benefit-Based Data Caching in Ad Hoc Networks
20
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
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.
Active Queue Management for Fair Resource Allocation in Wireless Networks
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper investigates the interaction between end-to-end flow control and medium access control (MAC)-layer scheduling on wireless links. We consider a wireless network with multiple users receiving information from a common access point; each user suffers fading and a scheduler allocates the channel based on channel quality but is subject to fairness and latency considerations. We show that the fairness property of the scheduler is compromised by the transport-layer flow control of transmission control protocol (TCP) New Reno. We provide a receiver-side control algorithm, CLAMP that remedies this situation. CLAMP works at a receiver to control a TCP sender by setting the TCP receiver's advertised window limit, and this allows the scheduler to allocate bandwidth fairly between the users.
Logarithmic Store-Carry-Forward Routing in Mobile Ad Hoc Networks
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Two schools of thought exist in terms of handling mobility in mobile ad hoc networks (MANETs). One is the traditional connection-based model, which views node mobility as undesirable and tries to either remove (through recovery schemes) or mask (through tolerant schemes) the effect of mobility. The other is the mobility-assisted model, which considers mobility as a desirable feature, where routing is based on the store-carry-forward paradigm with random or controlled movement of mobile nodes (called ferries). It is well known that mobility increases the capacity of MANETs by reducing the number of relays in routing. Surprisingly, only two models, diameter hop count in the connection-based model and constant hop count in the mobility-assisted model, which correspond to two extremes of the spectrum, have been systematically studied. In this paper, we propose a new routing model that deals with message routing, as well as trajectory planning, of the ferries that carry the message. A logarithmic number of relays are enforced to achieve a good balance among several contradictory goals, including increasing network capacity, increasing ferry sharing, and reducing moving distance. The model considers the dynamic control of ferries in terms of the number of ferries, trajectory planning of ferries, and node communication and synchronization. The effectiveness of the proposed model is evaluated analytically, as well as through simulation
An acknowledgement based approach for the detection of routing in misbehavior Manets
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We study routing misbehavior in MANETs (Mobile Ad Hoc Networks) in this paper. In general, routing protocols for MANETs are designed based on the assumption that all participating nodes are fully cooperative. However, due to the open structure and scarcely available battery-based energy, node misbehaviors may exist. One such routing misbehavior is that some selfish nodes will participate in the route discovery and maintenance processes but refuse to forward data packets. In this paper, we propose the 2ACK scheme that serves as an add-on technique for routing schemes to detect routing misbehavior and to mitigate their adverse effect. The main idea of the 2ACK scheme is to send two-hop acknowledgment packets in the opposite direction of the routing path. In order to reduce additional routing overhead, only a fraction of the received data packets are acknowledged in the 2ACK scheme. Analytical and simulation results are presented to evaluate the performance of the proposed scheme
Toward broadcast reliability in mobile ad hoc networks with double coverage
42
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The broadcast operation, as a fundamental service in mobile ad hoc networks (MANETs), is prone to the broadcast storm problem if forwarding nodes are not carefully designated. The objective of reducing broadcast redundancy while still providing high delivery ratio under high transmission error rate is a major challenge in MANETs. In this paper, we propose a simple broadcast algorithm, called double-covered broadcast (DCB), which takes advantage of broadcast redundancy to improve the delivery ratio in an environment that has rather high transmission error rate. Among the 1-hop neighbors of the sender, only selected forwarding nodes retransmit the broadcast message. Forwarding nodes are selected in such a way that 1) the sender’s 2-hop neighbors are covered and 2) the sender’s 1-hop neighbors are either forwarding nodes or nonforwarding nodes covered by at least two forwarding neighbors. The retransmissions of the forwarding nodes are received by the sender as the confirmation of their reception of the packet. The nonforwarding 1-hop neighbors of the sender do not acknowledge the reception of the broadcast. If the sender does not detect all its forwarding nodes’ retransmissions, it will resend the packet until the maximum number of retries is reached. Simulation results show that the proposed broadcast algorithm provides good performance under a high transmission error rate environment.
A location based routing method for mobile ad-hoc networks
25
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Using location information to help routing is often proposed as a means to achieve scalability in large mobile ad hoc networks. However, location-based routing is difficult when there are holes in the network topology and nodes are mobile or frequently disconnected to save battery. Terminode routing, presented here, addresses these issues. It uses a combination of location-based routing (Terminode Remote Routing, TRR), used when the destination is far, and link state routing Terminode Local Routing, TLR), used when the destination is close. TRR uses anchored paths, a list of geographic points (not nodes) used as loose source routing information. Anchored paths are discovered and managed by sources, using one of two low overhead protocols: Friend Assisted Path Discovery and Geographical Map-based Path Discovery. Our simulation results show that terminode routing performs well in networks of various sizes. In smaller networks, the performance is comparable to MANET routing protocols. In larger networks that are not uniformly populated with nodes, terminode routing outperforms existing location-based or MANET routing protocols
A fault-tolerant distributed channel allocation scheme for cellular networks
45
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In cellular networks, it is vital to allocate communication channels efficiently because the bandwidth allocated for cellular communication is limited. If channels are statically allocated, as is the case in current cellular networks, a cell may run out of channels when a large number of mobile hosts move to the cell. To overcome this problem, dynamic channel allocation approaches have been proposed. Under dynamic channel allocation, channels are allocated to cells on demand, thus increasing channel utilization. Such channel allocation approaches fall under two categories, namely, centralized and distributed. Centralized approaches are neither scalable nor reliable, while distributed approaches have the potential to be both reliable and scalable. In the distributed approaches, a mobile service station is responsible for allocating channels to mobile hosts in the same cell. In cellular networks, mobile service stations may fail. In addition, the network may encounter intermittent network congestion and/or link failures. It is desirable for a channel allocation algorithm to work well, even in the presence of network congestion, link failures, and/or mobile service station failures. In this paper, we present a distributed dynamic channel allocation scheme for cellular networks that is fault-tolerant. Our approach can tolerate the failure of mobile service stations, link failure, and network congestion, and make efficient reuse of channels. We also provide results of the performance evaluation of our algorithm.
Solving Systems of Linear Equations on the CELL Processor Using Cholesky Factorization
41
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The Sony/Toshiba/IBM (STI) CELL processor introduces pioneering solutions in processor architecture. At the same time it presents new challenges for the development of numerical algorithms. One is effective exploitation of the differential between the speed of single and double precision arithmetic; the other is efficient parallelization between the short vector SIMD cores. The first challenge is addressed by utilizing the well known technique of iterative refinement for the solution of a dense symmetric positive definite system of linear equations, resulting in a mixed-precision algorithm, which delivers double precision accuracy, while performing the bulk of the work in single precision. The main contribution of this paper lies in addressing the second challenge by successful thread-level parallelization, exploiting fine-grained task granularity and a lightweight decentralized synchronization. The implementation of the computationally intensive sections gets within 90 percent of peak floating point performance, while the implementation of the memory intensive sections reaches within 90 percent of peak memory bandwidth. On a single CELL processor, the algorithm achieves over 170~Gflop/s when solving a symmetric positive definite system of linear equation in single precision and over 150~Gflop/s when delivering the result in double precision accuracy.
Scalable live streaming service based on interoverlay optimization
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In order to provide scalable live-streaming services, we propose an Inter-Overlay Optimization scheme, IOO. Instead of selecting better paths in the same overlay, IOO constructs efficient paths using peers in different overlays, so as to (i) improve global resource utilization of P2P streaming networks; (ii) assign resources based on their locality and delay; (iii) guarantee streaming service quality by using the nearest peers, even when such peers might belong to different overlays; and (iv) balance the load among the group (streaming overlay) members. We compare the performance of IOO with existing approaches through trace driven simulations. Results show that IOO outperforms previous schemes in terms of resource utilization and the QoS of streaming services. IOO scheme has been implemented in an Internet based live streaming system, called AnySee. AnySee was successfully released in the summer of 2004 in CERNET of China. Over 60,000 users enjoy massive entertainment programs, including TV programs, movies, and academic conferences videos.
A new Task graph model for Qos Support in clusters
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Electronic collaboration among devices in a geographically localized environment is made possible with the implementation of IEEE 802.11 based wireless ad hoc networks. Dynamic nature of mobile ad hoc networks (MANETs) may lead to unpredictable intervention of attacks or fault occurrence, which consequently may partition the network, degrade its performance, violate the QoS requirements and most importantly, affect bandwidth allocation to mobile nodes in the network. In this paper, we propose a new distributed cluster scheme for MANETs, especially in harsh environments, based on the concept of survivability to support QoS requirements and to protect bandwidth efficiently. With the incorporation of clustering algorithms in survivability technology, we employ a simple network configuration and expect to reduce occurrences of faults in MANETs. At the same time, we address the scalability problem, which represents a great challenge to network configuration. We do expect a simplification of accessing bandwidth allocation with required QoS support for different applications.
Software-Based Failure Detection and Recovery in Programmable Network Interfaces
21
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Emerging network technologies have complex network interfaces that have renewed concerns about network reliability. In this paper, we present an effective low-overhead fault tolerance technique to recover from network interface failures. Failure detection is based on a software watchdog timer that detects network processor hangs and a self-testing scheme that detects interface failures other than processor hangs. The proposed self-testing scheme achieves failure detection by periodically directing the control flow to go through only active software modules in order to detect errors that affect instructions in the local memory of the network interface. Our failure recovery is achieved by restoring the state of the network interface using a small backup copy containing just the right amount of information required for complete recovery. The paper shows how this technique can be made to minimize the performance impact to the host system and be completely transparent to the user.
Congestion Adaptive Routing in Mobile Ad Hoc Networks
41
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Mobility, channel error, and congestion are the main causes for packet loss in mobile ad hoc networks. Reducing packet loss typically involves congestion control operating on top of a mobility and failure adaptive routing protocol at the network layer. In the current designs, routing is not congestion-adaptive. Routing may let a congestion happen which is detected by congestion control, but dealing with congestion in this reactive manner results in longer delay and unnecessary packet loss and requires significant overhead if a new route is needed. This problem becomes more visible especially in large-scale transmission of heavy traffic such as multimedia data, where congestion is more probable and the negative impact of packet loss on the service quality is of more significance. We argue that routing should not only be aware of, but also be adaptive to, network congestion. Hence, we propose a routing protocol (CRP) with such properties. Our ns-2 simulation results confirm that CRP improves the packet loss rate and end-to-end delay while enjoying significantly smaller protocol overhead and higher energy efficiency as compared to AODV and DSR.
Randomized Channel Selection in Multi channel Access Point Networks
52
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Multi-channel system are becoming more and more available and require new techniques to speed up the channel access, especially when the mobile device is equipped only with a single antenna. In this paper, we introduce some techniques and selection policies which allow a mobile device to speed up the acquisition time for finding out a channel with satisfactory conditions. The 3 policies we introduce all speed up the scanning phase significantly while achieving near optimal throughput. We assess analytically and numerically the performance of the policies and show an acquisition time divided by a factor two to five, while the achieved throughput stays comparable to an exhaustive search.
On Maximizing the Lifetime of Distributed Information in AdHoc Networks with Individual Constraints
52
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Ad-Hoc Networks and in particular sensor networks are networks of nodes with limited battery and limited processing capacity. As such, a single node carries an incentive to limit the amount of data it contains. This leads to the expiration of the data carried by the node after a period of time, due for instance, to a re-boot after an o® period in the duty cycle, or to older information being "pushed" out by new data received by the mobile node. On the other hand, some data is critical to the functioning of the whole network. For instance, the existence and position of a gateway towards the infrastructure network should be kept somewhere in the network, so that nodes are able to recover this information when needed. In this paper, we study the trade-o® between the nite lifetime of a piece of information at each node, and the survival of this information indenitely within the network. We consider a simple dissemination process for the information akin to an AODV-based information request/reply mechanism. We show that the maximum number of hops in a request is a critical parameter to ensure the survivability indenitely of any information within the network. We identify the parameter which minimizes the load on the network, for two typical ad-hoc network topologies: a square lattice, which accurately models the distribution of the nodes in a axed and organized ad hoc or sensor network, and a n-ary tree, which models ad hoc networks for which routing is constructed so as to have no routing loops.
On the Computational Complexity and Effectiveness of “N-hub Shortest-Path routing
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we study the computational complexity and effectiveness of a concept we term ldquoN-hub shortest-path routing rdquo in IP networks. N-hub shortest-path routing allows the ingress node of a routing domain to determine up to N intermediate nodes (ldquohubsrdquo) through which a packet will pass before reaching its final destination. This facilitates better utilization of the network resources, while allowing the network routers to continue to employ the simple and well-known shortest-path routing paradigm. Although this concept has been proposed in the past, this paper is the first to investigate it in depth. We apply N-hub shortest-path routing to the problem of minimizing the maximum load in the network. We show that the resulting routing problem is NP-complete and hard to approximate. However, we propose efficient algorithms for solving it both in the online and the offline contexts. Our results show that N-hub shortest-path routing can increase network utilization significantly even for N = 1. Hence, this routing paradigm should be considered as a powerful mechanism for future datagram routing in the Internet.
Two techniques for fast computation of constrained shortest paths
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Computing constrained shortest paths is fundamental to some important network functions such as QoS routing, MPLS path selection, ATM circuit routing, and traffic engineering. The problem is to find the cheapest path that satisfies certain constraints. In particular, finding the cheapest delay-constrained path is critical for real-time data flows such as voice/video calls. Because it is NP-complete, much research has been designing heuristic algorithms that solve the epsiv-approximation of the problem with an adjustable accuracy. A common approach is to discretize (i.e., scale and round) the link delay or link cost, which transforms the original problem to a simpler one solvable in polynomial time. The efficiency of the algorithms directly relates to the magnitude of the errors introduced during discretization. In this paper, we propose two techniques that reduce the discretization errors, which allow faster algorithms to be designed. Reducing the overhead of computing constrained shortest paths is practically important for the successful design of a high-throughput QoS router, which is limited at both processing power and memory space. Our simulations show that the new algorithms reduce the execution time by an order of magnitude on power-law topologies with 1000 nodes. The reduction in memory space is similar.
On the Performance Benefits of Multihoming Route Control
52
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Multihoming is increasingly being employed by large enterprises and data centers to extract good performance and reliability from their ISP connections. Multihomed end networks today can employ a variety of route control products to optimize their Internet access performance and reliability. However, little is known about the tangible benefits that such products can offer, the mechanisms they employ and their trade-offs. This paper makes two important contributions. First, we present a study of the potential improvements in Internet round-trip times (RTTs) and transfer speeds from employing multihoming route control. Our analysis shows that multihoming to three or more ISPs and cleverly scheduling traffic across the ISPs can improve Internet RTTs and throughputs by up to 25% and 20%, respectively. However, a careful selection of ISPs is important to realize the performance improvements. Second, focusing on large enterprises, we propose and evaluate a wide-range of route control mechanisms and evaluate their design trade-offs. We implement the proposed schemes on a Linux-based Web proxy and perform a trace-based evaluation of their performance. We show that both passive and active measurement-based techniques are equally effective and could improve the Web response times of enterprise networks by up to 25% on average, compared to using a single ISP. We also outline several "best common practices" for the design of route control products.
Efficient and Secure Content Processing and Distribution by Cooperative Intermediaries
23
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Content services such as content filtering and transcoding; adapt contents to meet system requirements, display capacities, or user preferences. Data security in such a framework is an important problem, and crucial for many web applications. In this paper, we propose an approach that addresses data integrity and confidentiality in content adaptation and caching by intermediaries. Our approach permits multiple intermediaries to simultaneously perform content services on different portions of the data. Our protocol supports decentralized proxy and key managements and flexible delegation of services. Our experimental results show that our approach is efficient and minimizes the amount of data transmitted across the network.
Dynamic search algorithm in unstructured peer-to-peer networks
25
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Flooding and random walk (RW) are the two typical search algorithms in unstructured peer-to-peer networks. The flooding algorithm searches the network aggressively. It covers the most nodes but generates a large number of query messages. Hence it is considered to be not scalable. This cost issue is especially serious when the queried resource locates far from the query source. On the contrary, RW searches the network conservatively. It only generates a fixed amount of query messages at each hop, but it may take particularly longer search time to find the queries resource. We propose the dynamic search algorithm (DS) which is a generalization of flooding, modified breadth first search (MBFS), and RW. This search algorithm takes advantage of different contexts under which each previous search algorithm performs well. The operation of DS resembles flooding or MBFS for the short-term search, and RW for the long-term search. We analyze the performance of DS based on the power-law random graph model and adopt some performance metrics including the guaranteed search time, query hits, query messages, success rate, and a unified metric, search efficiency. The main objective is to obtain the effects of the parameters of DS. Numerical results show that proper setting of the parameters of DS can obtain the short guaranteed search time and provide a good tradeoff between the search performance and the cost.
The server reassignment problem for load balancing in structured p2p systems
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Application-layer peer-to-peer (P2P) networks are considered to be the most important development for next-generation Internet infrastructure. For these systems to be effective, load balancing among the peers is critical. Most structured P2P systems rely on ID-space partitioning schemes to solve the load imbalance problem and have been known to result in an imbalance factor of ominus(log N) in the zone sizes. This paper makes two contributions. First, we propose addressing the virtual-server-based load balancing problem systematically using an optimization-based approach and derive an effective algorithm to rearrange loads among the peers. We demonstrate the superior performance of our proposal in general and its advantages over previous strategies in particular. We also explore other important issues vital to the performance in the virtual server framework, such as the effect of the number of directories employed in the system and the performance ramification of user registration strategies. Second, and perhaps more significantly, we systematically characterize the effect of heterogeneity on load balancing algorithm performance and the conditions in which heterogeneity may be easy or hard to deal with based on an extensive study of a wide spectrum of load and capacity scenarios.
Node isolation model and age-based neighbor selection in unstructured P2P networks
42
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Previous analytical studies of unstructured P2P resilience have assumed exponential user lifetimes and only considered age-independent neighbor replacement. In this paper, we overcome these limitations by introducing a general node-isolation model for heavy-tailed user lifetimes and arbitrary neighbor-selection algorithms. Using this model, we analyze two age-biased neighbor-selection strategies and show that they significantly improve the residual lifetimes of chosen users, which dramatically reduces the probability of user isolation and graph partitioning compared with uniform selection of neighbors. In fact, the second strategy based on random walks on age-proportional graphs demonstrates that, for lifetimes with infinite variance, the system monotonically increases its resilience as its age and size grow. Specifically, we show that the probability of isolation converges to zero as these two metrics tend to infinity. We finish the paper with simulations in finite-size graphs that demonstrate the effect of this result in practice.
Entropy based adaptive flow aggregation Abstract:
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Internet traffic flow measurement is vitally important for network management, accounting and performance studies. Cisco’s Net Flow is a widely deployed flow measurement solution that uses a configurable static sampling rate to control processor and memory usage on the router and the amount of reporting flow records generated. But during flooding attacks the memory and network bandwidth consumed by flow records can increase beyond what is available. Currently available countermeasures have their own problems: 1) reject new flows when the cache is full—some legitimate new flows will not be counted; 2) export not-terminated flows to make room for new ones—this will exhaust the export bandwidth; and 3) adapt the sampling rate to traffic rate—this will reduce the overall accuracy of accounting, including legitimate flows. In this paper, we propose entropy based adaptive flow aggregation algorithm. Relying on information-theoretic techniques, the algorithm efficiently identifies the clusters of attack flows in real time and aggregates those large number of short attack flows into a few metaflows. Compared to currently available solutions, our solution not only alleviates the problem in memory and export bandwidth, but also significantly improves the accuracy of legitimate flows. Finally, we evaluate our system using both synthetic trace file and real trace files from the Internet.
Optimal Backpressure routing for wireless networks with Multi-Receiver diversity
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We consider the problem of optimal scheduling and routing in an ad-hoc wireless network with multiple traffic streams and time varying channel reliability. Each packet transmission can be overheard by a subset of receiver nodes, with a transmission success probability that may vary from receiver to receiver and may also vary with time. We develop a simple backpressure routing algorithm that maximizes network throughput and expends an average power that can be pushed arbitrarily close to the minimum average power required for network stability, with a corresponding tradeoff in network delay. The algorithm can be implemented in a distributed manner using only local link error probability information, and supports a "blind transmission" mode (where error probabilities are not required) in special cases when the power metric is neglected and when there is only a single destination for all traffic streams.
Energy-Robustness trade off in cellular network power control
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In the seminal paper by Foschini and Miljanic in 1993, a distributed power control algorithm was developed to meet SIR targets with minimal powers in cellular network uplinks. Since the SIR on an active link may dip below the SIR target during the transient after a new user enters the cell, Bambos proposed an active link protection algorithm to provide robustness, at the expense of higher energy consumption. This paper examines the tradeoff between energy and robustness. An optimization problem is formulated where robustness is captured in the constraint and the price of robustness penalized in the objective function. A distributed algorithm is developed to solve this problem. Local convergence and optimality of equilibrium are proved for the algorithm. The objective function modulates the tradeoff between energy and robustness, and between energy and speed of admission, as illustrated through a series of numerical experiments. A parameterized family of objective functions is constructed to control the transient and equilibrium properties of robust distributed power control.
Minimizing the file download time in stochastic peer-to-peer networks
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The average download time of a file is an important performance metric for a user in a peer-to-peer network. We point out that the common approach of analyzing the average download time based on average service capacity is fundamentally flawed, and show that spatial heterogeneity and temporal correlation in the service capacity over different paths are the two major factors that have negative impact on the average file download time. We then propose a simple and distributed algorithm that can completely remove this negative impact of the two factors and yield the smallest possible average download time for each user in the network.
Building heterogeneous peer-to-peer networks: protocol and Analysis
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we propose a simple protocol for building heterogeneous unstructured peer-to-peer (P2P) networks. The protocol consists of two parts—the joining process and the rebuilding process. The basic idea for the joining process is to use a random walk to assist new incoming peers in selecting their suitable neighbors in terms of capacity and connectivity to achieve load-balancing. The rebuilding process specifies how the nodes should react when they lose links. In particular, we examine two representative schemes, namely the probabilistic-rebuilding scheme and the adaptive-rebuilding scheme. Furthermore, we provide a detailed analysis to investigate our proposed protocol under any heterogeneous P2P environment. We prove that the topology structure of the P2P network depends heavily on the node heterogeneity. The analytical results are validated by the simulations. Our framework provides a guideline to engineer and optimize a P2P network in different respects under a heterogeneous environment. The ultimate goal of this paper is to stimulate further research to explore the fundamental issues in heterogeneous P2P networks.
A geometric approach to improving active packet loss measurement
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Measurement and estimation of packet loss characteristics are challenging due to the relatively rare occurrence and typically short duration of packet loss episodes. While active probe tools are commonly used to measure packet loss on end-to end paths, there has been little analysis of the accuracy of these tools or their impact on the network. The objective of our study is to understand how to measure packet loss episodes accurately with end-to-end probes. We begin by testing the capability of standard Poisson-modulated end-to-end measurements of loss in a controlled laboratory environment using IP routers and commodity end hosts. Our tests show that loss characteristics reported from such Poisson-modulated probe tools can be quite inaccurate over a range of traffic conditions. Motivated by these observations, we introduce a new algorithm for packet loss measurement that is designed to overcome the deficiencies in standard Poisson-based tools. Specifically, our method entails probe experiments that follow a geometric distribution to (1) enable an explicit trade-off between accuracy and impact on the network, and (2) enable more accurate measurements than standard Poisson probing at the same rate. We evaluate the capabilities of our methodology experimentally by developing and implementing a prototype tool, called BADABING. The experiments demonstrate the trade-offs between impact on the network and measurement accuracy. We show that BADABING reports loss characteristics far more accurately than traditional loss measurement tools.
Efficient Approximate Query Processing in Peer-to-Peer Networks
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Peer-to-peer (P2P) databases are becoming prevalent on the Internet for distribution and sharing of documents, applications, and other digital media. The problem of answering large-scale ad hoc analysis queries, for example, aggregation queries, on these databases poses unique challenges. Exact solutions can be time consuming and difficult to implement, given the distributed and dynamic nature of P2P databases. In this paper, we present novel sampling-based techniques for approximate answering of ad hoc aggregation queries in such databases. Computing a high-quality random sample of the database efficiently in the P2P environment is complicated due to several factors: the data is distributed (usually in uneven quantities) across many peers, within each peer, the data is often highly correlated, and, moreover, even collecting a random sample of the peers is difficult to accomplish. To counter these problems, we have developed an adaptive two-phase sampling approach based on random walks of the P2P graph, as well as block-level sampling techniques. We present extensive experimental evaluations to demonstrate the feasibility of our proposed solution.
fusion: A P2P Architecture for Internet-Scale Content-Based Search And Retrieval
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The emerging peer-to-peer (p2p) model has become a very powerful and attractive paradigm for developing Internet-scale systems for sharing resources, including files and documents. The distributed nature of these systems, where nodes are typically located across different networks and domains, inherently hinders the efficient retrieval of information. In this paper, we consider the effects of topologically aware overlay construction techniques on efficient p2p keyword search algorithms. We present the peer fusion (pFusion) architecture that aims to efficiently integrate heterogeneous information that is geographically scattered on peers of different networks. Our approach builds on work in unstructured p2p systems and uses only local knowledge. Our empirical results, using the pFusion middleware architecture and data sets from Akamai's Internet mapping infrastructure (AKAMAI), the active measurement project (NLANR), and the text retrieval conference (TREC) show that the architecture we propose is both efficient and practical
Smartening the environment using wireless sensor networks in a developing country
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The miniaturization process of various sensing devices has become a reality by enormous research and advancements accomplished in micro electro-mechanical systems (MEMS) and very large scale integration (VLSI) lithography. Regardless of such extensive efforts in optimizing the hardware, algorithm, and protocols for networking, there still remains a lot of scope to explore how these innovations can all be tied together to design wireless sensor networks (WSN) for smartening the surrounding environment for some practical purposes. In this paper we explore the prospects of wireless sensor networks and propose a design level framework for developing a smart environment using WSNs, which could be beneficial for a developing country like Bangladesh. In connection to this, we also discuss the major aspects of wireless sensor networks
Lord of the Links: A Framework for Discovering Missing Links in the Internet Topology
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The topology of the Internet at the autonomous system (AS) level is not yet fully discovered despite significant research activity. The community still does not know how many links are missing, where these links are and finally, whether the missing links will change our conceptual model of the Internet topology. An accurate and complete model of the topology would be important for protocol design, performance evaluation and analyses. The goal of our work is to develop methodologies and tools to identify and validate such missing links between ASes. In this work, we develop several methods and identify a significant number of missing links, particularly of the peer-to-peer type. Interestingly, most of the missing AS links that we find exists as peer-to-peer links at the Internet exchange points (IXPs). First, in more detail, we provide a large-scale comprehensive synthesis of the available sources of information. We cross-validate and compare BGP routing tables, Internet routing registries, and trace route data, while we extract significant new information from the less-studied Internet exchange points (IXPs). We identify 40% more edges and approximately 300% more peer-to-peer edges compared to commonly used data sets. All of these edges have been verified by either BGP tables or trace route. Second, we identify properties of the new edges and quantify their effects on important topological properties. Given the new peer-to-peer edges, we find that for some ASes more than 50% of their paths stop going through their ISPs assuming policy-aware routing. A surprising observation is that the degree of an AS may be a poor indicator of which ASes it will peer with.
A Waiting-Time Dependent Back off Algorithm for QoS Enhancement of Voice over WLAN
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
As the integration of prevailing Wireless Local Area Network (WLAN) and Voice over Internet Protocol (VoIP) technology, Voice over WLAN (VoWLAN) is expected to experience a dramatic growth in the near future. However, the widely deployed IEEE 802.11 contention-based Media Access Control (MAC) mechanism is unsuitable for voice transmission with strict Quality of Service (QoS) requirements. In this paper, the delay jitter and collision problems in Binary Exponential Back off (BEB) algorithm are analyzed first. Then, a novel "Waiting-time Dependent Back off (WDB)" algorithm is proposed to cope with these problems and improve QoS of voice transmission. Simulation results show that WDB can dramatically reduce delay jitter and collision probability, as well as end-to-end delay, while maintaining acceptable drop rate.
Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
While there are distributed algorithms for the MST problem, these algorithms require relatively large number of messages and time; this makes these algorithms impractical for resource-constrained networks such as ad hoc wireless sensor networks. In such networks, a sensor has very limited power, and any algorithm needs to be simple, local, and energy efficient for being practical. Motivated by these considerations, we design and analyze a class of simple and local distributed algorithms called nearest neighbor tree (NNT) algorithms for energy-efficient construction of MSTs in a wireless ad hoc setting. We assume that the nodes are uniformly distributed in a unit square and show provable bounds on the performance with respect to both the quality of the spanning tree produced and the energy needed to construct them. In particular, we show that NNT produces a close approximation to the MST, and they can be maintained dynamically with polylogarithmic number of rearrangements under node insertions/deletions. We also perform extensive simulations of our algorithms. We tested our algorithms on both uniformly random distributions of nodes, and on realistic distributions of nodes in an urban setting. Simulations validate the theoretical results and show that the bounds are much better in practice
A Multiobjective Optimization-Based Evolutionary Algorithm for Constrained Optimization
41
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A considerable number of constrained optimization evolutionary algorithms (COEAs) have been proposed due to increasing interest in solving constrained optimization problems (COPs) by evolutionary algorithms (EAs). In this paper, we first review existing COEAs. Then, a novel EA for constrained optimization is presented. In the process of population evolution, our algorithm is based on multiobjective optimization techniques, i.e., an individual in the parent population may be replaced if it is dominated by a nondominated individual in the offspring population. In addition, three models of a population-based algorithm-generator and an infeasible solution archiving and replacement mechanism are introduced. Furthermore, the simplex crossover is used as a recombination operator to enrich the exploration and exploitation abilities of the approach proposed. The new approach is tested on 13 well-known benchmark functions, and the empirical evidence suggests that it is robust, efficient, and generic when handling linear/nonlinear equality/inequality constraints. Compared with some other state-of-the-art algorithms, our algorithm remarkably outperforms them in terms of the best, mean, and worst objective function values and the standard deviations. It is noteworthy that our algorithm does not require the transformation of equality constraints into inequality constraints
Public-key based security scheme for Wireless Sensor Network
41
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Wireless sensor nodes have restricted computational resources, and are always deployed in a harsh, unattended or hostile environment. Therefore, network security represents a challenging task. This work presents a public-key based pre-distribution scheme with time-position nodes for simultaneous exchange of secure keys. The proposed defend attack and key management mechanism for sensor network applications can successfully handle sink mobility and can continually deliver data to neighboring nodes and sinks. Simulation results indicate that the proposed mechanism can reduce energy consumption and extend the average network lifetime by about 25%.
Faster Algorithms for Construction of Recovery Trees Enhancing QoP and QoS
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Medard et al. proposed an elegant recovery scheme (known as the MFBG scheme) using red/blue recovery trees for multicast path protection against single link or node failures. Xue et al. extended the MFBG scheme and introduced the concept of quality of protection (QoP) as a metric for multifailure recovery capabilities of single failure recovery schemes. They also presented polynomial time algorithms to construct recovery trees with good QoP and quality of service (QoS). In this paper, we present faster algorithms for constructing recovery trees with good QoP and QoS performance. For QoP enhancement, our O (n + m) time algorithm has comparable performance with the previously best O (n2 (n + m)) time algorithm, where n and m denote the number of nodes and the number of links in the network, respectively. For cost reduction, our O (n + m) time algorithms have comparable performance with the previously best O (n2 (n + m)) time algorithms. For bottleneck bandwidth maximization, our O (m log n) time algorithms improve the previously best O (nm) time algorithms. Simulation results show that our algorithms significantly outperform previously known algorithms in terms of running time, with comparable QoP or QoS performance.
Securing User-controlled Routing Infrastructures
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Designing infrastructures that give entrusted third parties (such as end-hosts) control over routing is a promising research direction for achieving flexible and efficient communication. However, serious concerns remain over the deployment of such infrastructures, particularly the new security vulnerabilities they introduce. The flexible control plane of these infrastructures can be exploited to launch many types of powerful attacks with little effort. In this paper, we make several contributions towards studying security issues in forwarding infrastructures (FIs). We present a general model for an FI; analyze potential security vulnerabilities, and present techniques to address these vulnerabilities. The main technique that we introduce in this paper is the use of simple lightweight cryptographic constraints on forwarding entries. We show that it is possible to prevent a large class of attacks on end-hosts and bound the flooding attacks that can be launched on the infrastructure nodes to a small constant value. Our mechanisms are general and apply to a variety of earlier proposals such as, Data Router, and Network Pointers.
Controlling IP Spoofing through Inter-Domain Packet filters
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The Distributed Denial of Services (DDoS) attack is a serious threat to the legitimate use of the Internet. Prevention mechanisms are thwarted by the ability of attackers to forge, or spoof, the source addresses in IP packets. By employing IP spoofing, attackers can evade detection and put a substantial burden on the destination network for policing attack packets. In this paper, we propose an inter-domain packet filter (IDPF) architecture that can mitigate the level of IP spoofing on the Internet. A key feature of our scheme is that it does not require global routing information. IDPFs are constructed from the information implicit in BGP route updates and are deployed in network border routers. We establish the conditions under which the IDPF framework works correctly in that it does not discard packets with valid source addresses. Based on extensive simulation studies, we show that even with partial deployment on the Internet, IDPFs can proactively limit the spoofing capability of attackers. In addition, they can help localize the origin of an attack packet to a small number of candidate networks.
A Practical Password-Based Two-Server Authentication and Key Exchange System
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A great part of protocols for password-based authenticated key exchange system are designed for a single- server environment where all the information about legitimate users is stored in one server. Therefore, a credential weakness is existed in this approach because the user's password is exposed if this server is ever compromised. In 2006, Yang et al. proposed a practical two-server authenticated key exchange system which split user's password into two and store them into the servers respectively. They also extended the basic two-server model to an architecture in which multiple service servers were supported by single control server, but they didn't demonstrate an adequate protocol in the extended model. In this paper, we present a protocol which is suitable for the extended model. In addition, we describe that our proposed protocol is robust against various known attacks and has a user-friendless.
A Fully Distributed Proactively Secure Threshold-Multisignature Scheme
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Threshold-multisignature schemes combine the properties of threshold group-oriented signature schemes and multisignature schemes to yield a signature scheme that allows a threshold (t) or more group members to collaboratively sign an arbitrary message. In contrast to threshold group signatures, the individual signers do not remain anonymous, but are publicly identifiable from the information contained in the valid threshold-multisignature. The main objective of this paper is to propose such a secure and efficient threshold-multisignature scheme. The paper uniquely defines the fundamental properties of threshold-multisignature schemes and shows that the proposed scheme satisfies these properties and eliminates the latest attacks to which other similar schemes are subject. The efficiency of the proposed scheme is analyzed and shown to be superior to its counterparts. The paper also proposes a discrete logarithm based distributed-key management infrastructure (DKMI), which consists of a round optimal, publicly verifiable, distributed-key generation (DKG) protocol and a one round, publicly verifiable, distributed-key redistribution/ updating (DKRU) protocol. The round optimal DKRU protocol solves a major problem with existing secret redistribution/updating schemes by giving group members a mechanism to identify malicious or faulty share holders in the first round, thus avoiding multiple protocol executions.
A Novel approach for computation efficient rekeying for multicast key distribution
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
An important problem for secure group communication is key distribution. Most of the centralized group key management schemes employ high rekeying cost. Here we introduce a novel approach for computation efficient rekeying for multicast key distribution. This approach reduces the rekeying cost by employing a hybrid group key management scheme (involving both centralized and contributory key management schemes). The group controller uses the MDS Codes, a class of error control codes, to distribute the multicast key dynamically. In order to avoid frequent rekeying as and when the user leaves, a novel approach is introduced where clients recomputed the new group key with minimal computation. This approach ensures forward secrecy as well as backward secrecy and significantly reduces the rekeying cost and communication cost. This scheme well suits wireless applications where portable devices require low computation.
A new Reliable Broadcasting in Mobile Ad-Hoc Networks
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In mobile ad hoc network, every link is wireless and every node is mobile. Those features make data lost easily as well as broadcasting inefficient and unreliable. Moreover, efficiency and reliability is conflicting each other. Hence it is hard to achieve both at a time with just one scheme. In this paper, we present the scheme to improve the reliability and efficiency of the broadcast protocol in mobile ad hoc network. This scheme, unlike flooding which keeps reliability by sending excessive redundant packets, improves delivery rate with minimum overhead without degrading efficiency.
A Hybrid Reliable Routing Technique (HRR) for Wireless Sensor Networks
42
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The life span of the sensor network is limited to its residual power. In order to increase the normal life span of the network it is necessary to implement energy aware algorithm. While there are many ways to achieve energy efficiency during routing, organizing the entire network into clusters and henceforth performing routing is one such approach. Current work is focused on two issues: Organizing the network into clusters, changing the Cluster Head at the appropriate time and perform routing through the cluster heads to the sink consuming least energy.
Anonymity in Wireless Broadcast Networks
17
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Systems that provide network traffic anonymity typically focus on wide-area network topologies, and exploit the infeasibility of eavesdropping on all links to prevent attackers from determining communication peers. This approach is inappropriate for high-security wireless local area networks, since it does not obscure the traffic volume, allowing attackers to identify critical nodes (e.g., amilitary HQ) and, given the ability of an attacker to obtain a global view of all communications, the relative ease of identifying the source and destination of traffic flows. These weaknesses derive from the fact that, whereas in wide-area networks the sender, the receiver and the adversary are on different physical links, in wireless networks they may share a single broadcast link. Moreover, the adversary can easily find the physical location of the transmitter and thereby identify the entity sending the traffic, not just its network identity. We introduce Wireless Anonymous Routing (war), an approach to achieve anonymity in a broadcast network. We describe a formal threat model for war and compare it to the traditional anonymity approaches. We show that these are inadequate when applied to the broadcast model, and describe new protocols that preserve security with better performance, adequately addressing the requirements of security-critical environments. We provide analytical and some preliminary experimental evidence that our protocols achieve anonymity at a reasonable cost.
Enhanced communal Global, Local Memory Management for effective performance of cluster computing
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Memory management becomes a prerequisite when handling applications that require immense volume of data in Cluster Computing. For example when executing data pertaining to satellite images for remote sensing or defense purposes, scientific or engineering applications. Here even if the other factors perform to the maximum possible levels and if memory management is not properly handled the performance will have a proportional degradation. Hence it is critical to have a fine memory management technique deployed to handle the stated scenarios. To overwhelm the stated problem we have extended our previous work with a new technique that manages the data in Global Memory and Local Memory and enhances the performance of communicating across clusters for data access. The issue of the Global Memory and Local Memory Management is solved with the approach discussed in this paper. Experimental results show performance improvement to considerable levels with the implementation of the concept, specifically when the cost of data access from other clusters is higher and is proportionate to the amount of data.
Elliptic curve cryptography based threshold cryptography implementation for MANETs
41
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A Mobile Ad hoc Network (MANET) consists of multiple wireless mobile devices that form a network on the fly to allow communication with each other without any infrastructure. Due to its nature, providing security in this network is challenging. Threshold Cryptography (TC) provides a promise of securing this network. In this paper, our purpose is to find most suitable ECC algorithm compared to RSA. Through our implementation of Elliptic Curve Cryptography -based Threshold Cryptography (ECC-TC), we have explored three most-efficient ECC encryption algorithms and put forth possibility of using these ECC-TC algorithms in different scenarios in a MANET. We compare all ECC-TC results and suggest an algorithm that would be most suitable for MANET. Finally, we put forth a new secret sharing alternative that limit communication overheads for transmitting multiple secrets at the same time.
Polynomial Time Approximation Algorithms for Multi-Constrained QoS Routing
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We study the multi-constrained quality-of-service (QoS) routing problem where one seeks to find a path from a source to a destination in the presence of K ges 2 additive end-to-end QoS constraints. This problem is NP-hard and is commonly modeled using a graph with n vertices and m edges with K additive QoS parameters associated with each edge. For the case of K = 2, the problem has been well studied, with several provably good polynomial time-approximation algorithms reported in the literature, which enforce one constraint while approximating the other. We first focus on an optimization version of the problem where we enforce the first constraint and approximate the other K - 1 constraint. We present an O (mn log log log n + mn/epsi) time (1 + epsi) (K - 1)-approximation algorithm and an O (mn log log log n + m (n/epsi) K-1) time (1 + epsi)-approximation algorithm, for any epsi > 0. When K is reduced to 2, both algorithms produce an (1 + espy)-approximation with a time complexity better than that of the best-known algorithm designed for this special case. We then study the decision version of the problem and present an O(m(n/epsi)K-1) time algorithm which either finds a feasible solution or confirms that there does not exist a source-destination path whose first weight is bounded by the first constraint and whose every other weight is bounded by (1 - epsi) times the corresponding constraint. If there exists an H-hop source-destination path whose first weight is bounded by the first constraint and whose every other weight is bounded by (1 - epsi) times the corresponding constraint, our algorithm finds a feasible path in O(m(H/epsi)K-1) time. This algorithm improves previous best-known algorithms with O ((m + n log n) n/epsi) time for K = 2 and 0(mn (n/epsi) K-1) time for if ges 2.
Securing Mobile Ad Hoc Networks with Certificate less Public Keys
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper studies key management, a fundamental problem in securing mobile ad hoc networks (MANETs). We present IKM, an ID-based key management scheme as a novel combination of ID-based and threshold cryptography. IKM is a certificate less solution in that public keys of mobile nodes are directly derivable from their known IDs plus some common information. It thus eliminates the need for certificate-based authenticated public-key distribution indispensable in conventional public-key management schemes. IKM features a novel construction method of ID-based public/private keys, which not only ensures high-level tolerance to node compromise, but also enables efficient network-wide key update via a single broadcast message. We also provide general guidelines about how to choose the secret-sharing parameters used with threshold cryptography to meet desirable levels of security and robustness. The advantages of IKM over conventional certificate-based solutions are justified through extensive simulations. Since most MANET security mechanisms thus far involve the heavy use of certificates, we believe that our findings open a new avenue towards more effective and efficient security design for MANETs.
Dynamic routing with security considerations
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Security has become one of the major issues for data communication over wired and wireless networks. Different from the past work on the designs of cryptography algorithms and system infrastructures, we aim at the proposing of a dynamic routing algorithm that could randomize delivery paths for data transmission. The algorithm is easy to implement and compatible with popular routing protocols, such as routing information protocol in wired networks and destination-sequenced distance vector protocol in wireless networks, without introducing extra control messages. An analytic study on the proposed algorithm is presented, and a series of simulation experiments are conducted to verify the analytic results and to show the capability of the proposed algorithm.
Cooperative Secondary Authorization Recycling
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
As enterprise systems, Grids, and other distributed applications scale up and become increasingly complex, their authorization infrastructures--based predominantly on the request-response paradigm--are facing the challenges of fragility and poor scalability. We propose an approach where each application server recycles previously received authorizations and shares them with other application servers to mask authorization server failures and network delays. This paper presents the design of our cooperative secondary authorization recycling system and its evaluation using simulation and prototype implementation. The results demonstrate that our approach improves the availability and performance of authorization infrastructures. Specifically, by sharing authorizations, the cache hit rate--an indirect metric of availability--can reach 70 percent, even when only 10 percent of authorizations are cached. Depending on the deployment scenario, the average time for authorizing an application request can be reduced by up to a factor of two compared with systems that do not employ cooperation.
Flexible Rollback recovery in dynamic Heterogeneous GRID Computing
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Large applications executing on Grid or cluster architectures consisting of hundreds or thousands of computational nodes create problems with respect to reliability. The source of the problems is node failures and the need for dynamic configuration over extensive run-time. This paper presents two fault-tolerance mechanisms called theft induced check pointing and systematic event logging. These are transparent protocols capable of overcoming problems associated with both, benign faults, i.e., crash faults, and node or subnet volatility. Specifically, the protocols base the state of the execution on a dataflow graph, allowing for efficient recovery in dynamic heterogeneous systems as well as multi-threaded applications. By allowing recovery even under different numbers of processors, the approaches are especially suitable for applications with need for adaptive or reactionary configuration control. The low-cost protocols offer the capability of controlling or bounding the overhead. A formal cost model is presented, followed by an experimental evaluation. It is shown that the overhead of the protocol is very small and the maximum work lost by a crashed process is small and bounded.
Trust for Location-based Authorization
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Role-based access control (RBAC) has been generally accepted as one of the most promising access control policies, and it has become a hot research topic in information security area. However, traditional RBAC model is not completely fit for the access control in pervasive computing environment. In this paper, trust management technology is introduced on the basis of traditional access control model and the role-trust based access control model on interval-valued fuzzy sets theory (RTBAC) is proposed. It evaluates the trust degree of subjects according to interval-valued fuzzy theory and the access control policy is made by the trust level of the subjects who request to access. The subjects with higher trust degree and reliability are classified into higher trust level, and then the role-assign procedure assigns the trust level to a corresponding role. So it meets the requirements of pervasive computing environment better.
Congestion Control Protocol for Wireless Sensor Networks Handling Prioritized Heterogeneous Traffic
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In order to achieve higher reliability and load balancing various multipaths routing protocols have been proposed in Wireless Sensor Network. Moreover, wireless sensor network typically incorporates heterogeneous applications within the same network. A sensor node may have multiple sensors i.e. light, temperature, seismic etc with different transmission characteristics. Each application has different characteristics and requirements in terms of transmission rates, bandwidth, packet loss and delay demands may be initiated towards the sink. But achieving desired throughput for diverse data while disseminating through multiple paths is non trivial task as occurrence of congestion through multipath is obvious. In this paper we propose an efficient scheme to control multipath congestion so that the sink can get priority based throughput for heterogeneous data. We have used packet service ratio for detecting congestion as well as performed hop-by-hop multipath congestion control based on that metric. Finally, simulation results have demonstrated the effectiveness of our proposed approach.
An Efficient PKC-Based Security Architecture for Wireless Sensor Networks
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In spite of previous widely held belief of the incompatibility of public key cryptography (PKC) schemes for wireless sensor networks (WSNs), some recent works have shown that, PKC based schemes could be implemented for such networks in some ways. The major challenge of employing a PKC scheme in wireless sensor network is posed by the limitations of resources of the tiny sensors. Considering this feature of the sensors, in this paper, we propose an efficient PKC based security architecture with relatively less resource requirements than those of the other previously proposed PKC schemes for WSN. Our security architecture comprises basically of two parts; a key handshaking scheme based on simple linear operations and the derivation of decryption key by a receiver node. Our architecture allows both base-station-to-node or node-to-base-station secure communications, and node-to-node secure communications. Analysis and simulation results show that, our proposed architecture ensures a good level of security for communications in the network and could effectively be implemented using the limited computation, memory and energy budgets of the current generation sensor nodes.
A Secure Lightweight Approach of Node Membership Verification in Dense HDSN
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we consider a particular type of deployment scenario of a distributed sensor network (DSN), where sensors of different types and categories are densely deployed in the same target area. In this network, the sensors are associated with different groups, based on their functional types and after deployment they collaborate with one another in the same group for doing any assigned task for that particular group. We term this sort of DSN as a heterogeneous distributed sensor network (HDSN). Considering this scenario, we propose a secure membership verification mechanism using one-way accumulator (OWA) which ensures that, before collaborating for a particular task, any pair of nodes in the same deployment group can verify each other's legitimacy of membership. Our scheme also supports addition and deletion of members (nodes) in a particular group in the HDSN. Our analysis shows that, the proposed scheme could work well in conjunction with other security mechanisms for sensor networks and is very effective to resist any adversary's attempt to be included in a legitimate group in the network.
Implementation of fractal image compression employing artificial neural networks
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper presents a back propagation based neural network for fractal image compression. One of the image compression techniques in the spatial domain is Fractal Image Compression (FIC) but the main drawback of FIC using traditional exhaustive search is that it involves more computational time due to global search. In order to improve the computational time and compression ratio, artificial intelligence technique like neural network has been used. Feature extraction reduces the dimensionality of the problem and enables the neural network to be trained on an image separate from the test image thus reducing the computational time. Lowering the dimensionality of the problem reduces the computations required during the search. The main advantage of neural network is that it can adapt itself from the training data. The network adapts itself according to the distribution of feature space observed during training. Computer simulations reveal that the Network has been properly trained and classifies the domains correctly with minimum deviation which helps in encoding the image using FIC.
Automatic Cluster Detection in Kohonen’s SOM
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Kohonen’s self-organizing map (SOM) is popular neural network architecture for solving problems in the field of explorative data analysis, clustering, and data visualization. One of the major drawbacks of the SOM algorithm is the difficulty for nonexpert users to interpret the information contained in a trained SOM. In this paper, this problem is addressed by introducing an Enhanced version of the Clusot algorithm. This algorithm consists of two main steps: 1) the computation of the Clusot surface utilizing the information contained in a trained SOM and 2) the automatic detection of clusters in this surface. In the Clusot surface, clusters present in the underlying SOM are indicated by the local maxima of the surface. For SOMs with 2-D topology, the Clusot surface can, therefore, be considered as a convenient visualization technique. Yet, the presented approach is not restricted to a certain type of 2-D SOM topology and it is also applicable for SOMs having an -dimensional grid topology
A Method of Face Recognition Based on Fuzzy c-Means Clustering and Associated Sub-NNs
5
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The face is a complex multidimensional visual model and developing a computational model for face recognition is difficult. In this paper, we present a method for face recognition based on parallel neural networks. Neural networks (NNs) have been widely used in various fields. However, the computing efficiency decreases rapidly if the scale of the NN increases. In this paper, a new method of face recognition based on fuzzy clustering and parallel NNs is proposed. The face patterns are divided into several small-scale neural networks based on fuzzy clustering and they are combined to obtain the recognition result. In particular, the proposed method achieved a 98.75% recognition accuracy for 240 patterns of 20 registrants and a 99.58% rejection rate for 240 patterns of 20 nonregistrants. Experimental results show that the performance of our new face-recognition method is better than those of the back propagation NN (BPNN) system, the hard c-means (HCM) and parallel NNs system, and the pattern- matching system.
Speech recognition using artificial neural networks
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The synergism of Web and phone technologies has led to the development of a new innovative voice Web network. The voice Web requires a voice recognition and authentication system incorporating a reliable speech recognition technique for secure information access on the Internet. In line with this requirement, we investigate the applicability of artificial neural networks to speech recognition. In our experiment, a total number of 200 vowel signals from individuals with different gender and race were recorded. The filtering process was performed using the wavelet approach to de-noise and compress the speech signals. An artificial neural network, specially the probabilistic neural network model, was then employed to recognize and classify vowel signals into their respective categories. A series of parameter settings for the PNN model was investigated and the results obtained were analyzed and discussed.
Constructive neural-network learning algorithms for pattern classification
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Constructive learning algorithms offer an attractive approach for the incremental construction of near-minimal neural-network architectures for pattern classification. They help overcome the need for ad hoc and often inappropriate choices of network topology in algorithms that search for suitable weights in a priori fixed network architectures. Several such algorithms are proposed in the literature and shown to converge to zero classification errors (under certain assumptions) on tasks that involve learning a binary to binary mapping (i.e., classification problems involving binary-valued input attributes and two output categories). We present two constructive learning algorithms, MPyramid-real and MTiling-real, that extend the pyramid and tiling algorithms, respectively, for learning real to M-ary mappings (i.e., classification problems involving real-valued input attributes and multiple output classes). We prove the convergence of these algorithms and empirically demonstrate their applicability to practical pattern classification problems. Additionally, we show how the incorporation of a local pruning step can eliminate several redundant neurons from MTiling-real networks.
Stable adaptive neural network control of MIMO nonaffine nonlinear discrete-time systems
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, stable adaptive neural network (NN) control, a combination of weighted one-step-ahead control and adaptive NN is developed for a class of multi-input-multi-output (MIMO) nonaffine nonlinear discrete-time systems. The weighted one-step-ahead control is designed to stabilize the nominal linear system, while the adaptive NN compensator is introduced to deal with the nonlinearities. Under the assumption that the inverse control gain matrix has an either positive definite or negative definite symmetric part, the obstacle in NN weights tuning for the MIMO systems is transformed to unknown control direction problem for single-input-single-output (SISO) system. Discrete Nussbaum gain is introduced into the NN weights adaptation law to overcome the unknown control direction problem. It is proved that all signals of the closed-loop system are bounded, while the tracking error converges to a compact set. Simulation result illustrates the effectiveness of the proposed control.
Automatic Detection of Handwriting Forgery
12
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We investigated the detection of handwriting forgery by both human and machine. We obtained experimental handwriting data from subjects writing samples in their natural style and writing forgeries of other subjects? handwriting. These handwriting samples were digitally scanned and stored in an image database. We investigated the ease of forging handwriting, and found that many subjects can successfully forge the handwriting of others in terms of shape and size by tracing the authentic handwriting. Our hypothesis is that the authentic handwriting samples provided by subjects in their own natural writing style will have smooth ink traces, while forged handwritings will have wrinkly traces. We believe the reason for this is that forged handwriting is often either traced or copied slowly and is therefore more likely to appear wrinkly when scanned with a high-resolution scanner. Using seven handwriting distance features, we trained an artificial neural network to achieved 89% accuracy on test samples.
Local Classifier Weighting by Quadratic Programming
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
It has been widely accepted that the classification accuracy can be improved by combining outputs of multiple classifiers. However, how to combine multiple classifiers with various (potentially conflicting) decisions is still an open problem. A rich collection of classifier combination procedures-many of which are heuristic in nature-have been developed for this goal. In this brief, we describe a dynamic approach to combine classifiers that have expertise in different regions of the input space. To this end, we use local classifier accuracy estimates to weight classifier outputs. Specifically, we estimate local recognition accuracies of classifiers near a query sample by utilizing its nearest neighbors, and then use these estimates to find the best weights of classifiers to label the query. The problem is formulated as a convex quadratic optimization problem, which returns optimal nonnegative classifier weights with respect to the chosen objective function, and the weights ensure that locally most accurate classifiers are weighted more heavily for labeling the query sample. Experimental results on several data sets indicate that the proposed weighting scheme outperforms other popular classifier combination schemes, particularly on problems with complex decision boundaries. Hence, the results indicate that local classification-accuracy-based combination techniques are well suited for decision making when the classifiers are trained by focusing on different regions of the input space.
Bayesian retrieval in associative memories with storage errors
17
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
It is well known that for finite-sized networks, one-step retrieval in the auto associative Willshaw net is a suboptimal way to extract the information stored in the synapses. Iterative retrieval strategies are much better, but have hitherto only had heuristic justification. We show how they emerge naturally from considerations of probabilistic inference under conditions of noisy and partial input and a corrupted weight matrix. We start from the conditional probability distribution over possible patterns for retrieval. We develop two approximate, but tractable, iterative retrieval methods. One performs maximum likelihood inference to find the single most likely pattern, using the conditional probability as a Lyapunov function for retrieval. The second method makes a mean field assumption to optimize a tractable estimate of the full conditional probability distribution. In the absence of storage errors, both models become very similar to the Willshaw model.
Matrix-Variate Factor Analysis and Its Applications
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Factor analysis (FA) seeks to reveal the relationship between an observed vector variable and a latent variable of reduced dimension. It has been widely used in many applications involving high-dimensional data, such as image representation and face recognition. An intrinsic limitation of FA lies in its potentially poor performance when the data dimension is high, a problem known as curse of dimensionality. Motivated by the fact that images are inherently matrices, we develop, in this brief, an FA model for matrix-variate variables and present an efficient parameter estimation algorithm. Experiments on both toy and real-world image data demonstrate that the proposed matrix-variant FA model is more efficient and accurate than the classical FA approach, especially when the observed variable is high-dimensional and the samples available are limited.
Decision manifolds a supervised learning algorithm based on self organization
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we present a neural classifier algorithm that locally approximates the decision surface of labeled data by a patchwork of separating hyper planes, which are arranged under certain topological constraints similar to those of self-organizing maps (SOMs). We take advantage of the fact that these boundaries can often be represented by linear ones connected by a low-dimensional nonlinear manifold, thus influencing the placement of the separators. The resulting classifier allows for a voting scheme that averages over the classification results of neighboring hyper- planes. Our algorithm is computationally efficient both in terms of training and classification. Further, we present a model selection method to estimate the topology of the classification boundary. We demonstrate the algorithm's usefulness on several artificial and real-world data sets and compare it to the state-of-the-art supervised learning algorithms.
Nonnegative Matrix Factorization in Polynomial Feature Space
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Plenty of methods have been proposed in order to discover latent variables (features) in data sets. Such approaches include the principal component analysis (PCA), independent component analysis (ICA), factor analysis (FA), etc., to mention only a few. A recently investigated approach to decompose a data set with a given dimensionality into a lower dimensional space is the so-called nonnegative matrix factorization (NMF). Its only requirement is that both decomposition factors are nonnegative. To approximate the original data, the minimization of the NMF objective function is performed in the Euclidean space, where the difference between the original data and the factors can be minimized by employing L 2-norm. In this paper, we propose a generalization of the NMF algorithm by translating the objective function into a Hilbert space (also called feature space) under nonnegativity constraints. With the help of kernel functions, we developed an approach that allows high-order dependencies between the basis images while keeping the nonnegativity constraints on both basis images and coefficients. Two practical applications, namely, facial expression and face recognition, show the potential of the proposed approach.
Optimized Approximation Algorithm in Neural Networks Without Over fitting
18
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, an optimized approximation algorithm (OAA) is proposed to address the overfitting problem in function approximation using neural networks (NNs). The optimized approximation algorithm avoids overfitting by means of a novel and effective stopping criterion based on the estimation of the signal-to-noise-ratio figure (SNRF). Using SNRF, which checks the goodness-of-fit in the approximation, overfitting can be automatically detected from the training error only without use of a separate validation set. The algorithm has been applied to problems of optimizing the number of hidden neurons in a multilayer perceptron (MLP) and optimizing the number of learning epochs in MLP's back propagation training using both synthetic and benchmark data sets. The OAA algorithm can also be utilized in the optimization of other parameters of NNs. In addition, it can be applied to the problem of function approximation using any kind of basis functions, or to the problem of learning model selection when overfitting needs to be considered.
Supervised texture classification using a probabilistic neural network and constraint satisfaction model
15
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The texture classification problem is projected as a constraint satisfaction problem. The focus is on the use of a probabilistic neural network (PNN) for representing the distribution of feature vectors of each texture class in order to generate a feature-label interaction constraint. This distribution of features for each class is assumed as a Gaussian mixture model. The feature-label interactions and a set of label-label interactions are represented on a constraint satisfaction neural network. A stochastic relaxation strategy is used to obtain an optimal classification of textures in an image. The advantage of this approach is that all classes in an image are determined simultaneously, similar to human perception of textures in an image.
Handwritten Character Recognition Using Multiscale Neural Network Training Technique
14
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Advancement in Artificial Intelligence has lead to the developments of various “smart” devices. Character recognition device is one of such smart devices that acquire partial human intelligence with the ability to capture and recognize various characters in different languages. Firstly multiscale neural training with modifications in the input training vectors is adopted in this paper to acquire its advantage in training higher resolution character images. Secondly selective thresholding using minimum distance technique is proposed to be used to increase the level of accuracy of character recognition. A simulator program (a GUI) is designed in such a way that the characters can be located on any spot on the blank paper in which the characters are written. The results show that such methods with moderate level of training epochs can produce accuracies of at least 85% and more for handwritten upper case English characters and numerals.
OFF-LINE SIGNATURE VERIFICATION AND RECOGNITION BY SUPPORT VECTOR MACHINE
50
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper we present an off-line signature verification and recognition system using the global, directional and grid features of signatures. Support Vector Machine (SVM) was used to verify and classify the signatures and a classification ratio of 0.95 was obtained. As the recognition of signatures represents a multiclass problem SVM's one-against-all method was used. We also compare our methods performance with Artificial Neural Network’s (ANN) back propagation method
Real-Time Hand Tracking and Gesture Recognition System Using Neural Networks
48
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper introduces a hand gesture recognition system to recognize real time gesture in unstrained environments. Efforts should be made to adapt computers to our natural means of communication: Speech and body language. A simple and fast algorithm using orientation histograms will be developed. It will recognize a subset of MAL static hand gestures. A pattern recognition system will be using a transform that converts an image into a feature vector, which will be compared with the feature vectors of a training set of gestures. The final system will be Perceptron implementation in MATLAB. This paper includes experiments of 33 hand postures and discusses the results. Experiments shows that the system can achieve a 90% recognition average rate and is suitable for real time applications.
Classification and Feature Extraction by Simplexization
25
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Techniques for classification and feature extraction are often intertwined. In this paper, we contribute to these two aspects via the shared philosophy of simplexizing the sample set. For general classification, we present a new criteria based on the concept of -nearest-neighbor simplex (), which is constructed by the nearest neighbors, to determine the class label of a new datum. For feature extraction, we develop a novel subspace learning algorithm, called discriminant simplex analysis (DSA), in which the intraclass compactness and interclass separability are both measured by distances. Comprehensive experiments on face recognition and lipreading validate the effectiveness of the DSA as well as the -based classification approach.
Blind and Semi-Blind Deblurring of Natural Images
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A method for blind image deblurring is presented. The method only makes weak assumptions about the blurring filter and is able to undo a wide variety of blurring degradations. To overcome the ill-posedness of the blind image deblurring problem, the method includes a learning technique which initially focuses on the main edges of the image and gradually takes details into account. A new image prior, which includes a new edge detector, is used. The method is able to handle unconstrained blurs, but also allows the use of constraints or of prior information on the blurring filter, as well as the use of filters defined in a parametric manner. Furthermore, it works in both single-frame and multiframe scenarios. The use of constrained blur models appropriate to the problem at hand, and/or of multiframe scenarios, generally improves the deblurring results. Tests performed on monochrome and color images, with various synthetic and real-life degradations, without and with noise, in single-frame and multiframe scenarios, showed good results, both in subjective terms and in terms of the increase of signal to noise ratio (ISNR) measure. In comparisons with other state of the art methods, our method yields better results, and shows to be applicable to a much wider range of blurs.
Combining Local Filtering and Multiscale Analysis for Edge, Ridge, and Curvilinear Objects Detection
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper presents a general method for detecting curvilinear structures, like filaments or edges, in noisy images. This method relies on a novel technique, the feature-adapted beamlet transform (FABT) which is the main contribution of this paper. It combines the well-known beamlet transform (BT), introduced by Donoho , with local filtering techniques in order to improve both detection performance and accuracy of the BT. Moreover, as the desired feature detector is chosen to belong to the class of steerable filters, our transform requires only O(N log(N)) operations, where N = n 2 is the number of pixels. Besides providing a fast implementation of the FABT on discrete grids, we present a statistically controlled method for curvilinear objects detection. To extract significant objects, we propose an algorithm in four steps: 1) compute the FABT, 2) normalize beamlet coefficients, 3) select meaningful beamlets thanks to a fast energy-based minimization, and 4) link beamlets together in order to get a list of objects. We present an evaluation on both synthetic and real data, and demonstrate substantial improvements of our method over classical feature detectors.
Image Thumbnails That Represent Blur and Noise
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The information about the blur and noise of an original image is lost when a standard image thumbnail is generated by filtering and subsampling. Image browsing becomes difficult since the standard thumbnails do not distinguish between high-quality and low-quality originals. In this paper, an efficient algorithm with a blur-generating component and a noise-generating component preserves the local blur and the noise of the originals. The local blur is rapidly estimated using a scale-space expansion of the standard thumbnail and subsequently used to apply a space-varying blur to the thumbnail. The noise is estimated and rendered by using multirate signal transformations that allow most of the processing to occur at the lower spatial sampling rate of the thumbnail. The new thumbnails provide a quick, natural way for users to identify images of good quality. A subjective evaluation shows the new thumbnails are more representative of their originals for blurry images. The noise generating component improves the results for noisy images, but degrades the results for textured images. The blur generating component of the new thumbnails may always be used to advantage. The decision to use the noise generating component of the new thumbnails should be based on testing with the particular image mix expected for the application.
Generic Lossless Visible Watermarking
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A novel method for generic visible watermarking with a capability of lossless image recovery is proposed. The method is based on the use of deterministic one-to-one compound mappings of image pixel values for overlaying a variety of visible watermarks of arbitrary sizes on cover images. The compound mappings are proved to be reversible, which allows for lossless recovery of original images from watermarked images. The mappings may be adjusted to yield pixel values close to those of desired visible watermarks. Different types of visible watermarks, including opaque monochrome and translucent full color ones, are embedded as applications of the proposed generic approach. A two-fold monotonically increasing compound mapping is created and proved to yield more distinctive visible watermarks in the watermarked image. Security protection measures by parameter and mapping randomizations have also been proposed to deter attackers from illicit image recoveries. Experimental results demonstrating the effectiveness of the proposed approach are also included.
Automatic Color Based Reassembly of Fragmented Images and Paintings
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The problem of reassembling image fragments arises in many scientific fields, such as forensics and archaeology. In the field of archaeology, the pictorial excavation findings are almost always in the form of painting fragments. The manual execution of this task is very difficult, as it requires great amount of time, skill and effort. Thus, the automation of such a work is very important and can lead to faster, more efficient, painting reassembly and to a significant reduction in the human effort involved. In this paper, an integrated method for automatic color based 2-D image fragment reassembly is presented. The proposed 2-D reassembly technique is divided into four steps. Initially, the image fragments which are probably spatially adjacent, are identified utilizing techniques employed in content based image retrieval systems. The second operation is to identify the matching contour segments for every retained couple of image fragments, via a dynamic programming technique. The next step is to identify the optimal transformation in order to align the matching contour segments. Many registration techniques have been evaluated to this end. Finally, the overall image is reassembled from its properly aligned fragments. This is achieved via a novel algorithm, which exploits the alignment angles found during the previous step. In each stage, the most robust algorithms having the best performance are investigated and their results are fed to the next step. We have experimented with the proposed method using digitally scanned images of actual torn pieces of paper image prints and we produced very satisfactory reassembly results.
Active Reranking for Web Image Search
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Image search reranking methods usually fail to capture the user's intention when the query term is ambiguous. Therefore, reranking with user interactions, or active reranking, is highly demanded to effectively improve the search performance. The essential problem in active reranking is how to target the user's intention. To complete this goal, this paper presents a structural information based sample selection strategy to reduce the user's labeling efforts. Furthermore, to localize the user's intention in the visual feature space, a novel local-global discriminative dimension reduction algorithm is proposed. In this algorithm, a submanifold is learned by transferring the local geometry and the discriminative information from the labelled images to the whole (global) image database. Experiments on both synthetic datasets and a real Web image search dataset demonstrate the effectiveness of the proposed active reranking scheme, including both the structural information based active sample selection strategy and the local-global discriminative dimension reduction algorithm.
Distributed Image Coding for Digital Image Recovery From the Print-Scan Channel
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A printed digital photograph is difficult to reuse because the digital information that generated the print may no longer be available. This paper describes a method for approximating the original digital image by combining a scan of the printed photograph with digital auxiliary information kept together with the print. We formulate and solve the approximation problem using a Wyner-Ziv coding framework. During encoding, the Wyner-Ziv auxiliary information consists of a small amount of digital data composed of a number of sampled luminance pixel blocks and a number of sampled color pixel values to enable subsequent accurate registration and color-reproduction during decoding. The registration and color information is augmented by an additional amount of digital data encoded using Wyner-Ziv coding techniques that recovers residual errors and lost high spatial frequencies. The decoding process consists of scanning the printed photograph, together with a two step decoding process. The first decoding step, using the registration and color auxiliary information, generates a side-information image which registers and color corrects the scanned image. The second decoding step uses the additional Wyner-Ziv layer together with the side-information image to provide a closer approximation of the original, reducing residual errors and restoring the lost high spatial frequencies. The experimental results confirm the reduced digital storage needs when the scanned print assists in the digital reconstruction.
On-line Learning of Mutually Orthogonal Subspaces for Face Recognition by Image Sets
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We address the problem of face recognition by matching image sets. Each set of face images is represented by a subspace (or linear manifold) and recognition is carried out by subspace-to-subspace matching. In this paper, 1) a new discriminative method that maximises orthogonality between subspaces is proposed. The method improves the discrimination power of the subspace angle based face recognition method by maximizing the angles between different classes. 2) We propose a method for on-line updating the discriminative subspaces as a mechanism for continuously improving recognition accuracy. 3) A further enhancement called locally orthogonal subspace method is presented to maximise the orthogonality between competing classes. Experiments using 700 face image sets have shown that the proposed method outperforms relevant prior art and effectively boosts its accuracy by online learning. It is shown that the method for online learning delivers the same solution as the batch computation at far lower computational cost and the locally orthogonal method exhibits improved accuracy. We also demonstrate the merit of the proposed face recognition method on portal scenarios of multiple biometric grand challenge.
Misalignment-Robust Face Recognition
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Subspace learning techniques for face recognition have been widely studied in the past three decades. In this paper, we study the problem of general subspace-based face recognition under the scenarios with spatial misalignments and/or image occlusions. For a given subspace derived from training data in a supervised, unsupervised, or semi-supervised manner, the embedding of a new datum and its underlying spatial misalignment parameters are simultaneously inferred by solving a constrained ¿1 norm optimization problem, which minimizes the ¿1 error between the misalignment-amended image and the image reconstructed from the given subspace along with its principal complementary subspace. A byproduct of this formulation is the capability to detect the underlying image occlusions. Extensive experiments on spatial misalignment estimation, image occlusion detection, and face recognition with spatial misalignments and/or image occlusions all validate the effectiveness of our proposed general formulation for misalignment-robust face recognition.
Efficient Compression of Encrypted Grayscale Images
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Lossless compression of encrypted sources can be achieved through Slepian-Wolf coding. For encrypted real-world sources, such as images, the key to improve the compression efficiency is how the source dependency is exploited. Approaches in the literature that make use of Markov properties in the Slepian-Wolf decoder do not work well for grayscale images. In this correspondence, we propose a resolution progressive compression scheme which compresses an encrypted image progressively in resolution, such that the decoder can observe a low-resolution version of the image, study local statistics based on it, and use the statistics to decode the next resolution level. Good performance is observed both theoretically and experimentally.
Multiscale AM-FM Demodulation and Image Reconstruction Methods With Improved Accuracy
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We develop new multiscale amplitude-modulation frequency-modulation (AM-FM) demodulation methods for image processing. The approach is based on three basic ideas: (i) AM-FM demodulation using a new multiscale filterbank, (ii) new, accurate methods for instantaneous frequency (IF) estimation, and (iii) multiscale least squares AM-FM reconstructions. In particular, we introduce a variable-spacing local linear phase (VS-LLP) method for improved instantaneous frequency (IF) estimation and compare it to an extended quasilocal method and the quasi-eigen function approximation (QEA). It turns out that the new VS-LLP method is a generalization of the QEA method where we choose the best integer spacing between the samples to adapt as a function of frequency. We also introduce a new quasi-local method (QLM) for IF and IA estimation and discuss some of its advantages and limitations. The new IF estimation methods lead to significantly improved estimates. We present different multiscale decompositions to show that the proposed methods can be used to reconstruct and analyze general images.
Registering a MultiSensor Ensemble of Images
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Many registration scenarios involve aligning more than just two images. These image sets-called ensembles-are conventionally registered by choosing one image as a template, and every other image is registered to it. This pairwise approach is problematic because results depend on which image is chosen as the template. The issue is particularly acute for multisensor ensembles because different sensors create images with different features. Also, pairwise methods use only a fraction of the available data at a time. In this paper, we propose a maximum-likelihood clustering method that registers all the images in a multisensor ensemble simultaneously. Experiments involving rigid-body and affine transformations show that the clustering method is more robust and accurate than competing pairwise registration methods. Moreover, the clustering results can be used to form a rudimentary segmentation of the image ensemble.
A Robust Fuzzy Local Information C-Means Clustering Algorithm
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper presents a variation of fuzzy c-means (FCM) algorithm that provides image clustering. The proposed algorithm incorporates the local spatial information and gray level information in a novel fuzzy way. The new algorithm is called fuzzy local information C-Means (FLICM). FLICM can overcome the disadvantages of the known fuzzy c-means algorithms and at the same time enhances the clustering performance. The major characteristic of FLICM is the use of a fuzzy local (both spatial and gray level) similarity measure, aiming to guarantee noise insensitiveness and image detail preservation. Furthermore, the proposed algorithm is fully free of the empirically adjusted parameters (a, ¿g, ¿s, etc.) incorporated into all other fuzzy c-means algorithms proposed in the literature. Experiments performed on synthetic and real-world images show that FLICM algorithm is effective and efficient, providing robustness to noisy images.
Adaptive Kernel-Based Image Denoising Employing Semi-Parametric Regularization
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The main contribution of this paper is the development of a novel approach, based on the theory of Reproducing Kernel Hilbert Spaces (RKHS), for the problem of noise removal in the spatial domain. The proposed methodology has the advantage that it is able to remove any kind of additive noise (impulse, gaussian, uniform, etc.) from any digital image, in contrast to the most commonly used denoising techniques, which are noise dependent. The problem is cast as an optimization task in a RKHS, by taking advantage of the celebrated Representer Theorem in its semi-parametric formulation. The semi-parametric formulation, although known in theory, has so far found limited, to our knowledge, application. However, in the image denoising problem, its use is dictated by the nature of the problem itself. The need for edge preservation naturally leads to such a modeling. Examples verify that in the presence of gaussian noise the proposed methodology performs well compared to wavelet based technics and outperforms them significantly in the presence of impulse or mixed noise.
Adaptive Color Feature Extraction Based on Image Color Distributions
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper proposes an adaptive color feature extraction scheme by considering the color distribution of an image. Based on the binary quaternion-moment-preserving (BQMP) thresholding technique, the proposed extraction methods, fixed cardinality (FC) and variable cardinality (VC), are able to extract color features by preserving the color distribution of an image up to the third moment and to substantially reduce the distortion incurred in the extraction process. In addition to utilizing the earth mover's distance (EMD) as the distance measure of our color features, we also devise an efficient and effective distance measure, comparing histograms by clustering (CHIC). Moreover, the efficient implementation of our extraction methods is explored. With slight modification of the BQMP algorithm, our extraction methods are equipped with the capability of exploiting the concurrent property of hardware implementation. The experimental results show that our hardware implementation can achieve approximately a second order of magnitude improvement over the software implementation. It is noted that minimizing the distortion incurred in the extraction process can enhance the accuracy of the subsequent various image applications, and we evaluate the meaningfulness of the new extraction methods by the application to content-based image retrieval (CBIR). Our experimental results show that the proposed extraction methods can enhance the average retrieval precision rate by a factor of 25% over that of a traditional color feature extraction method.
A Unified Framework for Providing Recommendations in Social Tagging Systems Based on Ternary Semantic Analysis
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Social tagging is the process by which many users add metadata in the form of keywords, to annotate and categorize items (songs, pictures, Web links, products, etc.). Social tagging systems (STSs) can provide three different types of recommendations: They can recommend 1) tags to users, based on what tags other users have used for the same items, 2) items to users, based on tags they have in common with other similar users, and 3) users with common social interest, based on common tags on similar items. However, users may have different interests for an item, and items may have multiple facets. In contrast to the current recommendation algorithms, our approach develops a unified framework to model the three types of entities that exist in a social tagging system: users, items, and tags. These data are modeled by a 3-order tensor, on which multiway latent semantic analysis and dimensionality reduction is performed using both the higher order singular value decomposition (HOSVD) method and the kernel-SVD smoothing technique. We perform experimental comparison of the proposed method against state-of-the-art recommendation algorithms with two real data sets (Last.fm and BibSonomy). Our results show significant improvements in terms of effectiveness measured through recall/precision
FiVaTech: Page-Level Web Data Extraction from Template Pages
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Web data extraction has been an important part for many Web data analysis applications. In this paper, we formulate the data extraction problem as the decoding process of page generation based on structured data and tree templates. We propose an unsupervised, page-level data extraction approach to deduce the schema and templates for each individual deep Website, which contains either singleton or multiple data records in one Webpage. FiVaTech applies tree matching, tree alignment, and mining techniques to achieve the challenging task. In experiments, FiVaTech has much higher precision than EXALG and is comparable with other record-level extraction systems like ViPER and MSE. The experiments show an encouraging result for the test pages used in many state-of-the-art Web data extraction works.
Uninterpreted Schema Matching with Embedded Value Mapping under Opaque Column Names and Data Values
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Schema matching and value mapping across two heterogeneous information sources are critical tasks in applications involving data integration, data warehousing, and federation of databases. Before data can be integrated from multiple tables, the columns and the values appearing in the tables must be matched. The complexity of the problem grows quickly with the number of data attributes/columns to be matched and due to multiple semantics of data values. Traditional research has tackled schema matching and value mapping independently. We propose a novel method that optimizes embedded value mappings to enhance schema matching in the presence of opaque data values and column names. In this approach, the fitness objective for matching a pair of attributes from two schemas depends on the value mapping function for each of the two attributes. Suitable fitness objectives include the euclidean distance measure, which we use in our experimental study, as well as relative (cross) entropy. We propose a heuristic local descent optimization strategy that uses sorting and two-opt switching to jointly optimize value mappings and attribute matches. Our experiments show that our proposed technique outperforms earlier uninterpreted schema matching methods, and thus, should form a useful addition to a suite of (semi) automated tools for resolving structural heterogeneity.
Ensemble Rough Hypercuboid Approach for Classifying Cancers
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Cancer classification is the critical basis for patient-tailored therapy. Conventional histological analysis tends to be unreliable because different tumors may have similar appearance. The advances in microarray technology make individualized therapy possible. Various machine learning methods can be employed to classify cancer tissue samples based on microarray data. However, few methods can be elegantly adopted for generating accurate and reliable as well as biologically interpretable rules. In this paper, we introduce an approach for classifying cancers based on the principle of minimal rough fringe. For training rough hypercuboid classifiers from gene expression data sets, the method dynamically evaluates all available genes and sifts the genes with the smallest implicit regions as the dimensions of implicit hypercuboids. An unseen object is predicted to be a certain class if it falls within the corresponding class hypercuboid. Based upon the method, ensemble rough hypercuboid classifiers are subsequently constructed. Experimental results on some open cancer gene expression data sets show that the proposed method is capable of generating accurate and interpretable rules compared with some other machine learning methods. Hence, it is a feasible way of classifying cancer tissues in biomedical applications.
Ranked Query Processing in Uncertain Databases
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Recently, many new applications, such as sensor data monitoring and mobile device tracking, raise up the issue of uncertain data management. Compared to "certain¿ data, the data in the uncertain database are not exact points, which, instead, often reside within a region. In this paper, we study the ranked queries over uncertain data. In fact, ranked queries have been studied extensively in traditional database literature due to their popularity in many applications, such as decision making, recommendation raising, and data mining tasks. Many proposals have been made in order to improve the efficiency in answering ranked queries. However, the existing approaches are all based on the assumption that the underlying data are exact (or certain). Due to the intrinsic differences between uncertain and certain data, these methods are designed only for ranked queries in certain databases and cannot be applied to uncertain case directly. Motivated by this, we propose novel solutions to speed up the probabilistic ranked query (PRank) with monotonic preference functions over the uncertain database. Specifically, we introduce two effective pruning methods, spatial and probabilistic pruning, to help reduce the PRank search space. A special case of PRank with linear preference functions is also studied. Then, we seamlessly integrate these pruning heuristics into the PRank query procedure. Furthermore, we propose and tackle the PRank query processing over the join of two distinct uncertain databases. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed approaches in answering PRank queries, in terms of both wall clock time and the number of candidates to be refined.
Spectral Anonymization of Data
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The goal of data anonymization is to allow the release of scientifically useful data in a form that protects the privacy of its subjects. This requires more than simply removing personal identifiers from the data because an attacker can still use auxiliary information to infer sensitive individual information. Additional perturbation is necessary to prevent these inferences, and the challenge is to perturb the data in a way that preserves its analytic utility. No existing anonymization algorithm provides both perfect privacy protection and perfect analytic utility. We make the new observation that anonymization algorithms are not required to operate in the original vector-space basis of the data, and many algorithms can be improved by operating in a judiciously chosen alternate basis. A spectral basis derived from the data's eigenvectors is one that can provide substantial improvement. We introduce the term spectral anonymization to refer to an algorithm that uses a spectral basis for anonymization, and give two illustrative examples. We also propose new measures of privacy protection that are more general and more informative than existing measures, and a principled reference standard with which to define adequate privacy protection.
ViDE: A Vision-Based Approach for Deep Web Data Extraction
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Deep Web contents are accessed by queries submitted to Web databases and the returned data records are enwrapped in dynamically generated Web pages (they will be called deep Web pages in this paper). Extracting structured data from deep Web pages is a challenging problem due to the underlying intricate structures of such pages. Until now, a large number of techniques have been proposed to address this problem, but all of them have inherent limitations because they are Web-page-programming-language-dependent. As the popular two-dimensional media, the contents on Web pages are always displayed regularly for users to browse. This motivates us to seek a different way for deep Web data extraction to overcome the limitations of previous works by utilizing some interesting common visual features on the deep Web pages. In this paper, a novel vision-based approach that is Web-page-programming-language-independent is proposed. This approach primarily utilizes the visual features on the deep Web pages to implement deep Web data extraction, including data record extraction and data item extraction. We also propose a new evaluation measure revision to capture the amount of human effort needed to produce perfect extraction. Our experiments on a large set of Web databases show that the proposed vision-based approach is highly effective for deep Web data extraction.
Filter-Based Data Partitioning for Training Multiple Classifier Systems
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Data partitioning methods such as bagging and boosting have been extensively used in multiple classifier systems. These methods have shown a great potential for improving classification accuracy. This study is concerned with the analysis of training data distribution and its impact on the performance of multiple classifier systems. In this study, several feature-based and class-based measures are proposed. These measures can be used to estimate statistical characteristics of the training partitions. To assess the effectiveness of different types of training partitions, we generated a large number of disjoint training partitions with distinctive distributions. Then, we empirically assessed these training partitions and their impact on the performance of the system by utilizing the proposed feature-based and class-based measures. We applied the findings of this analysis and developed a new partitioning method called "Clustering, Declustering, and Selection" (CDS). This study presents a comparative analysis of several existing data partitioning methods including our proposed CDS approach.
Logic-Based Pattern Discovery
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In the data mining field, association rules are discovered having domain knowledge specified as a minimum support threshold. The accuracy in setting up this threshold directly influences the number and the quality of association rules discovered. Often, the number of association rules, even though large in number, misses some interesting rules and the rules' quality necessitates further analysis. As a result, decision making using these rules could lead to risky actions. We propose a framework to discover domain knowledge report as coherent rules. Coherent rules are discovered based on the properties of propositional logic, and therefore, requires no background knowledge to generate them. From the coherent rules discovered, association rules can be derived objectively and directly without knowing the level of minimum support threshold required. We provide analysis of the rules compare to those discovered via the a priori.
An UpDown Directed Acyclic Graph Approach for Sequential Pattern Mining
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Traditional pattern growth-based approaches for sequential pattern mining derive length-(k+1) patterns based on the projected databases of length-k patterns recursively. At each level of recursion, they unidirectionally grow the length of detected patterns by one along the suffix of detected patterns, which needs k levels of recursion to find a length-k pattern. In this paper, a novel data structure, UpDown Directed Acyclic Graph (UDDAG), is invented for efficient sequential pattern mining. UDDAG allows bidirectional pattern growth along both ends of detected patterns. Thus, a length-k pattern can be detected in [log2k + 1] levels of recursion at best, which results in fewer levels of recursion and faster pattern growth. When minSup is large such that the average pattern length is close to 1, UDDAG and PrefixSpan have similar performance because the problem degrades into frequent item counting problem. However, UDDAG scales up much better. It often outperforms PrefixSpan by almost one order of magnitude in scalability tests. UDDAG is also considerably faster than Spade and LapinSpam. Except for extreme cases, UDDAG uses comparable memory to that of PrefixSpan and less memory than Spade and LapinSpam. Additionally, the special feature of UDDAG enables its extension toward applications involving searching in large spaces.
Closeness: A New Privacy Measure for Data Publishing
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The k-anonymity privacy requirement for publishing microdata requires that each equivalence class (i.e., a set of records that are indistinguishable from each other with respect to certain “identifying” attributes) contains at least k records. Recently, several authors have recognized that k-anonymity cannot prevent attribute disclosure. The notion of ?-diversity has been proposed to address this; ?-diversity requires that each equivalence class has at least ? well-represented (in Section 2) values for each sensitive attribute. In this paper, we show that ?-diversity has a number of limitations. In particular, it is neither necessary nor sufficient to prevent attribute disclosure. Motivated by these limitations, we propose a new notion of privacy called “closeness.” We first present the base model t-closeness, which requires that the distribution of a sensitive attribute in any equivalence class is close to the distribution of the attribute in the overall table (i.e., the distance between the two distributions should be no more than a threshold t). We then propose a more flexible privacy model called (n,t)-closeness that offers higher utility. We describe our desiderata for designing a distance measure between two probability distributions and present two distance measures. We discuss the rationale for using closeness as a privacy measure and illustrate its advantages through examples and experiments.
Deriving Concept-Based User Profiles from Search Engine Logs
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
User profiling is a fundamental component of any personalization applications. Most existing user profiling strategies are based on objects that users are interested in (i.e., positive preferences), but not the objects that users dislike (i.e., negative preferences). In this paper, we focus on search engine personalization and develop several concept-based user profiling methods that are based on both positive and negative preferences. We evaluate the proposed methods against our previously proposed personalized query clustering method. Experimental results show that profiles which capture and utilize both of the user's positive and negative preferences perform the best. An important result from the experiments is that profiles with negative preferences can increase the separation between similar and dissimilar queries. The separation provides a clear threshold for an agglomerative clustering algorithm to terminate and improve the overall quality of the resulting query clusters.
BinRank: Scaling Dynamic Authority-Based Search Using Materialized Subgraphs
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Dynamic authority-based keyword search algorithms, such as ObjectRank and personalized PageRank, leverage semantic link information to provide high quality, high recall search in databases, and the Web. Conceptually, these algorithms require a query-time PageRank-style iterative computation over the full graph. This computation is too expensive for large graphs, and not feasible at query time. Alternatively, building an index of precomputed results for some or all keywords involves very expensive preprocessing. We introduce BinRank, a system that approximates ObjectRank results by utilizing a hybrid approach inspired by materialized views in traditional query processing. We materialize a number of relatively small subsets of the data graph in such a way that any keyword query can be answered by running ObjectRank on only one of the subgraphs. BinRank generates the subgraphs by partitioning all the terms in the corpus based on their co-occurrence, executing ObjectRank for each partition using the terms to generate a set of random walk starting points, and keeping only those objects that receive non-negligible scores. The intuition is that a subgraph that contains all objects and links relevant to a set of related terms should have all the information needed to rank objects with respect to one of these terms. We demonstrate that BinRank can achieve subsecond query execution time on the English Wikipedia data set, while producing high-quality search results that closely approximate the results of ObjectRank on the original graph. The Wikipedia link graph contains about 10^8 edges, which is at least two orders of magnitude larger than what prior state of the art dynamic authority-based search systems have been able to demonstrate. Our experimental evaluation investigates the trade-off between query execution time, quality of the results, and storage requirements of BinRank.
An Efficient Concept-Based Mining Model for Enhancing Text Clustering
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Most of the common techniques in text mining are based on the statistical analysis of a term, either word or phrase. Statistical analysis of a term frequency captures the importance of the term within a document only. However, two terms can have the same frequency in their documents, but one term contributes more to the meaning of its sentences than the other term. Thus, the underlying text mining model should indicate terms that capture the semantics of text. In this case, the mining model can capture terms that present the concepts of the sentence, which leads to discovery of the topic of the document. A new concept-based mining model that analyzes terms on the sentence, document, and corpus levels is introduced. The concept-based mining model can effectively discriminate between nonimportant terms with respect to sentence semantics and terms which hold the concepts that represent the sentence meaning. The proposed mining model consists of sentence-based concept analysis, document-based concept analysis, corpus-based concept-analysis, and concept-based similarity measure. The term which contributes to the sentence semantics is analyzed on the sentence, document, and corpus levels rather than the traditional analysis of the document only. The proposed model can efficiently find significant matching concepts between documents, according to the semantics of their sentences. The similarity between documents is calculated based on a new concept-based similarity measure. The proposed similarity measure takes full advantage of using the concept analysis measures on the sentence, document, and corpus levels in calculating the similarity between documents. Large sets of experiments using the proposed concept-based mining model on different data sets in text clustering are conducted. The experiments demonstrate extensive comparison between the concept-based analysis and the traditional analysis. Experimental results demonstrate the substantial enhancement of the clustering - - quality using the sentence-based, document-based, corpus-based, and combined approach concept analysis.
MABS: Multicast Authentication Based on Batch Signature
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Conventional block-based multicast authentication schemes overlook the heterogeneity of receivers by letting the sender choose the block size, divide a multicast stream into blocks, associate each block with a signature, and spread the effect of the signature across all the packets in the block through hash graphs or coding algorithms. The correlation among packets makes them vulnerable to packet loss, which is inherent in the Internet and wireless networks. Moreover, the lack of Denial of Service (DoS) resilience renders most of them vulnerable to packet injection in hostile environments. In this paper, we propose a novel multicast authentication protocol, namely MABS, including two schemes. The basic scheme (MABS-B) eliminates the correlation among packets and thus provides the perfect resilience to packet loss, and it is also efficient in terms of latency, computation, and communication overhead due to an efficient cryptographic primitive called batch signature, which supports the authentication of any number of packets simultaneously. We also present an enhanced scheme MABS-E, which combines the basic scheme with a packet filtering mechanism to alleviate the DoS impact while preserving the perfect resilience to packet loss.
Maximizing Rewards in Wireless Networks with Energy and Timing Constraints for Periodic Data Streams
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Power efficiency is an important design issue in mobile devices with limited power supplies. In this paper, we study a reward-based packet scheduling problem in wireless environments. We consider a general scenario in which a transmitter communicates with multiple receivers periodically. To guarantee timely transmission of data, each packet is associated with a delay constraint. The periodic data streams have different importance levels, power functions, and levels of data sizes. The more data a transmitter delivers, the more rewards it obtains. Our objective is to develop schemes that selectively transmit data streams of different data sizes at different transmission rates so that the system reward can be maximized under given time and energy constraints. We show that the problem is NP-hard and develop a dynamic programming algorithm for the optimal solution in pseudopolynomial time. A fast polynomial-time heuristic approach based on clustering of states in state space is presented to achieve close approximation. Simulation results demonstrate the effectiveness of the optimal solution and show that the proposed polynomial-time approach can achieve near-optimal results. Both approaches make a significant improvement over other approaches adapted from existing studies at a marginal runtime overhead.
Secure Distance-Based Localization in the Presence of Cheating Beacon Nodes
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Secure distance-based localization in the presence of cheating beacon (or anchor) nodes is an important problem in mobile wireless ad hoc and sensor networks. Despite significant research efforts in this direction, some fundamental questions still remain unaddressed: In the presence of cheating beacon nodes, what are the necessary and sufficient conditions to guarantee a bounded error during a two-dimensional distance-based location estimation? Under these necessary and sufficient conditions, what class of localization algorithms can provide this error bound? In this paper, we attempt to answer these and other related questions by following a careful analytical approach. Specifically, we first show that when the number of cheating beacon nodes is greater than or equal to a given threshold, there do not exist any two-dimensional distance-based localization algorithms that can guarantee a bounded error. Furthermore, when the number of cheating beacons is below this threshold, we identify a class of distance-based localization algorithms that can always guarantee a bounded localization error. Finally, we outline three novel distance-based localization algorithms that belong to this class of bounded error localization algorithms. We verify their accuracy and efficiency by means of extensive simulation experiments using both simple and practical distance estimation error models.
Fault-tolerant Mobile Agent-based Monitoring Mechanism for Highly Dynamic Distributed Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
A certain number of mobile agent-based monitoring mechanisms have actively been developed to monitor large-scale and dynamic distributed networked systems adaptively and efficiently. Among them, some mechanisms attempt to adapt to dynamic changes in various aspects such as network traffic patterns, resource addition and deletion, network topology and so on. However, failures of some domain managers are very critical to providing correct, real-time and efficient monitoring functionality in a large-scale mobile agent-based distributed monitoring system. In this paper, we present a novel fault tolerance mechanism to have the following advantageous features appropriate for large-scale and dynamic hierarchical mobile agent-based monitoring organizations. It supports fast failure detection functionality with low failure-free overhead by each domain manager transmitting heart-beat messages to its immediate higher-level manager. Also, it minimizes the number of non-faulty monitoring managers affected by failures of domain managers. Moreover, it allows consistent failure detection actions to be performed continuously in case of agent creation, migration and termination, and is able to execute consistent takeover actions even in concurrent failures of domain managers.
Optimal Jamming Attack Strategies and Network Defense Policies in Wireless Sensor Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We consider a scenario where a sophisticated jammer jams an area in which a single-channel random-access-based wireless sensor network operates. The jammer controls the probability of jamming and the transmission range in order to cause maximal damage to the network in terms of corrupted communication links. The jammer action ceases when it is detected by the network (namely by a monitoring node), and a notification message is transferred out of the jammed region. The jammer is detected by employing an optimal detection test based on the percentage of incurred collisions. On the other hand, the network defends itself by computing the channel access probability to minimize the jamming detection plus notification time. The necessary knowledge of the jammer in order to optimize its benefit consists of knowledge about the network channel access probability and the number of neighbors of the monitor node. Accordingly, the network needs to know the jamming probability of the jammer. We study the idealized case of perfect knowledge by both the jammer and the network about the strategy of each other and the case where the jammer and the network lack this knowledge. The latter is captured by formulating and solving optimization problems where the attacker and the network respond optimally to the worst-case or the average-case strategies of the other party. We also take into account potential energy constraints of the jammer and the network. We extend the problem to the case of multiple observers and adaptable jamming transmission range and propose a meaningful heuristic algorithm for an efficient jamming strategy. Our results provide valuable insights about the structure of the jamming problem and associated defense mechanisms and demonstrate the impact of knowledge as well as adoption of sophisticated strategies on achieving desirable performance.
On the Performance Bounds of Practical Wireless Network Coding
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Network coding is an attracting technology that has been shown to be able to improve the throughput of wireless networks. However, there still lacks fundamental understanding on how network coding works under realistic scenarios. In this paper, we examine the performance of a recently proposed network coding system under a realistic wireless physical layer and practical random access mechanisms. We propose a key performance measure called “encoding number”—the number of packets that can be encoded via network coding in each transmission. We provide an upper bound on the encoding number for the general coding topology, and derive the average encoding number and system throughput for a general class of random access mechanisms. Based on the practical coding system, we also derive a tighter upper bound on the throughput gain for a general wireless network. Our results are of fundamental value for coding-related MAC/Routing protocol design and analysis.
SSUM: Smart Server Update Mechanism for Maintaining Cache Consistency in Mobile Environments
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper proposes a cache consistency scheme based on a previously proposed architecture for caching database data in MANETs. The original scheme for data caching stores the queries that are submitted by requesting nodes in special nodes, called query directories (QDs), and uses these queries to locate the data (responses) that are stored in the nodes that requested them, called caching nodes (CNs). The consistency scheme is server-based in which control mechanisms are implemented to adapt the process of caching a data item and updating it by the server to its popularity and its data update rate at the server. The system implements methods to handle disconnections of QD and CN nodes from the network and to control how the cache of each node is updated or discarded when it returns to the network. Estimates for the average response time of node requests and the average node bandwidth utilization are derived in order to determine the gains (or costs) of employing our scheme in the MANET. Moreover, ns2 simulations were performed to measure several parameters, like the average data request response time, cache update delay, hit ratio, and bandwidth utilization. The results demonstrate the advantage of the proposed scheme over existing systems.
Modeling Power Saving Protocols for Multicast Services in 802.11 Wireless LANs
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In recent years, a series of power saving (PS) protocols has been proposed in the family of 802.11 standards to save energy for mobile devices. To evaluate their performance, many works have been carried out on testbeds or simulation platforms. However, till now, there is a lack of accurate theoretical models to analyze the performance for these protocols. In an effort to fill this gap, we present a Markov chain-based analytical model in this paper to model these PS protocols, with its focus on multicast services in wireless LANs. The proposed analytical model successfully captures the key characteristic of the power saving system: the data delivery procedure starts periodically at the previously negotiated time, but ends at a rather random time with its distribution depending on the end time of data delivery in the last delivery period as well as the arrival rate of incoming traffic. In the situations with light to moderate traffic loads and under the Poisson assumption for incoming traffic, the amount of data delivered between consecutive delivery periods possesses the Markov property, which builds up our Markov chain-based model. For incoming traffic with long-range dependence (LRD), a multistate Markov-Modulated Poisson Process (MMPP) is used to approximate the traffic, making the analytical model valid in more general cases. We verify our model by simulations on ns2 and the results show that the model can faithfully predict the performance of these PS protocols over a wide variety of testing scenarios.
DCAR: Distributed Coding-Aware Routing in Wireless Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Recently, there has been a growing interest of using network coding to improve the performance of wireless networks, for example, authors of proposed the practical wireless network coding system called COPE, which demonstrated the throughput gain achieved by network coding. However, COPE has two fundamental limitations: (1) the coding opportunity is crucially dependent on the established routes and (2) the coding structure in COPE is limited within a two-hop region only. The aim of this paper is to overcome these limitations. In particular, we propose DCAR, the distributed coding-aware routing mechanism which enables: (1) the discovery for available paths between a given source and destination and (2) the detection for potential network coding opportunities over much wider network region. One interesting result is that DCAR has the capability to discover high throughput paths with coding opportunities, while conventional wireless network routing protocols fail to do so. In addition, DCAR can detect coding opportunities on the entire path, thus eliminating the ¿two-hop¿ coding limitation in COPE. We also propose a novel routing metric called coding-aware routing metric (CRM) which facilitates the performance comparison between ¿coding-possible¿ and "coding-impossible¿ paths. We implement the DCAR system in ns-2 and carry out extensive evaluation. We show that when comparing to the coding mechanism in, DCAR can achieve much higher throughput gain.
VEBEK: Virtual Energy-Based Encryption and Keying for Wireless Sensor Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Designing cost-efficient, secure network protocols for Wireless Sensor Networks (WSNs) is a challenging problem because sensors are resource-limited wireless devices. Since the communication cost is the most dominant factor in a sensor's energy consumption, we introduce an energy-efficient Virtual Energy-Based Encryption and Keying (VEBEK) scheme for WSNs that significantly reduces the number of transmissions needed for rekeying to avoid stale keys. In addition to the goal of saving energy, minimal transmission is imperative for some military applications of WSNs where an adversary could be monitoring the wireless spectrum. VEBEK is a secure communication framework where sensed data is encoded using a scheme based on a permutation code generated via the RC4 encryption mechanism. The key to the RC4 encryption mechanism dynamically changes as a function of the residual virtual energy of the sensor. Thus, a one-time dynamic key is employed for one packet only and different keys are used for the successive packets of the stream. The intermediate nodes along the path to the sink are able to verify the authenticity and integrity of the incoming packets using a predicted value of the key generated by the sender's virtual energy, thus requiring no need for specific rekeying messages. VEBEK is able to efficiently detect and filter false data injected into the network by malicious outsiders. The VEBEK framework consists of two operational modes (VEBEK-I and VEBEK-II), each of which is optimal for different scenarios. In VEBEK-I, each node monitors its one-hop neighbors where VEBEK-II statistically monitors downstream nodes. We have evaluated VEBEK's feasibility and performance analytically and through simulations. Our results show that VEBEK, without incurring transmission overhead (increasing packet size or sending control messages for rekeying), is able to eliminate malicious data from the network in an energy-efficient manner. We also show that our framework performs be- - tter than other comparable schemes in the literature with an overall 60-100 percent improvement in energy savings without the assumption of a reliable medium access control layer.
Minimizing Delay and Maximizing Lifetime for Wireless Sensor Networks With Anycast
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we are interested in minimizing the delay and maximizing the lifetime of event-driven wireless sensor networks for which events occur infrequently. In such systems, most of the energy is consumed when the radios are on, waiting for a packet to arrive. Sleep-wake scheduling is an effective mechanism to prolong the lifetime of these energy-constrained wireless sensor networks. However, sleep-wake scheduling could result in substantial delays because a transmitting node needs to wait for its next-hop relay node to wake up. An interesting line of work attempts to reduce these delays by developing ¿anycast¿-based packet forwarding schemes, where each node opportunistically forwards a packet to the first neighboring node that wakes up among multiple candidate nodes. In this paper, we first study how to optimize the anycast forwarding schemes for minimizing the expected packet-delivery delays from the sensor nodes to the sink. Based on this result, we then provide a solution to the joint control problem of how to optimally control the system parameters of the sleep-wake scheduling protocol and the anycast packet-forwarding protocol to maximize the network lifetime, subject to a constraint on the expected end-to-end packet-delivery delay. Our numerical results indicate that the proposed solution can outperform prior heuristic solutions in the literature, especially under practical scenarios where there are obstructions, e.g., a lake or a mountain, in the coverage area of the wireless sensor network.
Fast Algorithms for Resource Allocation in Wireless Cellular Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We consider a scheduled orthogonal frequency division multiplexed (OFDM) wireless cellular network where the channels from the base-station to the $n$ mobile users undergo flat fading. Spectral resources are to be divided among the users in order to maximize total user utility. We show that this problem can be cast as a nonlinear convex optimization problem, and describe an $O(n)$ algorithm to solve it. Computational experiments show that the algorithm typically converges in around 25 iterations, where each iteration has a cost that is $O(n)$, with a modest constant. When the algorithm starts from an initial resource allocation that is close to optimal, convergence typically takes even fewer iterations. Thus, the algorithm can efficiently track the optimal resource allocation as the channel conditions change due to fading. We also show how our techniques can be extended to solve resource allocation problems that arise in wideband networks with frequency selective fading and when the utility of a user is also a function of the resource allocations in the past.
Integration of False Data Detection With Data Aggregation and Confidential Transmission in Wireless Sensor Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In wireless sensor networks, compromised sensor nodes can inject false data during both data aggregation and data forwarding. The existing false data detection techniques consider false data injections during data forwarding only and do not allow any change on the data by data aggregation. However, this paper presents a data aggregation and authentication protocol, called DAA, to integrate false data detection with data aggregation and confidentiality. To support data aggregation along with false data detection, the monitoring nodes of every data aggregator also conduct data aggregation and compute the corresponding small-size message authentication codes for data verification at their pairmates. To support confidential data transmission, the sensor nodes between two consecutive data aggregators verify the data integrity on the encrypted data rather than the plain data. Performance analysis shows that DAA detects any false data injected by up to $T$ compromised nodes, and that the detected false data are not forwarded beyond the next data aggregator on the path. Despite that false data detection and data confidentiality increase the communication overhead, simulation results show that DAA can still reduce the amount of transmitted data by up to 60% with the help of data aggregation and early detection of false data.
Toward Practical Opportunistic Routing With Intra-Session Network Coding for Mesh Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We consider opportunistic routing in wireless mesh networks. We exploit the inherent diversity of the broadcast nature of wireless by making use of multipath routing. We present a novel optimization framework for opportunistic routing based on network utility maximization (NUM) that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. All previous work on NUM assumed unicast transmissions; however, the wireless medium is by its nature broadcast and a transmission will be received by multiple nodes. The structure of our design is fundamentally different; this is due to the fact that our link rate constraints are defined per broadcast region instead of links in isolation. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. Optimal MAC scheduling is difficult to implement, and we use 802.11-like random scheduling rather than optimal in our comparisons. Under random scheduling, our protocol becomes fully decentralized (we assume ideal signaling). The use of network coding introduces additional constraints on scheduling, and we propose a novel scheme to avoid starvation. We simulate realistic topologies and show that we can achieve 20%-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).
Provisioning of Deadline-Driven Requests With Flexible Transmission Rates in WDM Mesh Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
With the increasing diversity of applications supported over optical networks, new service guarantees must be offered to network customers. Among the emerging data-intensive applications are those which require their data to be transferred before a predefined deadline. We call these deadline-driven requests (DDRs). In such applications, data-transfer finish time (which must be accomplished before the deadline) is the key service guarantee that the customer wants. In fact, the amount of bandwidth allocated to transfer a request is not a concern for the customer as long as its service deadline is met. Hence, the service provider can choose the bandwidth (transmission rate) to provision the request. In this case, even though DDRs impose a deadline constraint, they provide scheduling flexibility for the service provider since it can choose the transmission rate while achieving two objectives: 1) satisfying the guaranteed deadline; and 2) optimizing the network's resource utilization. We investigate the problem of provisioning DDRs with flexible transmission rates in wavelength-division multiplexing (WDM) mesh networks, although this approach is generalizable to other networks also. We investigate several (fixed and adaptive to network state) bandwidth-allocation policies and study the benefit of allowing dynamic bandwidth adjustment, which is found to generally improve network performance. We show that the performance of the bandwidth-allocation algorithms depends on the DDR traffic distribution and on the node architecture and its parameters. In addition, we develop a mathematical formulation for our problem as a mixed integer linear program (MILP), which allows choosing flexible transmission rates and provides a lower bound for our provisioning algorithms.
Inside the Permutation-Scanning Worms: Propagation Modeling and Analysis
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In recent years, both sophistication and damage potential of Internet worms have increased tremendously. To understand their threat, we need to look into their payload for signatures as well as propagation pattern for Internet-scale behavior. An accurate analytical propagation model allows us to comprehensively study how a worm propagates under various conditions, which is often computationally too intensive for simulations. More importantly, it gives us an insight into the impact of each worm/network parameter on the propagation of the worm. Traditionally, most modeling work in this area concentrates on the relatively simple random-scanning worms. However, modeling the permutation-scanning worms, a class of worms that are fast yet stealthy, has been a challenge to date. This paper proposes a mathematical model that precisely characterizes the propagation patterns of the general permutation-scanning worms. The analytical framework captures the interactions among all infected hosts by a series of interdependent differential equations, which are then integrated into closed-form solutions that together present the overall worm behavior. We use the model to study how each worm/network parameter affects the worm propagation. We also investigate the impact of dynamic network conditions on the correctness of the model.
Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged by further involving sink mobility. As most proposals give their evidence of lifetime improvement through either (small-scale) field tests or numerical simulations on rather arbitrary cases, a theoretical understanding of the reason for this improvement and the tractability of the joint optimization problem is still missing. In this paper, we build a framework for investigating the joint sink mobility and routing problem by constraining the sink to a finite number of locations. We formally prove the NP-hardness of the problem. We also investigate the induced subproblems. In particular, we develop an efficient primal-dual algorithm to solve the subproblem involving a single sink, then we generalize this algorithm to approximate the original problem involving multiple sinks. Finally, we apply the algorithm to a set of typical topological graphs; the results demonstrate the benefit of involving sink mobility, and they also suggest the desirable moving traces of a sink.
Equilibrium of Heterogeneous Congestion Control: Optimality and Stability
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
When heterogeneous congestion control protocols that react to different pricing signals share the same network, the current theory based on utility maximization fails to predict the network behavior. The pricing signals can be different types of signals such as packet loss, queueing delay, etc, or different values of the same type of signal such as different ECN marking values based on the same actual link congestion level. Unlike in a homogeneous network, the bandwidth allocation now depends on router parameters and flow arrival patterns. It can be non-unique, suboptimal and unstable. In Tang (“Equilibrium of heterogeneous congestion control: Existence and uniqueness,” IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 824–837, Aug. 2007), existence and uniqueness of equilibrium of heterogeneous protocols are investigated. This paper extends the study with two objectives: analyzing the optimality and stability of such networks and designing control schemes to improve those properties. First, we demonstrate the intricate behavior of a heterogeneous network through simulations and present a framework to help understand its equilibrium properties. Second, we propose a simple source-based algorithm to decouple bandwidth allocation from router parameters and flow arrival patterns by only updating a linear parameter in the sources' algorithms on a slow timescale. It steers a network to the unique optimal equilibrium. The scheme can be deployed incrementally as the existing protocol needs no change and only new protocols need to adopt the slow timescale adaptation.
Rate Control With Pairwise Intersession Network Coding
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we develop a distributed rate-control algorithm for networks with multiple unicast sessions when network coding is allowed across different sessions. Building on recent flow-based characterization of pairwise intersession network coding, the corresponding optimal rate-control problem is formulated as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where any coded symbol is formed by coding over at most two original symbols. The objective function is the sum of the utilities based on the rates supported by each unicast session. Working on the Lagrangian of the formulated problem, a distributed algorithm is developed with little coordination among intermediate nodes. Each unicast session has the freedom to choose its own utility function. The only information exchange required by the source is the weighted sum of the queue length of each link, which can be piggybacked to the acknowledgment messages. In addition to the optimal rate-control algorithm, we propose a decentralized pairwise random coding scheme that decouples the decision of coding from that of rate control, which further enhances the distributiveness of the proposed scheme. The convergence of the rate-control algorithm is proven analytically and verified by extensive simulations. Simulation results also demonstrate the advantage of the proposed algorithm over the state-of-the-art in terms of both throughput and fairness.
Distributed Algorithms for Minimum Cost Multicast With Network Coding
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Network coding techniques are used to find the minimum-cost transmission scheme for multicast sessions with or without elastic rate demand. It is shown that in wireline networks, solving for the optimal coding subgraphs in network coding is equivalent to finding the optimal routing scheme in a multicommodity flow problem. A set of node-based distributed gradient projection algorithms are designed to jointly implement congestion control/routing at the source node and ¿virtual¿ routing at intermediate nodes. The analytical framework and distributed algorithms are further extended to interference-limited wireless networks where link capacities are functions of the signal-to-interference-plus-noise ratio (SINR). To achieve minimum-cost multicast in this setting, the transmission powers of links must be jointly optimized with coding subgraphs and multicast input rates. Node-based power allocation and power control algorithms are developed for the power optimization. The power algorithms, when iterated in conjunction with the congestion control and routing algorithms, converge to the jointly optimal multicast configuration. The scaling matrices required in the gradient projection algorithms are explicitly derived and are shown to guarantee fast convergence to the optimum from any initial condition.
An Analytical Approach to Optimizing Parallel Image Registration/Retrieval
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Image-content queries or image registration algorithms typically have very high computational requirements. In this paper, we address the problem of minimizing the total execution time of data-parallel image-content query algorithms on heterogeneous platforms. The model we use to capture the inner workings of these algorithms is comprehensive enough to incorporate not only the communication overheads, both distribution and result collection, but also the presence of local data caches that could exist as a result of previous queries. The problem is solved under all possible computation and communication configurations, including single and multiple-port communications and block or stream-type tasks. Our analysis, either, yields closed-form solutions to the partitioning problem, or, formulates the problem in a fashion that allows the use of linear programming tools toward this end. The latter are used for solving the multi-installment data distribution approaches, that tend to utilize the computational resources more efficiently. Additionally, a heuristic algorithm is presented, for producing a close-to-optimum sequence of load distribution/result collection operations for single-port communications. Based on our analytical results, a thorough simulation and experimental study is performed, yielding substantial design guidelines for implementation strategies.
Dealing with Transient Faults in the Interconnection Network of CMPs at the Cache Coherence Level
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The importance of transient faults is predicted to grow due to current technology trends of increased scale of integration. One of the components that will be significantly affected by transient faults is the interconnection network of chip multiprocessors (CMPs). To deal efficiently with these faults and differently from other authors, we propose to use fault-tolerant cache coherence protocols that ensure the correct execution of programs when not all messages are correctly delivered. We describe the extensions made to a directory-based cache coherence protocol to provide fault tolerance and provide a modified set of token counting rules which are useful to design fault-tolerant token-based cache coherence protocols. We compare the directory-based fault-tolerant protocol with a token-based fault-tolerant one. We also show how to adjust the fault tolerance parameters to achieve the desired level of fault tolerance and measure the overhead achieved to be able to support very high fault rates. Simulation results using a set of scientific, multimedia, and commercial applications show that the fault tolerance measures have virtually no impact on execution time with respect to a non-fault-tolerant protocol. Additionally, our protocols can support very high rates of transient faults at the cost of slightly increased network traffic.
Detecting Application Denial-of-Service Attacks: A Group-Testing-Based Approach
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Application DoS attack, which aims at disrupting application service rather than depleting the network resource, has emerged as a larger threat to network services, compared to the classic DoS attack. Owing to its high similarity to legitimate traffic and much lower launching overhead than classic DDoS attack, this new assault type cannot be efficiently detected or prevented by existing detection solutions. To identify application DoS attack, we propose a novel group testing (GT)-based approach deployed on back-end servers, which not only offers a theoretical method to obtain short detection delay and low false positive/negative rate, but also provides an underlying framework against general network attacks. More specifically, we first extend classic GT model with size constraints for practice purposes, then redistribute the client service requests to multiple virtual servers embedded within each back-end server machine, according to specific testing matrices. Based on this framework, we propose a two-mode detection mechanism using some dynamic thresholds to efficiently identify the attackers. The focus of this work lies in the detection algorithms proposed and the corresponding theoretical complexity analysis. We also provide preliminary simulation results regarding the efficiency and practicability of this new scheme. Further discussions over implementation issues and performance enhancements are also appended to show its great potentials.
Flexible Cache Consistency Maintenance over Wireless Ad Hoc Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
One of the major applications of wireless ad hoc networks is to extend the Internet coverage and support pervasive and efficient data dissemination and sharing. To reduce data access cost and delay, caching has been widely used as an important technique. The efficiency of data access in caching systems largely depends on the cost for maintaining cache consistency, which can be high in wireless ad hoc networks due to network dynamism. Therefore, to make better trade-off between cache consistency and the cost incurred, it would be highly desirable to provide users the flexibility in specifying consistency requirements for their applications. In this paper, we propose a general consistency model called Probabilistic Delta Consistency (PDC), which integrates the flexibility granted by existing consistency models, covering them as special cases. We also propose the Flexible Combination of Push and Pull (FCPP) algorithm which satisfies user-specified consistency requirements under the PDC model. The analytical model of FCPP is used to derive the balance of minimizing the consistency maintenance cost and ensuring the specified consistency requirement. Extensive simulations are conducted to evaluate whether FCPP can satisfy arbitrarily specified consistency requirements, and whether FCPP works cost-effectively in dynamic wireless ad hoc networks. The evaluation results show that FCPP can adaptively tune itself to satisfy various user-specified consistency requirements. Moreover, it can save the traffic cost by up to 50 percent and reduce the query delay by up to 40 percent, compared with the widely used Pull with TTR algorithm.
Impact of Feature Reduction on the Efficiency of Wireless Intrusion Detection Systems
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Intrusion Detection Systems (IDSs) are a major line of defense for protecting network resources from illegal penetrations. A common approach in intrusion detection models, specifically in anomaly detection models, is to use classifiers as detectors. Selecting the best set of features is central to ensuring the performance, speed of learning, accuracy, and reliability of these detectors as well as to remove noise from the set of features used to construct the classifiers. In most current systems, the features used for training and testing the intrusion detection systems consist of basic information related to the TCP/IP header, with no considerable attention to the features associated with lower level protocol frames. The resulting detectors were efficient and accurate in detecting network attacks at the network and transport layers, but unfortunately, not capable of detecting 802.11-specific attacks such as deauthentication attacks or MAC layer DoS attacks. In this paper, we propose a novel hybrid model that efficiently selects the optimal set of features in order to detect 802.11-specific intrusions. Our model for feature selection uses the information gain ratio measure as a means to compute the relevance of each feature and the k-means classifier to select the optimal set of MAC layer features that can improve the accuracy of intrusion detection systems while reducing the learning time of their learning algorithm. In the experimental section of this paper, we study the impact of the optimization of the feature set for wireless intrusion detection systems on the performance and learning time of different types of classifiers based on neural networks. Experimental results with three types of neural network architectures clearly show that the optimization of a wireless feature set has a significant impact on the efficiency and accuracy of the intrusion detection system.
Improving Reliability for Application-Layer Multicast Overlays
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Reliability of tree-like multicast overlays caused by nodes' abrupt failures is considered as one of the major problems for the Internet application-layer media streaming service. In this paper, we address this problem by designing a distributed and light-weighted protocol named the instantaneous reliability oriented protocol (IRP). Unlike most of existing empirical solutions, we first define the overlay reliability problem formally, and propose a protocol containing a node joining algorithm (IRP-Join), a node preemption algorithm (IRP-Preempt), and a node switching algorithm (IRP-Switch) for reactively constructing and repairing the overlay, as well as proactively maintaining the overlay. With the formal problem presentation, we set up a paradigm for solving the overlay reliability problem by theoretically proving the effectiveness of our algorithms. Moreover, by comparing IRP with existing solutions via simulation-based experiments and real-world deployment, we show that IRP achieves a better reliability, while incurs fewer structural adjustments on the multicast overlay, thus, providing a superior overall performance.
Logoot-Undo Distributed Collaborative Editing System on P2P Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Peer-to-peer systems provide scalable content distribution for cheap and resist to censorship attempts. However, P2P networks mainly distribute immutable content and provide poor support for highly dynamic content such as produced by collaborative systems. A new class of algorithms called CRDT (Commutative Replicated Data Type), which ensures consistency of highly dynamic content on P2P networks, is emerging. However, if existing CRDT algorithms support the "edit anywhere, anytime” feature, they do not support the "undo anywhere, anytime” feature. In this paper, we present the Logoot-Undo CRDT algorithm, which integrates the "undo anywhere, anytime” feature. We compare the performance of the proposed algorithm with related algorithms and measure the impact of the undo feature on the global performance of the algorithm. We prove that the cost of the undo feature remains low on a corpus of data extracted from Wikipedia.
Resource Bundles Using Aggregation for Statistical Large-Scale Resource Discovery and Management
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Resource discovery is an important process for finding suitable nodes that satisfy application requirements in large loosely coupled distributed systems. Besides internode heterogeneity, many of these systems also show a high degree of intranode dynamism, so that selecting nodes based only on their recently observed resource capacities can lead to poor deployment decisions resulting in application failures or migration overheads. However, most existing resource discovery mechanisms rely mainly on recent observations to achieve scalability in large systems. In this paper, we propose the notion of a resource bundle-a representative resource usage distribution for a group of nodes with similar resource usage patterns-that employs two complementary techniques to overcome the limitations of existing techniques: resource usage histograms to provide statistical guarantees for resource capacities and clustering-based resource aggregation to achieve scalability. Using trace-driven simulations and data analysis of a month-long PlanetLab trace, we show that resource bundles are able to provide high accuracy for statistical resource discovery, while achieving high scalability. We also show that resource bundles are ideally suited for identifying group-level characteristics (e.g., hot spots, total group capacity). To automatically parameterize the bundling algorithm, we present an adaptive algorithm that can detect online fluctuations in resource heterogeneity.
Secure Synchronization of Periodic Updates in Ad Hoc Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We present techniques for synchronizing nodes that periodically broadcast content and presence updates to colocated nodes over an ad hoc network, where nodes may exhibit Byzantine malicious behavior. Instead of aligning duty cycles, our algorithms synchronize the periodic transmissions of nodes. This allows nodes to save battery power by switching off their network cards without missing updates from their neighbors. We propose several novel attack classes and show that they are able to disrupt synchronization even when launched by a single attacker. Finally, we devise a rating based algorithm (RBA) that rates neighbors based on the consistency of their behavior. By favoring well-behaved nodes in the synchronization process, we show that RBA quickly stabilizes the synchronization process and reduces the number of lost updates by 85 percent. Our evaluation also shows that all our algorithms are computationally efficient and, for the setup considered, extend the device lifetime by 30 percent over an always-on Wi-Fi scenario.
Snoogle A Search Engine for Pervasive Environments
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Embedding small devices into everyday objects like toasters and coffee mugs creates a wireless network of objects. These embedded devices can contain a description of the underlying objects, or other user defined information. In this paper, we present Snoogle, a search engine for such a network. A user can query Snoogle to find a particular mobile object, or a list of objects that fit the description. Snoogle uses information retrieval techniques to index information and process user queries, and Bloom filters to reduce communication overhead. Security and privacy protections are also engineered into Snoogle to protect sensitive information. We have implemented a prototype of Snoogle using off-the-shelf sensor motes, and conducted extensive experiments to evaluate the system performance.
Stabilizing Distributed R-Trees for Peer-to-Peer Content Routing
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Publish/subscribe systems provide useful platforms for delivering data (events) from publishers to subscribers in a decoupled fashion. Developing efficient publish/subscribe schemes in dynamic distributed systems is still an open problem for complex subscriptions (spanning multidimensional intervals). We propose a distributed R-tree (DR-tree) structure that uses R-tree-based spatial filters to construct a peer-to-peer overlay optimized for scalable and efficient selective dissemination of information. We adapt well-known variants of R-trees to organize publishers and subscribers in balanced peer-to-peer networks that support content-based filtering in publish/subscribe systems. DR-tree overlays guarantee subscription and publication times logarithmic in the size of the network while keeping space requirements low (comparable to distributed hash tables). The maintenance of the overlay is local and the structure is balanced with height logarithmic in the number of nodes. DR-tree overlays disseminate messages with no false negatives and very few false positives in the embedded publish/subscribe system. In addition, we propose self-stabilizing algorithms that guarantee consistency despite failures and changes in the peer population.
The Topology of Gaussian and Eisenstein-Jacobi Interconnection Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Earlier authors have used quotient rings of Gaussian and Eisenstein-Jacobi integers to construct interconnection networks with good topological properties. In this paper, we present a unified study of these two types of networks. Our results include decomposing the edges into disjoint Hamiltonian cycles, a simplification of the calculation of the Eisenstein-Jacobi distance, a distribution of the distances between Eisenstein-Jacobi nodes, and shortest path routing algorithms. In particular, the known Gaussian routing algorithm is simplified.
SocioNet: A Social-Based Multimedia Access System for Unstructured P2P Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Increasingly, peer-to-peer (P2P) network users expect to be able to search objects by semantic attributes based on their preferences for multimedia content. Partial match search (i.e., search through the use of multimedia content semantic information) has become an essential service in P2P systems. In this paper, we propose SocioNet, a social-based overlay that clusters peers based on their preference relationships as a small-world network. In SocioNet, peers mimic how people form a social network and how they query, by preference, their friends or acquaintances. Hence, SocioNet benefits from two desirable features of a social network: interest-based clustering and small-world properties (i.e., high cluster coefficient among all peers yet short path lengths between any two peers). To realize an interest-based small-world SocioNet, we also investigate the following practical design issues: 1) similarity estimation: we define a quantifiable similarity measure that enables clustering of similar peers in SocioNet; 2) distributed small-world overlay adaptation: peers maintain a small-world overlay under network dynamics; and 3) query strategy under the small-world overlay: we analyze appropriate settings for the Time-to-Live (TTL) value, for TTL-limited flooding, that provides a satisfactory success ratio and avoids redundant message overhead. We use simulations and a real database called AudioScrobbler [CHECK END OF SENTENCE], which tracks users' listening habits, to evaluate the performance of SocioNet. The results show that SocioNet assists peers in locating content at peers with similar interests through short path lengths, and hence, achieves a higher success ratio (than nonsmall-world interest-based overlays and noninterest-based small-world overlays) while reducing message overhead significantly.
A Cross-Layer Approach-Based Gnutella for Collaborative Virtual Environments over Mobile Ad Hoc Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Collaborative Virtual Environments (CVEs) such as military training programs, emergency preparedness simulations, and online games place strict requirements on network performance when participating users share the 3D virtual environment through their mobile devices in an ad hoc network. However, most support systems for existing CVEs are confined to a desktop setting, thus preventing collaboration while users are mobile. In this work, we propose and evaluate a Gnutella peer-to-peer network over mobile ad hoc networks (MANETs) to support Mobile Collaborative Virtual Environment (MCVE) applications. Both architectures share some common features such as decentralization, self-reorganization, and self-healing. However, peer-to-peer networks and MANETs operate on different network layers, and thus, cause poor performance. To address this problem, we explore a novel cross-layer approach to improve the overall performance of CVEs over MANETs. The network layer should be aware of the user's physical position in the virtual environment (VE) in order to minimize network traffic and cope with a moderate workload between nodes. In this paper, we present a cross-layer approach model for collaborative virtual environment over MANET. We describe its implementation and evaluate its performance using NS2 simulator.
Adaptive Workload Prediction of Grid Performance in Confidence Windows
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Predicting grid performance is a complex task because heterogeneous resource nodes are involved in a distributed environment. Long execution workload on a grid is even harder to predict due to heavy load fluctuations. In this paper, we use Kalman filter to minimize the prediction errors. We apply Savitzky-Golay filter to train a sequence of confidence windows. The purpose is to smooth the prediction process from being disturbed by load fluctuations. We present a new adaptive hybrid method (AHModel) for load prediction guided by trained confidence windows. We test the effectiveness of this new prediction scheme with real-life workload traces on the AuverGrid and Grid5000 in France. Both theoretical and experimental results are reported in this paper. As the lookahead span increases from 10 to 50 steps (5 minutes per step), the AHModel predicts the grid workload with a mean-square error (MSE) of 0.04-0.73 percent, compared with 2.54-30.2 percent in using the static point value autoregression (AR) prediction method. The significant gain in prediction accuracy makes the new model very attractive to predict Grid performance. The model was proved especially effective to predict large workload that demands very long execution time, such as exceeding 4 hours on the Grid5000 over 5,000 processors. With minor changes of some system parameters, the AHModel can apply to other computational grids as well. At the end, we discuss extended research issues and tool development for Grid performance prediction.
Correlation-Based Traffic Analysis Attacks on Anonymity Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we address attacks that exploit the timing behavior of TCP and other protocols and applications in low-latency anonymity networks. Mixes have been used in many anonymous communication systems and are supposed to provide countermeasures to defeat traffic analysis attacks. In this paper, we focus on a particular class of traffic analysis attacks, flow-correlation attacks, by which an adversary attempts to analyze the network traffic and correlate the traffic of a flow over an input link with that over an output link. Two classes of correlation methods are considered, namely time-domain methods and frequency-domain methods. Based on our threat model and known strategies in existing mix networks, we perform extensive experiments to analyze the performance of mixes. We find that all but a few batching strategies fail against flow-correlation attacks, allowing the adversary to either identify ingress and egress points of a flow or to reconstruct the path used by the flow. Counterintuitively, some batching strategies are actually detrimental against attacks. The empirical results provided in this paper give an indication to designers of Mix networks about appropriate configurations and mechanisms to be used to counter flow-correlation attacks.
On the Benefits of Cooperative Proxy Caching for Peer-to-Peer Traffic
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper analyzes the potential of cooperative proxy caching for peer-to-peer (P2P) traffic as a means to ease the burden imposed by P2P traffic on Internet Service Providers (ISPs). In particular, we propose two models for cooperative caching of P2P traffic. The first model enables cooperation among caches that belong to different autonomous systems (ASs), while the second considers cooperation among caches deployed within the same AS. We analyze the potential gain of cooperative caching in these two models. To perform this analysis, we conduct an eight-month measurement study on a popular P2P system to collect traffic traces for multiple caches. Then, we perform extensive trace-based simulations to analyze different angles of cooperative caching schemes. Our results demonstrate that: 1) significant improvement in byte hit rate can be achieved using cooperative caching, 2) simple object replacement policies are sufficient to achieve that gain, and 3) the overhead imposed by cooperative caching is negligible. In addition, we develop an analytic model to assess the gain from cooperative caching in different settings. The model accounts for number of caches, salient P2P traffic features, and network characteristics. Our model confirms that substantial gains from cooperative caching are attainable under wide ranges of traffic and network characteristics.
Coupling-Based Internal Clock Synchronization for Large-Scale Dynamic Distributed Systems
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
This paper studies the problem of realizing a common software clock among a large set of nodes without an external time reference (i.e., internal clock synchronization), any centralized control, and where nodes can join and leave the distributed system at their will. The paper proposes an internal clock synchronization algorithm which combines the gossip-based paradigm with a nature-inspired approach, coming from the coupled oscillators phenomenon, to cope with scale and churn. The algorithm works on the top of an overlay network and uses a uniform peer sampling service to fulfill each node's local view. Therefore, differently from clock synchronization protocols for small scale and static distributed systems, here, each node synchronizes regularly with only the neighbors in its local view and not with the whole system. An evaluation of the convergence speed and the synchronization error of the coupled-based internal clock synchronization algorithm has been carried out, showing how convergence time and the synchronization error depends on the coupling factor and the local view size. Moreover, the variation of the synchronization error with respect to churn and the impact of a sudden variation of the number of nodes have been analyzed to show the stability of the algorithm. In all these contexts, the algorithm shows nice performance and very good self-organizing properties. Finally, we showed how the assumption on the existence of a uniform peer-sampling service is instrumental for the good behavior of the algorithm and how, in system models where network delays are unbounded, a mean-based convergence function reaches a lower synchronization error than median-based convergence functions exploiting the number of averaged clock values.
Efficient Algorithms for Global Snapshots in Large Distributed Systems
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Existing algorithms for global snapshots in distributed systems are not scalable when the underlying topology is complete. There are primarily two classes of existing algorithms for computing a global snapshot. Algorithms in the first class use control messages of size 0(1) but require O(N) space and O(N) messages per processor in a network with JV processors. Algorithms in the second class use control messages (such as rotating tokens with vector counter method) of size O(N), use multiple control messages per channel, or require recording of message history. As a result, algorithms in both of these classes are not efficient in large systems when the logical topology of the communication layer such as MPI is complete. In this paper, we propose three scalable algorithms for global snapshots: a grid-based, a tree-based, and a centralized algorithm. The grid-based algorithm uses O(N) space but only O(¿(N)) messages per processor each of size O(¿(N)). The tree-based and centralized algorithms use only O(1) size messages. The tree-based algorithm requires O(1) space and O(log N log(W/N)) messages per processor where W is the total number of messages in transit. The centralized algorithm requires O(1) space and O(log(W/N)) messages per processor. We also have a matching lower bound for this problem. We also present hybrid of centralized and tree-based algorithms that allow trade-off between the decentralization and the message complexity. Our algorithms have applications in checkpointing, detecting stable predicates, and implementing synchronizers.
PowerPack: Energy Profiling and Analysis of High-Performance Systems and Applications
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Energy efficiency is a major concern in modern high-performance computing system design. In the past few years, there has been mounting evidence that power usage limits system scale and computing density, and thus, ultimately system performance. However, despite the impact of power and energy on the computer systems community, few studies provide insight to where and how power is consumed on high-performance systems and applications. In previous work, we designed a framework called PowerPack that was the first tool to isolate the power consumption of devices including disks, memory, NICs, and processors in a high-performance cluster and correlate these measurements to application functions. In this work, we extend our framework to support systems with multicore, multiprocessor-based nodes, and then provide in-depth analyses of the energy consumption of parallel applications on clusters of these systems. These analyses include the impacts of chip multiprocessing on power and energy efficiency, and its interaction with application executions. In addition, we use PowerPack to study the power dynamics and energy efficiencies of dynamic voltage and frequency scaling (DVFS) techniques on clusters. Our experiments reveal conclusively how intelligent DVFS scheduling can enhance system energy efficiency while maintaining performance.
Highly Available Intrusion-Tolerant Services with Proactive-Reactive Recovery
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In the past, some research has been done on how to use proactive recovery to build intrusion-tolerant replicated systems that are resilient to any number of faults, as long as recoveries are faster than an upper bound on fault production assumed at system deployment time. In this paper, we propose a complementary approach that enhances proactive recovery with additional reactive mechanisms giving correct replicas the capability of recovering other replicas that are detected or suspected of being compromised. One key feature of our proactive-reactive recovery approach is that, despite recoveries, it guarantees the availability of a minimum number of system replicas necessary to sustain correct operation of the system. We design a proactive-reactive recovery service based on a hybrid distributed system model and show, as a case study, how this service can effectively be used to increase the resilience of an intrusion-tolerant firewall adequate for the protection of critical infrastructures.
A Synchronous Scheduling Service for Distributed Real-Time Java
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Current trends in real-time systems identify Java as a new alternative to develop both centralized and distributed real-time systems. Many efforts have been devoted to develop the Real-Time Specification for Java (RTSJ), and there is substantial ongoing activity to produce a straightforward and valuable Distributed Real-Time Specification for Java (DRTSJ). The current paper provides a contribution to this latter activity defining, from different angles, a synchronous scheduling service aligned with principles of some popular real-time architectures. This service orchestrates the system in such a way that it provides end-to-end guarantees in the distributed transactions, guaranteeing their timely execution across the network and nodes. The service is described from two points of view: the system one, characterizing a portable model; and the programmer one, defining a distributed object-oriented implementation of a model based on Real-Time Remote Method Invocation (RTRMI). Finally, it also presents results of an implementation carried out to judge the efficiency of the service, offering a preliminary predictability and performance assessment of a distributed real-time Java technology.
Scheduling Multisource Divisible Loads on Arbitrary Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Scheduling multisource divisible loads is a challenging task as different sources should cooperate and share their computing power with others to balance their loads and minimize total computational time. In this study, we attempt to address a generalized divisible load scheduling problem for handling loads from multiple sources on arbitrary networks. This problem is all the more challenging as 1) the topology is arbitrary, 2) in such networks, it is difficult to decide from which source and which route a processing node should receive loads, and 3) processing nodes must be allocated to different sources when they become available. We study two distinct cases of interest, static case and dynamic case, and propose two novel strategies, referred to as static scheduling strategy (SSS) and dynamic scheduling strategy (DSS), respectively. Both strategies work in an iterative fashion. In each iteration, they will use a novel graph partitioning (GP) scheme to partition the network such that each source in the network gains a portion of network resources and then these sources cooperate to process their loads. We analyze the performance of DSS using queuing theory and derive upper bounds on a load's average waiting time and a source's average queue length. We use simulation to verify the usefulness and effectiveness of SSS and DSS. Our findings reveal an interesting ¿load insensitive¿ propertyof SSS and also verify the theoretical upper bound of average queue length at each source in the dynamic case.
Reputation-Based Resource Allocation in P2P Systems of Rational Users
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we study p2p systems, where peers have to share their available resources between their own and other peers' needs. One such example is a system of peers who use their capacity-limited access links both for their upstream and downstream connections. In the selfish approach, each peer would like to exploit the full capacity of his access link only for his downloads. However, if all peers acted selfishly, the system would collapse. In order to motivate peers to cooperate, we propose a distributed reputation-based system according to which peers earn reputation analogous to their contributions. In this way, each peer has to trade off the capacity he will dedicate for uploading in order to increase his reputation and therefore his revenue and the capacity he will dedicate for his downloads. All peers act rationally, trying to maximize their utility. Our proposed policies lead rational peers to cooperation while promoting fairness, as peers receive resources in proportion to their contributions. Our policies outperform existing work in this area in which the slowest link becomes the bottleneck of a heterogeneous system of different link capacity peers. On the contrary, no such bottleneck appears when our policies are used, improving the performance of the system. Finally, we apply our reputation-based approach in a BitTorrent-like file sharing system and we highlight the potential performance gains.
Privacy-Conscious Location-Based Queries in Mobile Environments
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In location-based services, users with location-aware mobile devices are able to make queries about their surroundings anywhere and at any time. While this ubiquitous computing paradigm brings great convenience for information access, it also raises concerns over potential intrusion into user location privacy. To protect location privacy, one typical approach is to cloak user locations into spatial regions based on user-specified privacy requirements, and to transform location-based queries into region-based queries. In this paper, we identify and address three new issues concerning this location cloaking approach. First, we study the representation of cloaking regions and show that a circular region generally leads to a small result size for region-based queries. Second, we develop a mobility-aware location cloaking technique to resist trace analysis attacks. Two cloaking algorithms, namely MaxAccu_Cloak and MinComm_Cloak, are designed based on different performance objectives. Finally, we develop an efficient polynomial algorithm for evaluating circular-region-based kNN queries. Two query processing modes, namely bulk and progressive, are presented to return query results either all at once or in an incremental manner. Experimental results show that our proposed mobility-aware cloaking algorithms significantly improve the quality of location cloaking in terms of an entropy measure without compromising much on query latency or communication cost. Moreover, the progressive query processing mode achieves a shorter response time than the bulk mode by parallelizing the query evaluation and result transmission.
Minimizing Delay and Maximizing Lifetime for Wireless Sensor Networks With Anycast
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we are interested in minimizing the delay and maximizing the lifetime of event-driven wireless sensor networks for which events occur infrequently. In such systems, most of the energy is consumed when the radios are on, waiting for a packet to arrive. Sleep-wake scheduling is an effective mechanism to prolong the lifetime of these energy-constrained wireless sensor networks. However, sleep-wake scheduling could result in substantial delays because a transmitting node needs to wait for its next-hop relay node to wake up. An interesting line of work attempts to reduce these delays by developing ¿anycast¿-based packet forwarding schemes, where each node opportunistically forwards a packet to the first neighboring node that wakes up among multiple candidate nodes. In this paper, we first study how to optimize the anycast forwarding schemes for minimizing the expected packet-delivery delays from the sensor nodes to the sink. Based on this result, we then provide a solution to the joint control problem of how to optimally control the system parameters of the sleep-wake scheduling protocol and the anycast packet-forwarding protocol to maximize the network lifetime, subject to a constraint on the expected end-to-end packet-delivery delay. Our numerical results indicate that the proposed solution can outperform prior heuristic solutions in the literature, especially under practical scenarios where there are obstructions, e.g., a lake or a mountain, in the coverage area of the wireless sensor network.
Fast Algorithms for Resource Allocation in Wireless Cellular Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We consider a scheduled orthogonal frequency division multiplexed (OFDM) wireless cellular network where the channels from the base-station to the $n$ mobile users undergo flat fading. Spectral resources are to be divided among the users in order to maximize total user utility. We show that this problem can be cast as a nonlinear convex optimization problem, and describe an $O(n)$ algorithm to solve it. Computational experiments show that the algorithm typically converges in around 25 iterations, where each iteration has a cost that is $O(n)$, with a modest constant. When the algorithm starts from an initial resource allocation that is close to optimal, convergence typically takes even fewer iterations. Thus, the algorithm can efficiently track the optimal resource allocation as the channel conditions change due to fading. We also show how our techniques can be extended to solve resource allocation problems that arise in wideband networks with frequency selective fading and when the utility of a user is also a function of the resource allocations in the past.
Integration of False Data Detection With Data Aggregation and Confidential Transmission in Wireless Sensor Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In wireless sensor networks, compromised sensor nodes can inject false data during both data aggregation and data forwarding. The existing false data detection techniques consider false data injections during data forwarding only and do not allow any change on the data by data aggregation. However, this paper presents a data aggregation and authentication protocol, called DAA, to integrate false data detection with data aggregation and confidentiality. To support data aggregation along with false data detection, the monitoring nodes of every data aggregator also conduct data aggregation and compute the corresponding small-size message authentication codes for data verification at their pairmates. To support confidential data transmission, the sensor nodes between two consecutive data aggregators verify the data integrity on the encrypted data rather than the plain data. Performance analysis shows that DAA detects any false data injected by up to $T$ compromised nodes, and that the detected false data are not forwarded beyond the next data aggregator on the path. Despite that false data detection and data confidentiality increase the communication overhead, simulation results show that DAA can still reduce the amount of transmitted data by up to 60% with the help of data aggregation and early detection of false data.
Toward Practical Opportunistic Routing With Intra-Session Network Coding for Mesh Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
We consider opportunistic routing in wireless mesh networks. We exploit the inherent diversity of the broadcast nature of wireless by making use of multipath routing. We present a novel optimization framework for opportunistic routing based on network utility maximization (NUM) that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. All previous work on NUM assumed unicast transmissions; however, the wireless medium is by its nature broadcast and a transmission will be received by multiple nodes. The structure of our design is fundamentally different; this is due to the fact that our link rate constraints are defined per broadcast region instead of links in isolation. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. Optimal MAC scheduling is difficult to implement, and we use 802.11-like random scheduling rather than optimal in our comparisons. Under random scheduling, our protocol becomes fully decentralized (we assume ideal signaling). The use of network coding introduces additional constraints on scheduling, and we propose a novel scheme to avoid starvation. We simulate realistic topologies and show that we can achieve 20%-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).
Provisioning of Deadline-Driven Requests With Flexible Transmission Rates in WDM Mesh Networks
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
With the increasing diversity of applications supported over optical networks, new service guarantees must be offered to network customers. Among the emerging data-intensive applications are those which require their data to be transferred before a predefined deadline. We call these deadline-driven requests (DDRs). In such applications, data-transfer finish time (which must be accomplished before the deadline) is the key service guarantee that the customer wants. In fact, the amount of bandwidth allocated to transfer a request is not a concern for the customer as long as its service deadline is met. Hence, the service provider can choose the bandwidth (transmission rate) to provision the request. In this case, even though DDRs impose a deadline constraint, they provide scheduling flexibility for the service provider since it can choose the transmission rate while achieving two objectives: 1) satisfying the guaranteed deadline; and 2) optimizing the network's resource utilization. We investigate the problem of provisioning DDRs with flexible transmission rates in wavelength-division multiplexing (WDM) mesh networks, although this approach is generalizable to other networks also. We investigate several (fixed and adaptive to network state) bandwidth-allocation policies and study the benefit of allowing dynamic bandwidth adjustment, which is found to generally improve network performance. We show that the performance of the bandwidth-allocation algorithms depends on the DDR traffic distribution and on the node architecture and its parameters. In addition, we develop a mathematical formulation for our problem as a mixed integer linear program (MILP), which allows choosing flexible transmission rates and provides a lower bound for our provisioning algorithms.
Inside the Permutation-Scanning Worms: Propagation Modeling and Analysis
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In recent years, both sophistication and damage potential of Internet worms have increased tremendously. To understand their threat, we need to look into their payload for signatures as well as propagation pattern for Internet-scale behavior. An accurate analytical propagation model allows us to comprehensively study how a worm propagates under various conditions, which is often computationally too intensive for simulations. More importantly, it gives us an insight into the impact of each worm/network parameter on the propagation of the worm. Traditionally, most modeling work in this area concentrates on the relatively simple random-scanning worms. However, modeling the permutation-scanning worms, a class of worms that are fast yet stealthy, has been a challenge to date. This paper proposes a mathematical model that precisely characterizes the propagation patterns of the general permutation-scanning worms. The analytical framework captures the interactions among all infected hosts by a series of interdependent differential equations, which are then integrated into closed-form solutions that together present the overall worm behavior. We use the model to study how each worm/network parameter affects the worm propagation. We also investigate the impact of dynamic network conditions on the correctness of the model.
Joint Sink Mobility and Routing to Maximize the Lifetime of Wireless Sensor Networks: The Case of Constrained Mobility
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
The longevity of wireless sensor networks (WSNs) is a major issue that impacts the application of such networks. While communication protocols are striving to save energy by acting on sensor nodes, recent results show that network lifetime can be prolonged by further involving sink mobility. As most proposals give their evidence of lifetime improvement through either (small-scale) field tests or numerical simulations on rather arbitrary cases, a theoretical understanding of the reason for this improvement and the tractability of the joint optimization problem is still missing. In this paper, we build a framework for investigating the joint sink mobility and routing problem by constraining the sink to a finite number of locations. We formally prove the NP-hardness of the problem. We also investigate the induced subproblems. In particular, we develop an efficient primal-dual algorithm to solve the subproblem involving a single sink, then we generalize this algorithm to approximate the original problem involving multiple sinks. Finally, we apply the algorithm to a set of typical topological graphs; the results demonstrate the benefit of involving sink mobility, and they also suggest the desirable moving traces of a sink.
Equilibrium of Heterogeneous Congestion Control: Optimality and Stability
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
When heterogeneous congestion control protocols that react to different pricing signals share the same network, the current theory based on utility maximization fails to predict the network behavior. The pricing signals can be different types of signals such as packet loss, queueing delay, etc, or different values of the same type of signal such as different ECN marking values based on the same actual link congestion level. Unlike in a homogeneous network, the bandwidth allocation now depends on router parameters and flow arrival patterns. It can be non-unique, suboptimal and unstable. In Tang (“Equilibrium of heterogeneous congestion control: Existence and uniqueness,” IEEE/ACM Trans. Netw., vol. 15, no. 4, pp. 824–837, Aug. 2007), existence and uniqueness of equilibrium of heterogeneous protocols are investigated. This paper extends the study with two objectives: analyzing the optimality and stability of such networks and designing control schemes to improve those properties. First, we demonstrate the intricate behavior of a heterogeneous network through simulations and present a framework to help understand its equilibrium properties. Second, we propose a simple source-based algorithm to decouple bandwidth allocation from router parameters and flow arrival patterns by only updating a linear parameter in the sources' algorithms on a slow timescale. It steers a network to the unique optimal equilibrium. The scheme can be deployed incrementally as the existing protocol needs no change and only new protocols need to adopt the slow timescale adaptation.
Rate Control With Pairwise Intersession Network Coding
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
In this paper, we develop a distributed rate-control algorithm for networks with multiple unicast sessions when network coding is allowed across different sessions. Building on recent flow-based characterization of pairwise intersession network coding, the corresponding optimal rate-control problem is formulated as a convex optimization problem. The formulation exploits pairwise coding possibilities between any pair of sessions, where any coded symbol is formed by coding over at most two original symbols. The objective function is the sum of the utilities based on the rates supported by each unicast session. Working on the Lagrangian of the formulated problem, a distributed algorithm is developed with little coordination among intermediate nodes. Each unicast session has the freedom to choose its own utility function. The only information exchange required by the source is the weighted sum of the queue length of each link, which can be piggybacked to the acknowledgment messages. In addition to the optimal rate-control algorithm, we propose a decentralized pairwise random coding scheme that decouples the decision of coding from that of rate control, which further enhances the distributiveness of the proposed scheme. The convergence of the rate-control algorithm is proven analytically and verified by extensive simulations. Simulation results also demonstrate the advantage of the proposed algorithm over the state-of-the-art in terms of both throughput and fairness.
Distributed Algorithms for Minimum Cost Multicast With Network Coding
0
View Icon   Download Abstract   Download Project   Add to My Project

Abstract
Network coding techniques are used to find the minimum-cost transmission scheme for multicast sessions with or without elastic rate demand. It is shown that in wireline networks, solving for the optimal coding subgraphs in network coding is equivalent to finding the optimal routing scheme in a multicommodity flow problem. A set of node-based distributed gradient projection algorithms are designed to jointly implement congestion control/routing at the source node and ¿virtual¿ routing at intermediate nodes. The analytical framework and distributed algorithms are further extended to interference-limited wireless networks where link capacities are functions of the signal-to-interference-plus-noise ratio (SINR). To achieve minimum-cost multicast in this setting, the transmission powers of links must be jointly optimized with coding subgraphs and multicast input rates. Node-based power allocation and power control algorithms are developed for the power optimization. The power algorithms, when iterated in conjunction with the congestion control and routing algorithms, converge to the jointly optimal multicast configuration. The scaling matrices required in the gradient projection algorithms are explicitly derived and are shown to guarantee fast convergence to the optimum from any initial condition.
   
 
© olympods.com
Developed by: Olympods