Federated Learning (FL) provides a flexible distributed platform where numerous clients with high data and system heterogeneity can collaborate to learn a model. While previous research has shown that FL can handle diverse data, it often completely assumes idealized conditions. In practice, real-world factors make it hard to predict or design individual client participation. This complexity results in an unknown participation pattern - arbitrary client participation (ACP). Hence, the key open problem is to understand the impact of client participation and develop a lightweight mechanism to support ACP in FL. In this paper, we first empirically investigate the client participation's influence in FL, revealing that FL algorithms are adversely impacted by ACP. To alleviate the impact, we propose a lightweight solution, Federated Average with Snapshot (FAST), that supports almost ACP for FL and can seamlessly integrate with other classic FL algorithms. Specifically, FAST enforces clients to take a snapshot once in a while and facilitates ACP for the majority of training processes. We prove that the convergence rates of FAST in non-convex and strongly-convex cases match those under ideal client participation. Furthermore, we empirically introduce an adaptive strategy to dynamically configure the snapshot frequency, tailored to accommodate diverse FL systems. Extensive experiments show that FAST significantly improves performance under ACP and high data heterogeneity.

Dataset obfuscation refers to techniques in which random noise is added to the entries of a given dataset, prior to its public release, to protect against leakage of private information. In this work, dataset obfuscation under two objectives is considered: i) rank-preservation: to preserve the row ordering in the obfuscated dataset induced by a given rank function, and ii) anonymity: to protect user anonymity under fingerprinting attacks. The first objective, rank-preservation, is of interest in applications such as the design of search engines and recommendation systems, feature matching, and social network analysis. Fingerprinting attacks, considered in evaluating the anonymity objective, are privacy attacks where an attacker constructs a fingerprint of a victim based on its observed activities, such as online web activities, and compares this fingerprint with information extracted from a publicly released obfuscated dataset to identify the victim. By evaluating the performance limits of a class of obfuscation mechanisms over asymptotically large datasets, a fundamental trade-off is quantified between rank-preservation and user anonymity. Single-letter obfuscation mechanisms are considered, where each entry in the dataset is perturbed by independent noise, and their fundamental performance limits are characterized by leveraging large deviation techniques. The optimal obfuscating test-channel, optimizing the privacy-utility tradeoff, is characterized in the form of a convex optimization problem which can be solved efficiently. Numerical simulations of various scenarios are provided to verify the theoretical derivations.

Distributed estimation in the context of sensor networks is considered, where distributed agents are given a set of sensor measurements, and are tasked with estimating a target variable. A subset of sensors are assumed to be faulty. The objective is to minimize i) the mean squared estimation error at each node (accuracy objective), and ii) the mean squared distance between the estimates at each pair of nodes (consensus objective). It is shown that there is an inherent tradeoff between the former and latter objectives. Assuming a general stochastic model, the sensor fusion algorithm optimizing this tradeoff is characterized through a computable optimization problem, and a Cramér-Rao type lower bound for the achievable accuracy-consensus loss is obtained. Finding the optimal sensor fusion algorithm is computationally complex. To address this, a general class of low-complexity Brooks-Iyengar Algorithms are introduced, and their performance, in terms of accuracy and consensus objectives, is compared to that of optimal linear estimators through case study simulations of various scenarios.

Federated learning has gained significant attention as a privacy-preserving approach for training machine learning models across decentralized devices. However, this distributed learning paradigm is susceptible to adversarial attacks, particularly model poisoning attacks, where adversaries inject malicious model updates to compromise the integrity of the global model. In this paper, we investigate the impact of randomness on model poisoning attacks in federated networks, where the server employs two aggregation rules, Krum and Trimmed Mean, randomly in each federated round. We present three distinct adversaries: one targeting Krum throughout the entire learning process, another targeting Trimmed Mean entirely, and a third adversary employing a randomized strategy between Krum and Trimmed Mean for each round. Our objective is to evaluate their performance in reducing the overall accuracy of the federated network. We propose novel techniques to craft poisoned models and explore the efficacy of these attacks by exploiting the aggregation rules. We evaluated our proposed methods on Fashion-MNIST dataset. The experiments reveal the robustness of the federated network against the proposed adversarial scenarios, contributing to a better understanding of the vulnerabilities and defenses in federated learning systems.

This talk covers a detailed direction for developing a Roadmap in the discipline of Computer Science for the next Decade. Over the past two decades, the science of computing has changed drastically both in the context of theory and applications. Dr. Iyengar is going to cover his experiences of four decades in areas of Sensor Fusion, Quantum Computing and theory of Machine Learning and AI for various applications. The duration of the talk is 1 hour and there will be time for discussions after the seminar.

The point-of-interest (POI) recommender exploits check-in information from location-based social networks (LBSNs) to recommend POIs that match user preferences. The preferences of users vary with region/locality, consumption type, and co-consumers. For instance, the places preferred for friends may be different from the places preferred for family, and the places preferred in one locality may be different from the places in another locality. These dynamic preferences can be crucial for an efficient recommender system. A locality consists of different preference trends, such as “known for food and recreational sites.” In real-world, different sets of users might be attracted toward different preference trends, and some users' preferences might overlap across multiple preference sets. Hence, an efficient aggregation of locality preferences is essential for the recommender systems. Many existing studies simply group items by their category and use simple collaborative filtering (CF) for recommendations, however, such techniques cannot efficiently handle the aggregated locality preferences. We propose a hierarchical recommendation model termed Hierarchical Contextual Location Recommendation System (HiRecS) that formulates users' preferences as a hierarchical structure and models the locality trend using aggregated hierarchy. For a locality, the root of hierarchy contains preferred k items from a set of visitors, and the subsequent levels contain preference wise subsets of those items. We also present a hierarchy aggregation technique to aggregate the hierarchical preferences from a similar set of users. The aggregated hierarchy is then contextually exploited for POI sequence recommendation. The core contributions of this article are: 1) it formulates the locality trends as hierarchical structures, presents a hierarchy aggregation technique, and models the personalized POI preferences with the aggregated hierarchy; 2) it exploits the aggregated popular trends to generate contextual POI sequence recommendation; and 3) it extensively evaluates the proposed model with two real-world data sets and demonstrates a significant performance gain of 0.006-5.91 on diversity metrics, 0.0349-17.51 on displacement metrics, and 0.114-0.289 on normalized discounted cumulative gain (NDCG) metrics, when compared to several baselines and relevant studies.

Online interactive recommender systems strive to promptly suggest users appropriate items (e.g., movies and news articles) according to the current context including both user and item content information. Such contextual information is often unavailable in practice, where only the users' interaction data on items can be utilized by recommender systems. The lack of interaction records, especially for new users and items, inflames the performance of recommendation further. To address these issues, both collaborative filtering, one of the most popular recommendation techniques relying on the interaction data only, and bandit mechanisms, capable of achieving the balance between exploitation and exploration, are adopted into an online interactive recommendation setting assuming independent items (i.e., arms). This assumption rarely holds in reality, since the real-world items tend to be correlated with each other. In this paper, we study online interactive collaborative filtering problems by considering the dependencies among items. We explicitly formulate item dependencies as the clusters of arms in the bandit setting, where the arms within a single cluster share the similar latent topics. In light of topic modeling techniques, we come up with a novel generative model to generate the items from their underlying topics. Furthermore, an efficient particle-learning based online algorithm is developed for inferring both latent parameters and states of our model by taking advantage of the fully adaptive inference strategy of particle learning techniques. Additionally, our inferred model can be naturally integrated with existing multi-armed selection strategies in an interactive collaborative filtering setting. Empirical studies on two real-world applications, online recommendations on movies and news, demonstrate both the effectiveness and efficiency of our proposed approach.

Mobile crowdsensing, an emerging sensing paradigm, promotes scalability and reduction in the deployment of specialized sensing devices for large-scale data collection in a decentralized fashion. However, its open structure allows malicious entities to interrupt a system by reporting fabricated or erroneous data, making trust evaluation a highly important issue in mobile crowdsensing applications. The goal of this research is to show that an introduction of a reputation system in the process of correlated sensor-based data fusion will enhance the overall quality of the sensed data. To do so, we design a reputation-aware data fusion mechanism to ensure data integrity. We use Gompertz function in our reputation method to rate the trustworthiness of the data reported by a crowdsensing participant. The proposed mechanism, on one hand, is capable of defending a data corruption attack and identifying malicious or honest participants based on their reported data in real time. On the other hand, this mechanism yields more accurate data prediction in terms of lower data prediction error. We conducted experiments using two different real-world datasets. We compare our correlated data and reputation-aware data prediction (CDR) method with other popular methods, and the results show that our effective method incurs lower data prediction error.

An efficient delivery of IT services for increasingly complex IT environments demands an intelligent automated solution for resolving existing and potential issues. An automation recommender system, promptly suggesting the most proper scripted resolution to an arriving IT incident ticket, would play a significant role in IT automation services. Hence, developing a comprehensive framework supporting becomes imperative for continuous improvement of automation recommendation.In this paper, we first identify the challenges of IT services followed by a discussion on AISTAR (an intelligent system for online IT ticket automation recommendation) designed and developed to provide them. Specifically, we define and formalize automation recommendation procedure as a multi-armed bandit problem with dependent arms, which is capable of achieving the optimal tradeoff between exploitation of the system for the best automation recommendation and exploration of automation execution information for future recommendation. Two novel multi-armed bandit models are proposed and integrated to handle the aforementioned challenges in IT automation services. Empirical studies on a large ticket dataset from IBM Global Services demonstrate both the effectiveness and efficiency of our intelligent integrated system. AISTAR is earmarked for Cognitive Event Automation for IBM Service delivery.

The Point-of-Interest (POI) preference of a user varies by locality, item type, and the co-visitors, e.g., user1 and user2 can have closest preference on food items but not on historic sites, etc. A locality can have different preference trends (e.g., popular for food, recreation, etc.) and a user's preference can span across multiple such trends. A good recommender should also exploit the aggregated locality preference trends. Most of the existing studies group items by category or global user preferences which might not be relevant for locality-based aggregated preferences. We propose HiCaPS (Hierarchical Contextual POI Sequence Recommender) that formulates user preferences as hierarchical structure and presents a hierarchy aggregation technique for POI recommendation. The top level of locality hierarchy contains preferred k items from a set of users and the subsequent levels contain preference wise subsets. The core contributions of this paper are: (i) it formulates user preferences as a preference hierarchy, presents a technique to aggregate preference hierarchies of a similar users, and models the target users' preference in terms of aggregated trend in a locality, (ii) it contextually exploits the aggregated trend to generate personalized POI sequences, and (iii) it extensively evaluates the proposed model with two real-world datasets and demonstrates performance gain (0.03 - 0.28 on pair F-score, 0.006 - 5.91 on diversity, 0.0349 - 17.51 on displacement, and 0.114 - 0.289 on NDCG) over baseline models.

Massive amount of queries with location data from mobile sensors, connected vehicles, and IoT devices make the Location-Based Services (LBS) pervasive. LBS service providers can provide valuable services for mobile users ranging from POI (Point-Of-Interest) discovery to local search, etc. However, user personal privacy issues mainly come from the fact that users need to send their coordinates and query interests or features to the service provider which may compromise their privacy. In this paper, we focus on a new user privacy problem from a historical query point of view, and consider query search features as new tools for attackers to possibly locate users in a specific location and/or region. We introduce a new query-feature-based inference attack with an illustration on a real-world data set. We define Indistinguishable Feature-Inferred Location/Grids and Probabilistic k-Effectiveness to provide a strong property with differential privacy mannered guarantee. To achieve the privacy property, we design novel randomized algorithms to countermeasure the privacy attack. Based on entropy and recourse cost related metrics, simulations and analysis are performed to show the effectiveness and efficiency of our approaches.

The location-based social networks (LBSN) (e.g., Facebook, etc.) have been explored in the past decade for Point-of-Interest (POI) recommendation. Many of the existing systems focus on recommending a single location or a list which might not be contextually coherent. In this paper, we propose a model termed CLoSe (Contextualized Location Sequence Recommender) that generates contextually coherent POI sequences relevant to user preferences. The POI sequence recommenders are helpful in many day-to-day activities, for e.g., itinerary planning, etc. To the best of our knowledge, this paper is the first to formulate contextual POI sequence recommendation by exploiting Recurrent Neural Network (RNN). We incorporate check-in contexts to the hidden layer and global context to the hidden and output layers of RNN. We also demonstrate the efficiency of extended Long-short term memory (LSTM) in sequence generation. The main contributions of this paper are: (i) it exploits multi-context, personalized user preferences to formulate contextual POI sequence generation, (ii) it presents contextual extensions of RNN and LSTM that incorporate different contexts applicable to a POI and POI sequence, and (iii) it demonstrates significant performance gain of proposed model on pair-F1 and NDCG metrics when evaluated with two real-world datasets.

The increasing complexity of IT environments urgently requires the use of analytical approaches and automated problem resolution for more efficient delivery of IT services. In this paper, we model the automation recommendation procedure of IT automation services as a contextual bandit problem with dependent arms, where the arms are in the form of hierarchies. Intuitively, different automations in IT automation services, designed to automatically solve the corresponding ticket problems, can be organized into a hierarchy by domain experts according to the types of ticket problems. We introduce a novel hierarchical multi-armed bandit algorithms leveraging the hierarchies, which can match the coarse-to-fine feature space of arms. Empirical experiments on a real large-scale ticket dataset have demonstrated substantial improvements over the conventional bandit algorithms. In addition, a case study of dealing with the cold-start problem is conducted to clearly show the merits of our proposed algorithms.

In Location-Based Services (LBS), users are required to disclose their precise location information to query a service provider. An untrusted service provider can abuse those queries to infer sensitive information on a user through spatio-temporal and historical data analyses. Depicting the drawbacks of existing privacy-preserving approaches in LBS, we propose a user-centric obfuscation approach, called KLAP, based on the three fundamental obfuscation requirements: k number of locations, l-diversity, and privacy area preservation. Considering user's sensitivity to different locations and utilizing Real-Time Traffic Information (RTTI), KLAP generates a convex Concealing Region (CR) to hide user's location such that the locations, forming the CR, resemble similar sensitivity and are resilient against a wide range of inferences in spatio-temporal domain. For the first time, a novel CR pruning technique is proposed to significantly improve the delay between successive CR submissions. We carry out an experiment with a real dataset to show its effectiveness for sporadic, frequent, and continuous service use cases.

The Location-Based Social Networks (LBSN) (e.g., Facebook, etc.) have many attributes (e.g., ratings, reviews, etc.) that play a crucial role for the Point-of-Interest (POI) recommendations. Unlike ratings, the reviews can help users to elaborate their consumption experience in terms of relevant factors of interest (aspects). Though some of the existing systems have exploited user reviews, most of them are less transparent and non-interpretable (as they conceal the reason behind recommendation). These reasons have motivated us towards explainable and interpretable recommendation. To the best of our knowledge, only a few of the researchers have exploited user reviews to incorporate the sentiment and opinions on different aspects for personalized and explainable POI recommendation. This paper proposes a model termed as ReEL (Review aware Explanation of Location Recommendation) which models the review-aspect correlation by exploiting deep neural network, formulates user-aspect bipartite relation as a bipartite graph, and models the explainable recommendation by using dense subgraph extraction and ranking-based techniques. The major contributions of this paper are: (i) it models users and POIs using the aspects posted on user reviews, and it provisions incorporation of multiple contexts (e.g., categorical, spatial, etc.) in POI recommendation, (ii) it formulates preference of users' on aspects as a bipartite relation, represents it as a location-aspect bipartite graph, and models the explainable recommendation with the notion of ordered dense subgraph extraction using bipartite cores, shingles, and ranking-based techniques, and (iii) it extensively evaluates the proposed models using three real-world datasets and demonstrates an improvement of 5.8% to 29.5% on F-score metric, when compared to the relevant studies.

With recent widespread usage of state-of-the-art technology (e.g., various mobile devices), environmental sensing is getting popular. The sensors used for sensing are small and due to the mobility they become more error-prone, which results in data corruption or loss from sensor. Therefore, cleaning of the sensed data is of high importance to recover the lost or corrupted data. In this paper, we propose a novel data cleaning mechanism to ensure better accuracy in environmental sensing applications. Based on the sensed data and the context relationship of each sensor, we update the credibility (or alternatively reliability) of the sensed data. We consider mobility pattern of the mobile sensor nodes while selecting the candidate sensor nodes for data stream cleaning. Through simulations, we evaluate the performance of our proposed approach. We compare our proposed sensor data stream cleaning approach with Influence Mean Cleaning (IMC) (a recent algorithm in data stream cleaning) and Mean-based cleaning. Simulation results show up to 24% reduction in root mean square error (RMSE) over IMC and up to 30% over Mean-based cleaning.

Crowdsourcing services have become one of the most common ways organizations can gather ideas for new products and services from large crowds of consumers by offering monetary rewards depending on the tasks. However, this monetary reward has begun to attract malicious crowds of users who wish to complete the task with minimal effort through collaboration. For instance, a task based on reviews of a product can be degraded when malicious users copy each other with minimal edits of the review, giving a misrepresentation of the true quality of the product. More specifically, we investigate the case where different malicious crowd sizes cooperate on different tasks, known as overlapping groups. Such sophisticated and hard to detect malicious crowds provide unfair evaluations and misleading results to the crowdsourcers. To overcome this type of attack, we propose two methods to point out such groups with high accuracy. The first method detects similar reviews by including a new proposed similarity between review texts and show the results outperform the vectorial similarity measures used in prior works. The second method is based on community detection on networks and exploits the semantic similarity of the reviews. The experiments were conducted on reviews from Ott dataset on Amazon Mechanical Turk.

Power loss minimization plays an important role in the appropriate operation of power networks. Line power loss occurs when the power is transmitted through the lines of a network due to the permittivity of lines medium. Transmission loss may increase the dispatch cost of all of the obtained power flows based on market contracts. Hence, the independent system operators should use loss minimization methods to facilitate the implementation of the contracted power transactions. Loss minimization also will improve the security and stability of power network. In this paper, we present a novel loss minimization scheme based on oblivious network design, referred to as oblivious routing-based power flow method. The method is built on the bottom-up oblivious network routing scheme which offers multiple paths from several sources (generation units) to the specific destinations (electric load demands). Although there is limited information regarding other line flows and the current status of network, the routing scheme mathematically guarantees that the power flow solution is an approximation of the optimal solution with a specific competitiveness ratio. In fact, the Our main focus is on the power flow calculation while optimizing power losses. Compared with the recently developed power flow methods, our approach does not depend on the network topology and its performance for both radial and non-radial networks is accurate. Hence, it is suitable to use the propose approach for large-scale loss minimization while determining the power flows. This paper mainly focuses on the theoretical aspect of the proposed method. As our method is based on a novel concept from computer science discipline, we provide sufficient explanation about the preliminaries of oblivious routing scheme.

The popularity of location-aware mobile devices and the advances of wireless networking have seriously pushed location-based services into the IT market. However, moving users need to report their coordinates to an application service provider to utilize interested services that may compromise user privacy. In this paper, we propose an online personalized scheme for generating anonymity zones to protect users with mobile devices while on the move. We also introduce a strong adversary model, which can conduct inference attacks in the system. Our design combines a geometric transformation algorithm with a dynamic pseudonyms-changing mechanism and user-controlled personalized dummy generation to achieve strong trajectory privacy preservation. Our proposal does not involve any trusted third-party and will not affect the existing LBS system architecture. Simulations are performed to show the effectiveness and efficiency of our approach.

A basic problem in time of arrival (TOA)-based locating systems using narrow-band ultrasound (NBU) is how to improve the location update rate for tracking multiple targets. It is challenging because each ongoing ultrasound (US) signal occupies the channel for a rather long time because the slow propagation speed in air and it is hard to encode information in the narrow-band US. In this paper, we investigate to allow multiple NBU targets to transmit signals concurrently and to determine their locations by signal processing, which is called locating in chorus mode. The key observation is the signal interference characteristics of the concurrently chorusing targets. Based on it, the necessary and sufficient conditions for the receivers to determine the TOAs from multiple concurrently transmitting targets are investigated. However, because NBU cannot encode the target's ID, the detected TOAs are lacking labels of the target ID, causing ambiguities in location estimation. We exploited both historical consistence and self-consistence methods to narrow down the possible IDs of the TOAs and proposed probabilistic particle filter algorithm to disambiguate the motion trajectories of targets based on the targets' motion pattern consistency. A prototype of chorus-mode NBU locating system was developed. Extensive evaluations of both simulations and prototype experiments showed the effectiveness of the proposed theories and algorithms. In the testbed experiment, chorus locating provided 300% refreshing rate improvements compared with exclusive locating method, while the accuracy is still kept.

Mobile applications can be enhanced to a great extent by using the offloading mechanism in an energy efficient manner to the bounty resourceful clouds. Due to the huge demand of smart phones, the issue of providing more processing capability to this resource constraint device is getting more concern now-a-days. In this paper, a method level offloading mechanism has been proposed where no prior image of the mobile device is needed to be transferred to the cloud. The application is partitioned at different points where the migration of the execution thread is performed from mobile device to nearby resourceful cloud to get the best execution performance in optimal energy cost. The mobile can complete the execution after the partitioned thread returns back from the cloud to the device. This mechanism increases scalability as well as performance in the form of faster execution speed of the mobile devices. Moreover, we consider the mobility of the mobile device and propose a solution to find the best cloud instance on the move. To find out which cloud to offload, the communication latency, capacity, and current load at individual clouds are considered to find out the best cloud to offload to ensure better service for the mobile device. The proposed solution has been simulated and compared against CloneCloud in two different simulation scenarios where we show that our method performs superior to CloneCloud.

One of the most important features of the Smart Grid (SG) is real-time self-assessment which may threat that target power system stability. In order to improve robustness of power systems against such attacks, accurate estimation of the power system operation is required and conventional power flow methods should be upgraded. In this paper, we derive minimum variance unbiased estimators (MVUEs) for active power based on the voltage phase at each node of the power system. The state variables are the voltage phases and the received measurement signals are active power measurements. The proposed method is implemented on a four-bus test system. Three scenarios are defined to investigate the effect of covariance matrix topology on the estimation accuracy. The results shows that lower correlation between the noise vector elements leads to a more accurate estimation of power system operation.

The tight integration of mobile devices and apps into our daily routine impacts our approach to health. While existing solutions propose to take advantage of recent developments in mobile and sensor technologies to encourage users to lead healthier lives, we still lack a viable approach that motivates user participation. In this paper we aim to integrate fitness challenges into the daily routine of users, in order to motivate them to participate more frequently. We develop GeoFit, a mobile app that enables users to discover and add novel fitness challenges in their proximity. In addition to achievement badges, GeoFit relies on top-k lists to motivate users to become top performers. Since participation incentives may also raise cheating concerns, GeoFit leverages GPS and accelerometer sensors of the mobile device to verify the authenticity of fitness challenges performed by users. We have implemented and tested GeoFit on Android devices. Our experimental results show that the GeoFit client imposes only little overhead on the user device, while the server side can support hundreds of client interactions per second.

Population density and natural and man-made disasters make public safety a concern of growing importance. In this paper we aim to enable the vision of smart and safe cities by exploiting mobile and social networking technologies to securely and privately extract, model and embed real-time public safety information into quotidian user experiences. We first propose novel approaches to define location- and user-based safety metrics. We evaluate the ability of existing forecasting techniques to predict future safety values. We introduce iSafe, a privacy-preserving algorithm for computing safety snapshots of co-located mobile devices as well as geosocial network users. We present implementation details of iSafe as both an Android application and a browser plugin that visualizes safety levels of visited locations and browsed geosocial venues. We evaluate iSafe using crime and census data from the Miami-Dade (FL) county as well as data we collected from Yelp, a popular geosocial network.

In natural language, there are many gaps between what is stated and what is understood. Speakers and listeners fill in these gaps, presumably from some life experience, but no one knows how to get this experiential data into a computer. As a first step, we have created a methodology and software interface for collecting commonsense data about simple experiences. This work is intended to form the basis of a new resource for natural language processing.

With the rapid development of next generation sequencing technology, the amount of biological sequence data of the cancer genome increases exponentially, which calls for efficient and effective algorithms that may identify patterns hidden underneath the raw data that may distinguish cancer Achilles' heels. From a signal processing point of view, biological units of information, including DNA and protein sequences, have been viewed as one-dimensional signals. Therefore, researchers have been applying signal processing techniques to mine the potentially significant patterns within these sequences. More specifically, in recent years, wavelet transforms have become an important mathematical analysis tool, with a wide and ever increasing range of applications. The versatility of wavelet analytic techniques has forged new interdisciplinary bounds by offering common solutions to apparently diverse problems and providing a new unifying perspective on problems of cancer genome research. In this paper, we provide a survey of how wavelet analysis has been applied to cancer bioinformatics questions. Specifically, we discuss several approaches of representing the biological sequence data numerically and methods of using wavelet analysis on the numerical sequences.

The optimal data fusion rule for multiple sensor detection systems based on the Bayesian criterion has been derived by Chair and Varshney in 1986. However, most of the following works are focused on how to implement such a fusion rule, since the probability of false alarm and the probability of miss detection are hard to evaluate in practice. Till now, although more and more satisfactory data-fusion implementation schemes are available, most of the cooperative spectrum sensing techniques are based on the simple energy-detection algorithm, which only relies on the energy of the received signal. However, when noise is relatively large or the time-varying characteristics of the signal are conspicuous, the energy-detection spectrum sensing algorithm is more prone to fail. Thus, in this paper, we propose a new adaptive cooperative spectrum sensing scheme, which is based on a novel detection algorithm involving JB (Jarque-Bera) statistic. The ROC (receiver-operating characteristic) curves show that our new cooperative spectrum sensing scheme is more robust than that based on the energy-detection spectrum sensing algorithm. Besides, the performance comparison also implies that the optimal data-fusion rule in our new cooperative spectrum sensing scheme is superior to the commonly adopted “OR” and “AND” rules in the existing literature.

We consider the problem of constructing a single spanning tree for the single-sink buy-at-bulk network design problem for doubling-dimension graphs. We compute a spanning tree to route a set of demands along a graph G to or from a designated sink node. The demands could be aggregated at (or symmetrically distributed to) intermediate edges where the fusion cost is specified by a nonnegative concave function f. We describe a novel approach for developing an oblivious spanning tree in the sense that it is independent of the number and location of data sources (or demands) and cost function at the edges. We present a deterministic, polynomial-time algorithm for constructing a spanning tree in low doubling-dimension graphs that guarantees a log3D-approximation over the optimal cost, where D is the diameter of the graph G. With a constant fusion-cost function, our spanning tree gives an O(log3D)-approximation for every Steiner tree that includes the sink. We also provide a Ω(log n) lower bound for any oblivious tree in low doubling-dimension graphs. To our knowledge, this is the first paper to propose a single spanning tree solution to the single-sink buy-at-bulk network design problem (as opposed to multiple overlay trees).

Nowadays, there is urgent demand for wireless sensor network applications. In these applications, usually a base station is responsible for monitoring the entire network and collecting information. If emergency happens, it will propagate such information to all other nodes. However, quite often the message source is not a fixed node, since there may be base stations in charge of different regions or events. Therefore, how to propagate information efficiently when message sources vary from time to time is a challenging issue. None of conventional broadcast algorithms can deal with this case efficiently, since the change of message source incurs a huge implementation cost of rebuilding a broadcast tree. To deal with this difficult problem, we make endeavor in studying multiple source broadcast, in which targeted algorithms should be source-independent to serve the practical need. In this paper, we formulate the Minimum-Latency Multisource Broadcast problem. We propose a novel solution using a fixed shared backbone, which is independent of the message sources and can be used repeatedly to reduce the broadcast latency. To the best of our knowledge, our work is deemed the first attempt to design such a multisource broadcast algorithm with a derived theoretical latency upper bound.

This paper studies the optimal inspection of autonomous robots in a complex pipeline system. We solve a 3-D region-guarding problem to suggest the necessary inspection spots. The proposed hierarchical integer linear programming optimization algorithm seeks the fewest spots necessary to cover the entire given 3-D region. Unlike most existing pipeline inspection systems that focus on designing mobility and control of the explore robots, this paper focuses on global planning of the thorough and automatic inspection of a complex environment. We demonstrate the efficacy of the computation framework using a simulated environment, where scanned pipelines and existing leaks, clogs, and deformation can be thoroughly detected by an autonomous prototype robot.

With the advance of scanning devices, 3-d geometric models have been captured and widely used in animation, video, interactive virtual environment design nowadays. Their effective analysis, integration, and retrieval are important research topics in multimedia. This paper studies a geometric modeling problem called 3D region guarding. The 3D region guarding is a well known NP-hard problem; we present an efficient hierarchical integer linear programming (HILP) optimization algorithm to solve it on massive data sets. We show the effectiveness of our algorithm and briefly illustrate its applications in multimedia data processing and computer graphics such as shape analysis and retrieval, and morphing animation.

In this paper, the DTV (digital television) spectrum sensing problem is studied, which plays a key role in the cognitive radio. In contrast to the existing higher-order-statistics (HOS) approach, we propose a novel robust spectrum-sensing method, which is based on the JB (Jarqur-Bera) statistic. In our studies, the existing detector may often not be robust when the sample size is small. Our proposed JB detector is heuristically justified to be superior for the simulated microphone signals as well as the real DTV signals. Moreover, the computational complexity analysis for our proposed new JB detector and the HOS detector is also presented. Ultimately, the normality test and the spectral analysis are provided to justify the advantage of our proposed spectrum sensing method.

In this paper, the DTV (digital television) spectrum sensing problem is studied, which plays a key role in the cognitive radio. In contrast to the existing higher-order-statistics (HOS) approach, we propose a novel robust spectrum-sensing method, which is based on the JB (Jarqur-Bera) statistic. In our new studies, the existing HOS spectrum sensing technique may often not be robust. Our proposed JB-statistic based detector has been justified to be superior for the simulated microphone signals as well as the real DTV signals.

In this paper, we propose a novel blind equalizer which can deal with high-order modulated QAM (quadrature amplitude modulation) signals. This new scheme is based on the signal selection (SS) and the iterative weighted-least-mean-square (IWLMS) algorithm. The incurred additional complexity by the SS scheme is linear with respect to the sample size of the received signal and the IWLMS method is also very efficient. We employ numerous Monte Carlo experiments to compare our proposed blind equalization method with the popular constant modulus algorithm (CMA). The simulation results demonstrate that our proposed scheme is more robust than CMA especially when the QAM modulation order is large.

In this paper, we describe the cognitive radios sharing the spectrum with licensed users and its effects on operational coexistence with unlicensed users. Due to the unlicensed spectrum band growing needs and usage by many IEEE 802.11 protocols, normal wireless radio operation sees high interference leading to high error rates on operational environments. We study the licensed bands and the characteristics of the unlicensed bands in general and more specific to radio characterization of individual radios and cognitive deployment of sensor networks and its effect on lifetime. The cognitive radio signals detection algorithm for this probabilistic model for the unlicensed users, uses a mobility model which takes into account the threshold variable ratio Eb/Noand also calculates the lower-bound of the combined value of secondary user interference for overlapping frequencies with the primary user. By using simulation, we detect the primary user when the radio frequencies are known a priori and compare it when the frequencies are unknown. In our analysis we exploit the similarity measure seen at each sub-channel frequency, which are due to multiple paths of the same reflected signal by maximizing the correlated information of the correlation matrix. For the general case the co-variance matrix for blind source separation, we use ICA de-correlation methods and show that cognitive radio can efficiently identify users in complex situations. The effects of large deployment and cognitive sensor network are studied for a family of 802.15.4 radios adapting to power-aware algorithms.

Identification of a low-level point radioactive source amidst background radiation is achieved by a network of radiation sensors using a two-step approach. Based on measurements from three or more sensors, a geometric difference triangulation method or an N -sensor localization method is used to estimate the location and strength of the source. Then a sequential probability ratio test based on current measurements and estimated parameters is employed to finally decide: (1) the presence of a source with the estimated parameters, or (2) the absence of the source, or (3) the insufficiency of measurements to make a decision. This method achieves specified levels of false alarm and missed detection probabilities, while ensuring a close-to-minimal number of measurements for reaching a decision. This method minimizes the ghost-source problem of current estimation methods, and achieves a lower false alarm rate compared with current detection methods. This method is tested and demonstrated using: (1) simulations, and (2) a test-bed that utilizes the scaling properties of point radioactive sources to emulate high intensity ones that cannot be easily and safely handled in laboratory experiments.

We propose a binary decision fusion rule that reaches a global decision on the presence of a target by integrating local decisions made by multiple sensors. Without requiring a priori probability of target presence, the fusion threshold bounds derived using Chebyshev's inequality ensure a higher hit rate and lower false alarm rate compared to the weighted averages of individual sensors. The Monte Carlo-based simulation results show that the proposed approach significantly improves target detection performance, and can also be used to guide the actual threshold selection in practical sensor network implementation under certain error rate constraints.

Guo and Nixon proposed a feature selection method based on maximizingI(x;Y), the multidimensional mutual information between feature vectorxand class variableY. Because computingI(x;Y) can be difficult in practice, Guo and Nixon proposed an approximation ofI(x;Y) as the criterion for feature selection. We show that Guo and Nixon's criterion originates from approximating the joint probability distributions inI(x;Y) by second-order product distributions. We remark on the limitations of the approximation and discuss computationally attractive alternatives to computeI(x;Y) .

Wideband source localization using acoustic sensor networks has been drawing a lot of research interest recently in wireless communication applications, such as cellular handset localization, global positioning systems (GPS), and land navigation technologies, etc. The maximum-likelihood is the predominant objective which leads to a variety of source localization approaches. However, the appropriate optimization (search) algorithms are still being pursuit by researchers since different aspects about the effectiveness of such algorithms have to be addressed on different circumstances. In this paper, we focus on the two popular source localization methods for wideband acoustic signals, namely the alternating projection (AP) algorithm and the expectation maximization (EM) algorithm. We explore the respective limitations of these two methods and design a new hybrid approach thereupon. Through Monte Carlo simulations, we demonstrate that the trade-off can be achieved between the computational complexity and the localization accuracy using our newly proposed scheme. Moreover, we present the new robustness analysis for the source localization algorithms. We derive the Cramer-Rao lower bound (CRLB) involving the source spectral estimation error and thus prove that the new hybrid algorithm is more efficient than the EM algorithm. By employing the Gaussianity test, we also quantify the statistical mismatch between the actual statistics of the sensor signals and the underlying Gaussian model. We show that the Gaussianity measure can be a reliable robustness figure for source localization.

In this study of wireless sensor networks (WSN) protocols, the application Qos, system, and protocol performance metrics are measured for a large scalable wireless deployment using a typical wireless radio and an energy model. As there are many different types of WSN algorithms, we have categorized it into pro-active, re-active, and query driven information processing. A typical Qos is based on the useful lifetime of sensor nodes, after which reliability of the sensor data cannot be guaranteed and typically, a threshold such as a percentage of the sensor drains out of energy or a minimum through-put of real-time data from the sensor network is expected, which is used to compare the Qos of the routing algorithm. The results from lifetime based Qos, measured in simulation seconds, for the implemented protocols show that with varying sampled data sources for a BE Qos multi-hop deployment and varying percentage of cluster heads in a time- synchronized deployment, the lifetime is based on network size and protocol invariant. However, low sensing ranges result in dense networks, and therefore, it becomes necessary to achieve an efficient medium-access protocol subjected to power constraints. Scalability of sensor network applications are based on energy energy-harvesting techniques in which the various layers of the network inter-operate and extend the system network lifetime, the battery residual power per node, and the application reliability in terms of cross-layer energy savings. In this study, we have extended the lifetime metrics from a constant metrics into a break down of how much percentage of time is spent for Tx, Rx, and Idle tasks, respectively. This helps one to highlight the cross-layer energy dissipation per node and how the performance of an algorithm differs in terms of duty-cycling. Furthermore, we have shown that the energy savings due owing to the distributed algorithms in a large sensor network will not be practical without a complimentary lower-layer MAC. We show have demonstrated that the Qos is very much related to the ambient conditions, namely, are the Rx and Idle modes. From these preliminary results, we have added a new category of WSN protocols which are based ion the renewable energy resources, namely, the Fusion Ambient Renewable Measuring Sensors (FARMS). The study of sensor FARMS -harvesting applications allows one to measure the impact on Idle, Sleep, and renewable energy cycles as well as their unique deployment (density) needs, as all the sensor are not active(Rx) at all times. We have also shown that the efficiency of cross-layer Qos performance of routing algorithms with MAC losses has a long tail which is similarly observed in Power Law. In this sensor network model we like to show the complexity of clustering, messaging and data rate in terms of O(√(N) log N), O(N) and O(log2N) where N is the number of nodes.

Glaucoma is the second leading cause of blindness worldwide. Often, the optic nerve head (ONH) glaucomatous damage and ONH changes occur prior to visual field loss and are observable in vivo. Thus, digital image analysis is a promising choice for detecting the onset and/or progression of glaucoma. In this paper, we present a new framework for detecting glaucomatous changes in the ONH of an eye using the method of proper orthogonal decomposition (POD). A baseline topograph subspace was constructed for each eye to describe the structure of the ONH of the eye at a reference/baseline condition using POD. Any glaucomatous changes in the ONH of the eye present during a follow-up exam were estimated by comparing the follow-up ONH topography with its baseline topograph subspace representation. Image correspondence measures of L1-norm and L2 -norm, correlation, and image Euclidean distance (IMED) were used to quantify the ONH changes. An ONH topographic library built from the Louisiana State University Experimental Glaucoma study was used to evaluate the performance of the proposed method. The area under the receiver operating characteristic curves (AUCs) was used to compare the diagnostic performance of the POD-induced parameters with the parameters of the topographic change analysis (TCA) method. The IMED and L2-norm parameters in the POD framework provided the highest AUC of 0.94 at 10 degrees field of imaging and 0.91 at 15 degrees field of imaging compared to the TCA parameters with an AUC of 0.86 and 0.88, respectively. The proposed POD framework captures the instrument measurement variability and inherent structure variability and shows promise for improving our ability to detect glaucomatous change over time in glaucoma management.

Multi-sensor biomedical image registration and fusion usually require intensive computational effort. This article presented a novel automated approach of the multi-sensor retinal optic nerve head image registration and fusion using heuristic optimization algorithm. The reference and the to-be-registered images are from two different modalities, i.e. angiogram grayscale images and fundus color images. The optic nerve head vasculature is extracted using Canny Edge Detector. Control points are detected at the vessel bifurcations using adaptive exploratory algorithm. Mutual-Pixel-Count (MPC) maximization based heuristic optimization adjusts the control points at the sub-pixel level. The iteration stops either when MPC reaches the maximum value, or when the maximum allowable loop count is reached. A refinement of the parameter set is obtained at the end of each loop, and finally an optimal fused image is generated at the end of the iteration. Comparative evaluation is performed with the genetic algorithm. The results show the advantages of the presented method in terms of novelty, efficiency and accuracy.

Multi-modality biomedical imagespsila feature detection, registration, and fusion are usually scene dependent which requires intensive computational effort. A novel automated approach of the multi-modality retinal image control point detection, registration, and fusion is proposed in this paper. The new algorithm is reliable and time efficient, which implements automatic adaptation from frame to frame with a few tunable thresholds. The reference and input images are from two different modalities, i.e., the angiogram grayscale and fundus true color images. Retinal imagepsilas properties determine the fuzzy vessel boundaries and bifurcations. The retinal vasculature is extracted using canny edge detector and the control points are detected at the fuzzy vasculature bifurcations using the adaptive exploratory algorithm. Shape similarity criteria are employed to match the control point pairs. The proposed heuristic optimization algorithm adjusts the control points at the sub-pixel level in order to maximize the objective function mutual-pixel-count (MPC). The iteration stops either whenfMPCreaches the maximal, or when the maximum allowable loop count is reached. The comparative analysis with other existing approaches has shown the advantages of the new algorithm in terms of novelty, efficiency, and accuracy.

In this paper, we first provide a joint source and channel coding (JSCC) approach in estimating Gaussian sources over Gaussian MAC channels, as well as its sufficient and necessary condition in restoring Gaussian sources with a prescribed distortion value. An interesting relationship between our proposed joint approach with a more straightforward separate source and channel coding (SSCC) scheme is further established. We then formulate constrained power minimization problems to minimize total transmission power consumption under a distortion constraint for arbitrary in-homogeneous networks under JSCC, SSCC and uncoded scheme (UC). They are transformed to relaxed convex geometric programming problems. Our numerical results exhibit that none of the three schemes is consistently most energy efficient. The proposed JSCC could be more energy efficient than either the uncoded scheme, or SCCC, but not both. In addition, we prove that the optimal decoding order to minimize the total transmission powers for both source and channel coding parts is solely subject to the ordering of MAC channel qualities, and has nothing to do with the ranking of measurement qualities across measuring nodes.

Nowadays, the source localization has been widely applied for wireless sensor networks. The Gaussian mixture model has been adopted for maximum-likelihood (ML) source localization schemes. However, this model does not match the statistics of the real data in practice. In this paper, we study the probability density function of the sensor signals and demonstrate that the distribution is not Gaussian. We propose to employ the Gaussianity test based on the bootstrap algorithm to quantify the departure of Gaussianity for the received signals added with different kinds of noise. Our proposed Gaussianity test can be used as the robustness figure for evaluating the prevalent ML source localization schemes.

Identification of a low-level point radiation source amidst background radiation is achieved by a network of radiation sensors using a two-step approach. Based on measurements from three sensors, the geometric difference triangulation method is used to estimate the location and strength of the source. Then a sequential probability ratio test based on current measurements and estimated parameters is employed to finally decide: (1) the presence of a source with the estimated parameters, or (2) the absence of the source, or (3) the insufficiency of measurements to make a decision. This method achieves specified levels of false alarm and missed detection probabilities, while ensuring a close-to-minimal number of measurements for reaching a decision. This method minimizes the ghost-source problem of current estimation methods, and achieves a lower false alarm rate compared with current detection methods. This method is tested and demonstrated using: (1) simulations, and (2) a test-bed that utilizes the scaling properties of point radiation sources to emulate high intensity ones that cannot be easily and safely handled in laboratory experiments.

Next-generation scientific applications require the capability to visualize large archival data sets or on-going computer simulations of physical and other phenomena over wide-area network connections. To minimize the latency in interactive visualizations across wide-area networks, we propose an approach that adaptively decomposes and maps the visualization pipeline onto a set of strategically selected network nodes. This scheme is realized by grouping the modules that implement visualization and networking subtasks and mapping them onto computing nodes with possibly disparate computing capabilities and network connections. Using estimates for communication and processing times of subtasks, we present a polynomial-time algorithm to compute a decomposition and mapping to achieve minimum end-to-end delay of the visualization pipeline. We present experimental results using geographically distributed deployments to demonstrate the effectiveness of this method in visualizing data sets from three application domains.

This paper presents a novel approach on bootstrapping chord and other ring-based peer-to-peer (P2P) systems over mobile ad hoc networks (MANETs). Only inter-neighbor communication is used to build the ring topology in node ID space of structured P2P systems. Upon this ring entire chord could be put into normal operation without lengthy stabilization. RAN protocol suite is proposed. It includes three patterns: distributed exhaustive, virtual centralized exhaustive, and random. Two exhaustive patterns adapt well to the disturbance caused by mobility. Simulation results show that the distributed exhaustive pattern has optimal overall performance. Once again the superiority of decentralization is demonstrated.

In this study, we compare the performance of four different imputation strategies ranging from the commonly used Listwise Deletion to model based approaches such as the Maximum Likelihood on enhancing completeness in incomplete software project data sets. We evaluate the impact of each of these methods by implementing them on six different real-time software project data sets which are classified into different categories based on their inherent properties. The reliability of the constructed data sets using these techniques are further tested by building prediction models using stepwise regression. The experimental results are noted and the findings are finally discussed.

A number of science applications employing collaborative computations require transport methods that guarantee end- to-end performance at the application level. Throughputs achieved by the traditional transport methods are limited to single default best-effort IP paths, which are often insufficient for the application tasks. In this paper, we present a measurement-based approach that utilizes application-level daemons at the collaborating sites to enhance the transport performance by utilizing multiple quickest paths. This method is based on a linear approximation of the effective bandwidth, and is computationally efficient and analytically tractable under fairly general conditions. We implemented and tested this method at Internet nodes, and the experimental results show significant performance improvements over the default TCP.

Abstract One of the most challenging topics in the automatic document rating process is the development of a rating scheme for the image quality of documents. As part of the Department of Energy (DOE) document declassification program, we have developed a generalized rating system to predict the optical character recognition (OCR) accuracy level that is achieved when processing a document. The need for such a system emerged from the declassification of degraded, typewriter‐era documents, which is currently a time‐consuming manual process. This article presents the statistical analysis of the most influential document quality features affecting OCR accuracy, develops consistent predictive models for four currently used OCR engines, and studies the applicability of different OCR products to the DOE document declassification process. This study is expected to lead to an efficient and completely automated document declassification system.

Sensor networks usually operate under very severe energy restrictions. Therefore, sensor communications should consume the minimum possible amount of energy. White broadcasting is a very energy-expensive protocol, it is also widely used as a building block for a variety of other network layer protocols. Therefore, reducing the energy consumption by optimizing broadcasting is a major improvement in sensor networking. In this paper, we propose an optimized broadcast protocol for sensor networks (BPS). The major novelty of BPS is its adaptive-geometric approach that enables considerable reduction of retransmissions by maximizing each hop length. BPS adapts itself and gets the best out of existing radio conditions. In BPS, nodes do not need any neighborhood information, which leads to low communication and memory overhead. We analyze the worst-case scenario for BPS and show that the number of transmissions in such a scenario is a constant multiple of those required in the ideal case. Our simulation results show that BPS is very scalable with respect to network density. BPS is also resilient to transmission errors.

One of the most compelling technological advances of this decade has been the advent of deploying wireless networks of heterogeneous smart sensor nodes for complex information gathering tasks. A wireless distributed sensor network (DSN) is a self-organizing , ad-hoc network of a large number of cooperative intelligent sensor nodes. Due to the limited power of sensor nodes, energy-efficient DSN are essentially multi-hop networks. The self-organizing capabilities, and the cooperative operation of DSN allow for forming reliable clusters of sensors deployed near, or at, the sites of target phenomena. Reliable monitoring of a phenomenon (or event detection) depends on the collective data provided by the target cluster of sensors, and not on any individual node. The failure of one or more nodes may not cause the operational data sources to be disconnected from the data sinks (command nodes or end user stations). However, it may increase the number of hops a data message has to go through before reaching its destination (and subsequently increase the message delay). In this paper, we focus on two related problems: computing a measure for the reliability of DSN, and computing a measure for the expected & the maximum message delay between data sources (sensors) & data sinks in an operational DSN. Given an estimation of the failure probabilities of the sensors, as well as the intermediate nodes (nodes used to relay messages between data sources, and data sinks), we use a probabilistic graph to model DSN. We define the DSN reliability as the probability that there exists an operating communication path between the sink node, and at least one operational sensor in a target cluster. We show that both problems are #P-hard for arbitrary networks. We then present two algorithms for computing the reliability, and the expected message delay for arbitrary networks. We also consider two special cases where efficient (polynomial time) algorithms are developed. Finally, we present some numerical results that demonstrate some of the applications of our algorithms.

The design of the IP protocol makes it difficult to reliably identify the originator of an IP packet making the defense against distributed denial of service attacks one of the hardest problems on the Internet today. Previous solutions for this problem try to traceback to the exact origin of the attack by requiring every router's participation. For many reasons this requirement is impractical and the victim ends up with an approximate location of the attacker. Reconstruction of the whole path is also very difficult owing to the sheer size of the Internet. This paper presents lightweight schemes for tracing back to the attack-originating AS instead to the exact origin itself. Once the attack-originating AS is determined, all further routers in the path to the attacker are within that AS and under the control of a single entity; which can presumably monitor local traffic in a more direct way than a generalized, Internet scale, packet marking scheme can. We also provide a scheme to prevent compromised routers from forging markings.

This paper presents a random asynchronous wakeup (RAW), a power saving technique for sensor networks that reduces energy consumption without significantly affecting the latency or connectivity of the network. RAW builds on the observation that when a region of a shared-channel wireless network has a sufficient density of nodes, only a small number of them need be active at any time to forward the traffic for active connections. RAW is a distributed, randomized algorithm where nodes make local decisions on whether to sleep, or to be active. Each node is awake for a randomly chosen fixed interval per time frame. High node density results in existence of several paths between two given nodes whose path length and delay characteristics are similar to the shortest path. Thus, a packet can be forwarded to any of several nodes in order to be delivered to the destination without affecting much the path length and delay experienced by the packet as compared to forwarding the packet through the shortest path. The improvement in system lifetime, due to RAW, increases as the ratio of idle-to-sleep energy consumption increases, and as the density of the network increases. Through analytical and experimental evaluations, we show that RAW improves communication latency and system lifetime compared to current schemes.

This paper discusses algorithmic and implementation aspects of a remote visualization system, which adoptively decomposes and maps the visualization pipeline onto a wide-area network. Visualization pipeline modules such as filtering, geometry extraction, rendering, and display are dynamically assigned to network nodes to achieve minimal total delay or maximal frame rate. Polynomial-time optimal algorithms using the dynamic programming method to compute the optimal decomposition and mapping are proposed. We implemented an OpenGL-based remote visualization system. We evaluated its performance using a deployment at three geographically distributed nodes.

Interest in the use of unmanned underwater vehicles (UUVs) for both commercial and military uses is growing. Control of UUVs poses a difficult problem because traditional methods of communication and navigation, i.e. radio and GPS, are not effective due to the properties of seawater. Control and communication algorithms were developed to carry out multiple UUV formation maneuvering using acoustic communications and first tested in computer simulation and then on mobile robots. Three control schemes, classic logic, behavior, and neural network were tested in line formations in both simulator and lab environments. Results and issues are discussed along with future directions.

Path length, path reliability, and sensor energy-consumption are three major constraints affecting routing in resource constrained, unreliable wireless sensor networks. By considering the implicit collaborative imperative for sensors to achieve overall network objectives subject to individual resource consumption, we develop a game-theoretic model of reliable, length and energy-constrained, sensor-centric information routing in sensor networks. We define two distinct payoff (benefit) functions and show that computing optimally reliable energy-constrained paths is NP-Hard under both models for arbitrary sensor networks. We then show that optimal length-constrained paths can be computed in polynomial time in a distributed manner (using O(E) messages) for popular sensor network implementations using geographic routing. We also develop sensor-centric metrics called path weakness to measure the qualitative performance of different routing schemes and provide theoretical limits on the inapproximability of computing paths with bounded weakness. Heuristics for computing optimal paths in arbitrary sensor networks are described along with simulation results comparing performance with other routing algorithms.

We propose a distributed solution for a canonical task in wireless sensor networks - the binary detection of interesting environmental events. We explicitly take into account the possibility of sensor measurement faults and develop a distributed Bayesian algorithm for detecting and correcting such faults. Theoretical analysis and simulation results show that 85-95 percent of faults can be corrected using this algorithm, even when as many as 10 percent of the nodes are faulty.

The problem of computing a route for a mobile agent that incrementally fuses the data as it visits the nodes in a distributed sensor network is considered. The order of nodes visited along the route has a significant impact on the quality and cost of fused data, which, in turn, impacts the main objective of the sensor network, such as target classification or tracking. We present a simplified analytical model for a distributed sensor network and formulate the route computation problem in terms of maximizing an objective function, which is directly proportional to the received signal strength and inversely proportional to the path loss and energy consumption. We show this problem to be NP-complete and propose a genetic algorithm to compute an approximate solution by suitably employing a two-level encoding scheme and genetic operators tailored to the objective function. We present simulation results for networks with different node sizes and sensor distributions, which demonstrate the superior performance of our algorithm over two existing heuristics, namely, local closest first and global closest first methods.

This paper presents distributed adaptation techniques for use in wireless sensor networks. As an example application, we consider data routing by a sensor network in an urban terrain. The adaptation methods are based on ideas from physics, biology, and chemistry. All approaches are emergent behaviors in that: (i) perform global adaptation using only locally available information, (ii) have strong stochastic components, and (iii) use both positive and negative feedback to steer themselves. We analyze the approaches' ability to adapt, robustness to internal errors, land power consumption. Comparisons to standard wireless communications techniques are given.

In window-based transport methods for stabilizing and/or maximizing the goodput at the destination, it is very important to understand the statistical properties of the transport control and performance response parameters. Based on traffic measurements collected over the Internet during a 6-month period, we formulate and test hypotheses on the main effects of two control parameters on the goodput response and the interaction effects between them. We infer from the statistical analysis that the congestion window and sleep time parameters strongly interact with each other, and they both have significant main effects on the destination goodput. Consequently the underlying randomness in network traffic must be explicitly accounted for in the design of flow control methods.

Any reliable multicast protocol requires some recovery mechanism. A generic description of a recovery mechanism consists of a prioritized list of recovery servers/receivers (clients), hierarchically and/or geographically and/or randomly organized. Recovery requests are sent to the recovery clients on the list one-by-one until the recovery effort is successful. There are many recovery strategies available in literature fitting the generic description. We propose a polynomial time algorithm for choosing the recovery strategy with law recovery latency without sacrificing much bandwidth. We compared our method with two existing recovery methods, SRM (scalable reliable multicast) and RMA (reliable multicast architecture), by simulation and found that our method performs better. Although our theoretical analyses are based on a reliable network, our simulation results show that our strategy performs as well with the per link loss probability in a network up to 20% or more

Mobile robot teams are increasingly deployed in various applications involving remote operations in unstructured environments that do not support wireless network infrastructures. We propose a class of protocols based on the connectivity-through-time concepts that exploit the robot movements to extend the traditional notions of network connectivity. These protocols enable the formation of adhoc networks of mobile robots without the infrastructure of access points by utilizing the robots as routers. These protocols are implemented as a collection of daemons that track connectivity changes, compute single and multiple hop connectivity, route the packets via robots with suitable buffering, and adapt the transport parameters to the connection characteristics. The implementation employs UDP with window-based flow control that is tuned to the nature of connections. We present experimental performance results based on our implementation on robot teams to illustrate the salient features of this approach.

Standard embedded sensor network models emphasize energy efficiency and distributed decision-making by considering untethered and unattended sensors. To this we add two constraints - the possibility of sensor failure and the fact that each sensor must tradeoff its own resource consumption with overall network objectives. In this paper, we develop an analytical model of data-centric information routing in sensor networks under all the above constraints. Unlike existing techniques, we use game theory to model intelligent sensors thereby making our approach sensor-centric. Sensors behave as rational players in an N-player routing game, where they tradeoff individual communication and other costs with network wide benefits. The outcome of the sensor behavior is a sequence of communication link establishments, resulting in routing paths from reporting to querying sensors. We show that the optimal routing architecture is the Nash equilibrium of the N-player routing game and that computing the optimal paths (which maximizes payoffs of the individual sensors) is NP-hard with and without data-aggregation. We develop a game-theoretic metric called path weakness to measure the qualitative performance of different routing mechanisms. This sensor-centric concept which is based on the contribution of individual sensors to the overall routing objective is used to define the quality of routing (QoR) paths. Simulation results are used to compare the QoR of different routing paths derived using various energy-constrained routing algorithms.

Given the increasing importance of optimal sensor deployment for battlefield strategists, the converse problem of reacting to a particular deployment by an enemy is equally significant and not yet addressed in a quantifiable manner in the literature. We address this issue by modeling a two stage game in which the opponent deploys sensors to cover a sensor field and we attempt to maximally reduce his coverage at minimal cost. In this context, we introduce the concept of minimal sensor integrity which measures Me vulnerability of any sensor deployment. We find the best response by quantifying the merits of each response. While the problem of optimally deploying sensors subject to coverage constraints is NP-complete, in this paper we show that the best response (i.e. the maximum vulnerability) can be computed in polynomial time for sensors with arbitrary coverage capabilities deployed over points in any dimensional space. In the special case when sensor coverages form an interval graph (as in a linear grid), we describe a better O(Min(M/sup 2/, NM)) dynamic programming algorithm.

We present novel grid coverage strategies for effective surveillance and target location in distributed sensor networks. We represent the sensor field as a grid (two or three-dimensional) of points (coordinates) and use the term target location to refer to the problem of locating a target at a grid point at any instant in time. We first present an integer linear programming (ILP) solution for minimizing the cost of sensors for complete coverage of the sensor field. We solve the ILP model using a representative public-domain solver and present a divide-and-conquer approach for solving large problem instances. We then use the framework of identifying codes to determine sensor placement for unique target location, We provide coding-theoretic bounds on the number of sensors and present methods for determining their placement in the sensor field. We also show that grid-based sensor placement for single targets provides asymptotically complete (unambiguous) location of multiple targets in the grid.

The image registration problem of finding a mapping that matches data from multiple cameras is computationally intensive. Current solutions to this problem tolerate Gaussian noise, but are unable to perform the underlying global optimization computation in real time. This paper expands these approaches to other noise models and proposes the Terminal Repeller Unconstrained Subenergy Tunneling (TRUST) method, originally introduced by B.C. Cetin et al. (1993), as an appropriate global optimization method for image registration. TRUST avoids local minima entrapment, without resorting to exhaustive search by using subenergy-tunneling and terminal repellers. The TRUST method applied to the registration problem shows good convergence results to the global minimum. Experimental results show TRUST to be more computationally efficient than either tabu search or genetic algorithms.

Abstract The explosive growth of digital image collections on the Web sites is calling for an efficient and intelligent method of browsing, searching, and retrieving images. In this article, an artificial neural network (ANN)‐based approach is proposed to explore a promising solution to the Web image retrieval (IR). Compared with other image retrieval methods, this new approach has the following characteristics. First of all, the Content‐Based features have been combined with Text‐Based features to improve retrieval performance. Instead of solely relying on low‐level visual features and high‐level concepts, we also take the textual features into consideration, which are automatically extracted from image names, alternative names, page titles, surrounding texts, URLs, etc. Secondly, the Kohonen neural network model is introduced and led into the image retrieval process. Due to its self‐organizing property, the cognitive knowledge is learned, accumulated, and solidified during the unsupervised training process. The architecture is presented to illustrate the main conceptual components and mechanism of the proposed image retrieval system. To demonstrate the superiority of the new IR system over other IR systems, the retrieval result of a test example is also given in the article.

Abstract Content‐based image retrieval is based on the idea of extracting visual features from image and using them to index images in a database. The comparisons that determine similarity between images depend on the representations of the features and the definition of appropriate distance function. Most of the research literature uses vectors as the predominate representation given the rich theory of vector spaces. While vectors are an extremely useful representation, their use in large databases may be prohibitive given their usually large dimensions and similarity functions. In this paper, we propose similarity measures and an indexing algorithm based on information theory that permits an image to be represented as a single number. When use in conjunction with vectors, our method displays improved efficiency when querying large databases.

Abstract A fundamental aspect of content‐based image retrieval (CBIR) is the extraction and the representation of a visual feature that is an effective discriminant between pairs of images. Among the many visual features that have been studied, the distribution of color pixels in an image is the most common visual feature studied. The standard representation of color for content‐based indexing in image databases is the color histogram. Vector‐based distance functions are used to compute the similarity between two images as the distance between points in the color histogram space. This paper proposes an alternative real valued representation of color based on the information theoretic concept of entropy. A theoretical presentation of image entropy is accompanied by a practical description of the merits and limitations of image entropy compared to color histograms. Specifically, the L1norm for color histograms is shown to provide an upper bound on the difference between image entropy values. Our initial results suggest that image entropy is a promising approach to image description and representation.

We describe the use of the mobile agent paradigm to design an improved infrastructure for data integration in a distributed sensor network (DSN). We use the acronym MADSN to denote the proposed mobile-agent-based DSN. Instead of moving data to processing elements for data integration, as is typical of a client/server paradigm, MADSN moves the processing code to the data locations. This saves network bandwidth and provides an effective means for overcoming network latency, since large data transfers are avoided. Our major contributions are the use of mobile agent in DSN for distributed data integration and the evaluation of performance between DSN and MADSN approaches. We develop an enhanced multiresolution integration (MRI) algorithm where multiresolution analysis is applied at a local node before accumulating the overlap function by mobile agent. Compared to the MRI implementation in DSN, the enhanced integration algorithm saves up to 90% of the data transfer time. We develop objective functions to evaluate the performance between DSN and MADSN approaches. For a given set of network parameters, we analyze the conditions under which MADSN performs better than DSN and determine the condition under which MADSN reaches its optimum performance level.

Features in satellite images of the oceans often have weak edges. These images also have a significant amount of noise, which is either due to the clouds or atmospheric humidity. The presence of noise compounds the problems associated with the detection of features, as the use of any traditional noise removal technique will also result in the removal of weak edges. Recently, there have been rapid advances in image processing as a result of the development of the mathematical theory of wavelet transforms. This theory led to multifrequency channel decomposition of images, which further led to the evolution of important algorithms for the reconstruction of images at various resolutions from the decompositions. The possibility of analyzing images at various resolutions can be useful not only in the suppression of noise, but also in the detection of fine features and their classification. This paper presents a new computational scheme based on multiresolution decomposition for extracting the features of interest from the oceanographic images by suppressing the noise. The multiresolution analysis from the median presented by Starck-Murtagh-Bijaoui (1994) is used for the noise suppression.

In past years, a large number of published distributed algorithms have been shown to be incorrect. Unfortunately, designers of distributed algorithms typically use informal correctness proofs, which tend to be unreliable. Formal correctness proofs offer a much higher degree of reliability, but they are not popular among algorithm designers because they are too mathematical and they typically assume synchronous message communication or some other abstract notation, and are therefore not easily applicable to the asynchronous message passing environment, the environment commonly assumed by many algorithm designers. To address this problem, we have developed a semiformal correctness proof method for the asynchronous message passing environment, using ideas from well known formal correctness proof methods. We illustrate part of the proof method by proving the safety property of a simple network broadcast algorithm.

This paper presents a new computational scheme based on multiresolution decomposition for extracting the features of interest from oceanographic images by suppressing noise. The multiresolution analysis from the median presented by (Starck et al., 1994) is used for the noise suppression. A parallel approach is presented for this computationally intensive problem of infrared images.

The ability to recognize edges of an object fast and accurately is a fundamental goal in computer vision and image processing. The facility is important in automatic manufacturing environment in industry. This paper defines and investigates an efficient method of edge extraction of image using directional tracing algorithm. Based on the approach of linear feature extraction presented by R. Nevatia and K.R. Babu (1980), our algorithm is developed for the general situation of edge extraction. The technique employs the basic and intuitive principle that an edge pixel should possess local maximal gradient but no more domain information or knowledge is required. An effective and robust tracing strategy is proposed. Our algorithm has been tested on different kinds of images, and the results are satisfactory.

This paper presents a new scheme for probabilistic relaxation labeling that consists of an update function and a dictionary construction method. The nonlinear update function is derived from Markov random field theory and Bayes' formula. The method combines evidence from neighboring label assignments and eliminates label ambiguity efficiently. This result is important for a variety of image processing tasks, such as image restoration, edge enhancement, edge detection, pixel classification, and image segmentation. The authors successfully applied this method to edge detection. The relaxation step of the proposed edge-detection algorithm greatly reduces noise effects, gets better edge localization such as line ends and corners, and plays a crucial role in refining edge outputs. The experiments show that our algorithm converges quickly and is robust in noisy environments.

We introduce a framework for a class of algorithms solving shortest path related problems, such as the one-to-one shortest path problem, the one-to-many shortest paths problem and the minimum spanning tree problem, in the presence of obstacles. For these algorithms, the search space is restricted to a sparse strong connection graph that is implicitly represented and its searched portion is constructed incrementally on-the-fly during search. The time and space requirements of these algorithms essentially depend on actual search behavior. Therefore, additional techniques or heuristics can be incorporated into search procedure to further improve the performance of the algorithms. These algorithms are suitable for large VLSI design applications with many obstacles.

We present two classes of convergent algorithms for learning continuous functions and regressions that are approximated by feedforward networks. The first class of algorithms, applicable to networks with unknown weights located only in the output layer, is obtained by utilizing the potential function methods of Aizerman et al. (1970). The second class, applicable to general feedforward networks, is obtained by utilizing the classical Robbins-Monro style stochastic approximation methods (1951). Conditions relating the sample sizes to the error bounds are derived for both classes of algorithms using martingale-type inequalities. For concreteness, the discussion is presented in terms of neural networks, but the results are applicable to general feedforward networks, in particular to wavelet networks. The algorithms can be directly adapted to concept learning problems.

The paper defines a new approach and investigates a fundamental problem in route planners. This capability is important for robotic vehicles (Martian Rovers, etc.) and for planning off road military manoeuvres. The emphasis throughout the paper is on the design and analysis and hierarchical implementation of our route planner. The work was motivated by anticipation of the need to search a grid of a trillion points for optimum routes. This cannot be done simply by scaling upward from the algorithms used to search a grid of 10,000 points. Algorithms sufficient for the small grid are totally inadequate for the large grid. Soon, the challenge will be to compute off road routes more then 100 km long and with a one or two meter grid. Previous efforts are reviewed and the data structures, decomposition methods and search algorithms are analyzed and limitations are discussed. A detailed discussion of a hierarchical implementation is provided and the experimental results are analyzed. The principal contributions of the paper are: new algorithms for decomposing the map and new search methods; analysis of new approaches; and the use of expert systems, deductive databases and mediators. Experimental results are included of a detailed implementation.

Template matching is a fundamental method of detecting the presence or the absence of objects and identifying them in an image. A template is itself an image that contains a feature or an object or a part of a bigger image, and is used to search a given image for the presence or the absence of the contents of the template. This search is carried out by translating the template systematically pixel-by-pixel all over the image, and at each position of the template the closeness of the template to the area covered by it is measured. The location at which the maximum degree of closeness is achieved is declared to be the location of the object detected. The problem of object/shape recognition is addressed in this paper in a multiresolutional setting using pyramidal decomposition of images with respect to an orthonormal wavelet basis. A new approach to efficient template matching to detect objects using computational geometric methods is put forward. An efficient paradigm for object recognition is described in detail with a complexity analysis.

Proposes an abstract framework to address the problem of fault-tolerant integration of information provided by multiple sensors. This paper presents a formal description of spatially distributed sensor networks, where i) clusters of sensors monitor (possible overlapping) regions of the environment; ii) sensors return measured values of a multidimensional parameter of interest; and iii) uncertainties associated with a sensor output are represented by a connected subset in the parameter space. A method to obtain interval estimates of components of the actual parameter vector is developed, wherein information from faulty sensors are filtered out. The problem addressed involves combining interval estimates of sensor outputs into a best intersection estimate of outputs. The sensor fault model used assumes most faults cluster in the neighborhood of the correct values. The procedure of this paper is superior to earlier work. To test the theoretical analysis of the framework proposed, we have developed a modular parameter-driven simulator SIMDSN for the fault-tolerant integration of abstract sensor interval estimates. The simulator uses the well-known Monte-Carlo technique to generate random correct and tamely faulty intervals.>

This paper investigates a fundamental problem of determining the position and orientation of a three-dimensional (3-D) object using a single perspective image view. The technique is focused on the interpretation of trihedral angle constraint information. A new closed form solution based on Kanatani's formulation is proposed. The main distinguishing feature of the authors' method over the original Kanatani formulation is that their approach gives an effective closed form solution for a general trihedral angle constraint. The method also provides a general analytic technique for dealing with a class of problem of shape from inverse perspective projection by using "angle to angle correspondence information." A detailed implementation of the authors' technique is presented. Different trihedral angle configurations were generated using synthetic data for testing the authors' approach of finding object orientation by angle to angle constraint. The authors performed simulation experiments by adding some noise to the synthetic data for evaluating the effectiveness of their method in a real situation. It has been found that the authors' method worked effectively in a noisy environment which confirms that the method is robust in practical application.>

Proposes a versatile architecture for a distributed sensor network which consists of a multilevel network with the nodes (processing element/sensor pairs) at each level interconnected as a deBruijn network. The authors show that this multilevel network has reasonable fault tolerance, admits simple and decentralized routing, and offers easy extensibility. They model information from sensors as real valued intervals and derive an interesting property related to information integration in the presence of faults. Using this property, the search for a fault is narrowed down to two potentially faulty sensors or communication links. In a distributed environment, information has to be integrated from "temporally close" signals in the presence of imperfect clocks in a distributed environment. The authors apply the results of past research in this area to state various relationships between the clocks of the processing elements in the network for proper information integration.>

Presents a new edge detector for automatic extraction of oceanographic (mesoscale) features present in infrared (IR) images obtained from the Advanced Very High Resolution Radiometer (AVHRR). Conventional edge detectors are very sensitive to edge fine structure, which makes it difficult to distinguish the weak gradients that are useful in this application from noise. Mathematical morphology has been used in the past to develop efficient and statistically robust edge detectors. Image analysis techniques use the histogram for operations such as thresholding and edge extraction in a local neighborhood in the image. An efficient computational framework is discussed for extraction of mesoscale features present in IR images. The technique presented in the present article, called the Histogram-Based Morphological Edge detector (HMED), extracts all the weak gradients, yet retains the edge sharpness in the image. A new morphological operation defined in the domain of the histogram of an image is also presented. An interesting experimental result was found by applying the HMED technique to oceanographic data in which certain features are known to have edge gradients of varying strength.>

A fundamental problem of determining the position and orientation of a 3-D object using a single perspective image view is defined and investigated. The technique is based on the interpretation of trihedral angle constraint information. A new closed-form solution to the problem is proposed. The method also provides a general analytic technique for dealing with a class of problem of shape from inverse perspective projection by using angle to angle correspondence information. Simulation experiments show that the authors' method is effective and robust for real application.>

An effective method of surface characterization of 3D objects using surface curvature properties and an efficient approach to recognizing and localizing multiple 3D free-form objects (free-form object recognition and localization) are presented. The approach is surface based and is therefore not sensitive to noise and occlusion, forms hypothesis by local analysis of surface shapes, does not depend on the visibility of complete objects, and uses information from a CAD database in recognition and localization. A knowledge representation scheme for describing free-form surfaces is described. The data structure and procedures are well designed, so that the knowledge leads the system to intelligent behavior. Knowledge about surface shapes is abstracted from CAD models to direct the search in verification of vision hypotheses. The knowledge representation used eases processes of knowledge acquisition, information retrieval, modification of knowledge base, and reasoning for solution.>

A general approach for the channel routing problem is presented as a framework for a class of heuristic routing algorithms. The algorithm is shown to possess a backtracking capability that increases the chance of completing the routing with a minimum number of tracks. Since the concepts described are general, they can be applied to other channel problems, such as switchbox routing, three-layer routing, and multilayer routing, or even to the overlap model, with only a few modifications. It is shown that track-oriented greedy algorithms can be modified to solve other channel routing problems. As examples, the algorithm is modified to solve the Manhattan switch-box problem and channel routing problems in the overlap and knock-knee models. Preliminary results show that the modified algorithms have good performance and show strong potential to outperform existing algorithms. Applying the algorithm MCRP-ROUT to the benchmark Deutsch's difficult problem and Burstein's difficult problem, routing solutions of 19 tracks and six tracks, respectively, were obtained.>

The authors consider the problem of learned navigation of a circular robot R, of radius delta (>or=0), through a terrain whose model is not a priori known. The authors consider two-dimensional finite-sized terrains populated by an unknown (but finite) number of simple polygonal obstacles. The number and locations of the vertices of each obstacle are unknown to R; R is equipped with a sensor system that detects all vertices and edges that are visible from its present location. The authors deal with two problems: the visit problem and the terrain model acquisition problem. In the visit problem, the robot is required to visit a sequence of destination points, and in the terrain model acquisition problem, the robot is required to acquire the complete model of the terrain. The authors present an algorithmic network framework for solving these two problems based on a retraction of the free space onto the Voronoi diagram of the terrain.>

The computational, i.e. architectural, algorithmic, and synchronization, issues related to competitive information integration in a distributed sensor network (DSN) are addressed. The proposed DSN architecture consists of a set of binary trees whose roots are fully connected. Each node of the tree has a processing element and one or more sensors associated with it. The information from each of the sensors has to be integrated in such a manner that the communication costs are low and that the real time needs are met. An information integration algorithm that has a low message cost (linear in the number of nodes of the network) and a low distributed computation cost is presented. The problems associated with synchronizing information to be integrated in the presence of imperfect clocks is considered. The fault tolerant features of the network and the integration algorithm are discussed.>

Fault-tolerance is an important issue in network design because sensor networks must function in a dynamic, uncertain world. A functional characterization of the fault-tolerant integration of abstract interval estimates is proposed. This model provides a preliminary version for a general framework that is hoped to develop to address the general problem of fault-tolerant integration of abstract sensor estimates. A scheme for narrowing the width of the sensor output in a specific failure model is proposed and given a functional representation. The main distinguishing feature of the model over the original model of K. Marzullo (1989) is in reducing the width of the output interval estimate significantly in most cases where the number of sensors involved is large.>

The successful development of fifth-generation systems requires enormous computational capability and flexibility, necessitating the ability to achieve operational responses in hard real-time through optimal resource utilisation and introduction of adaptive control. This necessitates dynamically balancing the computational load among all the processing nodes in the system. In this paper we propose a graph-theoretic, receiver-initiated, distributed protocol for dynamic load balancing protocol in large-scale hypercube ensembles. Using attributed hypergraphs as the primary data structure for constraint modelling and dynamic optimisation, we consider systems running precedence-constrained heterogeneous tasks. Fault Tolerance is ensured by incorporating a dynamic integrity check for the decision nodes and their subsequent re-election if needed. Simulation studies are used to analyse the algorithm performance and correctness.

Thermal infrared images of the ocean obtained from satellite sensors are widely used for the study of ocean dynamics. The derivation of mesoscale ocean information from satellite data depends to a large extent on the correct interpretation of infrared oceanographic images. The difficulty of the image analysis and understanding problem for oceanographic images is due in large part to the lack of precise mathematical descriptions of the ocean features, coupled with the time varying nature of these features and the complication that the view of the ocean surface is typically obscured by clouds, sometimes almost completely. Towards this objective, the present paper describes a hybrid technique that utilizes a nonlinear probabilistic relaxation method and an expert system for the oceanographic image interpretation problem. This paper highlights the advantages of using the contextual information in the feature labeling algorithm. The need for an expert system and its feedback in automatic interpretation of oceanic features is discussed. The paper presents some important results of the series of experiments conducted at the Remote Sensing Branch, of the Naval Oceanographic and Atmospheric Research Laboratory, on the National Oceanic and Atmospheric Administration Advanced Very High Resolution Radiometer (AVHRR) imagery data. The results clearly indicate the drastic improvement in labeling due to the oceanographic expert system.

The navigation of autonomous mobile machines, which are referred to as robots, through terrains whose models are not known a priori is considered. The authors deal with point-sized robots in 2-D and 3-D (two- and three-dimensional) terrains and circular robots in 2-D terrains. The 2-D (or 3-D) terrains are finite-sized and populated by an unknown, but finite, number of simple polygonal (or polyhedral) obstacles. The robot is equipped with a sensor system that detects all vertices and edges that are visible from its present location. Two basic navigational problems are considered. In the visit problem, the robot is required to visit a sequence of destination points in a specified order, using the sensor system. In the terrain model acquisition problem, the robot is required to acquire the complete model of the terrain by exploring the terrain with the sensor. A framework that yields solutions to both the visit problem and the terrain model acquisition problem using a single approach is presented, and the algorithms are described. The approach consists of incrementally constructing, in an algorithmic manner, an appropriate geometric graph structure (1-skeleton), called the navigational course. A point robot employs the restricted visibility graph and the visibility graph as the navigational course in 2-D and 3-D cases, respectively. A circular robot uses the modified visibility graph.>

It is argued that the design and analysis of a concurrent system can be made simpler and more intuitive if execution times of abstract operations are arbitrarily but systematically defined. This technique (time abstraction) is complementary to data abstraction and is more effective when used in combination with data abstraction. As examples, a bounced-buffer monitor and a multilevel concurrency scheme for a database system are analyzed by using data and time abstraction.>

An algorithm to navigate a point robot through a sequence of destination points amid unknown stationary polygonal obstacles in a two-dimensional terrain is presented. The algorithm implements learning in the course of building a global terrain model by integrating the sensor information obtained during navigation. This global model is used in planning future navigational paths. This approach prevents the robot from making localized detours, and results in better navigation, in an average case, than obtained using algorithms without learning. The proposed algorithms are implemented in the C language on a simulator for a HERMIES-II robot running on an IBM PC.>

The following problem, called the terrain model acquisition problem, is considered: a point robot R is placed in a finite-sized two-dimensional obstacle terrain populated by a set O= O/sub 1/O/sub 2/, . . ., O/sub n/) of unknown polygonal obstacles. Each obstacle O/sub i/ is a finite-sized polygon with a finite number of vertices. Initially the number of obstacles in the terrain and the number and the locations of vertices of each obstacle are unknown to R. The robot is equipped with sensors that detect all vertices and edges that visible from the present location of the robot. The robot is required to navigate and acquire the complete terrain model in a finite amount of time. A solution based on the retraction method is proposed that has the advantage of keeping the robot as far as possible from the obstacles during the navigation. A method for terrain model acquisition by a circular robot R of radius r, (r>O) is presented.>

We consider a distributed system consisting of a collection of clients and servers in which each server runs on a processor dedicated to it. Each server can be viewed as an instance of an abstract data-type module that provides a set of facilities for its clients. In such systems it may be possible to improve the performance of a server by scheduling its housekeeping activities to occur during periods when the server is waiting for requests from clients or is transmitting a response to a client. We consider the case where the client requests are handled by a foreground process while the maintenance tasks are performed by one or more background processes. We illustrate how the code for these processes can be developed in a stepwise manner, proceeding from coarse-grained concurrency to fine-grained concurrency. This approach is augmented with the use of rely/guarantee conditions which serve to simplify the proof of non-interference. The method is illustrated using a search-table abstraction.

The authors present parallel algorithms for recognizing the chordal graphs and k trees. Under the PRAM (parallel random-access-machine) model of computation with concurrent reading and writing allowed, these algorithms take O(log n) time and require O(n/sup 4/) processors. The algorithms have a better processor bound than an independent result by A. Edenbrandt (1985) for recognizing chordal graphs in parallel using O(n/sup 3/m) processors.>

The authors consider the problem of terrain model acquisition by a roving point placed in an unknown terrain populated by stationary polyhedral obstacles in two/three dimensions. The motivation for this problem is that after the terrain model is completely acquired, navigation from a source point to a destination point can be achieved along the collision-free paths. This can be done without the usage of sensors by applying the existing techniques for the find-path problem. In the paper, the point robot autonomous machine (PRAM) is used as a simplified abstract model for real-life roving robots. An algorithm is presented that enables PRAM to autonomously acquire the model of an unexplored obstacle terrain composed of an unknown number of polyhedral obstacles in two/three dimensions. In this method, PRAM undertakes a systematic exploration of the obstacle terrain with its sensor that detects all the edges and vertices visible from the present location, and builds the complete obstacle terrain model.>

The binary-image-compression problem is analyzed using irreducible cover of maximal rectangles. A bound on the minimum-rectangular-cover problem for image compression is given under certain conditions that previously have not been analyzed. It is demonstrated that for a simply connected image, the irreducible cover proposed uses less than four times the number of the rectangles in a minimum cover. With n pixels in a square, the parallel algorithm for obtaining the irreducible cover uses (n/log n) concurrent-read-exclusive write (CREW) processors in O(log n) time.>

A stepwise method of deriving the high-performance implementation of a set of operations is proposed. This method is based on the ability to organize the data into a multilevel data structure to provide an efficient implementation of all the operations. Typically, for such data organization the performance may deteriorate over a period of time and that can be corrected by reorganizing the data. This data reorganization is done by the introduction of maintenance processes. For a particular example, the multilevel data organization and the different models of maintenance processes possible are considered. The various models of maintenance process provide varying amounts of concurrency by varying the degree of atomicity in different operations. Performance behavior for the different models is derived and a correctness proof for the developed implementation is outlined.>

The terrain acquisition problem deals with the acquisition of the complete obstacle terrain model by a mobile robot placed in an unexplored terrain. This is a precursory problem to many well-known find-path and related problems which assume the availability of the complete terrain model. In this paper, we present a method for terrain acquisition by a finite-sized robot operating in plane populated by an unknown (but, finite) number of polygonal obstacles; each obstacle is arbitrarily located and has unknown (but, finite) number of vertices. The robot progressively explores newer vertices of the obstacles using sensor equipment. We show that the complete terrain model will be built by the robot in a finite time. We also show that at any point of time the partially acquired terrain suffices for the navigation of the robot during the exploration. Hence we conclude that the navigation techniques for known terrains can be applied for the robot navigation during exploration.

The “minimum vocabulary problem” for a dictionary has applications in indexing and other domains of information retrieval. A simple directed-graph model of a dictionary results in a linear-time algorithm for this problem. Since it is known that many minimum vocabularies can exist for a dictionary, a computationally useful criterion for finding a “desirable minimum vocabulary” is suggested and an O(|V|3) algorithm is outlined, where |V| is the number of words in the dictionary, duplicates eliminated. Furthermore, some enrichments to the model and the computational intractability of a variant called the 1-lexicon problem are discussed. Directions for further work are indicated. © 1987 John Wiley & Sons, Inc.

The problem of navigating an autonomous mobile robot through unexplored terrain of obstacles is discussed. The case when the obstacles are "known" has been extensively studied in literature. Completely unexplored obstacle terrain is considered. In this case, the process of navigation involves both learning the information about the obstacle terrain and path planning. An algorithm is presented to navigate a robot in an unexplored terrain that is arbitrarily populated with disjoint convex polygonal obstacles in the plane. The navigation process is constituted by a number of traversals; each traversal is from an arbitrary source point to an arbitrary destination point. The proposed algorithm is proven to yield a convergent solution to each path of traversal. Initially, the terrain is explored using a rather primitive sensor, and the paths of traversal made may be suboptimal. The visibility graph that models the obstacle terrain is incrementally constructed by integrating the information about the paths traversed so far. At any stage of learning, the partially learned terrain model is represented as a learned visibility graph, and it is updated after each traversal. It is proven that the learned visibility graph converges to the visibility graph with probability one when the source and destination points are chosen randomly. Ultimately, the availability of the complete visibility graph enables the robot to plan globally optimal paths and also obviates the further usage of sensors.

Navigation planning is one of the most vital aspects of an autonomous mobile robot. The problem of navigation in a completely known obstacle terrain is solved in many cases. Comparatively less number of research results are reported in literature about robot navigation in a completely unknown obstacle terrain. In recent times, this problem is solved by imparting the learning capability to the robot. The robot explores the obstacles terrain using sensors and incrementally builds the terrain model. As the robot keeps navigating, the terrain model becomes more learned and the usage of sensors is reduced. The navigation paths are computed by making use of the existing terrain model. The navigation paths gradually approach global optimality as the learning proceeds. In this paper, we present concurrent algorithms for an autonomous robot navigation in an unexplored terrain. These concurrent algorithms are proven to be free from deadlocks and starvation. The performance of the concurrent algorithms is analyzed in terms of the planning time, travel time, scanning time, and update time. The analysis reveals the need for an efficient data structure for the obstacle terrain in order to reduce the navigation time of the robot, and also to incorporate learning. The modified adjacency list is proposed as a data structure for the spatial graph that represents the obstacle terrain. The time complexities of various algorithms that access, maintain, and update the spatial graph are estimated, and the effectiveness of the the implementation is illustrated.

A recent trend in program methodologies is to derive efficient parallel programs from sequential programs. This study explores the question of transforming a sequential algorithm into an efficient parallel algorithm by considering the problem of balancing binary search trees. The derivation of the parallel algorithm makes use of stepwise refinement. The authors first derive a new iterative balancing algorithm that exploits the similarity of point restructuring required at all the nodes at the same level. From this they derive a parallel algorithm that has time complexity O(1) on anN-processor configuration. This achieves the theoretical limit of speedup possible in a multiprocessor configuration.

Abstract The algorithm proposed by Chang and lyengar to perfectly balance binary search trees has been modified to not only balance but also thread binary search trees. Threads are constructed in the same sequence as normal pointers during the balancing process. No extra workspace is necessary, and the running time is also linear for the modified algorithm. Such produced tree structure has minimal average path length for fast information retrieval, and threads to facilitate more flexible and efficient traversing schemes. Maintenance and manipulation of the data structure are discussed and relevant algorithms given.

The quadtree has recently become a major data structure in image processing. This correspondence investigates ways in which quadtrees may be efficiently stored as a forest of quadtrees and as a new structure we call a compact quadtree. These new structures are called virtual quadtrees because the basic operations we expect to perform in moving about within a quadtree can also be performed on the new representations. Space and time efficiency are investigated and it is shown these new structures often given an improvement in both.

An exposition of statistical techniques in modeling complex systems (single and multiresponse models) that are representative of recent work on modeling systems is provided. The paper begins with several basic concepts related to linear and nonlinear models. The authors then examine four representative techniques of model discrimination which deal with use of nonintrinsic and intrinsic parameters, use of Bayesian methods, and likelihood discrimination. Next they examine multiresponse models with issues dealing with design of experiments for parameter estimation and model discrimination. A case study on sequential model discrimination in multiresponse models is also discussed. Finally an overview on estimating parameters in models of a dynamical system is briefly discussed. The paper concludes with a summary of unresolved issues, and with suggestions on the future role of modeling in the complex situation.