Abstract:Based on the classical smoothing technology, this paper proposes a smoothing approach within head-driven parsing, which directly calculates interpolation weight from the average occurrences of event in the training sample and is proved by the statistic theory of errors. By using this approach and deriving zero-value assumption from other smoothing technologies, this paper proposes four smoothing algorithms for head-driven parsing. Experiments indicate that these four smoothing algorithms have higher performance than the Baseline algorithm and reduce the disturbing curve of the optimized parameter significantly, which prove the effectiveness of the proposed approach.

Abstract:The M-elite coevolutionary algorithm (MECA) is proposed for high-dimensional unconstrained numerical optimization problems based on the concept of coevolutionary algorithm and elitist strategy. In the MECA, the individuals with high fitness, called elite population, is considered to play dominant roles in the evolutionary process. The whole population is divided into two subpopulations which are elite population composed of M elites and common population including other individuals, and team members are selected to form M teams by M elites acting as the cores of the M teams (named as core elites) respectively. If the team member selected is another elite individual, it will exchange information with the core elite with the cooperating operation defined in the paper; If the team member is chosen from the common population, it will be led by the core elite with the leading operation. The cooperating and leading operation above are defined by different combinations of several crossover operators or mutation operators. The algorithm is proved to converge to the global optimization solution with probability one. Tests on 15 benchmark problems show that the algorithm can find the global optimal solution or near-optimal solution for most problems tested. Compared with three existing algorithms, MECA achieves an improved accuracy with the same number of function evaluations. Meanwhile, the runtime of MECA is less, even compared with the standard genetic algorithm with the same parameter setting. Moreover, the parameters of the MECA are analyzed in experiments and the results show that MECA is insensitive to parameters and easy to use.

Abstract:In this paper, a fuzzy scatter difference discrimininant criterion is presented. Based on this criterion, fuzzy clustering algorithm FMSDC (fuzzy maximum scatter difference discriminant criterion based clustering algorithm) is also presented. The proposed algorithm reduces dimensionality while clustering by iterative optimizing procedure. First, it introduces the fuzzy concept into maximum scatter difference discriminant criterion; then the parameter η in the fuzzy criterion is appropriately determined based on specific principles so that the sensibility aroused by parameter η can be decreased to some extent; At last clustering and reducing dimensionality are realized according to fuzzy membership μ_ik and optional discriminant vector ω, respectively. Experimental results demonstrate the proposed method FMSDC is not only capable of clustering but also robust and capable of reducing dimensionality.

Abstract:This paper describes the current state of the art of RDF (resource description framework) data management from 4 aspects, storage organization, query processing and optimization, prototypes as well as benchmarks. It also points out some future research topics.

Abstract:This paper studies uncertain graph data mining and especially investigates the problem of mining frequent subgraph patterns from uncertain graph data. A data model is introduced for representing uncertainties in graphs, and an expected support is employed to evaluate the significance of subgraph patterns. By using the apriori property of expected support, a depth-first search-based mining algorithm is proposed with an efficient method for computing expected supports and a technique for pruning search space, which reduces the number of subgraph isomorphism testings needed by computing expected support from the exponential scale to the linear scale. Experimental results show that the proposed algorithm is 3 to 5 orders of magnitude faster than a na?ve depth-first search algorithm, and is efficient and scalable.

Abstract:A system of structural integrity constraints for XML (XSICs) is introduced, which specifies five structural relationships between different paths or nodes in XML documents, including path implication, path cooccurrence, path mutual-exclusion, obligatory inclusion and exclusive inclusion. This paper defines the syntax and semantics of these XSICs, and studies their core role in XML query optimization. Based on the concept of sub-path, this paper proposes an algorithm for minimizing path expression in the presence of XSICs. By using the path implication closure as a tool, the algorithm cannot only effectively eliminate redundant nodes or predicates, but also identify invalid path expressions. Experimental results show the effectiveness and efficiency of the proposed minimization algorithm.

Abstract:This paper surveys related research work of Internet overlay routing, and focuses on the structure and methods of Internet overlay routing on network layer and transport layer according to Internet layering scheme. Apart from that, other related aspects of overlay routing are discussed, including the impacts on overlay routing performance, and interactions between multiple overlay networks routing, etc. The advantages and disadvantages in the key technologies of related research work are analyzed. At last, the possible future research directions are discussed as references for the research of Internet overlay routing.

Abstract:Pairings have found many cryptographic applications in recent years. The efficiency of implementing these cryptographic applications is determined by the speed of pairing computations. This paper categorizes and reviews the current progress on efficient pairing computations, and suggests the possibility of further research.

Abstract:The TOA (time of arrival) estimation algorithms based on match-filtering detection for UWB (ultra wideband) wireless sensor networks are extensively studied in this paper. Based on the analysis of the drawbacks of the algorithms in the literature, a three-step algorithm is proposed: first, determine the search region for DP (direct path) detection; then, a rough detection of DP is made by threshold comparison; and last, the precise location of DP, i.e., the center of the arriving pulse, is obtained by a refined search process. The threshold factor used to calculate the threshold in the second step is set dynamically by using a model in terms of the kurtosis of the match-filtering output. The model is well independent of the channel model, and its effectiveness is proved through the comparison of the resulted performance with that of using fixed threshold factor. By comparing the performance of this algorithm with that of other algorithms, it can be observed that the proposed three-step algorithm has achieved a good trade-off between computational efficiency and estimation accuracy, thus more appropriate for current applications. In addition, the reliability of TOA estimation result is discussed through statistical analysis. Two levels of reliability are defined with regard to the corresponding kurtosis of the TOA estimation, and the probability density function for TOA estimation errors of each level is modeled. Properly incorporating the reliability information into the positioning algorithm will definitely improve the final location estimation accuracy.

Abstract:An energy balancing routing model and its solution algorithm in wireless sensor networks are proposed in this paper, taking all the following factors into consideration: link access, packet transmission energy consumption and the remaining energy in the nodes. Its objective is to balance the energy consumption and maximize the network lifetime. Firstly, a distributed dynamic routing tree building algorithm and a routing selection function of two neighbor nodes are proposed with the cross-layer method, which satisfied the nodes’ computing capabilities. Secondly, a bi-level programming model and its algorithm are presented to make the energy consumption of the network tend to equilibrium and maximize the network lifetime. A numerical example illustrates the validation of the proposed routing policy and the bi-level programming model.

Abstract:In order to improve the scalability of multicast protocol in large-scale distributed interactive systems, a content-based bi-directional shared multicast routing protocol is presented, which is called CBSMRP (content-based bi-directional shared multicast routing protocol). Combined with active routing methods and content-based publish/subscribe pattern, this new protocol supports active routing and bi-directional filtering according to the content of packages in a bi-directional shared multicast tree based on CBT (core-based tree) structure, which cannot only solve the problems in the allocation and maintenance of multicast addresses, but also efficiently reduce the network load. Experimental results and application show that the protocol is scalable enough to meet network communication requirements of large-scale distributed interactive systems.

Abstract:Tests demonstrated that the wireless link quality of statically deployed sensor networks frequently varied in a short time span. Traditional link estimation methodology works well in the varying case of long time span, but poor in that of short time span. This paper proposes a multi-link cooperative forwarding protocol on fine-grain gradient strategy (MCFS), which can avoid the influence of quality jitters on parts of forwarding links through single-send-multiple-receive plus strategy on the synchronized random contention of ACK. A new channel model was developed on NS2 platform, which could simulate the link quality changing in a short time based on the model of two states non-homogeneous Markov chain. Through this channel model, the following conclusions would be reached: (1) MCFS protocol can adapt and work well with short time varying of link quality; (2) In reasonable configuration, MCFS was quite effective on performances in the network delivery rate and energy efficiency, compared with mono-link optimized protocol by the criteria of HOP/PRR, disjoint and braid multi-path forwarding protocols; (3) The good features of MCFS were independent of both network scale and nodes density of deployment.

Abstract:This paper proposes a belief multisets formalism for analyzing cryptographic protocols, and the formalism is foundationally different from the previous: a participant’s beliefs should depend only on the sent or received fresh messages and the beliefs already possessed by this party. The presented security adequacy of unilateral authentication secure, mutual authentication secure, unilateral session key secure, or mutual session key secure is proved not only substantial but also necessary to meet 4 security definitions respectively under the computational model of matching conversation and indistinguishability. Illustrations and comparison show that the analysis results based on the belief multisets suggest the correctness of a protocol or the way to construct attacks intuitively from the absence of security properties. The formalism is independent of the concrete formalization of a protocol or attackers’ possible behaviors. The formalism can be developed not only by hand but also by automation.

Abstract:Routing quality is affected by several factors altogether in mobile ad hoc networks (MANET). Most of current MANET routing protocols utilize hop count or other metric as their route creation criteria, which makes it hard to improve the overall protocol performance. This paper proposes an integrated routing metric which takes energy, communication interference, drop rate and mobility of a node (EIDM) into consideration. With an adaptive weight, this metric can adjust its stress on different items according to the network condition. Simulation results show that the EIDM does well in mitigating the hotspot effect.

Abstract:Using location information to assist routing is often proposed as an efficient means to achieve scalability in large mobile ad hoc networks (MANET). This paper proposes an algorithm, named as Cluster-Based Location Aided Routing (CLAR), a scalable and efficient routing algorithm for MANET. CLAR runs on top of a one-hop cluster cover of the MANET, which can be created and maintained by, for instance, the Least Cluster Change (LCC) algorithm. It has been proven that LCC can maintain a cluster cover with a constant density of clusterheads with the minimal update cost. CLAR then utilizes nodes’ location information to improve the network layer performance of routing. The location information of destination node is used to predict a smaller isosceles triangle, rectangle, or circle request zone, which is selected according to the relative location of the source and the destination, that covers the estimated region where the destination may locate. Instead of searching the route in the entire network blindly, CLAR confines the route searching space into a much smaller estimated range. Simulation results have shown that CLAR outperforms other protocols significantly in route set up time, routing overhead, mean delay and packet collision, and simultaneously maintains low average end-to-end delay, high success delivery ratio, low control overhead, as well as low route discovery frequency.