Entanglement distribution is a core function of quantum networks, and the paths used for this purpose are composed of quantum and conventional network components and are routed through physical facility sites. A game theoretic model is formulated for the defense of entanglement paths in a quantum network infrastructure by modeling the correlations and probabilities of reinforcement and failure of its components. A sum-form utility function is used to capture the cost-benefit trade-offs in reinforcing the entanglement path components to defend against their failures and attacks. Under Nash Equilibrium criteria, estimates of survival probabilities of entanglement paths are derived using the parameters and correlations of quantum, conventional, hybrid, and facility components. They provide insights into the dependencies of entanglement paths on its components, including cross-boundary effects of conventional, quantum, and facility components.

Science ecosystems with networked computing systems and physical instruments are increasingly being deployed with a goal to achieve the productivity promised by AI-supported remote automation. In support of these efforts, the virtual infrastructure twins (VITs) have been successfully utilized to develop the orchestration codes for these ecosystems without requiring physical access to expensive instruments, such as electron microscopes. Currently, the utility of such a VIT is severely limited by the computing capacity and capability of the computing system used as its host. Furthermore, codes developed on the VIT typically need to be transferred and refactored for production use, particularly, on high-performance systems with accelerators. In response, we develop a design-to-deployment continuum platform wherein a VIT runs natively on the ecosystem's own computing system, and thereby facilitates the continualin-situtesting and transition of codes for production use. We describe the development and testing of software for remote microscope steering and GPU-based image reconstruction using this platform on a multi-GPU computing system networked to Nion microscopes. We demonstrate a continual transition of steering and reconstruction codes developed under VIT platform to production ecosystem deployment.

Cloud networks utilize virtual connections to connect virtual machines distributed across cloud sites. They are increasingly deployed due to flexible provisioning using software and cost-effectiveness in not requiring to build physical network infrastructure. However, their extensive virtualization makes it unclear how well the established practices of conventional networks translate to them. We study throughput measurements over a Google Cloud network using a matching hardware-emulated conventional network, which provide production and exploratory conditions, respectively. The measurements span connections representing local, cross-continental and around the Earth distances. We study the effects of parallel flows, congestion control algorithms and retransmissions on the network throughput profile expressed as a function of RTT. We compare the throughput profile of Google Cloud network with those of emulated network under various loss conditions, including those too disruptive or expensive in the former. Our analysis based on the concave-convex shape and utilization-concavity coefficients of throughput profiles indicates an overall agreement of performance between the two networks, thereby justifying the use of conventional network emulations to analyze cloud networks. In terms of practical use, our study establishes that BBR and BBRv2 alpha TCP achieve higher throughput compared to loss-based congestion control algorithms under most network configurations, especially, under losses at large RTT.

Electrochemistry workflows utilize various instruments and computing systems to execute workflows consisting of electrocatalyst synthesis, testing and evaluation tasks. The heterogeneity of the software and hardware of these ecosystems makes it challenging to orchestrate a complete workflow from production to characterization by automating its tasks. We propose an autonomous electrochemistry computing platform for a multi-site ecosystem that provides the services for remote experiment steering, real-time measurement transfer, and AI/ML-driven analytics. We describe the integration of a mobile robot and synthesis workstation into the ecosystem by developing custom hub-networks and software modules to support remote operations over the ecosystem’s wireless and wired networks. We describe a workflow task for generating I-V voltammetry measurements using a potentiostat, and a machine learning framework to ensure their normality by detecting abnormal conditions such as disconnected electrodes. We study a number of machine learning methods for the underlying detection problem, including smooth, non-smooth, structural and statistical methods, and their fusers. We present experimental results to illustrate the effectiveness of this platform, and also validate the proposed ML method by deriving its rigorous generalization equations.

The need for real-time processing to enable automated decision making and experimental steering has driven a shift from high-performance computing workflows on a centralized system to a distributed approach that integrates remote data sources, edge devices, and diverse compute facilities. Under this paradigm, data can be processed close to the source where it is generated, thus reducing latency and bandwidth usage. System resilience is thus a key challenge, requiring distributed workflows to survive component failures and to meet stringent quality-of-service requirements, which results in the need to mitigate anomalies such as congestion and low availability of resources. To address these challenges, we propose Diaspora, a unified resilience framework that is inspired by event-driven communication patterns used in public clouds. Specifically, we propose an event fabric that extends across sites, facilities, and computations to provide timely, reliable, and accurate information about data, application, and resource status. On top of the event fabric, we build resilience-enabling services that combine QoS-aware data streaming, resilient data views, resilient compute and data resources, and anomaly detection and prediction, all of which collectively enhance workflow resilience for these scientific cases.

We consider a monitoring scenario of phenomenon using three different streams of measurements whose quality is proportional to their constant inter-arrival times. Each measurement of a stream needs to be binary-classified to reflect the state of interest of the phenomenon. A set of classifiers is separately trained and fused for each stream at its time resolution using measurements collected under known states. We present a machine learning method to fuse the outputs of these fusers to provide a final classification at the finest time resolution. We show that this fused-fusers method provides decisions with likely superior classification probability compared to the best individual classifiers and fused-classifiers. We derive generalization equations that guarantee a superior classification probability of fused-fusers with a confidence probability specified by the classifiers’ generalization equations. We apply these results to study a practical problem of classifying $\mathrm{Pu} / \mathrm{Np}$ target dissolution events at a radiochemical processing facility using gamma spectral measurements of effluent flows.

There is an increased interest in instrument-computing ecosystems (ICEs) that support science workflows empowered by AI-automated experiments and computations in diverse areas. In particular, electrochemistry ICEs are promising for accelerating the design and discovery of electrochemical systems for energy storage and conversion, by automating significant parts of workflows that combine synthesis and characterization experiments with computations. They require the integration of flow controllers, solvent containers, pumps, fraction collectors, and potentiostats, all connected to an electrochemical cell, as illustrated in Fig. 1. These are specialized instruments with custom software that is not originally designed for network integration. We developed network and software solutions for electrochemical workflows that adapt system and instrument settings in real-time for multiple rounds of experiments. In particular, we developed Python wrappers for Application Programming Interfaces (APIs) of instrument commands and Pyro client-server modules that enable them to be executed from remote computers. The entire workflow is orchestrated by a Jupyter notebook running on a remote computer.

The training error of Machine Learning (ML) methods has been extensively used for performance assessment, and its low values have been used as a main justification for complex methods such as estimator fusion and ensembles, and hyper parameter tuning. We present two practical cases where independent tests indicate that the low training error is more of a reflection of over-fitting rather than the generalization ability. We derive a generic form of the generalization equations that separates the training error terms of ML methods from their epistemic terms that correspond to approximation and learnability properties. It provides a framework to separately account for both terms to ensure an overall high generalization performance. For regression estimation tasks, we derive conditions for performance enhancements achieved by hyper parameter tuning, and fusion and ensemble methods over their constituent methods. We present experimental measurements and ML estimates that illustrate the analytical results for the throughput profile estimation of a data transport infrastructure.

Fundamentally and practically, quantum networks and conventional networks are inextricably tied, since the basic quantum protocols such as teleportation require both networks and the conventional network fiber is also used for the quantum network. A Recursive System of Systems (RSOS) model is developed for quantum-conventional (QC) networks by modeling the correlations at various levels based on the failure and attack modes of quantum, conventional and hybrid components and the propagative effects across QC boundaries. A game-theoretic formulation is developed to capture the cost-benefit trade-offs of the provider in defending against component attacks, using sum-form utility functions. By applying the Nash Equilibrium results, the conditions and sensitivity functions of the survival probabilities of a QC network at different levels are derived using the strong dependencies between quantum and conventional infrastructures. The results provide insights into the dependencies between conventional and quantum networks, including cross QC boundary effects in terms of disruption impact of conventional networks on quantum networks, and vice versa.

We propose a framework to develop cyber solutions to support remote steering of science instruments and measurements collection over instrument-computing ecosystems. It is based on provisioning separate data and control connections at the network level, and developing software modules consisting of Python wrappers for instrument commands and Pyro server-client codes that make them available across the ecosystem network. We demonstrate automated measurement transfers and remote steering operations in a microscopy use case for materials research over an ecosystem of Nion microscopes and computing platforms connected over site networks. The proposed framework is currently under further refinement and being adopted to science workflows with automated remote experiments steering for autonomous chemistry laboratories and smart energy grid simulations.

Networked infrastructures of recursively defined systems composed of discrete cyber and physical components are considered. The components of basic systems at the finest levels can be disrupted by cyber or physical means, and can be reinforced to survive at certain costs. A problem of ensuring the infrastructure performance is formulated as a game between a provider and an attacker, who probabilistically choose components to reinforce and attack, respectively. The disruptions of this infrastructure are characterized using the aggregate failure correlation function that specifies the conditional failure probability of the infrastructure given the failure of an individual system at that level. The survival probabilities of basic systems satisfy simple product-form, first-order differential equations expressed in terms of the multiplier functions. The utility functions of the provider and attacker are composed of the reward and cost terms, both expressed in terms of the component reinforcement and attack probabilities. The Nash equilibrium of this game is characterized, along with the sensitivity functions of the survival probabilities of basic systems that highlight their dependence individually on the cost-benefit terms, the correlation functions, and the multiplier functions. These results are illustrated using simplified models of a distributed cloud servers infrastructure, a 5G data network infrastructure, a high performance computing federation, and a smart energy grid infrastructure.

Advanced electron microscopy workflows require an ecosystem of microscope instruments and computing systems possibly located at different sites to conduct remotely steered and automated experiments. Current workflow executions involve manual operations for steering and measurement tasks, which are typically performed from control workstations co-located with microscopes; consequently, their operational tempo and effectiveness are limited. We propose an approach based on separate data and control channels for such an ecosystem of Scanning Transmission Electron Microscopes (STEM) and computing systems, for which no general solutions presently exist, unlike the neutron and light source instruments. We demonstrate automated measurement transfers and remote steering of Nion STEM physical instruments over site networks. We propose a Virtual Infrastructure Twin (VIT) of this ecosystem, which is used to develop and test our steering software modules without requiring access to the physical instrument infrastructure. Additionally, we develop a VIT for a multiple laboratory scenario, which illustrates the applicability of this approach to ecosystems connected over wide-area networks, for the development and testing of software modules and their later field deployment.

A network of virtual machines at cloud server sites connected over virtual IO connections is a flexible, easily deployable, and cost-effective alternative to a physical network infrastructure with dedicated servers connected over leased fiber lines. We study the throughput performance of such a cloud network by collecting measurements over Google Cloud infrastructure spanning multiple continents. To study its ideal performance and impact of packet losses, we utilize its emulation using dedicated servers and connection hardware emulation devices. We compare the measurements over the cloud network to those over its emulation on a testbed. We examine the throughput profiles of both networks as a function of the round trip time and their utilization-concavity coefficients, estimated using measurements for common TCP versions. The throughput profile's concave-convex shape and its coefficient are critical indicators of the network performance, qualitatively and quantitatively, respectively. The results indicate their overall agreement between the production cloud network and its emulation using dedicated connections, and a near optimal throughput performance of the former except for a few under-performing connections. Also, the number of parallel flows is found to be a dominant factor in optimizing the throughput across various conditions and TCP versions.

Softwarization of networked infrastructures combined with containerization of codes promises unprecedented computing capabilities distributed across the federations of computing systems and physical instruments. The development and testing of a software stack that implements these capabilities over an expensive physical production infrastructure is not cost-effective, and in the early stages, may potentially cause service disruptions. To address these aspects, we develop the Virtual Federated Science Instrument Environment (VFSIE), a digital twin of the physical infrastructure that emulates a multi-site federation. Each federated site is emulated using containers and virtual hosts that are connected over local-area networks, and the sites, in turn, are connected over an emulated wide-area network. We describe the framework design and implementation details. We also illustrate its application by emulating a federation of four laboratories that use Jupyter Notebook for computations and the EPICS software system for instrument control.

This article presents an analysis of the method of construction and results for a classifier intended to identify vehicles using low-frequency acoustic data collected by a distributed sensor network. This data is collected as part of a venture intended to explore data analytics and multisensor fusion techniques for the monitoring of activities at a test bed nuclear facility located at Oak Ridge National Laboratory in Oak Ridge, Tennessee. We describe the associated target signature and design a classifier based on a multilayer perceptron, followed by an analysis of its results. We discuss how overall accuracy is not the only consideration in constructing this classifier, and how for this application, it is actually desirable to operate at a lower level of accuracy in exchange for a reduction in the false alarm rate, as well as how this relates to the actual deployment of the classifier in practical use.

Estimates of the power level of a nuclear reactor based on measurements from an independent monitoring sensor system can help in the compliance verification of its declared operations. We present a three-level fusion method to estimate the power level of a nuclear reactor using features derived from infrared, electromagnetic, and acoustic sensor measurements collected in proximity to the reactor. Based on a simplified analytical model of the secondary coolant system of the reactor, we identify partial regression functions of the power level in terms of the temperature difference between inlet and outlet of coolant pipes, and the activity levels of four fans and four pumps, which are estimated as features from the sensor measurements. The power level estimator employs a combination of aggregate and complementary fusion steps at three levels to incorporate the multi-modal features in a structure that reflects the secondary cooling system and its partial regression functions. Using the measurements from a test campaign at an operational reactor, we show that this estimator achieves 3.47% or lower root mean square error under 5-fold cross validation. More generally, these results illustrate a progressive reduction in estimation error as additional modalities are appropriately incorporated, and that the fuser outperforms single modality features and their sub-combinations.

Big data generated by large-scale scientific and industrial applications need to be transferred between different geographical locations for remote storage, processing, and analysis. High-speed dedicated connections provisioned in High-performance Networks (HPNs) are increasingly utilized to carry out such big data transfer. HPN management highly relies on an important capability of performance (mainly throughput) prediction to reserve sufficient bandwidth and meanwhile avoid over-provisioning that may result in unnecessary resource waste. This capability is critical to improving the resource (mainly bandwidth) utilization of dedicated connections and meeting various user requests for data transfer. Conventional methods conduct performance prediction by fitting prior observed transfer history with predefined loss functions, without considering unobservable latent factors such as competing loads on end hosts. Such latent factors also have a significant impact on the application-level data transfer performance, which may result in an inaccurate prediction model. In this paper, we first investigate the impact of latent factors and propose a clustering-based method to eliminate their negative impact on performance prediction. We then develop a robust machine learning-based performance predictor by: i) incorporating the proposed latent factor elimination method into data preprocessing, and ii) adopting a customized domain guided loss function. Extensive experimental results show that our predictor achieves significantly higher prediction accuracy than several other state-of-the-art methods.

High Performance Computing (HPC) is an important method for scientific discovery via large-scale simulation, data analysis, or artificial intelligence. Leadership-class supercomputers are expensive, but essential to run large HPC applications. The Petascale era of supercomputers began in 2008, with the first machines achieving performance in excess of one petaflops, and with the advent of new supercomputers in 2021 (e.g., Aurora, Frontier), the Exascale era will soon begin. However, the high theoretical computing capability (i.e., peak FLOPS) of a machine is not the only meaningful target when designing a supercomputer, as the resources demand of applications varies. A deep understanding of the characterization of applications that run on a leadership supercomputer is one of the most important ways for planning its design, development and operation.

Wide area file transfers play an important role in many science applications. File transfer tools typically deliver the highest performance for datasets with a small number of large files, but many science datasets consist of many small files. Thus it is important to understand the factors that contribute to the decrease in wide area data transfer performance for datasets with many small files. To this end, we (i) benchmark the performance of subsystems involved in end-to-end file transfer between two HPC facilities for a many-file dataset that is representative of production science transfers; (ii) characterize the per-file overhead introduced by different subsystems; (iii) identify potential dependencies and bottlenecks; (iv) study the effectiveness of transferring many files concurrently as a means of reducing per-file overheads; and (v) prototype a prefetching mechanism as an alternative of concurrency to reduce the per-file overhead on source storage system. We show that both concurrency and prefetching can help reduce the per-file overhead significantly. A reasonable level of concurrency combined with prefetching can bring the per-file overhead down to a negligible level.

Radiation source detection is an important problem in homeland security-related applications. Deploying a network of detectors is expected to provide improved detection due to the combined, albeit dispersed, capture area of multiple detectors. Recently, localization-based detection algorithms provided performance gains beyond the simple “aggregated” area as a result of localization being enabled by the networked detectors. We propose the following three localization-based detection approaches: 1) source-attractor radiation detection (SRD); 2) triangulation-based radiation source detection (TriRSD); and 3) the ratio of square distance-based radiation source detection (ROSD-RSD). We use canonical datasets from Domestic Nuclear Detection Office's intelligence radiation sensors systems tests to assess the performance of these methods. Extensive results illustrate that SRD outperforms TriRSD and ROSD-RSD, and other existing detection algorithms based on the sequential probability ratio test and maximum likelihood estimation in terms of both false alarm and detection rates.

Big data transfer in next-generation scientific applications is now commonly carried out over dedicated channels in high-performance networks (HPNs), where transport protocols play a critical role in maximizing application-level throughput. Optimizing the performance of these protocols is challenging: i) transport protocols perform differently in various network environments, and the protocol choice is not straightforward; ii) even for a given protocol in a given environment, different parameter settings of the protocol may lead to significantly different performance and oftentimes the default setting does not yield the best performance. However, it is prohibitively time-consuming to conduct exhaustive transport profiling due to the large parameter space. In this paper, we propose a PRofiling Optimization Based DAta Transfer Advisor (ProbData) to help end users determine the most effective transport method with the most appropriate parameter settings to achieve satisfactory performance for big data transfer over dedicated connections in HPNs. ProbData employs a fast profiling scheme based on the Simultaneous Perturbation Stochastic Approximation algorithm, namely, FastProf, to accelerate the exploration of the optimal operational zones of various transport methods to improve profiling efficiency. We first present a theoretical background of the optimized profiling approach in ProbData and then detail its design and implementation. The advising procedure and performance benefits of FastProf and ProbData are illustrated and evaluated by both extensive emulations based on real-life performance measurements and experiments over various physical connections in existing production HPNs.

We abstract the accuracy performance of any fuser into a fusion quality measure that is within the range [0, 1] and monotonically decreases with increasing errors. Although there are many possible ways to map the actual error to this quality measure, we adopt a mapping function consisting of both concave and convex regions and its parameters can be tuned based on system design requirements. The effect of communication loss over the links from the sensors, where estimates are generated, to the fuser is then considered, and based on the variations of the quality measure with loss, we define the overall fuser utility that characterizes the resilience of a fuser with increasingly adverse communication constraints. Tracking examples are shown to demonstrate the comparative quality and utility performances of several closed-form fusers.

This research studies defense strategies of an interdependent system in the face of rational attacks. We propose a sequential game between an attacker and a defender for an interdependent System of Systems (SoS) to explore the effect of interdependency on an optimal defense strategy. We develop an algorithm of backward induction to obtain the Nash equilibrium of the game. The attacker is the first mover as he applies an attack strategy on constituent systems that maximizes his utility. The defender observes and responds by a defense strategy that maximizes her utility. Both players' utilities are expressed as the difference between a player's reward due to SoS functionality (dysfunctionality) and the cost of the action. The sensitivity analysis compares the effects of different parameters on the attacker's and defender's strategies such as the effectiveness of defense (attack), the unit cost of defense (attack) and the interdependency level of constituent systems.

We consider a class of Recursive System of Systems (RSoS), wherein systems are recursively defined and the basic systems at finest level are composed of discrete cyber and physical components. This formulation captures the models of systems that are adaptively refined to account for their varied structure, such as sites of a heterogeneous distributed computing infrastructure. The components can be disrupted by cyber or physical means, and can also be suitably reinforced to survive the attacks. We characterize the disruptions at each level of recursion using aggregate failure correlation functions that specify the conditional failure probability of RSoS given the failure of an individual system at that level. At finest levels, the survival probabilities of basic systems satisfy simple product-form, first-order differential conditions using the multiplier functions, which generalize conditions based on contest success functions and statistical independence of component survival probabilities. We formulate the problem of ensuring the performance of RSoS as a game between an attacker and a provider, each with a utility function composed of a survival probability term and a cost term, both expressed in terms of the number of basic system components attacked and reinforced. We derive sensitivity functions at Nash Equilibrium that highlight the dependence of survival probabilities of systems on cost terms, correlation functions, and their partial derivatives. We apply these results to a simplified model of distributed high-performance computing infrastructures.

Target detection is one fundamental problem in many sensor network-based applications, and is typically tackled in two separate stages for sensor deployment and data fusion. We propose an integrated solution, referred to as SSEM, which combines 2-level clustering-based sensor deployment and Source Strength Estimate Map-based data fusion for the detection of a single static or moving target. SSEM conducts the first level of clustering to determine a sensor deployment scheme and the second level of clustering to divide the deployed sensors into multiple subsets. For each sensor, the source strength is estimated at each grid point of the entire region based on a signal attenuation model, and for each subset of sensors, the target location is estimated using a strength distribution map-based statistical analysis method. A final detection decision is made by thresholding the clustering degree of the target location estimates computed by all subsets of sensors. Compared with traditional grid-based target detection methods, SSEM significantly reduces the computation complexity and improves the detection performance through an integrated optimization strategy. Extensive simulation results show the performance superiority of the proposed solution over several well-known methods for target detection.

Wide area data transfers play an important role in many science applications but rely on expensive infrastructure that often delivers disappointing performance in practice. In response, we present a systematic examination of a large set of data transfer log data to characterize transfer characteristics, including the nature of the datasets transferred, achieved throughput, user behavior, and resource usage. This analysis yields new insights that can help design better data transfer tools, optimize networking and edge resources used for transfers, and improve the performance and experience for end users. Our analysis shows that (i) most of the datasets as well as individual files transferred are very small; (ii) data corruption is not negligible for large data transfers; and (iii) the data transfer nodes utilization is low. Insights gained from our analysis suggest directions for further analysis.

The provisioning of network connections for data transfers that provide quality of service (QoS) over research and education (R&E) networks is currently performed by network operators. For network connections that span multiple administrative domains, network operators have to reach agreements on reservation requirements. As a result, a network reservation request may take from days to weeks to be provisioned. To improve provisioning times and the success rate of multidomain network reservations, we designed and implemented an application-aware orchestration framework for multidomain R&E networks. This framework leverages latest developments in software-defined networking to automate network provisioning in order to democratize access to network reservation through novel APIs. We present the design, implementation, and evaluation of our application-aware orchestration framework. We evaluate our system using Mininet and demonstrate that it provisions 49% more reservations than current state-of-the-art systems within seconds of receiving a request.

Bandwidth reservation has been increasingly used to provide QoS for various network applications. To accommodate a high-priority bandwidth reservation request (BRR), the bandwidth scheduler sometimes needs to preempt existing bandwidth reservations that have been made for BRRs with a lower priority, which is traditionally known as connection preemption. When such preemption is unavoidable, one primary goal of bandwidth scheduling is to minimize the disruption to existing reservations. In this paper, we study the problem of bandwidth reservation preemption for two types of BRRs, bandwidth- and data transfer- oriented, respectively, on one given link of the scheduling network with two different objectives: (i) minimize the number and then the total bandwidth of existing bandwidth reservations to be preempted, and (ii) minimize the total bandwidth and then the number of existing bandwidth reservations to be preempted. We prove these four problems to be NP-complete and propose a heuristic algorithm for each. We also design baseline heuristic algorithms for performance comparison. Extensive simulation results show that the proposed heuristic algorithms outperform those in comparison.

File transfers between the decentralized storage sites over dedicated wide-area connections are becoming increasingly important in high-performance computing and big data scenarios. Designing such scientific workflows for large file transfers is extremely challenging as they depend on the file, I/O, host, and local- and wide-area network subsystems, and their interactions. To gain insights into file-transfer rate profiles, we develop polynomial, bagging, and boosting regression models for Lustre and XFS file transfer measurements, which are collected using XDD over a suite of 10 Gbps connections with 0-366 ms round trip times (RTTs). In addition to overall trends and analytics, these regressions also provide file-transfer rate estimates for RTTs and number of parallel flows at which measurements might not have been collected. They show that bagging and boosting techniques provide closer data fits than the polynomial regression. We develop probabilistic bounds on the generalization error of these methods, which combined with the cross-validation error establish that former two are more accurate estimators than the polynomial regression. In addition, we present a method to efficiently determine the number of parallel flows to achieve a peak file-transfer rate using fewer than full sweep measurements; in our measurements, the peak is achieved in 96% of cases with 15-25% of measurements of a full sweep.

Multi-resolution grid computation is a technique used to speed up source localization with a Maximum Likelihood Estimation (MLE) algorithm. In the case where the source is located midway between grid points, the MLE algorithm may choose an incorrect location, causing following iterations of the search to close in on an area that does not contain the source. To address this issue, we propose a modification to multi-resolution MLE that expands the search area by a small percentage between two consecutive MLE iterations. At the cost of slightly more computation, this modification allows consecutive iterations to accurately locate the target over a larger portion of the field than a standard multi-resolution localization. The localization and computation performance of our approach is compared to both standard multi-resolution and single-resolution MLE algorithms. Tests are performed using seven data sets representing different scenarios of a single radiation source located within an indoor field of detectors. Results show that our method (i) significantly improves the localization accuracy in cases that caused initial grid selection errors in traditional MLE algorithms, (ii) does not have a negative impact on the localization accuracy in other cases, and (iii) requires a negligible increase in computation time relative to the increase in localization accuracy.

Large-scale infrastructures are critical to economic and social development, and hence their continued performance and security are of high national importance. Such an infrastructure often is a system of systems, and its functionality critically depends on the inherent robustness of its constituent systems and its defense strategy for countering attacks. Additionally, interdependencies between the systems play another critical role in determining the infrastructure robustness specified by its survival probability. In this paper, we develop game-theoretic models between a defender and an attacker for a generic system of systems using inherent parameters and conditional survival probabilities that characterize the interdependencies. We derive Nash Equilibrium conditions for the cases of interdependent and independent systems of systems under sum-form utility functions. We derive expressions for the infrastructure survival probability that capture its dependence on cost and system parameters, and also on dependencies that are specified by conditional probabilities. We apply the results to cyber-physical systems which show the effects on system survival probability due to defense and attack intensities, inherent robustness, unit cost, target valuation, and interdependencies.

In this paper, we consider a scenario where sensors are deployed over a large geographical area for tracking a target with circular nonlinear constraints on its motion dynamics. The sensor state estimates are sent over long-haul networks to a remote fusion center for fusion. We are interested in different ways to incorporate the constraints into the estimation and fusion process in the presence of communication loss. In particular, we consider closed-form projection-based solutions, including rules for fusing the estimates and for incorporating the constraints, which jointly can guarantee timely fusion often required in realtime systems. We test the performance of these methods in the long-haul tracking environment using a simple example.

We consider an infrastructure consisting of a network of systems each composed of discrete components that can be reinforced at a certain cost to guard against attacks. The network provides the vital connectivity between systems, and hence plays a critical, asymmetric role in the infrastructure operations. We characterize the system-level correlations using the aggregate failure correlation function that specifies the infrastructure failure probability given the failure of an individual system or network. The survival probabilities of systems and network satisfy first-order differential conditions that capture the component-level correlations. We formulate the problem of ensuring the infrastructure survival as a game between an attacker and a provider, using the sum-form and product-form utility functions, each composed of a survival probability term and a cost term. We derive Nash Equilibrium conditions which provide expressions for individual system survival probabilities, and also the expected capacity specified by the total number of operational components. These expressions differ only in a single term for the sum-form and product-form utilities, despite their significant differences. We apply these results to simplified models of distributed cloud computing infrastructures.

ide-area data transfers in high-performance computing infrastructures are increasingly being carried over dynamically provisioned dedicated network connections that provide high capacities with no competing traffic. We present extensive TCP throughput measurements and time traces over a suite of physical and emulated 10 Gbps connections with 0-366 ms round-trip times (RTTs). Contrary to the general expectation, they show significant statistical and temporal variations, in addition to the overall dependencies on the congestion control mechanism, buffer size, and the number of parallel streams. We analyze several throughput profiles that have highly desirable concave regions wherein the throughput decreases slowly with RTTs, in stark contrast to the convex profiles predicted by various TCP analytical models. We present a generic throughput model that abstracts the ramp-up and sustainment phases of TCP flows, which provides insights into qualitative trends observed in measurements across TCP variants: (i) slow-start followed by well-sustained throughput leads to concave regions; (ii) large buffers and multiple parallel streams expand the concave regions in addition to improving the throughput; and (iii) stable throughput dynamics, indicated by a smoother Poincare map and smaller Lyapunov exponents, lead to wider concave regions. These measurements and analytical results together enable us to select a TCP variant and its parameters for a given connection to achieve high throughput with statistical guarantees.

Dedicated wide-area network connections are increasingly employed in high-performance computing and big data scenarios. One might expect the performance and dynamics of data transfers over such connections to be easy to analyze due to the lack of competing traffic. However, non-linear transport dynamics and end-system complexities (e.g., multi-core hosts and distributed filesystems) can in fact make analysis surprisingly challenging. We present extensive measurements of memory-tomemory and disk-to-disk file transfers over 10 Gbps physical and emulated connections with 0-366 ms round trip times (RTTs). For memory-to-memory transfers, profiles of both TCP and UDT throughput as a function of RTT show concave and convex regions; large buffer sizes and more parallel flows lead to wider concave regions, which are highly desirable. TCP and UDT both also display complex throughput dynamics, as indicated by their Poincarέmaps and Lyapunov exponents. For diskto-disk transfers, we determine that high throughput can be achieved via a combination of parallel I/O threads, parallel network threads, and direct I/O mode. Our measurements also show that Lustre filesystems can be mounted over long-haul connections using LNet routers, although challenges remain in jointly optimizing file I/O and transport method parameters to achieve peak throughput.

The network infrastructures have been rapidly upgraded in many high-performance networks (HPNs). However, such infrastructure investment has not led to corresponding performance improvement in big data transfer, especially at the application layer, largely due to the complexity of optimizing transport control on end hosts. We design and implement ProbData, a PRofiling Optimization Based DAta Transfer Advisor, to help users determine the most effective data transfer method with the most appropriate control parameter values to achieve the best data transfer performance. ProbData employs a profiling optimization-based approach to exploit the optimal operational zone of various data transfer methods in support of big data transfer in extreme-scale scientific applications. We present a theoretical framework of the optimized profiling approach employed in ProbData as well as its detailed design and implementation. The advising procedure and performance benefits of ProbData are illustrated and evaluated by proof-of-concept experiments in real-life networks.

The transfer of big data is increasingly supported by dedicated channels in high-performance networks, where transport protocols play an important role in maximizing application-level throughput and link utilization. The performance of transport protocols largely depend on their control parameter settings, but it is prohibitively time consuming to conduct an exhaustive search in a large parameter space to find the best set of parameter values. We propose FastProf, a stochastic approximation-based transport profiler, to quickly determine the optimal operational zone of a given data transfer protocol/method over dedicated channels. We implement and test the proposed method using both emulations based on real-life performance measurements and experiments over physical connections with short (2ms) and long (380ms) delays. Both the emulation and experimental results show that FastProf significantly reduces the profiling overhead while achieving a comparable level of end-to-end throughput performance with the exhaustive search-based approach.

Wide-area data transfers in high-performance computing and big data scenarios are increasingly being carried over dedicated network connections that provide high capacities at low loss rates. UDP-based transport protocols are expected to be particularly well-suited for such transfers but their performance is relatively unexplored over a wide range of connection lengths, compared to TCP over shared connections. We present extensive throughput measurements of UDP-based Data Transfer (UDT) over a suite of physical and emulated 10 Gbps connections. In sharp contrast to current UDT analytical models, these measurements indicate much more complex throughput dynamics that are sensitive to the connection modality, protocol parameters, and round-trip times. Lyapunov exponents estimated from the Poincaré maps of UDT traces clearly indicate regions of instability and complex dynamics. We propose a simple model based on the ramp-up and sustainment regimes of a generic transport protocol, which qualitatively illustrates the dominant monotonicity and concavity properties of throughput profiles and relates them to Lyapunov exponents. These measurements and analytical results together enable us to comprehensively evaluate UDT performance and select parameters to achieve high throughput, and they also provide guidelines for designing effective transport protocols for dedicated connections.

In recent years, there has been a steady growth in network bandwidths. This is especially true in scientific and big data environments, where high bandwidth-delay products (BDPs) are common. It is well-understood that legacy TCP (e.g. TCP Reno) is not appropriate for such environments, and several TCP variants were developed to address this shortcoming. These variants, including CUBIC, STCP, and H-TCP, have been studied in some empirical contexts, and some analytical models exist for CUBIC and STCP. However, since these studies were conducted, BDPs further increased, and new bulk data transfer methods have emerged that utilize parallel TCP streams. In view of these new developments, it is imperative to revisit the question: `Which congestion control algorithms are best adapted to current networking environments?' In order to answer this question, (i) we create a general theoretical framework within which to develop mathematical models of TCP variants that account for finite buffer sizes, maximum window constraints, and parallel TCP streams; (ii) we validate the models using measurements collected over a high-bandwidth testbed and achieve low prediction errors; (iii) we find that CUBIC and H-TCP outperform STCP, especially when multiple streams are used.

In a long-haul sensor network, sensors are remotely deployed over a large geographical area to perform certain tasks, such as target tracking. In this paper, we study the scenario where sensors take measurements of one or more dynamic targets and send state estimates of the targets to a fusion center via satellite links. The severe loss and delay inherent over the satellite channels reduce the number of estimates successfully arriving at the fusion center, thereby limiting the potential fusion gain and resulting in suboptimal accuracy performance of the fused estimates. In addition, the errors in target-sensor data association can also degrade the estimation performance. To mitigate the effect of imperfect communications on state estimation and fusion, we consider retransmission and retrodiction. The system adopts certain retransmission-based transport protocols so that lost messages can be recovered over time. Moreover, retrodiction/smoothing techniques are applied so that the chances of incurring excess delay due to retransmission are greatly reduced. We analyze the extent to which retransmission and retrodiction can improve the performance of delay-sensitive target tracking tasks under variable communication loss and delay conditions. Simulation results of a ballistic target tracking application are shown in the end to demonstrate the validity of our analysis.

Smart meters are integral to demand response in emerging smart grids, by reporting the electricity consumption of users to serve application needs. But reporting real-time usage information for individual households raises privacy concerns. Existing techniques to guarantee differential privacy (DP) of smart meter users either are not fault tolerant or achieve (possibly partial) fault tolerance at high communication overheads. In this paper, we propose a fault-tolerant protocol for smart metering that can handle general communication failures while ensuring DP with significantly improved efficiency and lower errors compared with the state of the art. Our protocol handles fail-stop faults proactively by using a novel design of future ciphertexts, and distributes trust among the smart meters by sharing secret keys among them. We prove the DP properties of our protocol and analyze its advantages in fault tolerance, accuracy, and communication efficiency relative to competing techniques. We illustrate our analysis by simulations driven by real-world traces of electricity consumption.

In software-defined networks (SDNs) with multiple logically centralized controllers, it is challenging to maintain accurate link-state information, perceived as a global network view (GNV), at every controller in a consistent manner. Since online bandwidth scheduling, where every successful reservation triggers a GNV update at the controller, is expensive in terms of overhead, most networks adopt periodic scheduling with infrequent link-state information update, which, however, is the main cause of such inaccuracy/inconsistency. Even if up-to-date information is available, a controller does not always make frequent updates as it may cause network convergence issues. Consequently, bandwidth scheduling in such environments may lead to blocking or rejection of reservation requests, which deteriorates as the level of inaccuracy/inconsistency increases. To minimize such service disruptions, we formulate bandwidth scheduling in SDNs as an optimization problem and propose a randomization-based routing scheme to schedule bandwidth reservation requests such that the total number of blocked requests due to the inaccurate/inconsistent GNV is minimized. Simulation results show that the proposed solution exhibits a superior performance over existing methods.

In long-haul sensor networks, remote sensors are deployed to cover a large geographical area, such as a continent or the entire globe. Related applications can be found in military surveillance, air traffic control, greenhouse gas emission monitoring, and global cyber attack detection, among others. In this paper, we consider target monitoring and tracking using a long-haul sensor network, wherein the state and covariance estimates are sent from the sensors to a fusion center that generates a fused state estimate. Long-haul communications over submarine fibers and satellite links are subject to long latencies and/or high loss rates, which lead to lost or out-of-order messages. These in turn may significantly degrade the fusion performance: Fusing fewer state estimates may compromise the accuracy of the fused state, whereas waiting for all estimates to arrive may compromise its timeliness. We propose an online selective linear fusion method to fuse the state estimates based on projected information contribution from the pending data. Using both prediction and retrodiction techniques, our scheme enables the fusion center to opportunistically make decisions on when to fuse the estimates, thereby achieving a balance between accuracy and timeliness of the fused state. Simulation results of a target tracking application show that our scheme yields accurate and timely fused estimates under variable communications delay and loss conditions.

Smart meters are integral to demand response in emerging smart grids, by reporting the electricity consumption of users to serve application needs. But reporting real-time usage information for individual households raises privacy concerns. Existing techniques to guarantee differential privacy (DP) of smart meter users either are not fault tolerant or achieve (possibly partial) fault tolerance at high communication overheads. In this paper, we propose a fault-tolerant protocol for smart metering that can handle general communication failures while ensuring DP with significantly improved efficiency and lower errors compared with the state of the art. Our protocol handles fail-stop faults proactively by using a novel design of future ciphertexts, and distributes trust among the smart meters by sharing secret keys among them. We prove the DP properties of our protocol and analyze its advantages in fault tolerance, accuracy, and communication efficiency relative to competing techniques. We illustrate our analysis by simulations driven by real-world traces of electricity consumption.

Mobility traces of people and vehicles have been collected and published to assist the design and evaluation of mobile networks, such as large-scale urban sensing networks. Although the published traces are often made anonymous in that the true identities of nodes are replaced by random identifiers, the privacy concern remains. This is because in real life, nodes are open to observations in public spaces, or they may voluntarily or inadvertently disclose partial knowledge of their whereabouts. Thus, snapshots of nodes' location information can be learned by interested third parties, e.g., directly through chance/engineered meetings between the nodes and their observers, or indirectly through casual conversations or other information sources about people. In this paper, we investigate how an adversary, when equipped with a small amount of the snapshot information termed as side information, can infer an extended view of the whereabouts of a victim node appearing in an anonymous trace. Our results quantify the loss of victim nodes' privacy as a function of the nodal mobility, the inference strategies of adversaries, and any noise that may appear in the trace or the side information. Generally, our results indicate that the privacy concern is significant in that a relatively small amount of side information is sufficient for the adversary to infer the true identity (either uniquely or with high probability) of a victim in a set of anonymous traces. For instance, an adversary is able to identify the trace of 30%-50% of the victims when she has collected 10 pieces of side information about a victim.

Long-haul sensor networks are deployed in a wide range of applications from national security to environmental monitoring. We consider target tracking over a long-haul sensor network, wherein state and covariance estimates are sent from sensors to a fusion center that generates a fused state. Fusion serves as a viable means to improve the estimation performance to meet the system requirement on accuracy and delay. Communications over the long-haul links, such as submarine fibers and satellite links, is subject to long latencies and high loss rates that lead to many lost or out-of-order messages and may significantly degrade the fusion performance. We propose an online selective fuser to combine the received state estimates based on estimated information contribution from the pending data. By concurrently using prediction and retrodiction, the fuser opportunistically makes timely decisions to achieve a balance between accuracy and timeliness of the fused estimate. Simulation results show that our method effectively maintains high levels of fusion performance under various communication delay and loss conditions.

In a long-haul sensor network, sensors are remotely deployed over a large geographical area to perform certain tasks. We consider a class of such networks where sensors take measurements of one or more dynamic targets and send state estimates of the target(s) to a fusion center via satellite links. The severe loss and delay inherent over the satellite channels render insufficient the number of estimates successfully arriving at the fusion center, thereby limiting the potential fusion gain and resulting in suboptimal accuracy performance of the fused estimates. The system can adopt certain retransmission-based transport protocols so that lost messages can be recovered over time. However, excess delay may be incurred that can potentially violate the deadline for reporting the estimate. For many applications, though, retrodiction/smoothing techniques can be applied so that the chances of incurring such excess delay are greatly reduced. In this work, we analyze the extent to which retrodiction, along with message retransmission, can improve the performance of delay-sensitive state estimation tasks. Results of numerical and simulation studies of an illustrative example and a ballistic target tracking application are shown in the end to demonstrate the validity of our analysis.

We present a robust localization algorithm for multiple radiation sources using a network of sensors under random underlying physical processes and measurement errors. The proposed solution uses a hybrid formulation of particle filter and mean-shift techniques to achieve several important features that address major challenges faced by existing localization algorithms. First, our algorithm is able to maintain a constant number of estimation (source) parameters even as the number of radiation sources K increases. In existing algorithms, the number of estimation parameters is proportional to K and thus the algorithm complexity grows exponentially with K. Second, to decide the number of sources K, existing algorithms either require the information to be known in advance or rely on expensive statistical estimations that do not scale well with K. Instead, our algorithm efficiently learns the number of sources from the estimated source parameters. Third, when obstacles are present, our algorithm can exploit the obstacles to achieve better isolation between the source signatures, thereby increasing the localization accuracy in complex deployment environments. In contrast, incompletely specified obstacles will significantly degrade the accuracy of existing algorithms due to their unpredictable effects on the source signatures. We present extensive simulation results to demonstrate that our algorithm has robust performance in complex deployment environments, and its efficiency is scalable to many radiation sources in these environments.

A number of networked infrastructure systems rely on both cyber and physical components for their continued operation. We present graph models for a class of such systems, wherein both cyber and physical parts must be made robust, possibly using different methods at different costs. We present methods for ensuring that the system survives, with specified probability PS, cyber and physical degradations due to natural, incidental, or intentional factors. Based on first and second order statistics of the profiles of passive degradations, we present methods to compute the robustness levels needed to ensure PS. Then, we consider the case of intentional compromises, where cost profiles of the provider and compromiser are known to various extents. We present a game-theoretic formulation based on provider and disrupter cost and benefit functions, and their mutual knowledge. We present strategies and performance boundaries of these formulations in ensuring PS under utility functions that are sums of terms corresponding to infrastructure survival and cyber-physical costs.

Many computation-intensive scientific applications feature complex workflows of distributed computing modules with intricate execution dependencies. Such scientific workflows must be mapped and executed in shared environments to support distributed scientific collaborations. We formulate workflow mapping as an optimization problem for latency minimization, whose difficulty essentially arises from the topological matching nature in the spatial domain, which is further compounded by the resource sharing complicacy in the temporal dimension. We conduct a rigorous analysis of the resource sharing dynamics in workflow executions, which constitutes the base for a workflow mapping algorithm to minimize the end-to-end delay. The correctness of the dynamics analysis is verified in comparison with an approximate solution, a dynamic system simulation program, and a real network deployment, and the performance superiority of the proposed mapping solution is illustrated by extensive comparisons with existing methods using both simulations and experiments.

Several research and production high-performance networks now provision multi-Gbps dedicated channels to support large data transfers in network-intensive applications. However, end users have not seen a corresponding increase in application throughput mainly because traditional end-to-end transport methods are not optimized for such connections. New congestion or flow control mechanisms are desirable to meet the challenges brought by dedicated connections to transport protocol design. The advent and proliferation of multi-core processors make it now possible to improve application throughput by providing multiple processing and networking resources to a single data transfer. Based on the existing PLUT method, we propose a new transport method, Para-PLUT, which utilizes multiple parallel UDP connections to take advantage of the full power of multicore processors for maximum aggregate goodput. We implement and test Para-PLUT in a local dedicated network testbed and the experimental results illustrate its superior performance over several existing methods.

We propose a steepest descent method to compute optimal control parameters for balancing between multiple performance objectives in stateless stochastic scheduling, wherein the scheduling decision is effected by a simple constant-time coin toss operation only. We apply our method to the scheduling of a mobile sensor's coverage time among a set of points of interest (PoIs). The coverage algorithm is guided by a Markov chain wherein the sensor at PoI i decides to go to the next PoI j with transition probability pij . We use steepest descent to compute the transition probabilities for optimal tradeoff between two performance goals concerning the distributions of per-PoI coverage times and exposure times, respectively. We also discuss how other important goals such as energy efficiency and entropy of the coverage schedule can be addressed. For computational efficiency, we show how to optimally adapt the step size in steepest descent to achieve fast convergence. However, we found that the structure of our problem is complex in that there may exist surprisingly many local optima in the solution space, causing basic steepest descent to get stuck easily at a local optimum. To solve the problem, we show how proper incorporation of noise in the search process can get us out of the local optima with high probability. We provide simulation results to verify the accuracy of our analysis, and show that our method can converge to the globally optimal control parameters under different assigned weights to the performance goals and different initial parameters.

Mobility traces of people and vehicles have been collected and published to assist the design and evaluation of mobilee networks, such as large-scale urban sensing networks. Although the published traces are often made anonymous in that the true identities of nodes are replaced by random identifiers, the privacy concern remains. This is because in real life, nodes are open to observations in public spaces, or they may voluntarily or inadvertently disclose partial knowledge of their whereabouts. Thus, snapshots of nodes' location information can be learned by interested third parties, e.g., directly through chance/engineered meetings between the nodes and their observers, or indirectly through casual conversations or other information sources about people. In this paper, we investigate how an adversary, when equipped with a small amount of the snapshot information termed as side information, can infer an extended view of the whereabouts of a victim node appearing in an anonymous trace. Our results quantify the loss of victim nodes' privacy as a function of the nodal mobility (captured in both real and synthetic traces), the inference strategies of adversaries, and any noise that may appear in the trace or the side information. Generally, our results indicate that the privacy concern is significant in that a relatively small amount of side information is sufficient for the adversary to infer the true identity (either uniquely or with high probability) of a victim in a set of anonymous traces.

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 present a computational geometry method for the problem of estimating the location of a source in the plane using measurements of distance-differences to it. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance-difference as the objective function. We show the correctness of this method by establishing the unimodality of directional derivative of the objective function within each of a small number of regions of the plane, wherein a suitable binary search is supported. The computational complexity of this method is O (log (1/ γ )), where the computed solution is guaranteed to be within a distance γ of the actual location of the source. We present simulation results to compare this method with existing DTOA localization methods.

We analyze the quality of monitoring (QoM) of stochastic events by a periodic sensor which monitors a point of interest (PoI) for q time every p time. We show how the amount of information captured at a PoI is affected by the proportion q/p , the time interval p over which the proportion is achieved, the event type in terms of its stochastic arrival dynamics and staying times and the utility function. The periodic PoI sensor schedule happens in two broad contexts. In the case of static sensors, a sensor monitoring a PoI may be periodically turned off to conserve energy, thereby extending the lifetime of the monitoring until the sensor can be recharged or replaced. In the case of mobile sensors, a sensor may move between the PoIs in a repeating visit schedule. In this case, the PoIs may vary in importance, and the scheduling objective is to distribute the sensor's coverage time in proportion to the importance levels of the PoIs. Based on our QoM analysis, we optimize a class of periodic mobile coverage schedules that can achieve such proportional sharing while maximizing the QoM of the total system.

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.

Supporting visualization pipelines over wide-area networks is critical to enabling large-scale scientific applications that require visual feedback to interactively steer online computations. We propose a remote computational steering system that employs analytical models to estimate the cost of computing and communication components and optimizes the overall system performance in distributed environments with heterogeneous resources. We formulate and categorize the visualization pipeline configuration problems for maximum frame rate into three classes according to the constraints on node reuse or resource sharing, namely no, contiguous, and arbitrary reuse. We prove all three problems to be NP-complete and present heuristic approaches based on a dynamic programming strategy. The superior performance of the proposed solution is demonstrated with extensive simulation results in comparison with existing algorithms and is further evidenced by experimental results collected on a prototype implementation deployed over the Internet.

Several research and production networks now provide multiple Gbps dedicated connections to meet the demands of large data transfers over wide-area networks. Application throughputs, however, were not able to match these rates because the traditional transport methods have not been optimized for suc

Detection of a nuclear radioactive source is considered using a parallel sensor network architecture and a fusion center. A Poisson-Gamma hierarchical model is used to represent the distribution of the count data received by the sensors. Local sensors are assumed to be single threshold binary quantizers that send a vector of sensor decisions over time to the fusion center for global decision-making. Using the developed count model, a generalized likelihood ratio test (GLRT) using a restricted range MLE (RMLE) is proposed to declare the global decision. The performance improvement resulting from using the restricted range MLE over the unrestricted MLE while implementing the GLRT is depicted using simulated as well as real data collected from a test-bed using radiation sensors. Using bootstrap, 95% confidence bounds on the ROC curves, evaluated using real data, are obtained.

Sensor network lifetime is largely affected by the energy consumption for data transmission from sensor nodes to a base station. We generalize and solve the problems of deploying multiple base stations in sensor networks using one-hop and multi-hop communication models to maximize network lifetime. Under the one-hop communication model, the sensors far away from base stations always deplete their energy much faster than others. We propose an optimal solution for small-scale networks and a heuristic approach for large-scale ones based on the smallest enclosing circle algorithm that deploys a base station at the geometric center of each cluster. Under the multi-hop communication model, both the base station locations and the data routing scheme need to be considered in maximizing network lifetime. We propose an iterative algorithm based on rigorous mathematical derivations and use linear programming to compute the optimal routing path for benchmark purposes. Extensive simulation results show superior network lifetime performance of the proposed deployment algorithms in comparison with existing ones.

We consider the placement of sensors to detect propagative sources where the sensing area of each sensor is anisotropic and arbitrarily-shaped due to the terrain and meteorological conditions. The propagation and detection times are non-negligible due to the propagation of source effects through space at a slow speed. We formulate the problem as placing the minimum number of sensors to ensure a detection time T and the coverage utility C. Both the sensing areas of sensors and the utility function U(ldr) are chosen to capture the environmental factors and the population distribution. We show this problem to be NP-hard, and present heuristic algorithms for 1-coverage and fc-coverage by adopting exiting methods. We evaluate the proposed algorithms in the realistic setting of Port of Memphis where the objective is to protect the population against chemical leaks or attacks. We utilize the SCIPUFF dispersion model to determine the sensing areas by accounting for the terrain and meteorological conditions, and use the real-life population distribution as the utility function. Based on empirical study, we make several important observations.

Several research and production high-performance networks now provision multi-Gbps dedicated channels to meet the demands of large data transfers in network-intensive applications. However, end users have not seen corresponding increase in application throughput mainly because (i) the existence of high-bandwidth links has shifted the congestion from the network to end hosts, and (ii) such congestion is not well handled by TCP's Additive Increase and Multiplicative Decrease algorithm. Particularly, due to the sharing with unknown background workloads, the data receiver oftentimes lacks sufficient system resources to process the arriving packets, hence leading to significant packet drops at the end system. This paper proposes a UDP-based transport method that incorporates a performance-adaptive flow control mechanism to regulate the activities of both the sender and receiver in response to system dynamics to achieve high throughput. We construct a mathematical model for the socket receive buffer and data receiving process, and employ a profiling-based method to estimate the initial receiving bottleneck rate, which is dynamically adjusted and sent back to the sender for source rate control. The sending rate is stabilized at the estimated bottleneck rate based on a stochastic approximation algorithm. We test the proposed method on a local dedicated connection and the experimental results illustrate its superior performance over existing methods.

We analyze the ability of a stochastic coverage algorithm to achieve both accurate threat-based coverage and effective information capture. When mobile sensors are used to cover the region over time, the goal of threat-based coverage is to allocate the sensors' coverage time between the subregions in proportion to their threat levels. We show that, in contrast to prior results on mobile coverage for maximizing simple event capture, limiting mobility by strategically pausing the sensor is important for threat-based coverage of physical world monitoring. Besides being energy efficient, pausing has two desirable effects. First, it can improve the accuracy of the threat-based coverage, in particular, the accuracy increases monotonically with a pause time parameter, and a large enough parameter will ensure exact matching of the sensor's coverage profile with the region's threat profile. Second, diverse natural phenomena require a non-negligible sensing time to overcome statistical uncertainties posed by the random nature of the phenomena. Suitable pausing allows a subregion to be observed long enough for reliable results.

Mobile sensors can be used to effect complete coverage of a surveillance area for a given threat over time, thereby reducing the number of sensors necessary. The surveillance area may have a given threat profile as determined by the kind of threat, and accompanying meteorological, environmental, and human factors. In planning the movement of sensors, areas that are deemed higher threat should receive proportionately higher coverage. We propose a coverage algorithm for mobile sensors to achieve a coverage that will match - over the long term and as quantified by an RMSE metric - a given threat profile. Moreover, the algorithm has the following desirable properties: 1) stochastic, so that it is robust to contingencies and makes it hard for an adversary to anticipate the sensor's movement, 2) efficient, and 3) practical, by avoiding movement over inaccessible areas. Further to matching, we argue that a fairness measure of performance over the shorter time scale is also important. We show that the RMSE and fairness are, in general, antagonistic, and argue for the need of a combined measure of performance, which we call efficacy. We show how a pause time parameter of the coverage algorithm can be used to control the trade-off between the RMSE and fairness, and present an efficient offline algorithm to determine the optimal pause time maximizing the efficacy. Finally, we discuss the effects of multiple sensors, under both independent and coordinated operation. Extensive simulation results - under realistic coverage scenarios - are presented for performance evaluation.

We analyze the quality of monitoring (QoM) of stochastic events by a periodic sensor which monitors a point of interest (PoI) for q time every p time. We show how the amount of information captured at a PoI is affected by the proportion q/p, the time interval p over which the proportion is achieved, the event type, and the stochastic event arrival dynamics and staying times. The periodic PoI sensor schedule happens in two broad contexts. In the case of static sensors, a sensor monitoring a PoI may be periodically turned off to conserve energy, thereby extending the lifetime of the monitoring until the sensor can be recharged or replaced. In the case of mobile sensors, a sensor may move between the PoIs in a repeating visit schedule. In this case, the PoIs may vary in importance, and the scheduling objective is to distribute the sensor's coverage time in proportion to the importance levels of the PoIs. Based on our QoM analysis, we optimize a class of periodic mobile coverage schedules that can achieve such proportional sharing while maximizing the QoM of the total system.

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.

Recent studies on inter-domain DWDM networks have focused on topology abstraction for state summarization, i.e. transforming a physical topology to a virtual mesh, tree, or star network. Although these schemes give very good inter- domain blocking reduction, associated inter-domain routing overheads are significant, particularly as the number of domains and border OXC nodes increase. To address these scalability limitations, novel routing update triggering policies for multi-domain DWDM networks are developed. The performance of inter-domain lightpath RWA and signaling schemes in conjunction with these strategies is then studied in order to gauge the overall effectiveness of these approaches.

Supporting high performance computing pipelines over wide-area networks is critical to enabling large-scale distributed scientific applications that require fast responses for interactive operations or smooth flows for data streaming. We construct analytical cost models for computing modules, network nodes, and communication links to estimate the computing times on nodes and the data transport times over connections. Based on these time estimates, we present the efficient linear pipeline configuration method based on dynamic programming that partitions the pipeline modules into groups and strategically maps them onto a set of selected computing nodes in a network to achieve minimum end-to-end delay or maximum frame rate. We implemented this method and evaluated its effectiveness with experiments on a large set of simulated application pipelines and computing networks. The experimental results show that the proposed method outperforms the streamline and greedy algorithms. These results, together with polynomial computational complexity, make our method a potential scalable solution for large practical deployments.

We describe a system for computational monitoring and steering of an on-going computation or visualization on a remote host such as workstation or supercomputer. Unlike the conventional “launch-and-leave” batch computations, this system enables: (i) continuous monitoring of variables of an on-going remote computation using visualization tools, and (ii) interactive specification of chosen computational parameters to steer the computation. The visualization and control streams are supported over wide-area networks using transport protocols based on stochastic approximationmethods to provide stable throughput. Using performance models for transport channels and visualization modules, we develop a visualization pipeline configuration solution that minimizes end-to-end delay over wide-area connections. The user interface utilizes Asynchronous JavaScript and XML (Ajax) technologies to provide an interactive environment that can be accessed by multiple remote users using web browsers. We present experimental results on a geographically distributed deployment to illustrate the effectiveness of the proposed system.

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.

We consider six classes of linear pipeline configuration problems with different mapping objectives and network constraints in distributed heterogeneous computing environments. We prove that two of them are polynomially solvable and the rest are NP-complete, for each of which, an optimal or heuristic algorithm based on dynamic programming is designed. Extensive simulation results illustrate the efficacy of these algorithms in comparison with existing methods.

For wide-area high-performance applications, light-paths provide 10Gbps connectivity, and multi-core hosts with PCI-Express can drive such data rates. However, sustaining such end-to-end application throughputs across connections of thousands of miles remains challenging, and the current performance studies of such solutions are very limited. We present an experimental study of two solutions to achieve such throughputs based on: (a) 10Gbps Ethernet with TCP/IP transport protocols, and (b) InfiniBand and its wide-area extensions. For both, we generate performance profiles over 10Gbps connections of lengths up to 8600 miles, and discuss the components, complexity, and limitations of sustaining such throughputs, using different connections and host configurations. Our results indicate that IB solution is better suited for applications with a single large flow, and 10GigE solution is better for those with multiple competing flows.

The localization of a radioactive source can be solved in closed-form using 4 ideal sensors and the Apollonius circle in a noise- and error-free environment. When measurement errors and noise such as background radiation are considered, a larger number of sensors is needed to produce accurate results, particularly for extremely low source intensities. In this paper, we present an efficient fusion algorithm that can exploit measurements from n sensors to improve the localization accuracy, and show how the accuracy scales with n. We report testbed results for a 0.911 μCi source to illustrate the effectiveness of our algorithm, in particular performance comparisons with state-of-the-art fusion algorithms based on Mean of Estimates (MoE) and Maximum Likelihood Estimation (MLE). We show that ITP is more accurate than MoE, whereas the choice between ITP and MLE is generally a tradeoff between accuracy and run time efficiency. Higher-intensity radioactive sources are not safe for actual experiments. In this case, we present simulation results based on a validated simulation model. We show that a low-intensity 400 μCi source, similar to the radioactivity of a concealed dirty bomb, can be localized to within 32.5 m using a sensor density of about 1 per 1100 m 2 in a surveillance area.

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.

We present a computational geometry method for the problem of triangulation in the plane using measurements of distance-differences. Compared to existing solutions to this well-studied problem, this method is: (a) computationally more efficient and adaptive in that its precision can be controlled as a function of the number of computational operations, making it suitable to low power devices, and (b) robust with respect to measurement and computational errors, and is not susceptible to numerical instabilities typical of existing linear algebraic or quadratic methods. This method employs a binary search on a distance-difference curve in the plane using a second distance- difference as the objective function. We establish the unimodality of the directional derivative of the objective function within each of a small number of suitably decomposed regions of the plane to support the binary search. The computational complexity of this method is O(log21/gamma), where the computed solution is guaranteed to be within a gamma-precision region centered at the actual solution. We present simulation results to compare this method with existing DTOA triangulation methods.

A distributed detection method is developed for the detection of a nuclear radioactive source using a small number of radiation counters. Local one bit decisions are made at each sensor over a period of time and a fusion center makes the global decision. A novel test for the fusion of correlated decisions is derived using the theory of copulas and optimal sensor thresholds are obtained using the Normal copula function. The performance of the derived fusion rule is compared with that of the Chair-Varshney rule. An increase in detection performance is observed. A method to estimate the correlation between the sensor observations using only the vector of sensor decisions is also proposed.

No abstract available.

We consider a class of simple, idealized plumes which are specified by a product of injection and distance decay terms. The plume propagates with a constant velocity, and its distance term decays exponentially with respect to distance in a planar region. If the intensity sensors are error-free, the difference triangulation method can identify the origin of plume both in time and space within a specified precision. In our case, the sensors are subject to random, correlated errors with unknown distributions in measuring the plume intensity. The sensors are available or in place to conduct controlled experiments and collect measurements. We present a training method that utilizes the plume equation together with controlled sensor measurements to identify the plume's origin with distribution-free probabilistic performance guarantees. The training consists of utilizing the measurements to compute a suitable precision value for the difference triangulation method to account for sensor distributions. We present a distribution-free relationship between the training sample size and the precision and probability with which plume's origin is identified.

In this article, we describe our experiences in implementing an experimental wide-area GMPLS network called CHEETAH (Circuit-Switched End-to-End Transport Architecture). The key concept is to add a complementary end-to-end circuit based service with dynamic call-by-call bandwidth sharing to the connectionless service already available to end hosts via the Internet. The current CHEETAH experimental network consists of off-the-shelf GMPLS-capable SONET switches (with Ethernet interfaces) deployed at three locations, Research Triangle Park, North Carolina, Atlanta, Georgia, and Oak Ridge, Tennessee. We designed and implemented a CHEETAH software package to run on Linux end hosts connected to the CHEETAH network. Among other functions, this software package includes an RSVP-TE client module to enable end users and applications to dynamically initiate requests for dedicated end-to-end circuits and receive/respond to requests for circuits. We present measurements for typical end-to-end circuit setup delays across this network. For example, end-to-end circuit setup delay from a Linux end host in NC to a host in Atlanta is 166ms.

Instantaneous fair sharing (IFS) is a traditional network ideal prescribing to share the network capacity among competing applications fairly during any infinitesimal time interval. In this paper, we argue that IFS is an inappropriate ideal for the application of massive data transfers where the primary goal is to minimize message transfer times. We propose an alternative paradigm of virtual finish time first (ViFi) scheduling that dedicates the entire capacity to one message at a time in the order of message finish times under IFS. Unlike shortest remaining time first and other earlier algorithms for dedicated scheduling, ViFi provides a remarkable guarantee of delivering each message no later than under IFS. Our analysis and simulations show the dedicated ViFi scheduling offers significant reductions in the average transfer time. The above properties make ViFi a promising approach for resource allocation in emerging dedicated-channel networks that enable advance reservation of end-to-end channels between hosts.

A control-plane architecture for supporting advance reservation of dedicated bandwidth channels on a switched network infrastructure is described including the front-end web interface, user and token management scheme, bandwidth scheduler, and signaling daemon. A path computation algorithm for bandwidth scheduling is proposed based on an extension of Bellman-Ford algorithm to an algebraic structure on sequences of disjoint non-negative real intervals. An implementation of this architecture for UltraScience Net is briefly described.

The capacities of Internet backbone links have been continuously improving over the last decade, but such improvements have not been fully realized at the application level, particularly in high-performance applications. The complicated and monolithic TCP-AIMD dynamics are responsible to a large degree for low throughputs as a result of the difficulty in optimally configuring its parameters such as buffer sizes, AIMD coefficients, and slow-start transition points. In this paper, we propose a new class of UDP-based transport protocols that utilize a rate control scheme founded on the stochastic approximation method to achieve high throughputs at the application level. These protocols operate around a local maximum of the throughput regression curve by dynamically adjusting the source rate in response to acknowledgements and losses based on the statistical behavior of the network connection. We analytically show that this protocol generates a TCP-friendly flow, and also stochastically converges to the maximum throughput under a monotone loss rate condition. Our implementation achieved very robust performance over diverse Internet connections with different characteristics: it tracked the peak throughput in presence of time-varying cross traffic and consistently achieved 2-5 times the throughput of default TCP without significantly affecting the concurrent regular traffic.

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.

We consider systems whose parameters satisfy certain easily computable physical laws. Each parameter is directly measured by a number of sensors, or estimated using measurements, or both. The measurement process may introduce both systematic and random errors which may then propagate into the estimates. Furthermore, the actual parameter values are not known since every parameter is measured or estimated, which makes the existing sample-based fusion methods inapplicable. We propose a fusion method for combining the measurements and estimators based on the least violation of physical laws that relate the parameters. Under fairly general smoothness and nonsmoothness conditions on the physical laws, we show the asymptotic convergence of our method and also derive distribution-free performance bounds based on finite samples. For suitable choices of the fuser classes, we show that for each parameter the fused estimate is probabilistically at least as good as its best measurement as well as best estimate. We illustrate the effectiveness of this method for a practical problem of fusing well-log data in methane hydrate exploration.

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.

Messages transported over wide-area networks are subject to various delays at the hosts and intermediate nodes. In addition to bandwidth limits, the delays have an apparent "random" component due to the complicated dynamics of the network traffic. We consider that the messages sent over the network are subjected to three types of delays: 1) propagation delays along the links; 2) delays due to bandwidth of the links; 3) "other delays" at the hosts and intermediate nodes which are randomly distributed according to unknown distributions. We propose an overlay network of in situ instruments on such a network to collect delay measurements, compute paths and route messages. We propose regression methods to compute a path whose message delay is close to the optimal expected delay with a high probability, based entirely on measurements. The delay distributions are arbitrary and this guarantee is the best kind possible for this network. We then present a simple multiple path method for achieving low end-to-end delays. This overlay network is implemented over the Internet using user-level daemons that realize paths among themselves without explicit support from the underlying network routers. Internet measurements show that this method achieves significantly higher aggregated bandwidths compared with the default paths.

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.

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.

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.

Several recent transport methods employ routing at a level such as the datagram, TCP stream, or application level in order to address quality of service in wide-area networks. The quickest path problem deals with the transmission of a message from a source to a destination with the minimum end-to-end delay over a network with delay and bandwidth constraints on the links. The minimum end-to-end delay path depends on the routing mechanism used for transport in addition to the message size and the link bandwidths and delays. We present algorithms for computing the path-table that specifies the minimum end-to-end delay path as a function of message size for six routing modes reflecting mechanisms such as circuit switching, Internet Protocol, and their combinations. These algorithms have polynomial time complexity in some cases, and in others achieve polynomial time complexity when the set of link bandwidths is suitably bounded.

Messages transported over wide-area networks are subject to various delays at the intermediate nodes and hosts. In addition to bandwidth limits, the delays have an apparent "random" component due to the complicated dynamics of the network traffic. We consider that the messages sent over the network are subjected to three types of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) "other delays" at the intermediate nodes which are randomly distributed according to unknown distributions. We propose an overlay network of in-situ instruments on such a network to collect delay measurements, and to compute and implement paths for message transport. We propose an algorithm to compute a path whose message delay is close to the optimal expected delay with a high probability, based entirely on measurements. We then present a multiple path method for achieving low end-to-end delays, which is implemented over the Internet using user-level daemons. These daemons realize multiple paths among themselves without explicit support from the underlying network routers, and achieve higher aggregated bandwidths compared to the usual transport methods.

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.

In a multiple sensor system, sensor S/sub i/, i=1, 2..., N, outputs Y/sup (i)/ /spl isin/ [0,1], according to an unknown probability distribution P(Y/sup (i)/|X), in response to input X /spl isin/ [0,1]. We choose a fuser-that combines the outputs of sensors-from a function class F={f:[0,1]/sup N//spl rarr/[0,1]} by minimizing empirical error based on an i.i.d. sample. If F satisfies the isolation property, we show that the fuser performs at least as well as the best sensor in a probably approximately correct sense. Several well-known fusers, such as linear combinations, special potential functions, and certain feedforward networks, satisfy the isolation property.

We develop and evaluate several heuristics for the construction of a multicast tree to transmit a given message of size r from a source to a set of destinations with guarantees on the end-to-end delay over a computer network. Different multicast trees can be constructed for various values of r. We consider delay sources on links to be from propagation and bandwidth availability. The heuristics that we have developed try to minimize the end-to-end delay of the multicast tree taking into consideration various switching architectures that range from pipeline to store-and-forward. Our evaluations of these heuristics consider various network generation models including locality, Waxman I and II, and transit-stub. We have evaluated multicast tree generation heuristics based on both shortest path and Steiner tree heuristics. A novel heuristic called grow-tree is proposed in this paper and it is based on both Kruskal's and Prim's minimum spanning tree algorithm. This heuristic performs admirably well in many network environments.

A dynamic ad hoc network consists of a collection of mobile hosts with frequently changing network topology. We propose a distributed algorithm that adapts to the topology by utilizing spanning trees in the regions where the topology is stable, and resorting to an intelligent flooding-like approach in highly dynamic regions of the network. Routing is performed using the spanning trees based on a hold-and-forward or shuttling method. We introduce the notion of connectivity-through-time and holding time to quantify the performance of the routing algorithms for various network connectivity scenarios. Using simulation, we study the throughput, reachability and message-reachability ratio of the proposed network under various connection/reconnection rates and holding times.

We consider the transmission of a message of size r from a source to a destination over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, we consider that the delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, we propose O(m/sup 2/+mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. We then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. We propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays.

We consider two generic routing problems via multiple paths in a computer network wherein bandwidth can be reserved, and guaranteed, once reserved, on the links. The first problem requires that a message of finite length be transmitted from s to d within /spl tau/ units of time. The second problem requires that a sequential message of /spl tau/ units be transmitted at a rate of /spl eta/ such that maximum time difference between two units received out of order is no more than q. We propose a polynomial-time algorithm to the first problem, and present simulation results to illustrate its applicability. We show the second problem to be NP-complete, and propose a polynomial-time approximate solution.

In a system of N sensors, the sensor S/sub j/, j=1,2...,N, outputs Y/sup j/spl isin//[0, 1], according to an unknown probability density p/sub j/(Y/sup j|/X), corresponding to input X/spl isin/[0, 1]. A training n-sample (X/sub 1/,Y/sub 1/), (X/sub 2/,Y/sub 2/), ..., (X/sub n/,Y/sub n/) is given where Y/sub i/=(Y/sub i//sup 1,/Y/sub i//sup 2,/...,Y/sub i//sup N/) such that Y/sub i//sup j /is the output of S/sub j/ in response to input X/sub i/. The problem is to estimate a fusion rule f:[0,1]/sup N//spl rarr/[0,1], based on the sample, such that the expected square error, I(f), is minimized over a family of functions /spl Fscr/ with uniformly bounded modulus of smoothness. Let f* minimize I(.) over /spl Fscr/; f* cannot be computed since the underlying densities are unknown. We estimate the sample size sufficient to ensure that Nadaraya-Watson estimator f/spl circ/ satisfies P[I(f/spl circ/)-I(f*)>/spl epsiv/]0 and /spl delta/, 0</spl delta/<1. We apply this method to the problem of detecting a door by a mobile robot equipped with arrays of ultrasonic and infrared sensors.

The classical stochastic approximation methods are shown to yield algorithms to solve several formulations of the PAC learning problem defined on the domain [0,1](d). Under some smoothness conditions on the probability measure functions, simple algorithms to solve some PAC learning problems are proposed based on networks of nonpolynomial units (e.g. artificial neural networks). Conditions on the sizes of the samples required to ensure the error bounds are derived using martingale inequalities.

We address the model acquisition problem for an unknown planar polygonal terrain by a team of two or three point robots. The robots are equipped with visual sensors which acquire all visible parts of the terrain by scan operations executed from their locations. The robots communicate with each other via wireless connection. The performance is measured by the number of the sensor (scan) operations. We employ the restricted visibility graph methods an a hierarchical setup. For terrains with convex obstacles and for teams of n (where n=2, 3) robots, we prove that the sensing time is reduced by a factor of 1/n. For terrains with concave corners, the performance of the algorithm for the n(2, 3) robot team is expressed in terms of the sizes of n-connected components, and the sizes and diameters of (n-1) or less connected components.

We consider the problem of learning functions based on finite samples by using feedforward sigmoidal networks. The unknown function f is chosen from a family that has either bounded modulus of smoothness and/or bounded capacity. The sample is given by (X/sub 1/, f(X/sub 1/)), (X/sub 2/, f(X/sub 2/)), ...(X/sub n/, f(X/sub n/)). Where X/sub 1/, X/sub 2/, ..., X/sub n/, are independently and identically distributed according to an unknown distribution P/sub X/. General results guarantee the existence of a neural network, f/sub w/*, that best approximates f in terms of expected error. However, since both f and P/sub X/ are unknown, computing f/sub w/* is impossible in general. We propose to compute probability and approximately correct (PAC) approximations to f/sub w/*, based on alternative estimators, namely: 1) the nearest neighbor rule, 2) local averaging, and 3) Nadaraya-Watson estimators, all computed using the Haar system. We show that given a sufficiently large sample, each of these estimators guarantees a performance as close as desired to that of f/sub w/*. The practical importance of this result sterns from the fact that, unlike neural networks, the three estimators above are linear-time computable in terms of the sample size.

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.

Systems modeled as directed graphs where nodes represent components and edges represent fault propagation between components, are studied from a parallel computation viewpoint. Some of the components are equipped with alarms that ring in response to an abnormal condition. The single fault diagnosis problem is to compute the set of all potential failure sources, P/sub S/, that correspond to a set of ringing alarms A/sub R/. There is a lower bound for any sequential algorithm for this problem (under a decision tree model).

The Distributed Queue Dual Bus (DQDB) system consists of a linear arrangement of N nodes that communicate with each other using two contra-flowing buses. The nodes use an extremely simple protocol to send messages on these buses. This simple, but elegant, system has been found to be very challenging to analyze. We consider a simple and uniform abstraction of this model to highlight the fairness issues in terms of average waiting time. We introduce a new approximation method to analyze the performance of DQDB system in terms of the average waiting time of a node expressed as a function of its position. Our approach abstracts the intimate relationship between the load of the system and its fairness characteristics, and explains all basic behavior profiles of DQDB observed in previous simulation. For the uniform DQDB with equal distance between adjacent nodes, we show that the system operates under three basic behavior profiles and a finite number of their combinations that depend on the load of the network. Consequently, the system is not fair at any load in terms of the average waiting times. We also show that the main theme of the analysis carries over to the general (nonuniform) DQDB. By suitably choosing the inter-node distances, the DQDB can be made fair around some loads, but such system will become unfair as the load changes. In the vicinity of a critical load, the uniform network runs into a state of instability, where its behavior fluctuates from one extreme to the other with small load variations. Our analysis is supported by simulation results.>

This paper considers the problem of navigating a point robot in an unknown two-dimensional terrain populated by disjoint generalized polygonal obstacles. A generalized polygon consists of a connected sequence of circular arcs and straight-line segments. The terrain model is not known a priori, but the robot is equipped with a vision sensor. A discrete vision sensor detects all visible (from a single position) portions of the obstacle boundaries in a single scan operation. The navigation problem deals with moving the robot through the terrain from a source position to a destination position, and the terrain model acquisition problem deals with autonomously building a model of the terrain. A complete solution to either problem is shown to require an infinite number of scan operations in cusp regions formed by a pair of convex and concave obstacle edges. Either problem is considered solved with a precision /spl epsiv/ if the points that have not been scanned are those in a cusp region with a clearance less than /spl epsiv/ from two obstacle edges. Three methods are proposed to solve both problems with a precision /spl epsiv/ based on extensions of the generalized visibility graph, the generalized Voronoi diagram, and the trapezoidal decomposition. Then simplified versions of these structures are proposed to exactly solve the navigation and terrain model acquisition problems using a continuous vision sensor that detects all visible obstacle boundaries as the robot navigates along a path.>

Considers a simple and uniform abstraction of the distributed queue dual bus (DQDB) system of N nodes to highlight the fairness issues in terms of average waiting time. For the uniform DQDB with equal distance between adjacent nodes, the authors show that the system operates under three basic behavior profiles and a finite number of their combinations that depend on the load of the network. Consequently, the system is not fair at any load in terms of the average waiting times. In the vicinity of a critical load of 1-4/N the uniform network runs into a state akin to chaos, where its behavior fluctuates from one extreme to the other with a load variation of 2/N. The analysis is supported by simulation results. The authors also show that the main theme of the analysis carries over to the general (non-uniform) DQDB.>

Given two subsets S/sub 1/ and S/sub 2/ (not necessarily finite) of /spl Rfr//sup d/ separable by a Boolean combination of learning half-spaces, the authors consider the problem of (in the sense of Valiant) the separation function from a finite set of examples, i.e., they produce with a high probability a function close to the actual separating function. The authors' solution consists of a system of N perceptrons and a single consolidator which combines the outputs of the individual perceptrons; it is shown that an off-line version of this problem, where the examples are given in a batch, can be solved in time polynomial in the number of examples. The authors also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of the classical perceptron learning algorithm.>

The problems of identifying several nontrivial classes of Polynomial-Time Testable (PTT) circuits are shown to be NP-complete or harder. First, PTT classes obtained by using circuit decompositions proposed by Fujiwara (1988) and Chakradhar et al. (1990) are considered. Another type of decompositions, based on fanout-reconvergent (f-r) pairs, which also lead to PTT classes are proposed. The problems of obtaining these decompositions, and also some structurally similar general graph decompositions, are shown to be NP-complete or harder. Then, the problems of recognizing PTT classes formed by the Boolean formulae belonging to the weakly positive, weakly negative, bijunctive and affine classes are shown to be NP-complete.>

A system of probably and approximately correct learners of Valiant type that infer concepts from a sample is considered. Each learner had been trained by a sample using the methods of minimizing the empirical error, and no examples are available to the fuser. A majority fuser is known to make the composite system better than the best of the learners in terms of normalized confidence (that corresponds to the same precision value). An analysis of general majority fusers is carried out to obtain bounds on actual and expected errors. Conditions under which the r of N fuser performs better, in terms of normalized confidence or precision, than best of the individual learners are obtained. For a special class of statistically independent learners, slightly weaker conditions are obtained. Two fusers that use the location information of a test point are proposed, and are shown to be better than a learner with least empirical error.>

Given N learners each capable of learning concepts (subsets) in the sense of Valiant (1985), we are interested in combining them using a single fuser. We consider two cases. In open fusion the fuser is given the sample and the hypotheses of the individual learners; we show that a fusion rule can be obtained by formulating this problem as another learning problem. We show sufficiency conditions that ensure the composite system to be better than the best of the individual. Second, in closed fusion the fuser does not have an access to either the training sample or the hypotheses of the individual learners. By using a linear threshold fusion function (of the outputs of individual learners) we show that the composite system can be made better than the best of the statistically independent learners.>

Article Free Access Share on Hybrid pattern recognition system capable of self-modification Authors: Charles W. Glover Intelligent Systems Section, Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TN Intelligent Systems Section, Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TNView Profile , Nageswara S. V. Rao Intelligent Systems Section, Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TN Intelligent Systems Section, Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TNView Profile , E. M. Oblow Intelligent Systems Section, Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TN Intelligent Systems Section, Center for Engineering Systems Advanced Research, Oak Ridge National Laboratory, Oak Ridge, TNView Profile Authors Info & Claims CIKM '93: Proceedings of the second international conference on Information and knowledge managementDecember 1993 Pages 239–244https://doi.org/10.1145/170088.170140Published:01 December 1993Publication History 0citation362DownloadsMetricsTotal Citations0Total Downloads362Last 12 Months3Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The problem of diagnosing single faults is addressed for systems whose fault propagation properties can be modeled as directed graphs. In these systems, the nodes represent components and the edges represent fault propagation between the components. Some of the components are equipped with alarms that become active in response to faulty conditions. Two algorithms, FORWARD and BACKWARD, for computing the set of all potential candidates for a single fault that corresponds to a given set of active alarms, are studied. FORWARD moves forward from candidate nodes checking to see if they satisfy the alarm condition, and BACKWARD moves backwards from the alarms. In terms of worst-case time complexity, BACKWARD is better. These algorithms are analyzed using systems that are uniformly and randomly generated. In terms of the expected number of distinct nodes that are visited, FORWARD is shown to be better, and in terms of the total number of node visits, BACKWARD is found to be better. Thus, these algorithms are suited for different modes of storing the system graph.>

Systems that can be modeled as graphs, such that nodes represent the components and the edges represent the fault propagation between the components, are considered. Some components are equipped with alarms that ring in response to faulty conditions. In these systems, two types of problem are studies: fault diagnosis and alarm placement. The fault diagnosis problems deal with computing the set of all potential failure sources that correspond to a set of ringing alarms. Single faults, where exactly one component can become faulty at any time, are primarily considered. Systems are classified into zero-time and non-zero-time systems on the basis of fault propagation time. The latter are further classified on the basis of knowledge of propagation times. For each of these classes algorithms are presented for single fault diagnosis. The problem of detecting multiple faults is shown to be NP-complete. An alarm placement problem that requires a single fault to be uniquely diagnosed is examined.>

Given two subsets S/sub 1/ and S/sub 2/ (not necessarily finite) of R/sup d/ separable by a Boolean combination of N halfspaces, the authors consider the problem of learning the separation function from a finite set of examples. The solution consists of a system of N perceptrons and a single consolidator which combines the outputs of the individual perceptrons. The authors show that an off-line version of this problem where the examples are given in a batch, can be solved in time polynomial in the number of examples. The authors also provide an on-line learning algorithm that incrementally solves the problem by suitably training a system of N perceptrons much in the spirit of classical perceptron learning algorithm.>

Given N learners each capable of learning concepts (subsets) in the sense of Valiant (1985), we are interested in combining them using a single fuser. We consider two cases. In open fusion the fuser is given the sample and the hypotheses of the individual learners; we show that a fusion rule can be obtained by formulating this problem as another learning problem. We show sufficiency conditions that ensure the composite system to be better than the best of the individual. Second, in closed fusion the fuser does not have an access to either the training sample or the hypotheses of the individual learners. By using a linear threshold fusion function (of the outputs of individual learners) we show that the composite system can be made better than the best of the statistically independent learners. >

Single output logic circuits composed of AND and EXOR gates are studied. It is shown that for two level single output logic circuits composed of AND and EXOR gates, tests that detect all detectable stuck-at faults can be generated in polynomial time. In this method no extra input variables nor extra circuits are required. This contrasts with the fact that for AND, OR circuits the test generation problem is not polynomial time solvable even for two level circuits. Since AND-EXOR circuits can represent any switching function, this suggests that these circuits might be easier to test than AND, OR circuits.>

We consider the problem of planning a collision-free path for a point robot R from its present position to a specified destination position through an unknown terrain, i.e., a terrain whose model is not known a priori. R is equipped with a sensor system that is capable of detecting all visible vertices and edges of the obstacles. Algorithms that plan a required path for R have been reported earlier in literature. In this paper, we investigate some trade-offs in the performance of such algorithms in terms of distance traversed, number of sensor operations and computational complexity. These trade-offs accrue as a result of the details of an underlying graph search algorithm, and in this sense are independent of the other properties of the terrain. We show that among a general class of these algorithms (a) depth-first implementations result in minimum computational complexity, (b) shortest-path implementations result in a globally shortest path in each step, and that (c) among a set of implementations that attempt to optimize the distance to the destination, the A* implementation results in minimum number of scan operations. We also present some interesting intermediaries between the algorithms of (a) and (b). INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A simplified abstraction of the problem of recognizing planar arrangements of objects using camera pictures taken from unknown positions is considered. A set of polygons in planes is called a planar polygonal configuration. Given perspective images P and Q corresponding to planar polygonal configurations, the matching problem is to determine if P and Q correspond to the same configuration. An optimal theta (n log n) time algorithm is presented to solve this problem, where n is the total number of vertices of polygons in each image. The algorithm is obtained by combining ideas of cross ratios, which are well known to be invariant under perspective projections, and the first fundamental theorem of perspective projections. This algorithm has been implemented and tested with satisfactory results.>

The problem of test generation for detecting stuck-at faults in combinational circuits is computationally intractable. Consequently, the identification of classes of circuits that support polynomial-time test generation algorithms is very important from testing and design viewpoints. The authors discuss several classes of polynomially-time testable circuits. First, they consider the existing polynomial classes obtained by using decompositions of the circuits. Another type of decomposition is proposed, based on fanout-reconvergent pairs, which also lead to classes of polynomial-time testable circuits. Then, the authors present the classes of polynomial-time testable circuits that are formed by the Boolean formulae belonging to the classes of weakly positive, weakly negative, bijunctive and affine.>

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.>

Algorithmic issues of simple object detection problems in the context of a system consisting of a finite set of sensors that monitor a workspace are studied. Each sensor detects the presence of only a certain subset of a given set of objects O. Given that an object has been detected by a subset of sensors, the detection problem deals with identifying whether the object in the workspace is a member of O and, if so, computing the maximal set of such numbers. A conceptual graph structure called the detection network that yields efficient algorithms for the detection problem for combinational, message-based, sequential and parallel computing systems is proposed. The problem of computing a detection network with the minimum number of edges is shown to be computationally intractable, and polynomial-time approximation algorithms are presented. Sequential algorithms to solve the detection problem with and without preprocessing are presented. Parallel algorithms on shared memory systems and hypercube-based message passing systems are discussed. It is shown that the problem of detecting multiple objects is computationally intractable.>

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.>

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.>

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 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 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.