Globally optimal robust process control

A computational approach is developed for designing a globally optimal controller which is robust to time-varying nonlinear perturbations in the plant. This controller design problem is formulated as an optimization with bilinear matrix inequality (BMI) constraints, and is solved to optimality by a branch and bound algorithm. The algorithm is applied to a reactive ion etcher, and provides superior performance while providing robustness to nonlinear plant/model mismatch. The algorithm is also applied to a well known benchmark problem.     

Efficient authentication of scalable media streams over wireless networks

Media authentication of wireless transmission is becoming an increasingly important issue. Authenticated media content is constantly required to be transcoded at intermediates to accommodate heterogeneous applications. In this paper, a general and efficient authentication approach is proposed for scalable lossy media streams. Firstly, a joint coding and stream authentication (JCSA) media transmission system is described in a heterogeneous wireless network. For the JCSA system, a novel structure-maintained packetization is designed to realize flexible transcoding. Secondly, to obtain the optimal end-to-end quality and minimize the authentication overhead, a quality-optimized stream authentication (QOSA) framework is proposed for authenticating media content. Finally, an implementation of the proposed QOSA optimization framework on the consultative committee for space data systems image data compression (CCSDS IDC) coder is presented by combining graph-based and error-correction coding based (ECC-based) approaches. Experimental results demonstrate that our scheme can achieve the desired goal that it provides high robustness against packet-loss at the cost of a very low overhead.     

Media- and TCP-friendly congestion control for scalable video streams

This paper presents a media- and TCP-friendly rate-based congestion control algorithm (MTFRCC) for scalable video streaming in the Internet. The algorithm integrates two new techniques: i) a utility-based model using the rate-distortion function as the application utility measure for optimizing the overall video quality; and ii) a two-timescale approach of rate averages (long-term and short-term) to satisfy both media and TCP-friendliness. We evaluate our algorithm through simulation and compare the results against the TCP-friendly rate control (TFRC) algorithm. For assessment, we consider five criteria: TCP fairness, responsiveness, aggressiveness, overall video quality, and smoothness of the resulting bit rate. Our simulation results manifest that MTFRCC performs better than TFRC for various congestion levels, including an improvement of the overall video quality.     

Attribute grammars for scalable query processing on XML streams

We introduce the notion of XML Stream Attribute Grammars (XSAGs). XSAGs are the first scalable query language for XML streams (running strictly in linear time with bounded memory consumption independent of the size of the stream) that allows for actual data transformations rather than just document filtering. XSAGs are also relatively easy to use for humans. Moreover, the XSAG formalism provides a strong intuition for which queries can or cannot be processed scalably on streams. We introduce XSAGs together with the necessary language-theoretic machinery, study their theoretical properties such as expressiveness and complexity, and discuss their implementation.     

Globally optimal fuzzy decision trees for classification andregression

A fuzzy decision tree is constructed by allowing the possibility of partial membership of a point in the nodes that make up the tree structure. This extension of its expressive capabilities transforms the decision tree into a powerful functional approximant that incorporates features of connectionist methods, while remaining easily interpretable. Fuzzification is achieved by superimposing a fuzzy structure over the skeleton of a CART decision tree. A training rule for fuzzy trees, similar to backpropagation in neural networks, is designed. This rule corresponds to a global optimization algorithm that fixes the parameters of the fuzzy splits. The method developed for the automatic generation of fuzzy decision trees is applied to both classification and regression problems. In regression problems, it is seen that the continuity constraint imposed by the function representation of the fuzzy tree leads to substantial improvements in the quality of the regression and limits the tendency to overfitting. In classification, fuzzification provides a means of uncovering the structure of the probability distribution for the classification errors in attribute space. This allows the identification of regions for which the error rate of the tree is significantly lower than the average error rate, sometimes even below the Bayes misclassification rate     

Globally optimal surface mapping for surfaces with arbitrary topology

Computing smooth and optimal one-to-one maps between surfaces of same topology is a fundamental problem in computer graphics and such a method provides us a ubiquitous tool for geometric modeling and data visualization. Its vast variety of applications includes shape registration/matching, shape blending, material/data transfer, data fusion, information reuse, etc. The mapping quality is typically measured in terms of angular distortions among different shapes. This paper proposes and develops a novel quasi-conformal surface mapping framework to globally minimize the stretching energy inevitably introduced between two different shapes. The existing state-of-the-art inter-surface mapping techniques only afford local optimization either on surface patches via boundary cutting or on the simplified base domain, lacking rigorous mathematical foundation and analysis. We design and articulate an automatic variational algorithm that can reach the global distortion minimum for surface mapping between shapes of arbitrary topology, and our algorithm is sorely founded upon the intrinsic geometry structure of surfaces. To our best knowledge, this is the first attempt towards numerically computing globally optimal maps. Consequently, our mapping framework offers a powerful computational tool for graphics and visualization tasks such as data and texture transfer, shape morphing, and shape matching.     

Globally optimal regions and boundaries as minimum ratio weightcycles

We describe a new form of energy functional for the modeling and identification of regions in images. The energy is defined on the space of boundaries in the image domain and can incorporate very general combinations of modeling information both from the boundary (intensity gradients, etc.) and from the interior of the region (texture, homogeneity, etc.). We describe two polynomial-time digraph algorithms for finding the global minima of this energy. One of the algorithms is completely general, minimizing the functional for any choice of modeling information. It runs in a few seconds on a 256×256 image. The other algorithm applies to a subclass of functionals, but has the advantage of being extremely parallelizable. Neither algorithm requires initialization     

A scalable code dissemination protocol in heterogeneous wireless sensor networks

Code dissemination is currently a major research issue in wireless sensor networks (WSNs).Many studies focus on code dissemination in homogeneous WSNs,mainly using a broadcast approach to solve this problem;few studies on code dissemination in heterogeneous WSNs.Furthermore,broadcasting cannot readily be used to solve the heterogenous WSN code dissemination problem directly,which is where we have focused our attention.We transformed this problem into a minimum non-leaf nodes (MNN) Steiner tree problem.We designed a scalable multicast protocol,named Heterogeneous Sensor Networks Scalable Reprogramming Protocol (HSR) to solve the MNN problem.HSR can build different multicast trees according to different nodes or code modules to disseminate different codes to them.HSR is able to approximate the MNN tree problem to a ratio of ln|R| (R is the set of all destinations) best known lowest bound.Therefore,the communication cost is significantly decreased and the total energy required by WSNs is reduced.We further designed two scalable schemes,special routing log and hops-restricted local broadcast,which compress the multicast tree information and deliver the multicast messages without loss.We also designed a 3-stage pipeline to speed up the transmission of packets,which alleviated interference and hidden terminal issues.We evaluated our design through comprehensive simulations and prototype implementations on Mica2 motes.Experimental results demonstrate that HSR outperforms previous protocols including the most recent studies on Sprinkler and uCast.     

异构无线传感器网络中一种可扩展的代码分发技术

代码分发一直是无线传感器网络研究的热点问题.目前的研究工作主要集中在同构场景下的代码分发,广播是这些研究工作中最常用的手段.而对于异构场景下的代码分发问题,研究工作则相对较少,传统的基于广播的方法很难直接适用.文中针对异构网络下的代码分发问题,把该问题归约为最小非叶节点MNN(minimum nonleaf nodes)Steiner树问题,并设计了一种基于多播的代码分发协议HSR(heterogeneous sensor networks scalable reprogramming protocol).该协议利用组件化的思想,为不同类型节点(或代码模块)建立了多棵最优代码分发多播树.并证明了在解决MNN问题时,HSR达到了理论最优近似率ln|R|(R为目标节点数),有效的降低了异构网络下代码分发过程中的通信开销和能耗.在此基础上,文中还设计了两种压缩编码机制:特殊路由日志机制SRL(special routinglog)和跳步受限的局部广播机制HLB(hops-restricted local broadcast),使得多播树的信息可以被无损压缩,增强了HSR协议的可扩展性.在实时性方面,提出了基于多播树的3阶段流水线调度方法,有效缓解了隐藏终端和干扰问题.仿真结果证明了协议的正确性和有效性.     

SOLE: scalable on-line execution of continuous queries on spatio-temporal data streams

This paper presents the scalable on-line execution (SOLE) algorithm for continuous and on-line evaluation of concurrent continuous spatio-temporal queries over data streams. Incoming spatio-temporal data streams are processed in-memory against a set of outstanding continuous queries. The SOLE algorithm utilizes the scarce memory resource efficiently by keeping track of only the significant objects. In-memory stored objects are expired (i.e., dropped) from memory once they become insignificant. SOLE is a scalable algorithm where all the continuous outstanding queries share the same buffer pool. In addition, SOLE is presented as a spatio-temporal join between two input streams, a stream of spatio-temporal objects and a stream of spatio-temporal queries. To cope with intervals of high arrival rates of objects and/or queries, SOLE utilizes a load-shedding approach where some of the stored objects are dropped from memory. SOLE is implemented as a pipelined query operator that can be combined with traditional query operators in a query execution plan to support a wide variety of continuous queries. Performance experiments based on a real implementation of SOLE inside a prototype of a data stream management system show the scalability and efficiency of SOLE in highly dynamic environments. This work was supported in part by the National Science Foundation under Grants IIS-0093116, IIS-0209120, and 0010044-CCR.     

An optimal code for patient identifiers

How to distinguish 1 billion individuals by an identifier consisting of eight characters, allowing a reasonable amount of error detection or even error correction? Our solution of this problem is an optimal code over a 32-character alphabet that detects up to two errors and corrects one error as well as a transposition of two adjacent characters. The corresponding encoding and error checking algorithms are available for free; they are also embedded as components of the pseudonymisation service that is used in the TMF-the German telematics platform for health research networks.     

Globally optimal nonlinear model predictive control based on multi-parametric disaggregation

Nonlinear model predictive control is appropriate for controlling highly nonlinear processes, particularly when operating conditions change frequently. If the problem is nonconvex, the controller must lead the process to a global, rather than a local optimum. This work deals with computation of the control actions which lead to the global optimum via the normalized multi-parametric disaggregation technique. The continuous process model is transformed into a nonlinear programming (NLP) problem via discretization which uses an implicit integration method. The NLP problem is relaxed into a mixed integer linear programming (MILP) model. Iterations between solving MILP (lower bound) and using its solution as a starting point for a local nonlinear optimizer (which computes the upper bound) continue until the gap is closed (an l₁-norm objective function is used). Controller performance is illustrated by several examples. Relative simplicity of the algorithm makes it possible to be implemented by a wide audience.     

Thou code: a triple-erasure-correcting horizontal code with optimal update complexity

The Journal of Supercomputing - Taking advantage of consuming low storage resource, erasure codes have been widely adopted by various storage systems, e.g., HDFS, Ceph, and Microsoft Azure, to...     

On packetization of embedded multimedia bitstreams

We study the problem of packetizing embedded multimedia bitstreams to improve the error resilience of source (compression) codes. This problem is important because of the increasing popularity of embedded compression methodology and its suitability for scalable streaming media over IP or/and mobile IP. We study various packetization schemes against packet erasure at both low and high bit rates. Maximizing packetization efficiency for embedded bitstreams is formulated as a discrete optimization problem and globally optimal packetization (OP) algorithms are proposed under different settings. Suboptimal packetization algorithms are also devised to reduce the complexity of the OP algorithms. In order to assess their effectiveness, the proposed packetization algorithms are used to packetize embedded image and video bitstreams with simulated packet loss. Experimental results show that our OP algorithms slightly outperforms suboptimal ones. In addition to confirming the superiority of the OP algorithms, these results also provide justification of heuristic packetization methods published in the literature     

Globally optimal flight path update with adding or removing out-of-sequence measurements

In a multisensor target tracking system, observations produced by sensors can arrive at a central processor out of sequence. There have been some state estimate update algorithms for out-of-sequence measurements (OOSMs). In this paper, we propose a flight path update algorithm for a sequence with arbitrary delayed OOSMs. The new algorithm has three advantages: (1) it is a globally optimal recursive algorithm; (2) it is an algorithm for arbitrary delayed OOSMs including the case of interlaced OOSMs with less storage, compared with the optimal state update algorithm in Zhang, Li, and Zhu (2005); (3) it can update the current whole flight path in addition to the current single state with less computation, i.e., the dimension of the matrices which need to be inverted is not more than that of the state in the process of updating the past ? (lag steps) estimates and corresponding error covariances. Besides, this algorithm can be easily modified to derive a globally optimal flight path update with removing an earlier (incorrectly associated) measurement.     

Worst-case optimal algorithm for XPath evaluation over XML streams

We consider the XPath evaluation problem: Evaluate an XPath query Q on a streaming XML document D; i.e., determine the set Q(D) of document elements selected by Q. We mainly consider Conjunctive XPath queries that involve only the child and descendant axes. Previously known in-memory algorithms for this problem use O(|D|) space and O(|Q||D|) time. Several previously known algorithms for the streaming version use Ω(dn) space and Ω(dn|D|) time in the worst case; d denotes the depth of D, and n denotes the number of location steps in Q. Their exponential space requirement could well exceed the O(|D|) space used by the in-memory algorithms. We present an efficient algorithm that uses O(d|Q|+nc) space and O((|Q|+dn)|D|) time in the worst case; c denotes the maximum number of elements of D that can be candidates for output, at any one instant. For some worst case Q and D, the memory space used by our algorithm matches our lower bound proved in a different paper; so, our algorithm uses optimal memory space in the worst case.