ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 December 2006, Volume 43 Issue 12
A High-Throughput Scheduling Algorithm with Small Crosspoint Buffers for CICQ Switches
Lee Yong, Luo Junzhou, and Wu Jun
2006, 43(12):  2033-2040. 
Asbtract ( 427 )   HTML ( 0)   PDF (673KB) ( 646 )  
Related Articles | Metrics
With no internal speed-up required and parallel scheduling at input and output, the CICQ (combined input crosspoint queued) switch architecture using RR (round robin) algorithm provides unique advantage of designing high performance switches. However, it cannot achieve 100% throughput under non-uniform traffic. The performance of RR algorithm under non-uniform traffic comes from two critical factors: one is the buffer capacity of each crosspoint and the other is the service loss. Based the theoretical study, a high-throughput scheduling algorithm with small crosspoint buffers is presented. Simulations demonstrate that the new algorithm can achieve 100% throughput under arbitrary traffic using only one buffer cell in each crosspoint. The new algorithm keeps the high simplicity and efficiency of RR-RR with O(1) complexity while overcoming the instability problem of RR-RR.
A Fast Hybrid Loss Protection Method with Quality of Service Provision for Image Transmission
Yang Yadong, Wu Chengke, Xiao Song, and Du Jianchao
2006, 43(12):  2041-2047. 
Asbtract ( 425 )   HTML ( 1)   PDF (616KB) ( 516 )  
Related Articles | Metrics
The performance of the existing unequal loss protection system based on interleaver structure for progressive image transmission is usually measured by the expected quality without considering the minimum image quality requirement. In this paper, a new objective function named the effective expected quality is proposed, which is defined as the received expected quality excluding the contribution from failure transmission, i.e., the quality of the decoded image is below the minimum quality requirement. The performance criterion proposed is to maximize the effective expected quality under the constraint condition that the probability of failure transmission is below a given threshold. With this new performance criterion and equal and unequal protection strategies, a new local search algorithm is also presented for the allocation of the transmission bit budget between the source and channel codes. Experiments are carried out with the source coders of SPIHT and JPEG2000 by using the network model of two-state Markov. The results show that the new algorithm can provide higher effective expected quality and lower probability of failure transmission with significantly lower computational complexity compared with the previous algorithm.
KIR:A New Algorithm to Improve the Fairness of TCP Congestion Avoidance
Li Shining, Guan Junming, and Qin Zheng
2006, 43(12):  2048-2055. 
Asbtract ( 461 )   HTML ( 0)   PDF (815KB) ( 529 )  
Related Articles | Metrics
The traditional TCP congestion avoidance mechanism has strong bias against links with higher round-trip delays. As the competing TCP connection increase, the fairness and utilization of the sharing link degrades dramatically. The CR, IBK, CANIT examined firstly, and then a new fairness algorithm “K and additive increase ratio” (KIR) is proposed to correct the bias against these long connections. The new algorithm in which a new arithmetic formula “K” is used for the first time smoothly modifies the long and short round-trip delay link congestion avoidance algorithm. A series simulation is chosen and the different algorithm characteristic is analyzed. With these modifications, the simulation result show that the algorithm not only can improve TCP fairness, but can obtain good throughput performance as well. Finally, the effectiveness of KIR is proved by the simulation combined with NewReno, Sack and Tcpw under the GEO satellite environment.
Analytical Expressions of Properties of MANETs Uniformly Distributed in Rectangular Area
Gao Zhenguo, Cai Shaobin, and Zhao Yunlong
2006, 43(12):  2056-2061. 
Asbtract ( 450 )   HTML ( 0)   PDF (447KB) ( 556 )  
Related Articles | Metrics
Research on analytical expressions of properties of mobile ad hoc networks (MANETs) is of great importance to research works on MANETs. Based on combinatorial theory and asymptotic technique, the distribution of the Euclidean distances between node pairs in MANETs with nodes uniformly distributed in rectangular scenario is analyzed. A closed mathematical formula is obtained. Then, analytical expressions of some properties of uniform MANETs in rectangular scenario are obtained. Results obtained in the paper are verified through simulations.
A Diagram of Strand Spaces for Security Protocols
Wang Huanbao, Zhang Yousheng, and Li Yuan
2006, 43(12):  2062-2068. 
Asbtract ( 446 )   HTML ( 0)   PDF (484KB) ( 430 )  
Related Articles | Metrics
The strand space model illustrated with the diagram of strand spaces is adopted as a formalism of security protocols. The open bundle is defined, which is only one element for composing diagrams of strand spaces. And the two operators such as prefixing and parallel composition over the set of open bundles are defined. A novel method is proposed to generate diagrams of strand spaces of security protocols that run in an infinite concurrent way through operating of prefixing and parallel composition between open bundles. The bi-simulation equivalence relation between diagrams of strand spaces based on the bi-simulation between open bundles is defined. Reduction rules for eliminating redundancies of diagrams of strand spaces are also proposed. The case analysis and the comparison between this work and other related work show that the diagram of strand spaces can be used as an effective model for proving security properties of cryptographic protocols that run in an infinite concurrent way.
Research on Group Signature Scheme with Forward Security
Li Yunfa, Zou Deqing, Han Zongfen, and Qiang Weizhong
2006, 43(12):  2069-2075. 
Asbtract ( 479 )   HTML ( 0)   PDF (481KB) ( 485 )  
Related Articles | Metrics
Based on the basic theories of RSA signature, GQ signature, and IR forward secure signature, a group signature scheme with forward security is presented. In this signature scheme, the key server only generates one public key for all members of group and all members share this public key. At the same time, the key server also generates the secret key “seeds” for each member, thus, each member can only get one secret key “seed”. During each time period, each member of group can generate or update his own secret key by using the secret key generation algorithm or the secret key update algorithm. By analyzing the performance of the digital signature, a conclusion may be drawn. It can be described as follows: In a group communication that includes n members, if the digital signature is adopted, and even (n-1) members corrupt, the only one legal member is still secure under such attacks.
Security on Aydos et al's Elliptic Curve Cryptography Based Wireless Authentication Protocol
Liu Yongliang, Gao Wen, Yao Hongxun, and Huang Tiejun
2006, 43(12):  2076-2081. 
Asbtract ( 460 )   HTML ( 0)   PDF (508KB) ( 466 )  
Related Articles | Metrics
Recently, Aydos et al. proposed an ECC-based wireless authentication protocol. This protocol uses both the elliptic curve digital signature algorithm and the Diffie-Hellman key exchange scheme to provide mutual authentication and agree a session key for subsequent communication. Mangipudi et al show that the protocol is vulnerable to the man-in-the-middle attack from the attacker within the system. It is further shown in this paper that Aydos et al's protocol is vulnerable to man-in-the-middle attack from any attacker not restricted on the inside attacker. Finally, the reasons that Aydos et al's protocol suffers the attacks and some other security weaknesses of Aydos et al's protocol are analyzed.
Perturbed Variant of TTM Cryptosystem
Wu Zhiping, Ye Dingfeng, and Ma Weiju
2006, 43(12):  2082-2087. 
Asbtract ( 346 )   HTML ( 0)   PDF (416KB) ( 560 )  
Related Articles | Metrics
Internal perturbation is added to the TTM cryptosystem, and its new variant is constructed. Using small instances of the variant, the security of the new variant is investigated against minrank attack and linearization equation attack. The necessary condition is given, under which there do not exist linear equations in the variant of the TTM cryptosystem. Computer experiments indicate that there almost do not exist linear equations in the new variant. A specific instance is proposed for practical implementation, and its performance and security are estimated.
A Structural Formula Process Neural Networks and Its Applications
Xu Shaohua, He Xingui, and Wang Bing
2006, 43(12):  2088-2095. 
Asbtract ( 357 )   HTML ( 0)   PDF (629KB) ( 460 )  
Related Articles | Metrics
Aimed at the pattern classification and the system-modelling problem with complex time-varying signals that have singular values, a kind of structural formula process neural networks is proposed in this paper. This model is constructed based on the rational expression function's approximation character to complex process signals and the process neural networks' nonlinear transforming mechanism to time-varying information; its basic information processing unit is made up of two process neurons, logically constructing a structural process neuron. It is a type of extending for artificial neural networks at the architecture and the information processing mechanism. In this paper the continuity and functional approximation ability of structural formula process neural networks are analyzed, and the learning algorithm based on the function orthogonal expanded by bases is given. The experimental results demonstrate that the learning and the generalization character of structural formula process neural networks for the time-varying function samples with singular values are better than that of BP networks and the general process neural networks. The numbers of hidden layer and node numbers are greatly decreased, and the learning characters of the algorithm are the same with BP algorithm's.
Neural Networks' Distributed Cooperative Learning Strategy Based on Agent and Chips
Yang Bo, Wang Yadong, Su Xiaohong, and Tang Xianglong
2006, 43(12):  2096-2103. 
Asbtract ( 355 )   HTML ( 0)   PDF (580KB) ( 647 )  
Related Articles | Metrics
To solve the bottleneck of memory and running time problem in protein structure predicting with large-scale data set, a neural networks' distributed learning algorithm is studied. Based on the analysis of the previous methods of distributed learning algorithm in a distributed computing environment with a large number of processors, a new distributed neural network based on multi-agents, and a learning algorithm based on chips to work on the distributed neural networks are created, which approach the global optimum by competition from a group of agents that have the different training sample chips to process. It is proved that the new distributed learning algorithm is better on balancing the parallel computing efficiency and the success rate of learning compared with the previous algorithms. The experiment results demonstrate that this method is feasible and effective in practical applications when used in protein secondary structure predicting with large size of amino-acid sequence.
Fuzzy Neural Network Optimization by a Multi-Objective Particle Swarm Optimization Algorithm
Ma Ming, Zhou Chunguang, Zhang Libiao, and Ma Jie
2006, 43(12):  2104-2109. 
Asbtract ( 421 )   HTML ( 1)   PDF (468KB) ( 579 )  
Related Articles | Metrics
Designing a set of fuzzy neural networks can be considered as solving a multi-objective optimization problem. In the problem, performance and complexity are two conflicting criteria. An algorithm for solving the multi objective optimization problem is presented based on particle swarm optimization through the improvement of the selection manner for global and individual extremum. The search for the Pareto optimal set of fuzzy neural networks optimization problems is performed, and a tradeoff between accuracy and complexity of fuzzy neural networks is clearly shown by obtaining non-dominated solutions. Numerical simulations for taste identification of tea show the effectiveness of the proposed algorithm.
Automatic Composition of Web Services Based on Task Dependency Specification
Shi Yuliang, Huang Guang'an, Ye Wei, Zhang Liang, and Shi Baile
2006, 43(12):  2110-2116. 
Asbtract ( 323 )   HTML ( 0)   PDF (496KB) ( 480 )  
Related Articles | Metrics
As the number of available Web services is steadily increasing, there is a growing interest for reusing basic Web services in new, composite Web services. However, most current Web services choreography proposals, such as BPEL4WS or WSCI, need a fixed execution flow previously designed by human, thus the adaptability of Web services can not be fully used. Through formalizing the description of single Web service, a Web services composition mechanism based on dependences between tasks is developed and a flexible and self-adaptable workflow model to compose Web services automatically is proposed. Furthermore, respective algorithms to verify the correctness of composition process are developed and a dynamic compensation mechanism is designed to handle exceptions, which adds considerable practicability to the workflow model.
An Association Rule Mining Algorithm of Multidimensional Sets
Zhong Yong, Qin Xiaolin, and Bao Lei
2006, 43(12):  2117-2123. 
Asbtract ( 338 )   HTML ( 0)   PDF (533KB) ( 488 )  
Related Articles | Metrics
Most of multidimensional association rule mining algorithms such as mining algorithms based on data cube assume that an object attribute only has a single-value. In this paper, the attribute value of an object is extended to a multi-value and the concept of multidimensional set is presented, which brings about the semantics of multidimensional set association rule. Based on the semantics, an algorithm to mine association rules of multidimensional sets is given. The algorithm makes use of the restricted characteristics of multidimensional set association rule and can execute a triplicate pruning of candidate sets with a reduction of data set, which makes it a better performance than that of apriori and other algorithms. The performance, correctness and completeness of the algorithm are analyzed, and its effectiveness is also proved by experiments.
Research on Aggregate Query Matching in Semantic Cache
Cai Jianyu, Wu Quanyuan, Jia Yan, and Zou Peng
2006, 43(12):  2124-2130. 
Asbtract ( 372 )   HTML ( 0)   PDF (538KB) ( 570 )  
Related Articles | Metrics
queries are pervasive in massive database applications, whose execution tends to be time consuming and costly. Therefore promotion of their efficiency will largely improve the performance of the system. Semantic cache is a novel scheme for aiding query evaluation that reuses the results of previously answered queries. But little work has been done on semantic cache involving aggregate queries. This is a limiting factor in its applicability and it is mostly used in small scale database applications. In order to utilize semantic cache in massive database applications, it is necessary to extend semantic cache to support aggregate query. In this paper, query matching is identified as a foundation for answering query using semantic caches. First, a formal semantic cache model is proposed, which supports aggregate query and provides the basis for the whole research. Then the condition of query matching is presented and query matching is classified. Next, two algorithms are proposed for aggregate query matching. These two algorithms are applied to a massive database application project. Its result proves the efficiency of the algorithms.
A Parametric Active Contour Model for Medical Image Segmentation Using Priori Shape Force Field
Shi Chengxian, Wang Hongyuan, Heng Pheng Ann, and Xia Deshen
2006, 43(12):  2131-2137. 
Asbtract ( 411 )   HTML ( 3)   PDF (867KB) ( 602 )  
Related Articles | Metrics
A priori shape parametric active contour model has been widely used in image segmentation because of their computational efficiency and stability. The model can deal with properly the concave regions in the image and provide an accurate segmentation to weak edges and noise images. An initial contour must not be set near the feature of the image and can provide a large capture range. Priori shape force field incorporates into an active contour model. The novel model can avoid computing the distance of priori shape contour to active contour, and can decrease the complexity. The model solves efficiently some drawbacks of a parametric active contour model. Experiments demonstrate that the model curve is driven to the object boundary by the new forces even if the initial contour does not close the true boundary and the object is nonconvex or has weak edges and noise on medical CT and ultrasound images.
A Face Verification Algorithm Based on Negative Independent Sample Set and SVM
Zhang Xingming and Li Heheng
2006, 43(12):  2138-2143. 
Asbtract ( 546 )   HTML ( 0)   PDF (479KB) ( 556 )  
Related Articles | Metrics
In many face verification applications, there are no face database for SVM training, such as PC face security logging-on system. A new face verification algorithm based on negative independent sample (NIS) set is presented, by analyzing existing SVM-based face verification algorithm and the demand for practical application. The approach generates enough positive samples by means of wobbling eyes of the user's registered image, employs FLD to extract feature, and deletes uniform samples in NIS with the rank-based FLD face recognition method. This scheme can resolves the classification conflict problem between the negative and the positive sample sets. After the negative and positive samples are sent to SVM for training, the SVM can do face verification for face image. The experiments on the SCUT face database indicate that the proposed method can ensure lower FAR if the negative samples are large enough, and the number of support vectors does not increase alone with the number of negative samples. A PC security logging-on system has been developed based on this face verification algorithm.
Feature Preserving Mesh Simplification Based on Corner Cutting
Ji Zhongping, Liu Ligang, and Wang Guojin
2006, 43(12):  2144-2151. 
Asbtract ( 358 )   HTML ( 0)   PDF (828KB) ( 526 )  
Related Articles | Metrics
Most of the existing algorithms for simplifying triangular meshes might lose some important shape features of the original model, especially at low levels of the simplified models. Proposed in this paper is a novel algorithm for triangular mesh simplification, which uses the local volume as the cost of decimation based on edge collapse operators. Many examples demonstrate that the method proposed is fast, requires less memory overhead and preserves the details very well. Furthermore, A set of LOD models by this approach are also easily obtained.
Research and Implementation of a 32-Bit Asynchronous Multiplier
Li Yong, Wang Lei, Gong Rui, Dai Kui, and Wang Zhiying
2006, 43(12):  2152-2157. 
Asbtract ( 356 )   HTML ( 1)   PDF (553KB) ( 535 )  
Related Articles | Metrics
An asynchronous circuits design flow based on macrocell is presented in this paper. Being compatible with current EDA tools for synchronous design, this flow can decrease the difficulties of design and improve the efficiency as well. Based on this flow, a 32-bit asynchronous multiplier in 0.35μm process is designed. Compared with the synchronous multiplier of the same data path, the asynchronous multiplier has the similar performance but with smaller area size and lower power dissipation.
Global Partial Replicate Computation Partitioning
Wang Yiran, Chen Li, Feng Xiaobing, and Zhang Zhaoqing
2006, 43(12):  2158-2165. 
Asbtract ( 459 )   HTML ( 1)   PDF (869KB) ( 360 )  
Related Articles | Metrics
Early parallelizing compilers use the owner-computes rule to partition computation. Partial replication is then introduced to reduce near-neighbor communication at the cost of some repeated computation. It is an important optimization that improves the performance and scalability of parallel programs. Former exploration of partial replicate computation partitioning is limited within a single loop nest, and no explicit cost model is used. In this paper, a formal description of more general partial replicate computation partitioning problems is presented, which is called global partial replicate computation partitioning. As redundant message elimination exerts great influence on the effect of such optimizations, a linear cost model is introduced, which considers its effect. A framework is also developed, which employs the integer linear programming method. Experimental results show that the solution is superior to local approaches. Compared with the heuristic method, the new approach can deal with more general cases and is easier to adapt to different data distribution.
Exception Handling in Application Level Binary Translation
Tang Feng, Wu Chenggang, Zhang Zhaoqing, and Yang Hao,
2006, 43(12):  2166-2173. 
Asbtract ( 452 )   HTML ( 0)   PDF (632KB) ( 634 )  
Related Articles | Metrics
Binary translation is applied for not only the legacy code porting but also software being used in different hardware platform. Exception handling is a most important aspect of binary translation research. How to balance the exception handling and the efficiency of binary translation is the key problem. Two methods to solve the active and passive exception handling in the library function jacket level are presented. One algorithm comes up to deal with efficienly the passive exception such as signal exception efficiently:if the exception handler doesn't use the machine state after exception happens, the translator doesn't preserve the precise machine state in every block. Thus, the cost for exception handling is low. For the Spec 2000 CPU ref input set, the cost, when the algorithm is applied to the translator, is an average 15.42 percent lower than the cost when the algorithm is not applied to the system. Another algorithm using emulated stack unwinding is submitted to find the calling address to help dealing with the active exception such as try catch exception in C++. The experiments prove the validity of the two ways of handling the exception. Adding the exception mechanics to the system doesn't decrease the performance of the common programs. These algorithms solve the exception handler in the application level program in binary translation quickly and correctly.
Library Function Disposing Approach in Binary Translation
Yang Hao, Tang Feng, Xie Haibin, Wu Chenggang, and Feng Xiaobing
2006, 43(12):  2174-2179. 
Asbtract ( 441 )   HTML ( 1)   PDF (399KB) ( 635 )  
Related Articles | Metrics
Disposing the library functions call fast and efficiently is an important performance issue in the binary translation technology. One algorithm named JLSCL (jacket library and shortcut library) is presented to dispose the library functions classified, which is based on the dynamic binary translator integrated with static pre-translator. JLSCL can make use of the merit of dynamic translation and static translation, and make use of the convention of the function call on the target processor to reduce the redundant memory access. These make it more efficient that the original binary code runs on the target processor. The algorithm can flexibly switch between the library function and system call, and have applicability for the library function. The algorithm is verified in the binary translator system—digital bridge version 2. It can dispose the library function call successfully and efficiently, and its performance has been improved greatly.
A Vertical and Horizontal Multiway Algorithm for Parallel-Merging
Wang Ying, Li Kenli, Li Lang, and Li Renfa
2006, 43(12):  2180-2186. 
Asbtract ( 568 )   HTML ( 0)   PDF (633KB) ( 553 )  
Related Articles | Metrics
Based on the sloping-and-shaking k-way merging and sorting algorithm, a vertical and horizontal multiway algorithm for parallel-merging is proposed, which is different from these methods which apply recursive two-way to merge. The algorithm is a sort of brand-new multiway merge sorting algorithm, whose main characteristic is to sort directly the m×k matrix (m, k is a random integer) and not to rely on recursively the two-way merge process. Compared with the sloping-and-shaking k-way merging and sorting algorithm and high efficiency multiway parallel merging algorithm, while k is big in three small in forty, the time complexity of the algorithm is lower than the uniformity algorithm. In the meantime, the design complexity realized in the special hardware of the algorithm has obvious advantage.
Automatic Music Transcription Based on Harmonic Structure Information
Zheng Guibin, and Han Jiqing
2006, 43(12):  2187-2192. 
Asbtract ( 650 )   HTML ( 4)   PDF (463KB) ( 594 )  
Related Articles | Metrics
A novel method for automatic music transcription based on harmonic structure information is developed in this paper. The instruments of the same class have similar timber and harmonic structure. Therefore, harmonic structure information of an instrument is acquired beforehand and is used to construct the loudness spectrum for the unknown instrument of the same class in music transcription. The inharmonicity factor and the error in note fundamental frequency are considered during the spectrum construction. The loudness spectrum of input audio can be considered approximately as the linear sum of spectra corresponding to the mixed notes and the truncated total least squares is used to solve the sum equation. Experimental results of piano music transcription show that the method not only can transcribe music of an unknown instrument with high performance, but also can distinguish the loudness of mixed notes.