Abstract:Data race is a difficult problem for the development and testing of the concurrent program. Research has found that data race may cause duplicate computing which may decrease a system’s performance. First, the concurrent computation redundancy problem (CCRP) is defined. The related performance index and judging methods are given, and the general concurrent redundancy control mechanism is designed. When CCRP is studied,the parallel program generally be analyzed based on a producer-consumer model. In the case of the producerconsumer model with data source, CCRP is analyzed in detail. The single condition and cross condition redundancycontrol algorithms have different application scopes and can be used as fixed patterns to solve CCRP. Relativeproperty proofs and simulations are given based on Petri net. The concurrent program experiments show that theconcurrent redundancy control is necessary and efficient. Two control algorithms are compared in the experiments.The research has reference value for data race detection and concurrent programming.

Abstract:The tremendous scale of the social networks mined from Internet is the main obstacle of a social network analysis application. The bottleneck of many network analysis algorithms is the extortionate computational complexity of calculating the shortest path. Real-World networks usually exhibit the same topological features as complex networks such as the “scale-free” and etc, which indicate the intrinsic laws of the shortest paths in complex networks. Based on the topological features of real-world networks, a novel shortest path approximate algorithm which uses an existent short path passing through some local center nodes to estimate the shortest path in complex networks, is proposed. This paper illustrates the advantage and feasibility of incorporating the proposed algorithm within the network properties, which suggests a new idea for complex social network analysis. The proposed algorithm has been evaluated both on synthetic network stage and real world network stage. Experimental results show that the proposed algorithm can largely reduce the computational complexity and remain highly effective in complex networks.

Abstract:The study of new types of dominance mechanisms is a key point in current evolutionary multiobjective optimization community and ε dominance is a representative among them. However, their ability in diversity maintaining is sensitive to different shapes of Pareto fronts. This paper proposes an improved ε dominance mechanism by Isomap, which employs Isomap to embed the original population to low dimensional manifold space. The intrinsic geometric structure of them is discovered and ε dominance is adopted to select data in the embedding space. Compared with traditional ε dominance, the mechanism does not lose valid solutions and can maintain a set of uniform-distributed solutions. In addition, the extreme solution-check operator is proposed to enhance the ability of holding extreme solutions of ε dominance. The detailed experimental comparison with NSGAII, SPEA2, NNIA and εMOEA shows that the two strategies in this study are beneficial to uniformity and spread maintenance, which are in the enhanced version of traditional ε dominance.

Abstract:By exploiting the special structure in the solution space of the maximum clique problem (MCP), an improved RLS method, the RLS-II method, is has been created where the neighborhood-moving direction of the local search is guided by the multivariate constraints constructed by the dying partitioning. Therefore, the probability of the local search approaching the optimal solution is increased. Using the absorbing Markov chain theory as a reference, the mathematical models of the RLS and RLS-II algorithms in solving maximum clique problem are constructed and the absorbing time of the two algorithms is analyzed. Moreover, the analytical results are experimentally demonstrated on 77 Benchmark instances. Both the theoretical analysis and simulation results show that the dying partitioning filter can effectively improve the performance of the RLS algorithm. Furthermore, the longer average length of the dying group, the higher probability and amplitude of the performance improvement.

Abstract:Coverage control is a fundamental problem for wireless sensor networks, which has been explored thoroughly in the networks based on an omni-directional sensing model. Recently, thanks to the introduction of image/video, infrared, ultrasound sensors, coverage control algorithms for directional sensor networks have drawn more attention and have become a focus. This paper starts from the concept and characteristics of directional sensing model, and then summarizes the current research progresses at home or abroad. The study also classifies and summarizes the basic coverage control theories and algorithms in the context of directional sensor networks. Finally, the paper points out the open research problems to be solved and the future trends.

Abstract:In Ad Hoc networks, topology control is designed to save energy and increase network capacity by enabling nodes to use proper transmission power, which is usually much smaller than the maximal transmission power. However, the randomicity of network deployment and node movement results in a non-uniform distribution of nodes. In a region where nodes are sparse, the distance between two nodes may be much longer than that in a dense region, so the transmission power is not able decrease and does not depend on which topology control algorithm is adopted. For the first time, this paper proposes movement control algorithms to improve performance of topology control by moving a subset of nodes to desiring positions. Based on the minimum spanning tree of the network topology graph, addition links are determined. Moreover, addition links are shortened and large communication range may be reduced by moving some nodes. Three movement algorithms, PMST-P, PMST-UV and LMST-LUV, are realized, and their performance is compared with each other with respect to maximum communication range, total moving distance and etc. using simulations.

Abstract:Current reputation schemes, employed by an existing P2P file sharing network are faced with many threats, such as aggregate feedback, conspiracy, and fake transactions, which have affected the performance of whole system. To protect the P2P file sharing network, this paper proposes an accurate and adaptive reputation mechanism (AARep). In the paper, after an elegant analysis, it is concluded that besides the transaction evaluation, the relative and underlying transaction information plays an important role in the reputation system. This paper makes two important contributions. First, trust value computation is enhanced by adopting a decay function to display the importance of every transaction in sequence order. This weeds out suspected nodes that are less similar and utilizes the confident factors of reflect reliability in all observed values. Second, to make the confidence factors work, a simple transaction validation protocol is developed. Experimental results show that AARep can significantly eliminate or minimize the effects of a verity of attacks and improve the overall performance effectively.

Abstract:The spread spectrum based flow watermarking, which can be used to trace anonymity abuses effectively, applies spread spectrum technique to encode watermark signals and embeds them into suspect flows. This serves to confirm the communication relationship among network users. The implementation of watermarking can be divided into four phases: Signal encoding, flow modulation, flow demodulation and signal decoding. It is important to choose the right watermark carrier that determines the robustness and invisibility of watermarking techniques. Since most applications using anonymous communication, such as Web browsing, instant message and remote login generate interactive traffic with unstable traffic rate, existing spread spectrum based flow watermarking adopting traffic rate as its carrier has big limitations. Furthermore, there exist some attacks against the invisibility of this watermarking technique, destroying the traceback effect. Based on the spread spectrum flow marking model, this paper proposes a novel flow watermarking technique that adopts interval centroid as its watermark carrier, which is insensitive to different types of flows. The theoretical analysis and experimental results show that this flow watermarking technique is appropriate for both interactive and non-interactive traffic, and can resist most existing attacks against flow watermarking.

Abstract:Replication is an effective method that improves data access in Data Grids; however, the improvement of the efficiency of repilication is a crucial problem. Previous works on the replication mechanism mostly select high value replicas to replicate, and simply choose the files that have been accessed based on the access records of files. This paper starts with the analysis of the file access characteristics in the virtual organization (VO). After introducing the concept of implicit high-value file (IHVF), it proposes the cooperative replica prefetching mechanism (CoRPM) for virtual organization, which is based on which local grid nodes can obtain the replicas of IHVFs through cooperation with other gird nodes in the same VO. The architecture of CoRPM is presented first, in which prefetching elements running on every gird node work cooperatively to provide a file prefetching service for all the grid nodes in the VO. Then, on the basis of the design of CoRPM, the process of CoRPM is described, whose core algorithms include a job-type centric file prefetching algorithm and a prefetching file selecting algorithm. In the end, the paper evaluates the performance of CoRPM through simulations, and the results show that CoRPM does reduce the file access latency more effectively.

Abstract:Proxy Mobile IPv6 (PMIPv6) is the network-based localized mobility management protocol proposed by IETF. The local mobility anchor (LMA) and the mobile access gateway (MAG) are the key entities realizing the system function of PMIPv6. To solve the reliability problem of PMIPv6 MAG, this paper proposes an MAG faulttolerant method based on pool (MAGFT). MAGFT introduces MAG pool to realize MAG fault-tolerant. Several MAG pools are constructed in an PMIPv6 domain, and each MAG belongs to at least one of the pools. When an MAG fails, a given MAG in the same pool will take over. The results of theoretical analysis and simulation show that the fault-tolerant latency of MAGFT can be restricted within 35ms~340ms. When the fault-tolerant latency is lower than 120ms, MAGFT can avoid the influence of MAG failure on MNs’ up-layer TCP applications. In the worst condition, MAGFT can resume an MN’s TCP throughput within 1.1s, 1.6s, and 2.8s respectively when the MN resides in WLAN, 3G or satellite network. For the upper applications based on UPD, MAGFT can resume MNs’ packet rate within 2s after the occurrence of an MAG failure. At the same time, MAGFT introduces low signaling cost, which can be neglected when compared with the PMIPv6 signaling. MN’s access delay introduced by MAGFT is no more than 10ms.

Abstract:For the mobile-agent-based e-commerce environment, most reputation-based trust algorithms are onedimensional. They are only based on the node’s historical transactions, and the services are not taken into account, so the evaluations are coarse-gained. This paper proposes a reputation-based multi-dimensional trust (RMDT) algorithm which makes use of a self-confident coefficient to synthesize the directed and the reference trustworthiness to evaluate the node in the network. The time sensitive function in this paper not only serves as a reward and punishment mechanism, but is also dynamically attenuate in its trustworthiness. Both the transaction evaluation system and the weight system are introduced in the multi-dimensional trust mechanism. RMDT can uncover the influence on trust computation caused by the subjective factors, such as individual predilection and risk attitude. In addition, the sensitivity of RMDT on the single attribute is greatly improved.

Abstract:With the increase in bandwidth and computing power of wireless devices, video applications over wireless ad-hoc networks are expected to become widespread in intelligent vehicles, emergency communication, and battlefield command. However, a crucial problem is how to select the best paths for video streaming of qualify-on-service (QoS) in multi-hop wireless networks. Most of the existing research done on this topic tend to ignore the impacts of time- varying channel and wireless interference on the quality of multi-path video streaming. This paper proposes an optimized multi-path selection algorithm which takes not only network congestion into account, but also interference. Packet collision and delay in a MAC layer is predicted using the interference model. Each node is modeled as an M/M/1/K queuing system. Packet delay and loss, due to congestion, are predicted using the queuing theory. The distortion of path is defined as a function of packet losses and delays along the path. The paths with the minimum estimated distortion are selected as the optimal routings. Extensive experiments in NS-2 simulation environment have been carried out. The experimental results show that this algorithm achieves a certain level of satisfaction in the QoS of video streaming.

Abstract:Distributed Denial-of-Service (DDoS) attack, using random spoofed source addresses, is popular because it can protect the attacker’s anonymity. It is very difficult to defent against this attack because it is very hard to differentiate bad traffic from the normal. In this paper, based on the source addresses distribution statistical feature, an effective defense scheme, which can differentiate vicious traffic from normal traffic, is presented. Based on a novel Extended Counting Bloom Filter (ECBF) data structure, this paper proposes an algorithm to identify normal addresses accurately. Once a normal address is sought out, packets from it will be forwarded with high priority, thus, normal traffic is protected. The simulation results show that this scheme can identify legitimate addresses accurately, protect legitimate traffic effectively, and give better protection to valuable long flows. Because the time complexity of the method is O(1), and it needs several MB memory space, it can be implemented in edge routers or network secure devices like firewalls to defend against random spoofed source address DDoS attacks.

Abstract:Malware similarity comparison is one of the basic works in malware analysis and detection. Presently,most similarity comparison methods treat malware as CFG, or behavior sequences. Malware writers use obfuscation, packers and other means of technique to confuse traditional similarity comparison methods. This paper proposes a new approach in identifyling the similarities between malware samples, which rely on control dependence and data dependence. First, the dynamic taint analysis is performed to obtain control dependence relations and data dependence relations. Next, a control dependence graph and data dependence graph are constructed. Similarity information is obtained by comparing these two types of graph. In order to take full advantage of the inherent behavior of malicious codes and to increase the accuracy of comparison and anti-jamming capability, the loops are recued and the rubbish is removed by means of the dependence graph pre-processing, which reduces the complexity of the similarity comparison algorithm and improves the performance of the algorithm. The proposed prototype system has been applied to wild malware collections. The results show that the accuracy of the method and comparison capabilities all have an obvious advantage.

Abstract:Rendering global illumination for objects with mesostructure surfaces is a time-consuming task and cannot presently be applied to interactive graphics. This paper presents a real-time rendering method, based on a mesostructure height gradient map (MHGM), to exhibit lighting effects on meso-scale detail level in dynamic environments. This paper approximates global illumination by using a lighting model that includes specific characteristics: Incident ambient light, direct light, and a single bounce indirect light. In order to compute these three components in real time, this paper introduces the MHGM to create local apex sets, with which an adaptivemethod for calculating ambient occlusion is proposed. In direct lighting, the nearest local apex profile of the incident rays is to be found and presented as a mesostructure shadow algorithm, which can generate the shadow of meso-scale details. The color of the points enclosed by the local apexes is also sampled to estimate a single bounce indirect light. This approach runs entirely on the graphics hardware and uses deferred shading and the graphicspipeline to accelerate computation. High quality results, which can render meso-scale details with global illumination even for low-resolution geometric models, are achieved. Moreover, this approach fully supports dynamic scenes and deformable objects.

Abstract:In information visualization of social networks, force directed layout algorithms, which enable the creation of node-link diagrams of huge-graphs, are the most popular, however, they are not quite suitable for structural analysis and visualization which often produce images where nodes clump together in the center of the screen, making it hard to discern structural features. This paper proposes a Subgroup Analysis Layout (SAL) algorithm to solve this problem, which plots out and analyses the subgroups in social networks through the analysis of roles and key attributes. Then, the results of subgroup analysis are used to improve the force directed layout algorithm in both 2D and 3D visualization. Results with the case of terrorist organization information show that SAL algorithm can be excellent in analyzing and displaying the structure of social network.

Abstract:This paper presents a novel weighted linear method for the camera pose estimation. The key idea of this method is to replace the algebraic error in the classic linear method with the weighted algebraic error that closes the geometric error. The method provides a linear solution whose accuracy is close to the accuracy of an ML estimation. Based on the DLT (direct linear transformation) algorithm and EPnP algorithm, the weighted DLT (WDLT) and weighted EPnP (WEPnP) algorithms are obtained by using the weighted linear technique. Experimental results with simulative data and real images show that the WDLT and WEPnP algorithms remarkably outperform the DLT and EPnP algorithms and in the case of small depth ratio, both of them outperform the Lu’s nonlinear algorithm.

Abstract:Uniform grid is one of the important spatial organization structures, which is widely used in many applications such as ray tracing, collision detection, path planning and so on. Its simplicity to compute makes it very suitable for processing dynamic scenes. Because its construction time, space requirement and application efficiency are closely related with the grid resolution, optimizing grid construction has always been an important topic in the world. Hense, a new optimization method for grid construction which ensures that both of the construction time and the space requirement are in the complexity O(N), where N is the number of the primitives in the scene is proposed. In the related applications, such as ray tracing, it can achieve high acceleration efficiency, comparable with the best acceleration structures to date, such as the kd-tree, while reducing the construction time dramatically. These have been approved by the experimental results.

Abstract:Under the traditional static resource reservation mechanism (SRRM), once a user’s reservation request has passed the admission test, it is scheduled for a certain resource immediately. SRRM considers neither the impact of the resource change on the schedule target nor the impact of resource error on the reservation in the book-ahead time. A dynamic resource reservation mechanism (DRRM) is presented, in which the accepted reservation requests are scheduled during the consumption the resource. The resource-reservation graph (RRG) is introduced to describe DRRM, and the modification rules of RRG have also been presented. The simulation experimental results show that though DRRM loses some admission percentage, it considerably decreases task preemption, dramatically improves the resource utilization, and has a better capacity of fault tolerance to the resource error ratio.

Abstract:This paper aims at improving the performance of MPI broadcasts under unbalanced process arrival (UPA) patterns. This paper analyzes this problem with a performance model and proves that the negative impact of UPA on MPI broadcast can be effectively reduced by the competition of intra-node MPI processes on a multicore cluster. Based on this theory, a new optimizing method, called competitive and pipelined method (CP), is proposed. The CP method can start inter-node communications during the broadcast process through an intra-node competitive mechanism. In a CP method based broadcast algorithm, intra-node communications overlap inter-node communications through a pipelined method, and intra-node communications are implemented through shared memory while inter-node communications are executed by a set of leader MPI processes, which is selected by the competitive mechanism. In order to verify the CP method, this paper improves three typical broadcast algorithms by using this method and evaluates these algorithms in a real platform by using a micro-benchmark case and two practical applications. The results show that the performance of the CP method can effectively improve the performance of broadcast algorithms in the condition of UPA patterns. In the experimental results of the performance of the practical applications, the performance of CP broadcasts is about 16% higher than the performance of P broadcasts and is 18% to 24% higher than the performance of broadcast operation in MVAPICH2 1.2.

Abstract:This paper proposes a new snapshot method for continuous data protection (CDP) system that considers the disability of taking large amount of snapshots in traditional CDP systems. The snapshot method (Convex Point SNAPshot, CSNAP) is based on the concept of convex point set. After the data structure of CSNAP and introduced the concept of convex point based on the pointers in the data structure have been discussed, the study analyzes the properties of convex point set and proposed CSNAP algorithms. An enhanced CSNAP method by introducing the concept of retro-cost is also proposed. Finally, the study uses a typical workload and random generated trace data to test CSNAP method. The experimental results show that at average CSNAP takes less than 10% storage space of traditional snapshot method.

Abstract:In recent years, heterogeneous parallel architecture has become an important development trend of supercomputer because it mitigates the problem of increasingly high power consumption. As a high performance and power efficiency accelerator, GPU (graphics processing unit) has been extensively used in HPC (high performance computing) area. However, the inherent unreliability of the GPU hardware deteriorates the reliability of supercomputer. Presently, most research of FT (fault-tolerance) techniques for CPU-GPU heterogeneous system isolates the GPU from the system, and does FT work for it at the granularity of a single GPU invocation. This paper proposes a new Lazy FT method for CPU-GPU heterogeneous system, introduces a FT framework and its constraints based on directives, and demonstrates the validity of the Lazy FT method. The experimental results show that, compared with existing FT methods, the cost of LazyFT is very cheap.