Abstract:New words recognition and ambiguity resolving have vital effect on information retrieval precision. This paper presents a statistical model based algorithm for adaptive Chinese word segmentation. Then, a new word segmentation system called BUAASEISEG is designed and implemented using this algorithm. BUAASEISEG can recognize new words in various domains and do disambiguation and segment words with arbitrary length. It uses an iterative bigram method to do word segmentation. Through online statistical analysis on target article and using the offline words frequencies dictionary or the inverted index of the search engine, the candidate words selection and disambiguation are done. On the basis of the statistical methods, post-process using stopwords list, quantity suffix words list and surname list are used for further precision improvement. The comparative evaluation with the famous Chinese word segmentation system ICTCLAS, using news and papers as testing text, shows that BUAASEISEG outperforms ICTCLAS in new words recognition and disambiguation.

Abstract:The multi-criteria minimum spanning tree (mc-MST) problem is a typical NP-hard problem. An algorithm to enumerate the set of Pareto optimal spanning trees on some mc-MST instances was put forward by Zhou and Gen, but it does not guarantee returning all the Pareto optimal solutions. To settle this problem, an improved algorithm is developed and also proved to be able to find all the true Pareto optimal solutions in this paper. The new algorithm adds some conditions in the elimination of subtrees. Simulation results show that the new algorithm can find all the Pareto optimal solutions and also show that the new algorithm has potential usage in practice.

Abstract:In this paper, a source coding technique exploiting packet path diversity is presented, which combines the individual benefits of MDC (multiple description coding) and LC (layer coding) for video transmission over wireless networks. Performance comparisons between LC and MDC are discussed at the beginning of this paper. Their advantages and disadvantages are concluded. An improved coding technique named auto-resilient multiple description coding (ARMDC) is then shown for its ability to conjoin the merits and avoid the shortcomings of the above two coding schemes. Under the critical transmission conditions of error-prone wireless channels, ARMDC can make all the received packets useful, not just those consecutive from the first packet. At the same time, it can also process the feature of LC, creating a “base-layer” bit-stream to ensure the basic quality of video. Transmission policy of ARMDC varies with transmission environment and application limits to gain fine video quality. 3G mobile channels are simulated and then streams create by ARMDC, MDR (multiple description with restart) scheme and coding scheme without any LC or MDC are sent over the channels. Experiment results show that the decoded video sequences of ARMDC streams have better performance in R-D curve comparision than the other MDC scheme and also gain best personality effect because of the smooth sequence quality. This out-coming is well adapted to streaming and conversational applications in wireless environment.

Abstract:CluStream is a popular data stream cluster algorithm, however, it is not capable enough to cluster arbitrary shapes and make clusters in periodic data. This paper introduces a new algorithm ACluStream to solve these problems. The ACluStream is based on the partition and assemble of the space and cluster by density. In the experiment, it is shown that ACluStream is better than CluStream in speed and accuracy.

Abstract:It is a challenge to support the fault tolerance for satellite networks, in which fault identification is primary. After modeling satellite networks with two-level-node graph, a fault identification algorithm based on PMC test invalidation model is presented and proved to be correct. The effectiveness of the algorithm in different types of satellite networks is compared and studied by simulations. The results of experiments illustrate that the algorithm adapts to arbitrary network topology and has robustness.

Abstract:Intention, a crucial part of the mental states of an agent, plays an important role in determining the behaviors of the rational agent. In order to eliminate the flaws with existing logic of intention and establish a suitable semantic representation for intention, this paper addresses the requests for intention semantics on formal frameworks of rational agents, points out the problems with existing logic of intention, introduces a novel possible world semantics for intention, called the improved twin-subset semantics, which was developed by us recently based on the previous work about the true-false subset semantics, and presents its application in the formalization of intention for agent. It is also proved that some desired properties could be obtained through some restrictions to the algebraic structure of the models. In the two-value logic, the false value is as important as the true value. Of course, to one proposition, once the true values are described in some possible worlds, the false values are just the rest. However, to a set of propositions (the agent intents to do), descriptions to the false values are as important as descriptions to the true values. The representation of intention should describe a set of propositions (the propositions agent intents to achieve), but in the possible world semantics of classical normal modal operator, it merely pays attention to the true-value, which is denoted as R_I(w), and can be considered as single-subset semantics. In the improved twin-subset semantics, the false-value is considered as important as the true-value, and R_IT(w) is used to describe the true, while R_IF(w) the false. Thus this method can describe modal operator in two-value logic completely. In addition, the possible world semantics of the classical normal modal operator can be regarded as the degradation of the improved twin-subset semantics when R_IF(w)=?. It not only avoids the logical omniscience problem and other related problems (such as side-effect problem, and etc) but also overcomes the shortcomings of the true-false subset semantics and twin-subset semantics. Compared with Konolige and Pollack’s model of intention, this model not only is simpler and more natural, but also satisfies the K-axiom and the Joint Consistency. Actually, the improved twin-subset semantics provides a new method for semantic representation of non-normal modal operator and can be applied to establish a new proper agent’s logic system.

Abstract:Handwritten Chinese characters segmentation is to process strokes based on its spatial relations to form character elements for recognition. This paper introduces a method to segment Chinese characters according to the topological relations of Chinese component and minimal span tree of strokes. The experiment shows that this new method can achieve good performance. The accuracy of segmentation is over 91.6%.

Abstract:Wireless sensor networks are different from traditional networks and highly dependent on applications, so traditional routing protocols cannot be applied efficiently to them. Therefore many routing protocols for wireless sensor networks are studied. After describing the characteristics of wireless sensor networks, the classification standards for routing protocols are presented. Then the key mechanisms of the existing representative routing protocols are analyzed and their classifications, characteristics and application areas are compared. Finally, the important features that good routing protocols possess are summarized, and the future research strategies and trends.

Abstract:One of the most fundamental problems in wireless sensor networks is the coverage control problem, which reflects how well a region is apperceived. The coverage control theories and algorithms can result in not only network resources’ optimial allocation but also efficient sensing and collecting of the environmental information, and communicating with neighboring nodes by wireless sensor networks. In this paper, the coverage control problem is captured. Some recent novel theories and algorithms for wireless sensor networks coverage control problems are reviewed, and the taxonomy is described. More specifically, several typical algorithms and protocols are discussed in detail. In the end, advantages and disadvantages of the algorithms are summarized. The open research issues in this field are also pointed out.

Abstract:The large scaled TCP abnormal behavior, such as DDoS, scanning etc., can be detected by some metrics and their experimental values derived by the uniqueness of TCP connections. An algorithm named Bloom Filter Reproduction (BFR) is proposed to reconstruct the original parameters in large scaled TCP abnormal behaviors pithily by enhanced simple hash functions. Without maintaining the TCP information of 96bits’ 5-tuple, the BFR algorithm can reconstruct the abnormal parameters such as IP address or their aggregation timely during the detection process. The experiments show that BFR can disclose several abnormal behaviors mixed in network traffic at the same time with high precision and low overhead.

Abstract:With the rapid development of Internet, traditional centralized routers can not meet the requirements of next generation Internet on reliability, performance scalability and service scalability. Cluster routers will be the most important components of future Internet. It is very important for cluster routers to maintain the same forwarding table images among cluster router nodes. Different synchronization mechanisms have variant performance to control plane and packet forwarding plane. After the analysis of two typical synchronization mechanisms, this paper proposes an asymmetrical forwarding table synchronization framework — AREF (asymmetrical routes electing framework) synchronization framework. It fits the requirements of massively parallel cluster routers architecture perfectly. Continuous route flapping of the backbone network burdens the synchronization mechanisms of cluster routers. AREF synchronization algorithm is proposed to decrease the synchronization costs of AREF synchronization framework during route flapping. It uses route cache to predict a new best route when the original best route is deleted, and reduces the synchronization cost of AREF synchronization framework greatly. AREF synchronization framework and algorithm requires diverse abilities for different routing node types and can be used in heterogeneous cluster router widely.

Abstract:In SOA (service oriented architecture), the service registry takes place an important role which complies with UDDI (universal description, discovery and integration) specification. However, some tough problems are still in the way of present UDDI registry. For example, current registry has to replicate all web service publications in all UBR (universal business registry) nodes, and thus becomes impractical for a large number of web services. Furthermore, present UDDI registry is a passive directory and cannot guarantee the real-time validity of the services. In this paper, an active distributed architecture named as adUDDI is proposed for federated web service publication and discovery among multiple registries. With the distributed architecture, the service information is published within one or more adUDDIs so as to avoid the performance bottlenecks in centralized configuration. With the active monitoring mechanism, the service information is updated automatically and then the service requestor may find the latest service information. Finally, comprehensive simulations are evaluated and the results show that it outperforms the existing approaches.

Abstract:Network anomaly detection has been an active research topic in the field of Intrusion Detection for many years, however, it hasn’t been widely applied in practice due to some issues. The issues include high false alarm rate, limited types of attacks the approach can detect, and that such approach can’t perform real-time intrusion detection in high speed networks. This paper presents a network anomaly detector based on Dempster-Shafer (D-S) evidence theory. The detector fuses multiple features of network traffic to decide whether the network flow is normal, and by such fusion it achieves low false alarm rate and missing rate. It also incorporates some self-adaptation mechanisms to yield high accuracy of detection in dynamic networks. Furthermore, light-computation features are used to develop an efficient fusion mechanism to guarantee high performance of the algorithm. On the 1999 DARPA/Lincoln Laboratory intrusion detection evaluation data set, this detector detects 69% attacks at low false alarm rate. Such result is better than the 50% detection rate of EMERALD—the winner of 1999 DARPA/Lincoln Laboratory intrusion detection evaluation, and results from other research projects.

Abstract:It is difficult to distinguish the reliabilities of different resources in the grid environment. For the first time the signaling game theory is applied to the research on grid resource reliability in the paper. A grid resource transaction model based on compensation is proposed and the solution is presented. Theoretical analyses and simulation results show that the resource provider should abandon the cheating motivation voluntarily. The resource demander could make right decision without other nodes’ recommendations, so the calculating and communicating spending is reduced remarkably. This is a new solution to the problem of distinguishing resources’ reliabilities in the grid environment.

Abstract:In order to prolong the network lifetime, energy-efficient protocols should be designed to adapt the characteristic of wireless sensor networks. Clustering Algorithm is a kind of key technique used to reduce energy consumption, which can increase network scalability and lifetime. This paper studies the performance of clustering algorithm in saving energy for heterogeneous wireless sensor networks. A new distributed energy-efficient clustering scheme for heterogeneous wireless sensor networks is proposed and evaluated. In the new clustering scheme, cluster-heads are elected by a probability based on the ratio between residual energy of node and the average energy of network. The high initial and residual energy nodes will have more chances to be the cluster-heads than the low energy nodes. Simulational results show that the clustering scheme provides longer lifetime and higher throughput than the current important clustering protocols in heterogeneous environments.

Abstract:Network correlation plays a key role in the research of Internet topology. Current researches focus on the clustering, mixing and rich-club characteristics separately. This paper makes a deep study on the three network correlation characteristics. First, it points out the possible inconsistency between mean clustering and clustering coefficient, which are two main metrics for measuring the clustering characteristic. Then it shows that the local clustering coefficient is highly correlated with the nodes’ degree. After a deep study of the PFP (positive-feedback preference) model, the intrinsic mechanism governing the rise of rich-club phenomenon is discovered and verified. The work is extended by exploring the relationships between these network correlation characteristics.

Abstract:Dynamic topology is the essential difference between mobile ad hoc networks and other kinds. It is meaningful in both theory and industry application to study the dynamic topology of mobile ad hoc networks. In this paper, a method is proposed to study the dynamic topology with longest lifetime path. On basis of the previous research, the mathematic model of networks is improved to describe the change of topology. Based on it, the algorithm of longest lifetime path is presented and the distribution of its duration is studied. At the same time, it is proved that the re-routing is minimal with the longest lifetime paths as the routes. Simulation with NS -2 shows that the distribution of lognormal can be used to describe the duration of longest lifetime paths. The results show that the longest lifetime path and minimal re-routing are more suitable than the shortest path as the metrics to measure the dynamic of networks.

Abstract:The notion of quantum secure direct communication (QSDC) has been introduced recently in quantum cryptography as a replacement for quantum key distribution, in which two communication entities exchange secure classical messages without establishing any shared keys previously. In this paper, a quantum secure direct communication scheme using quantum Calderbank-Shor-Steane (CSS) error correction codes is proposed. In the scheme, a secure message is first transformed into a binary error vector and then encrypted (decrypted) via quantum coding (decoding) procedures. An adversary Eve, who has controlled the communication channel, can't recover the secrete messages because she doesn't know the deciphering keys. Security of this scheme is based on the assumption that decoding general linear codes is intractable even on quantum computers.

Abstract:Regularity is an important algebraic property of parametric curve and surface, which depends on the parameterization of parametric curve and surface. In computer-aided manufacturing, the processed parametric curve and surface should be regular, so the parametric curve and surface generated by computer-aided design should be regular first. However, the computation of determining the regularity of parametric curve and surface by solving equation or system of equations induced by the definition of regularity is considerably complex, and is actually infeasible. In this paper, by transforming the parametric representations of derivative vector curve (of Bézier curve) and normal vector surface (of Bézier surface) to their implicit representations, a simple and practical sufficient condition for determining the regularity of Bézier curve and surface is presented.

Abstract:Pose and illumination changings from picture to picture are two main barriers toward full automatic face recognition. In this paper, a novel method to handle both pose and lighting conditions simultaneously is proposed, which calibrates the pose and lighting to a predefined reference condition through an illumination invariant 3D face reconstruction. First, some located facial landmarks and a priori statistical deformable 3D model are used to recover an elaborate 3D shape. Based on the recovered 3D shape, the “texture image” calibrated to a standard illumination is generated by spherical harmonics ratio image and finally the illumination independent 3D face is reconstructed completely. The proposed method combines the strength of statistical deformable model to describe the shape information and the compact representations of the illumination in spherical frequency space, and handles both the pose and illumination variation simultaneously. This algorithm can be used to synthesize virtual views of a given face image and enhance the performance of face recognition. Experimental results on CMU PIE database show that this method can significantly improve the accuracy of the existing face recognition method when pose and illumination are inconsistent between gallery and probe sets.

Abstract:Interactive navigation of very large-scale terrain environment involves many difficulties because of its out-of-core geometric data and texture, which can not be wholly loaded into the internal memory. This paper puts forward a high performance technique for real-time walkthrough of the large-scale terrain environments. It performs geometric simplification within each terrain chunk during preprocessing and then generates a view-dependent continuous LOD of the whole scene with geomorphing at runtime. Both silhouette preserving and shading preserving criteria are satisfied by applying a new error metric-constrained normal cone to view-independent simplification. The generated models for rendering is more suitable to human’s perception than those by traditional geometric simplification criterion. Furthermore, the pre-extracted potential silhouette of each chunk can be used to construct the incremental horizon dynamically. This can prevent the ineffectual data from loading into the main memory and reduce the out-of-core paging and the number of triangles feeding to the renderer, thus lead to significant saving in interactive rendering. This paper also makes use of the advantage of GPU to generate lighting and shadow for large-scale outdoor environment, and balances the tradeoff between GPU, CPU and I/O through multi-thread.

Abstract:This paper presents an approach of constructing the application system in Distributed Virtual Reality. Based on a component model of application system in which three types of the basic components are discussed, this paper first focuses on the “semantic” interoperability among components, and presents a Primitive-Semantic component constructing method through a semantic model to deal with the semantic interoperability while the communication protocol among components doesn’t exist. It then presents a composable Distributed Virtual Reality Component-Based Architecture, including its key mechanism and algorithms. Finally the experimental result demonstrates the usability of this architecture.

Abstract:With the necessary and sufficient conditions for C^k-continuity of uniform stationary subdivision schemes, the range of free parameter in several classical interpolating curve schemes is presented. For the first time, this paper points out that the arity-2 interpolating 6-point scheme is C³-continuous in certain range. A new C³-continuous arity-3 interpolating 6-point scheme is also proposed.

Abstract:This paper, solves the 3D fluid dynamics problem in a complex environment by taking advantage of the parallelism and programmability of GPU (graphics processing unit). In difference from other methods, innovation is made in two aspects. Firstly, more general boundary conditions could be processed on GPU in the method. By the method, the boundary from a 3D scene with capped solid clipping is generated, making the computation run on GPU despite of the complexity of the whole geometry scene. Then by grouping the voxels into different types according to their positions relative to the obstacles and locating the voxel that determines the value of the current voxel, the values on the boundaries are modified according to the boundary conditions. Secondly, more compact structure in data packing is designed at the fragment processing level to enhance parallelism and reduce execution passes. The scalar variables including density and temperature are packed into four channels of texels to accelerate the computation of 3D Navier-Stokes Equations. The test results show the efficiency of the method, and as a result, it is feasible to run middle-scale problems of 3D fluid dynamics in an interactive speed for more general environment with complex geometry on PC platform.

Abstract:Based on the multi-layer textures approach, a new method of rendering real-time fur is proposed. The method takes full advantage of the new features of current Graphic Processing Units to compute the lighting of fur precisely and fast. More importantly, the self-shadow effect of fur and the soft shadow phenomenon over fur are simulated successfully, which enhances the rendering effects greatly. Experiments show that the method can deal with moderate models in real-time, which is very valuable for the applications of fur in many fields, such as cinema, video game and virtual reality etc.

Abstract:Ray casting is a widely recognized method for high quality volume rendering. It traverses and samples the volume data ray by ray in image space. Traditionally, the algorithm is implemented in CPU on PC platform,resulting in slow speed and poor interacfivity. This paper introduces a new technique named View Dependent Layer Sampling (VDLS), which supports a hardware implementation of ray casting by Graphics Processing Unit (GPU).VDLS organizes the ray sampling points into a set of layers which can be efficiently represented by two view dependent geometric buffers as two dynamic textures. Based on the structure of VDLS, the six steps involved in the ray casting algorithm including ray generation, ray traversal, interpolation, classification, shading and composition can be fully accomplished in GPU, taking advantage of its programmability and flexibility. In addition, two speedup techniques exploiting object space and image space coherence are proposed for fast culling of the lapsed rays.Several advanced features regarding illumination and composition are further discussed, with which VDLS is capable of reconfiguring the well-known geometric hardware engine for volume ray casting. The novel approach of GPU supported ray casting can render up to 150 million interpolated, post shaded and composed ray samples per second for perspective view. Experimental results suggest that the proposed framework can be regarded as an alternative for on-the-fly visualization and exploitation of discrete scalar data in medical visualization, physical phenomena simulation and material testing applications.

Abstract:In practice, the schedulability of static priority scheduling may be reduced when priority levels of the system are insufficient. If a task set requires more priority levels than the system can support, several tasks must be assigned the same priority level. This causes the priority mapping problem. To solve it, a priority mapping algorithm and necessary and sufficient conditions for analyzing the schedulability of a task after priority mapping are needed. There are three kinds of priority mapping algorithms: decreasing priority assignment algorithm, increasing priority assignment algorithm, and threshold segment mapping algorithm. This paper presents implementation and analyzing conditions of algorithms. Properties of the algorithms are also described and showed. Performance of the algorithms is compared through simulations. Simulation results and conclusions are useful for designing and implementing real-time embedded systems.

Abstract:In hybrid real-time systems, schedulers must guarantee that all of hard real-time jobs are finished by their deadlines and the QoS of soft real-time tasks and non real-time tasks are improved as greatly as possible. This paper presents RPDS (rigorously proportional dispatching server) algorithm, and constructs a hierarchical scheduling framework based on that. RPDS partitions CPU time flow into continuous segments, and in each segment RPDS will forcibly assign one time slice to non-hard real-time tasks. Experimental results show that RPDS can allocate processor time to various application classes reasonably and reduce the deadline miss ratio of real-time tasks effectively.

Abstract:Aspect-Oriented software development (AOSD) is a new type of software design idea and technique. This paper analyzes recent research results in three fields which are: (1) the crosscutting concerns and Aspect concept in operating systems; (2) component reconstruction, system evolution and design, and system security; (3) performance monitoring and fault tolerance. The paper points out that some positive research results of Aspect-Oriented operating systems have been acquired. However, the current research results lack necessary deepness and extent, the operating systems that adopt the Aspect idea during design stage do not exist yet, and there is no whole engineering and standardization for Aspect extraction procedure in the existing operating systems code. The solutions for these problems rely on further Aspect-Oriented research results. Final, the paper describes the respective of Aspect oriented operating systems research and indicates that the research of AOSD may possibly bring a significant impact to the research and development of future operating systems.

Abstract:Symbolic WCET (worst-case execution time) analysis yields symbolic upper bound expressions for tasks that contain parameters. Quickly evaluated at run-time, such expressions can improve the accuracy of WCET estimate. This paper proposes a symbolic WCET analysis method that is especially for the input-data dependent branches. First, the formulas described by Blieberger is expanded, so that they can express the input-data dependent branches. Simplification of the formulas using control-dependent graph yields conditional symbolic expressions that have different forms corresponding to different input value ranges. Different from the existing methods, the symbolic formulas are directly dependent on input-data, so WCET estimate evaluation at run-time is more simple and straightforward.

Abstract:parametric worst-case execution time (WCET) analysis;WCET analysis;program analysis;real-time system;software engineering