Abstract:Reducing power consumption to extend network lifetime is one of the most important challenges in designing wireless sensor networks. One promising approach to conserving system energy is to keep only a minimal number of sensors active and put others into low-powered sleep mode, while the active sensors can maintain the communication connectivity and cover the target region completely. The problem of computing such minimal active sensor set is NP-hard. In this paper, a centralized Voronoi tessellation (CVT) based approximate algorithm is proposed to construct a near optimal cover set of active sensors required to cover the target region completely. The communication graph induced by the cover set computed by CVT algorithm is connected if sensor’s communication radius is at least twice of its sensing radius. In case of sensor’s communication radius is smaller than twice of its sensing radius, a minimum spanning tree (MST) based connection algorithm is proposed to ensure the communication connectivity of the cover set. Finally, the performance of the proposed algorithm is evaluated through theoretical analysis and extensive numerical experiments. Experimental results show that the proposed algorithm outperforms the greedy algorithm in terms of the runtime and the size of the constructed connected cover set.

Abstract:On the basis of analyzing the newly time sequence research achievement nowadays, several definitions on seismological zone relativity are put forward in this paper for integrating the large amount of history earthquake source data and the experimental expert knowledge in seismological field. At the same time, the time sequence similarity-matching model of the relevant seismological zone is presented, and then it is implemented through several correlative experimental simulations. Based on the sequence similarity-matching model, a sequence-matching algorithm is given with seismological similarity. Furthermore, by discovering the history earthquake database (EQDB) in recent 20 years, some experiments are provided to analyze longitudinal thick-granularity sequential similarity and thin-granularity sequential similarity. Finally, the experimental result has found its satisfactory way out by using the proposed algorithm to support earthquake prediction.

Abstract:An error correcting algorithm is presented for detecting and correcting errors in the sequencing data before assembly process. The approach maps the sequencing data to an Euler superpath, and simplifies it dynamically by an equivalent transformation named Merging Transformation. In such a process, the algorithm isolates the right edges and error ones so that error paths are substituted and the corresponding errors in the sequencing data are corrected. In two test sets T.tengcongensis and T.whipplei, the algorithm has detected and corrected 86% and 83% errors on the “corrected” sequences respectively, compared with 71% and 53% errors using the original error correcting algorithm in the Eulerian path approach.

Abstract:This paper studies wavelength assignment algorithms on WDM all-optical trees of rings under different models: static, incremental and dynamic. It is shown that 5L/2 is the tight bound of the number of required wavelengths for static trees of rings with load L. This paper also proposes an O[log₂(t+1)]-approximation and a ∑_i=1^hmax_r∈Ri[log | V(r)|] +h-approximation algorithm for incremental and dynamic trees of rings respectively, where t,h and R_i are the number of rings, the number of the layers of the underlying tree and the set of rings of layer i in the network respectively.

Abstract:Some problems on Algorithmic Composition are discussed, and a survey for series of key techniques used in this approach is made, which include Markov chains, stochastic process, musical knowledge based system, musical grammar, artificial neural networks, and genetic algorithms. The conclusion is that the development of music composition system should involve a combination of the existing technologies, i.e. the Hybrid System development. In order to make the system become more practical and effective, there should be some flexible human intervenient ways for different level music composition in the system.

Abstract:Correlation algorithms based on pixel gray value are very popular and widely used in image template matching. However, these algorithms have high time complexity and are sensitive to the variation of image luminance and scale. To avoid that, a new algorithm based on coding image grey value is proposed. This algorithm divides the image into certain size blocks called R-block, sums the gray value of each R-block pixel, and codes the R-block according to the sorting result among the neighborhood of R-blocks. Image and template are matched by comparing their R-block coding. The R-block is very rapidly and easily coded and only equality comparison is needed. The new algorithm is robust to the linear transformation of pixel grey value and image noise. Its time complexity is reduced to O(M²log(N)), or namely is improved two order of magnitude in contrast to the current correlation algorithms’.

Abstract:Kernel method is an effective and popular trick in machine learning, and small world network is a common phenomenon which exists widely in social fields. In this paper, by introducing them into Hattori et al’s multi-module associative memory for many-to-many associations ((MMA)²), a unified framework of small world structure inspired many-to-many kernel associative memory models (SWSI-M²KAMs) is proposed. The SWSI-M²KAMs not only can store patterns online without more iteration steps, but also extend the range of the processed intelligent information. More importantly, the SWSI-M²KAMs framework can develop more new many-to-many associative memory models by selecting different kernel functions and reduce models’ configuration complexity by using the sparse small world architecture. Finally, computer simulations demonstrate that the constructed models have good performance on many-to-many associative memory.

Abstract:As a main method for predicting the functionality of genes, the sequence similarity querying technique is becoming one of the research hotspots in bioinformatics. The similarity of gene sequence and structure usually determines the similarity of gene functionality, and the function of an unknown gene can be predicted by sequence similarity querying. After analyzing the advantages and shortcomings of related work such as frequency transformation and wavelet transformation used in MRS, a new sequence similarity query processing technique based on the two-Partitioning Frequency Transformation 2-PFT is proposed. Firstly, the Two-partitioning frequency transformation and the corresponding distance function are designed. They have a higher filtering ability than frequency transformation and wavelet transformation, and the system performance is thus improved significantly. Secondly, the problem of processing the queries with any length is solved. Theoretical proof and experimental results show that the 2-PFT system outperforms the MRS system greatly.

Abstract:In most fingerprint classification and identification algorithms, extracting the number and precise location of singular points (core and delta) is of great importance. In this paper, an adaptive algorithm for singular points detection is proposed, which is based on the behavior of Gaussian-Hermite moments. In order to detect singular point accurately, the distribution of Gaussian-Hermite moments of different orders of the fingerprint image in multiple scales is used. A PCA-based (principal component analysis) method is used to analyze the distribution of Gaussian-Hermite of fingerprint image. Experimental results show that the proposed algorithm is able to locate singular points in fingerprint with high accuracy.

Abstract:In this paper, the interaction patterns and their automatic analysis in spontaneous spoken information-seeking dialogues are studied. First, based on previous work from discourse analysis (i.e., exchange as basic interaction unit in Birmingham School) and Sytemic Functional Grammar (i.e., Halliday’s speech function), a principled scheme is proposed to model interaction patterns with utterance groups. Then a dialogue corpus is annotated with this scheme and further analyzed. Some main factors affecting the structure of utterance group are distinguished. Based on these, an algorithm is established to analyze utterance groups and is evaluated in the corpus. The results achieve a correct rate of 55.4%～84.2% for overall utterance tags, depending on the different recognition performances of the extended sentence type and utterance topic.

Abstract:This paper describes the application of Fuzzy k-Means, a derivant of k-Means that may assign an item to more than one cluster, in the task of inducing fuzzy classes for Chinese polysemic verbs. The probability distributions over subcategorization frames of 60 Chinese verbs, among which there are 40 polysemic ones and 20 monosemic ones are first acquired, and then these verbs are clustered into fuzzy classes. Evaluation and post-hoc analysis show that a combined measure of purity and pairwise precision can better estimate the clustering performance, and although to a certain extent syntactic behaviors of verbs have their counterparts of meaning components underlying, syntactic behaviors of verbs cannot be easily predicted from a single semantic level, at least for Chinese polysemic verbs.

Abstract:In this paper, a concept of neighborhood for bandwidth allocation and a new bandwidth scheduling scheme are introduced based on two classical scheduling algorithms: round-robin and random choice. The proposed scheme first optimizes the bandwidth scheduling for a subset of Subscriber Station (SS), and then provides the optimal performance based on bandwidth scheduling for the whole WiMAX (world interoperability for microwave access) network, especially in the Mesh mode with step-wise approach. Extensive simulation results using NS2 show that the proposed scheme incurs a short delay and increases system throughput while using the network resource efficiently.

Abstract:Delay is the foundation for accurately measuring network performance metrics such as delay jitter, bandwidth, etc. While the delay measurement methods currently used have poor precision, for there exist clock errors and location errors. In this paper, an improved method for delay measurement is proposed. It replaces system clock with TSC (time stamp counter) register as time-stamping to eliminate clock errors, and it removes the time-stamping place from application to network driver to eliminate location errors. The precision has been elevated largely. Experiments show that when comparing with traditional methods under different packet lengths, the improved method can reduce measurement errors 21%~150%, and the measured delays are more stable. Furthermore, it basically has no effect on system throughput. The improved measurement method is based on general PC, so it has lower measurement cost and can be applied widely.

Abstract:PIM-SM (protocol-independent multicast-dense mode) is currently the preferred intra-domain multicast routing protocol. One problem that impedes its widely use is its high overhead of control messages. In order to improve and optimize the PIM-SM, its performance model should be established and the nicety performance analysis should be made above all. In this paper, the Stochastic Petri Net (SPN) model of the whole PIM-SM protocol is established, and the analysis and the experiments are made on the router processing load caused and the network bandwidth consumed by each type of the protocol messages, based on the model and router realization. It is discovered that register message and Join/Prune message cause most router processing load, while Join/Prune message and Bootstrap message consume most network bandwidth. According to the conclusion of performance analysis, an improvement is made on PIM-SM, which is achieving better performance compared with the former protocol.

Abstract:Under the situation of detecting attacks, current IDSs have no good reacting strategy to filter attack traffic. Based on network attacks’ traffic characters, an anomaly traffic character aggregation algorithm (AFCAA) is put forward. Because normal DOS (denial of service)/DDOS (distributed denial of service) attack traffic has some characters in their packets’ head, AFCAA uses the center of gravity theory to process statistic aggregation and aggregation partition based on the special field of the destination IP attack traffic in a fixed Euclid distance, and then it distills the center of attack traffic dynamically as the characters of attacks. Afterwards, through transmitting these characters to Net Filter, AFCAA can filter abnormal packets efficiently and protect the normal packet transmission. The experimental results show that the software router using AFCAA can efficiently find useful characters of prevalent DOS/DDOS attacks, reduce the harm of attack packets’ spreading, and protect the limited network resources.

Abstract:It is effective to use trust-management (TM) systems addressing authorization in decentralized environments. However, how to store certificates is an important and unresolved problem in this research area, which determines certificate chain discovery algorithm. In this paper, a new strategy to store certificates is put forward by using two-dimensional certificate information and Hilbert space filling curve. This strategy has not only the characteristic of load balance but also enough flexibility to search for certificates. An optimized certificates search algorithm is put forward, based on the query consisting of partial keyword. In addition to this, an algorithm to discover certificate chain is brought forward for creating the minimum certificates graph reducing the network traffic greatly.

Abstract:Semi-Fragile watermark has attracted attention due to its important role in content authentication for multimedia. In order to differentiate incidental attacks and malicious attacks, semi-fragile watermark must be robust against content-protection image processing. Semi-fragile watermark resisting to JPEG compression while maintaining high detection ability to tamper has been the emphasis in this area. In this paper, a semi-fragile watermarking algorithm to resist JPEG is proposed based on the fact that most of the coefficients of high frequency have the same relative energy relations after JPEG compression. The experimental results demonstrate that the proposed algorithm has the advantages such as simple computation complexity, big embedding capability, good robustness to JPEG, and exact location for tamper.

Abstract:Data allocation is a key problem in layered peer-to-peer streaming with the pattern of multiple senders and single receiver. To improve the requesting nodes’ streaming qualities and to reduce the bandwidth consumption of the root node, the above problem is discussed in two scenarios. The first scenario is that the root node doesn’t participate in the allocation session, and the allocation goal is to maximize the requesting nodes’ streaming qualities. A search and cut accurate algorithm and a heuristic approximation algorithm are presented. The second scenario is with the root node’s participation, and the goal is to satisfy the request nodes’ streaming qualities and to maximally save the bandwidth consumption of the root node. The problem’s computing complexity in the latter scenario is analyzed and a heuristic approximation algorithm is also presented. Simulation studies show that the proposed algorithms have improved performances than the related proposed algorithms with different parameters.

Abstract:The TAE (tweakable authenticated encryption) mode is an authenticated encryption mode which is based on a tweakable block cipher. Previous research results show that the secure tweakable block cipher is not sufficient for the security of the authenticated encryption TAE mode. Only when the tweakable block cipher is strong will the TAE be secure. Some improvements to the TAE mode are also given in this paper, resulting in a MTAE (modified tweakable authenticated encryption) mode with security proof.

Abstract:Structured P2P Networks create a virtual topology on top of the physical topology. The only relation between the two layers is the hashing algorithm, which makes the node’s logical ID independent of its physical location. By analyzing the Hash function, some novel logical connections among the destination node, the traditional semantic routing relay node sequence, and the ID of the clustering neighboring nodes are found. In this paper, the SCSRAA (self-organizing clustering semantic routing advanced algorithm) is resented to improve the efficiency of semantic routing. Since the clustering nodes only have local views in self-organizing mode, some rules are proposed for a node to learn other nodes’ physical location. The SCSRAA’s routing algorithm is described completely. Simulations have verified that the method can improve the semantic routing efficiently.

Abstract:Planning is a class of complex problem. It is a way to improve the efficiency of planning algorithm in extracting and using goal orderings. Because deciding goal orderings is also PSPACE-complete, it is necessary to extract goal orderings efficiently when using goal orderings. The paper presents a method, called GOWN (goal ordering with invariants) and uses state invariants to extract goal orderings. During the process of ordering, abstraction and unification are utilized to control the increase of problem size that improves the efficiency of ordering.