ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.

2014 Vol. 44, No. 1

  Previous Issue | Next Issue 
Display Method:
Original Paper
A fast DFA construction algorithm by subset encoding
PENG Kunyang
2014, 44(1): 1-11. doi: 10.3969/j.issn.0253-2778.2014.01.001
Article Views:94 Full article PDF
Abstract:
Regular expression matching is the foundation of many network functions such as deep packet inspection, which is performed using either non-deterministic finite automaton (NFA) or deterministic finite automation (DFA). To meet the requirement of high-speed regular expression matching, DFA has been the prevalent choice for its deterministic nature and matching efficiency. However, all these DFA-based approaches need to construct a DFA from an NFA as an intermediate step, thus the DFA construction process can be one of bottlenecks for the system. By exploring the inherent properties of finite automaton — whether the NFA states simultaneously active and how the self-looping NFA states lead to explosion of DFA state space — a state subset encoding and searching scheme was designed, and a new DFA construction algorithm was proposed. Through experiments based on real life pattern sets from the Snort intrusion detection system, the new DFA construction algorithm was demonstrated to reduce the running time by 8833%~9357% compared with that of the standard subset construction algorithm.
User behavior model based TVOS resource allocation
CHEN Lei, WANG Song, WU Gang
2014, 44(1): 12-18. doi: 10.3969/j.issn.0253-2778.2014.01.002
Article Views:73 Full article PDF
Abstract:
The resource allocation of the existing smart TV operating system (TVOS) depends on the operating system task resource allocation scheme, which tries to maximize the throughput of the system. However, this scheme cannot guarantee the quality of service (QoS) of applications in the real-time or multimedia system. In order to solve this problem, the user preferences of applications based on the user behavior model of TVOS were quantified, and two resource allocation algorithms named RA_DP and RA_PLSH were proposed based on the application QoS model. The experimental result shows that the algorithm based on dynamic programming (RA_DP) ensures optimal solution with high time complexity, and can be used as a reference for other algorithms. However, the other algorithm based on resource pricing local search heuristic (RA_PLSH) can obtain near-optimal solution in a very short time, and is thus more suitable for smart TV real-time resource allocation.
A colored Petri net based scheduling scheme for multiprocessor system-on-chip
FENG Xiaojing, LI Xi, WANG Chao, CHEN Peng, ZHOU Xuehai
2014, 44(1): 19-33. doi: 10.3969/j.issn.0253-2778.2014.01.003
Article Views:66 Full article PDF
Abstract:
A novel colored Petri net (CPN) based dynamic scheduling scheme was proposed, which aimed at generating a hardware scheduler for multiprocessor system-on-chip (MPSoC) platforms. CPN was employed to model inter-task dependences in the proposed scheduling scheme, including RAW, WAW and WAR data dependences, as well as structural dependences. All the dependences can be automatically detected during model execution. Tasks can be then scheduled and dispatched to different processors for out-of-order execution according to the dependences, achieving the goal of improving task-level parallelism. The scheduling scheme is implemented both with software simulation tools and on an FPGA-based hardware platform. Through state space analyses and comparing experiments, the correctness and effectiveness of the scheduling scheme are demonstrated.
Sensor data association using relative positions among targets and bias estimation between separate sensors
YU Zhaohua, LING Qiang, SHI Mengzhao
2014, 44(1): 34-42. doi: 10.3969/j.issn.0253-2778.2014.01.004
Article Views:81 Full article PDF
Abstract:
Sensor data association is an important problem in modern multi-sensor systems. The purpose to solve this problem is to decide which measurements from the different sensors belong to the same target. The traditional methods for data association usually form the association matrix and find the optimal solution in different ways. These solutions are, however, sensitive to the characteristics of the sensors. A novel method which uses the relative positions among the targets and extracts the relative positions pattern to compare and search for the matching pairs between the separate sensor systems is proposed. An improved algorithm which is suitable for sensor data association using relative positions is also presented. The sensor bias has little influence upon this association algorithm due to the inherent characteristics of the relative positions. Simulation results show that association using relative positions is robust against sensor bias and has an overall improvement.
The relationship of structural and functional brain networks via hierarchical synchronization
LIU Yingying, ZHUO Zhao, CAI Shimin, FU Zhongqian, ZHOU Peiling
2014, 44(1): 43-47. doi: 10.3969/j.issn.0253-2778.2014.01.005
Article Views:57 Full article PDF
Abstract:
Benefiting from the structural segmentation and functional conformity, the cerebra can reach an ‘economical work mode including both local clustering and global cooperation, which makes the relation of structural and functional network play an important role in the comprehension of cognitive brain activities. The collective dynamics of neural mass models coupled through structural brain network represents properties of brain activities. Based on functional brain networks derived from simulated time series, the relationship between structural and functional brain networks is investigated via comparing topologies of the two networks. The numeric results of structural networks in cats and monkeys show that the functional and structural networks display similar connecting patterns, which were also quantitively studied with the help of vertex similarity in structrual networks. Numeric results support the view point that the hierarchies in structural networks are the basis of functional brain activities and suggest that the functional conformity is realized via collective dynamics of neurons.
Subspace interference alignment on Grassmann manifold for cellular networks
ZHANG Chen, YIN Huarui, LI Xu, WEi Guo
2014, 44(1): 48-60. doi: 10.3969/j.issn.0253-2778.2014.01.006
Article Views:82 Full article PDF
Abstract:
The subspace interference alignment for multi-cell and multi-user cellular networks was focused. Different from most previous algorithms that are based on a joint design of precoder and receive filter, the proposed method achieves interference alignment with precoder design only. This means our algorithm only requires the participation of transmitters, which will alleviate significantly the overhead induced by alternation between the up and down links. More importantly, varying from the traditional constrained optimization method, the precoder design on complex Grassmann manifold with lower dimensions was reformulated and a novel steepest descent algorithm was derived to achieve perfect subspace interference alignment. Simulation results suggest that the proposed algorithm has better convergence performance and higher system capacity compared with previous methods.
Design of an integrated lens for separating microwave and optical wave
CHE Rongrong, YI Zixuan, ZHU Qi
2014, 44(1): 61-66. doi: 10.3969/j.issn.0253-2778.2014.01.007
Article Views:69 Full article PDF
Abstract:
An integrated lens was designed, which is composed of an optical Fresnel lens (OFL) and a microwave helix array (MHA). The OFL focuses the incident light wave while the MHA focuses on the incident microwave. The MHA has little effect on blocking incident light while the OFL has effect on microwave transmission. The proposed integrated lens can simultaneosly focus microwave and optical wave on two different spots, and the distance between them is 35cm. The intensity of the electric field has a 5-fold improvement at the microwave focus. So it can transmit and receive microwave signal on the basis of the full use of the incident visible light when the integrated lens is uploaded.
Image annotation by searching semantically related regions
DAI Lican, YU Nenghai
2014, 44(1): 67-73. doi: 10.3969/j.issn.0253-2778.2014.01.008
Article Views:71 Full article PDF
Abstract:
Based on abundant partially annotated images on the web, a novel framework for image annotation was proposed. By utilizing both the visual and textual knowledge of public available image database Image-Net, the proposed framework first learnt a set of weakly labeled visual concept classifiers, and then used the outputs of these learnt classifiers on image regions as descriptors to conduct the region-based search in a large scale image database for a query image. After that, search results mining and clustering was introduced to generate annotations to the query image. Compared with image-level representation, the proposed region-based semantic representation performs better at capturing images multi-objects/semantics. The proposed framework takes advantage of both traditional classification-based approaches and large scale data-driven approaches. Experimental results conducted on 24 million web images and challenging image database have demonstrated the effectiveness and efficiency of the proposed approach.
Study on the self-organized financial model based on scale-free networks
REN Xiaoye, ZHOU Peiling
2014, 44(1): 74-78. doi: 10.3969/j.issn.0253-2778.2014.01.009
Article Views:70 Full article PDF
Abstract:
For a series of grid-based Cont-Bouchaud (CB) models unable to correctly represent the heterogeneity of interactions among investors in the real financial market, an improved evolutionary model constrained by trading rules was proposed based on the percolation theory on scale-free networks. The time series of price fluctuations generated by the model was similar to the stock index in the real financial markets. For instances, the probability distributions of returns showed the sharp peak and fat tail, and their peak values restricted to the time scales obey the power-law behavior, which suggests that the time series of price fluctuations evolves in a self-similarity way. The clustering behavior of volatility shows that there are large fluctuations and long-range correlations in the evolutionary process. These statistical properties of return and volatility empirically are consistent with the real financial markets, indicating the effectiveness of the improved model.
Effect of output noise in inverse-model-based iterative learning control
LIU Shaojie
2014, 44(1): 79-86. doi: 10.3969/j.issn.0253-2778.2014.01.010
Article Views:41 Full article PDF
Abstract:
Inverse-model-based iterative learning control (ILC) for linear-time invariant, single-input single output (SISO) systems subject to output noise is proposed with the intent of predicting expectation of the underlying “noise-free” mean square error (Euclidean norm) on each iteration. Frequency domain formulae are derived to provide an insight into links between plant characteristics, noise spectra and inverse-model-based ILC parameters. Simulations are used to illustrate the theoretical findings.

Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

Supported by: Beijing Renhe Information Technology Co. Ltd