Abstract:Abstract: This paper proposes an approach for subgraph isomorphism testing from a set of priori given small graphs to a large graph issued on-line. In order to reduce the computational cost,based on DFS Code,an elaborate organization of a set of graphs is presented,and a look-ahead-pruning based algorithm of subgraph isomorphism testing from multiple small graphs to a large graph is proposed.Moreover, an index technique based on data miningis introduced.Analytical and experimental results show the on-line computational cost of the proposed method is much less than the state-of-the-art method and it is about one order of magnitude faster than the existing method with more than one order of magnitude less off-line construction time.

Abstract:This paper improves and extends the pointer logic that has been designed for verifying pointer programs. Its main contribution is that a concept of legal sets of access paths is presented, which simplifies elementary operations on access paths and makes inference rules of the logic easier to understand. Furthermore, the logic with inference rules is extended for local reasoning and for function construction, making the logic used conveniently in the context of function calls.

Abstract:Automatic generation of poetry has always been considered a hard nut in natural language generation.This paper reports some pioneering research on a possible generic algorithm and its automatic generation of SONGCI. In light of the characteristics of Chinese ancient poetry, this paper designed the level and oblique tones-based coding method, the syntactic and semantic weighted function of fitness, the elitism and roulette-combined selection operator, and the partially mapped crossover operator and the heuristic mutation operator. As shown by tests, the system constructed on the basis of the computing model designed in this paper is basically capable of generating Chinese SONGCI with some aesthetic merit. This work represents progress in the field of Chinese poetry automatic generation.

Abstract:Missing reads occur frequently during RFID (radio frequency identification) data collection, which will reduce the accuracy of query results in RFID applications. To solve this problem, the existing algorithms mainly take primitive RFID readings as granularity and adopt window smooth strategy based on tag historical readings, which may interpolate data that the query doesn’t care about and incur inaccuracy when multiple logic areas are involved. In this paper, data are transformed from data level to logic area level as the interpolation granularity. Then three data interpolating algorithms based on the probabilistic path-event model are proposed, where the incoming events are judged and interpolated by mining the sequence correlation of known area events. Furthermore, the factor of time is considered,and thus probabilistic path-event model is developed. Abundant experiments prove the proposed algorithms have different performance advantages in different conditions and are predominant over the existing strategy in redundancy and accuracy.

Abstract:This paper proposes a novel method for object recognition by using a computational model of feature binding, in which Gabor features are employed as the elementary features and correlation statistics provide the basis for implementing the feature binding. A group of object recognition experiments are conducted with this method,and the results prove the comparatively good performances with high recognition precision and high speed,indicating the validity of this method and the computational model.

Abstract:To overcome the difficulty of analyzing and detecting the data race in multithread programs, a method based on Hidden Markov model is presented for the analysis of time sequences in multithread programs. The random variable uncertainty is used to depict the mutual influence in different multithread in time sequences, and the probability distribution for random variable uncertainty is analyzed as the outcome of multithread programs on the condition of data race. Hidden Markov model is constructed to appreciate the state for the thread running according to the observed values of the running threads. The Baum-Welch and forwarding algorithm are used to simulate the real running process of the programs in the influence of context. It is proved by experiments that HMM model can quickly and effectively reflect the time sequence of the multithread programs, which can be used to instruct the detecting process of multithread programs.

Abstract:Wireless sensor networks are often deployed in diverse application specific contexts, which can be treated essentially as distributed databases. The event-involved responses can be obtained by issuing queries to this kind of database. The applications with real-time requirement have tight constraints on query delay. However, the existing query algorithms cannot meet the demands of the real-time query applications. With regard to the special applications, a real-time query processing algorithm based on ant colony optimization is proposed. In this algorithm,priority-based multiple-rings storage scheme and ant-based distributed search mechanism are adopted to improve the integrated performance of energy-efficiency, delay and query reception rate. It takes advantage of the self-organization and positive feedback characteristics of ant colony optimization algorithm. The proposed algorithm provide a new idea for distributed dynamic parallel real-time query applications, demanding merely local information to obtain named events efficiently and determine the number and allocation of event replicas adaptively.Theoretical analysis and experiments prove that compared with other existing query algorithms, this algorithm cannot only improve the performance of energy-efficiency and reception, it can also shorten the query delay considerably.

Abstract:The delay tolerant mobile sensor network (DTMSN) is a type of sensor network used for pervasive information gathering. DTMSN distinguishes itself from conventional sensor networks by several unique characteristics such as sensor mobility, loose connectivity, and delay tolerability. Therefore, traditional data gathering methods cannot be applied. In this paper, a novel data gathering method named relative distance-aware data delivery scheme (RDAD) is proposed. RDAD introduces a simple non-GPS method with small overhead to gain the relative distance from a node to sink and then to calculate the node delivery probability which gives a guidance to message transmission. RDAD also employs the message survival time and message maximal replication to decide message’s transmission and dropping for minimizing transmission overhead. Simulation results have shown that the proposed RDAD data delivery scheme does not only achieve a relatively long network lifetime but also get the higher message delivery ratio with lower transmission overhead and data delivery delay than other DTMSN data delivering approaches.

Abstract:The main topic of inter-domain routing security management is how to suppress the propagation of untrustworthy routes and malicious routing behaviors. Supervising and evaluating autonomous system’s (AS)routing behaviors is a key technology in this topic. This paper designs a distributed collaborative reputation mechanism of trustworthiness evaluation for AS’s routing behaviors. The mechanism takes in the statistical results on routing trustworthiness published by AS, uses a self-organizing method, employs posterior probability analysis,and finally calculates a reputation score for a particular AS. The score will be used as a metric on the trustworthiness of the routing information that AS propagates or announces afterwards. In simulations, this reputation mechanism has been shown to effectively contain AS’s bad behaviors, and hence improve the overall security of the inter-domain system. The reputation mechanism designed in this research supplies a reference to evaluation and analysis of AS’s routing behaviors. It has the following features: It supports incremental deployment.It needn’t modify the BGP protocol, so it is easy to be implemented.

Abstract:This paper proposes a key management scheme using time-based deployment for wireless sensor networks, which is characterized by a special two-tier random key pre-distribution and elimination mechanism as well as a time-based group deployment method. Each sensor node randomly chooses keys from multiple key pools and deletes related keys when certain conditions are satisfied; All the sensor nodes are organized into deployment groups and are chronologically deployed into the network. Compared with classical key management schemes for wireless sensor networks, The proposed scheme increases node resource efficiency and enhances network resilience against node compromise while ensuring a relatively high node connectivity for pair-wise key generation.

Abstract:The unevenly distributed traffic of Internet may lead to congestion and underutilization of network resources. Current methods of routing adjustment for load balancing often get a new path with excessively long length that can exacerbate the quality of service. This paper presents a new flow routing adjustment algorithm named LCBA (length-constrained most balanced algorithm), which can decrease the maximal bandwidth utilization rate of network with delay guaranteed. The experiment based on Abilene2 network topology and traffic data shows that LCBA can mitigate the congestion of backbone network effectively and the maximal bandwidth utilization rate can drease nearly 50% at most. This paper also evaluates the algorithm with an emulation method. Compared with current methods, the new algorithm can satisfy the demand of not only the length of key flow’s path but also the maximal bandwidth utilization rate. Moreover, the theoretical analysis proves that the computational complexity of LCBA is O(N2logN), which is better than that of a majority of methods nowaday.

Abstract:Based on predecessors’ work, this propose the concept of degenerate test set (DTS) and an approach that performs test generation and redundancy elimination in the light of the special requirement of verification of the secure operating system. This approach is secure state transition-based for the first time and can generate an efficient test set by reducing the redundant system state transitions and similar properties with model checkers in the test case generation. Furthermore, it discusses the validity of the DTS when only some cases of the set fail and improve the DTS generation algorithm. The experiments prove that this approach can reduce the size of test set efficiently.

Abstract:Traditional backoff algorithms in IEEE 802.11 networks adopt contention window scheme for collision resolution. Collided nodes are redistributed in extended window ranges to avoid further collisions. However, as long as these distribution windows intersect with each other, collision may still occur. To solve this problem, this paper puts forward a collision classification model to classify collisions into cross collision and intra collision and proposes to solve them with different policies. It utilizes sequential discrete window distribution (SDWD) scheme to resolve cross collision by distributing the collided nodes in a series of discrete Elementary Windows and the intra collision is resolved with an appropriate elementary window size to achieve a tradeoff between intra collision probability and packet latency. Based on this proposal, two algorithms are developed featuring cross collision resolution (CCR) and collision-free CCR (CF-CCR). The extensive simulations demonstrate that compared with IEEE 802.11 DCF protocol, the CCR and CF-CCR algorithms consistently excel, in terms of collision rate,throughput, delay, fairness and delay jitter. Moreover, CCR and CF-CCR exhibit their respective advantages in different scenarios.

Abstract:This paper points out the limitations of the existing Markov model of DCF protocol based on un-fixed slot in ad hoc networks, and analyzes the difficulty of the modeling of DCF protocol in multi-hop ad hoc networks in detail. On the basis of this, this paper proposes a Markov model of DCF protocol based on fixed slot in multi-hop ad hoc networks. By solving this model, the theoretic value which reflects the saturated throughput performance of multi-hop ad hoc networks is obtained. The effectiveness of this model is demonstrated by the simulations in GloMoSim environment.