Most large-scale Peer-to-Peer (P2P) live streaming systems are constructed as a mesh structure, which can provide robustness in the dynamic P2P environment. The pull scheduling algorithm is widely used in this mesh structure, which degrades the performance of the entire system. Recently, network coding was introduced in mesh P2P streaming systems to improve the performance, which makes the push strategy feasible. One of the most famous scheduling algorithms based on network coding is R2, with a random push strategy. Although R2 has achieved some success, the push scheduling strategy still lacks a theoretical model and optimal solution. In this paper, we propose a novel optimal pull-push scheduling algorithm based on network coding, which consists of two stages: the initial pull stage and the push stage. The main contributions of this paper are: 1) we put forward a theoretical analysis model that considers the scarcity and timeliness of segments; 2) we formulate the push scheduling problem to be a global optimization problem and decompose it into local optimization problems on individual peers; 3) we introduce some rules to transform the local optimization problem into a classical min-cost optimization problem for solving it; 4) We combine the pull strategy with the push strategy and systematically realize our scheduling algorithm. Simulation results demonstrate that decode delay, decode ratio and redundant fraction of the P2P streaming system with our algorithm can be significantly improved, without losing throughput and increasing overhead.

Multicast routing with Quality-of-Service (QoS) guarantees is the key to efficient content distribution and sharing. Developing QoS-aware multicast routing algorithm is an important open topic. This paper investigates QoS-aware multicast routing problem with K constraints where K > 2. The contributions made in this paper include a heuristic that employs the concept of nonlinear combination to extend the existing well-known algorithm for fast computation of a QoS multicast tree, and a Fully Polynomial Time Approximation Scheme (FPTAS) to approximate a multicast routing tree with QoS guarantees. The theoretical analyses and simulations conducted on both algorithms show that the algorithms developed in this paper are general and flexible, thus are applicable to the various networking systems.

To improve the observability during the post-silicon validation, it is the key to select the limited trace signals effectively for the data acquisition. This paper proposes an automated trace signal selection algorithm, which uses the pruning-based strategy to reduce the exploration space. First, the restoration range is covered for each candidate signals. Second, the constraints are generated based on the conjunctive normal form (CNF) to avoid the conflict. Finally the candidates are selected through pruning-based enumeration. The experimental results indicate that the proposed algorithm can bring higher restoration ratios and is more effective compared to existing methods.

It is well known that Boolean functions used in stream and block ciphers should have high algebraic immunity to resist algebraic attacks. Up to now, there have been many constructions of Boolean functions achieving the maximum algebraic immunity. In this paper, we present several constructions of rotation symmetric Boolean functions with maximum algebraic immunity on an odd number of variables which are not symmetric, via a study of invertible cyclic matrices over the binary field. In particular, we generalize the existing results and introduce a new method to construct all the rotation symmetric Boolean functions that differ from the majority function on two orbits. Moreover, we prove that their nonlinearities are upper bounded by .

As RFID technology is being more widely adopted, it is fairly common to read mobile tags using RFID systems, such as packages on conveyer belt and unit loads on pallet jack or forklift truck. In RFID systems, multiple tags use a shared medium for communicating with a reader. It is quite possible that tags will exit the reading area without being read, which results in tag leaking. In this letter, a reliable tag anti-collision algorithm for mobile tags is proposed. It reliably estimates the expectation of the number of tags arriving during a time slot when new tags continually enter the reader's reading area and no tag leaves without being read. In addition, it gives priority to tags that arrived early among read cycles and applies the expectation of the number of tags arriving during a time slot to the determination of the number of slots in the initial inventory round of the next read cycle. Simulation results show that the reliability of the proposed algorithm is close to that of DFSA algorithm when the expectation of the number of tags entering the reading area during a time slot is a given, and is better than that of DFSA algorithm when the number of time slots in the initial inventory round of next read cycle is set to 1 assuming that the number of tags arriving during a time slot follows Poisson distribution.

Non-homogeneous Poisson processes (NHPPs) have gained much popularity in actual software testing phases to estimate the software reliability, the number of remaining faults in software and the software release timing. In this paper, we propose a new modeling approach for the NHPP-based software reliability models (SRMs) to describe the stochastic behavior of software fault-detection processes. The fundamental idea is to apply the equilibrium distribution to the fault-detection time distribution in NHPP-based modeling. We also develop efficient parameter estimation procedures for the proposed NHPP-based SRMs. Through numerical experiments, it can be concluded that the proposed NHPP-based SRMs outperform the existing ones in many data sets from the perspective of goodness-of-fit and prediction performance.

This paper proposes an iterative maximum a posteriori (MAP) receiver for orthogonal frequency division multiplexing (OFDM) mobile communications under fast-fading conditions. The previous work in [21] developed a MAP receiver based on the expectation-maximization (EM) algorithm employing the differential model, which can allow correlated time-variation of channel impulse responses. In order to make such a MAP receiver more robust against time-variant channels, this paper proposes two new message-passing algorithms derived from factor graphs; subcarrier removal and partial turbo processing. The subcarrier removal estimates the channel frequency response by using all subcarriers other than the targeted subcarrier. Such channel estimate can be efficiently calculated by removing information on the targeted subcarrier from the estimate of the original EM algorithm that uses all the subcarriers. This modification can avoid the repetitive use of incorrectly detected signals for the channel estimation. On the other hand, the partial turbo processing performs symbol-by-symbol channel decoding by using a symbol interleaver. Owing to this process, the current channel estimate, which is more accurate due to the decoding gain, can be used as the initial channel estimate for the next symbol. Computer simulations under fast multipath fading conditions demonstrate that the subcarrier removal and the partial turbo processing can improve the error floor and the convergence speed, respectively, compared to the conventional MAP receiver.

The quasi-ARX neurofuzzy (Q-ARX-NF) model has shown great approximation ability and usefulness in nonlinear system identification and control. It owns an ARX-like linear structure, and the coefficients are expressed by an incorporated neurofuzzy (InNF) network. However, the Q-ARX-NF model suffers from curse-of-dimensionality problem, because the number of fuzzy rules in the InNF network increases exponentially with input space dimension. It may result in high computational complexity and over-fitting. In this paper, the curse-of-dimensionality is solved in two ways. Firstly, a support vector regression (SVR) based approach is used to reduce computational complexity by a dual form of quadratic programming (QP) optimization, where the solution is independent of input dimensions. Secondly, genetic algorithm (GA) based input selection is applied with a novel fitness evaluation function, and a parsimonious model structure is generated with only important inputs for the InNF network. Mathematical and real system simulations are carried out to demonstrate the effectiveness of the proposed method.

In this paper, we investigate the performance of Thorup's algorithm by comparing it to Dijkstra's algorithm for large-scale network simulations. One of the challenges toward the realization of large-scale network simulations is the efficient execution to find shortest paths in a graph with N vertices and M edges. The time complexity for solving a single-source shortest path (SSSP) problem with Dijkstra's algorithm with a binary heap (DIJKSTRA-BH) is O((M + N) log N). An sophisticated algorithm called Thorup's algorithm has been proposed. The original version of Thorup's algorithm (THORUP-FR) has the time complexity of O(M + N). A simplified version of Thorup's algorithm (THORUP-KL) has the time complexity of O(M α(N) + N) where α(N) is the functional inverse of the Ackerman function. In this paper, we compare the performances (i.e., execution time and memory consumption) of THORUP-KL and DIJKSTRA-BH since it is known that THORUP-FR is at least ten times slower than Dijkstra's algorithm with a Fibonaccii heap. We find that (1) THORUP-KL is almost always faster than DIJKSTRA-BH for large-scale network simulations, and (2) the performances of THORUP-KL and DIJKSTRA-BH deviate from their time complexities due to the presence of the memory cache in the microprocessor.

A key challenge in developing energy-efficient sensor networks is to extend network lifetime in resource-limited environments. As sensors are often densely distributed, they can be scheduled on alternative duty cycles to conserve energy while satisfying the system requirements. Directional sensor networks composed of a large number of directional sensors equipped with a limited battery and with a limited angle of sensing have recently attracted attention. Many types of directional sensors can rotate to face a given direction. Maximizing network lifetime while covering all of the targets in a given area and forwarding sensor data to the sink is a challenge in developing such rotatable directional sensor networks. In this paper, we address the maximum directional cover tree (MDCT) problem of organizing directional sensors into a group of non-disjoint subsets to extend network lifetime. One subset, in which the directional sensors cover all of the targets and forward the data to the sink, is activated at a time, while the others sleep to conserve energy. For the MDCT problem, we first present an energy-consumption model that mainly takes into account the energy expenditure for sensor rotation as well as for the sensing and relaying of data. We also develop a heuristic scheduling algorithm called directional coverage and connectivity (DCC)-greedy to solve the MDCT problem. To verify and evaluate the algorithm, we conduct extensive simulations and show that it extends network lifetime to a reasonable degree.

Zero-knowledge arguments allows one party to prove that a statement is true, without leaking any other information than the truth of the statement. In many applications such as verifiable shuffle (as a practical application) and circuit satisfiability (as a theoretical application), zero-knowledge arguments for mathematical statements related to linear algebra are essentially used. Groth proposed (at CRYPTO 2009) an elegant methodology for zero-knowledge arguments for linear algebraic relations over finite fields. He obtained zero-knowledge arguments of the sub-linear size for linear algebra using reductions from linear algebraic relations to equations of the form z=x*'y, where x, y ∈ Fnp are committed vectors, z ∈ Fp is a committed element, and *': FnpFnpFp is a bilinear map. These reductions impose additional rounds on zero-knowledge arguments of the sub-linear size. The round complexity of interactive zero-knowledge arguments is an important measure along with communication and computational complexities. We focus on minimizing the round complexity of sub-linear zero-knowledge arguments for linear algebra. To reduce round complexity, we propose a general transformation from a t-round zero-knowledge argument, satisfying mild conditions, to a (t-2)-round zero-knowledge argument; this transformation is of independent interest.

Mobility Robustness Optimization (MRO) is one of the most important goals in LTE-Advanced Self-Organizing Networks (SON). Seamless handover in femtocell network is urgent and challenging, which has not been paid enough attention. Handover decision parameters, such as Time-To-Trigger (TTT), Hysteresis, Cell Individual Offset (CIO), have great effect on mobility performance, which may lead to Radio Link Failures (RLFs) and Unnecessary Handover. This letter proposes a handover parameters optimization approach based on Ant Colony Algorithm in the femtocell networks. The simulation result shows that the proposed scheme has a better performance than the fixed parameters method.

It is important to optimize aggregation schemes for heterogeneous wireless networks for maximizing communication throughput utilizing any available radio access networks. In the heterogeneous networks, differences of the quality of service (QoS), such as throughput, delay and packet loss rate, of the networks makes difficult to maximize the aggregation throughput. In this paper, we firstly analyze influences of such differences in QoS to the aggregation throughput, and show that it is possible to improve the throughput by adjusting the parameters of an aggregation system. Since manual parameter optimization is difficult and takes much time, we propose an autonomous parameter tuning scheme using a machine learning algorithm for the heterogeneous wireless network aggregation. We implement the proposed scheme on a heterogeneous cognitive radio network system. The results on our experimental network with network emulators show that the proposed scheme can improve the aggregation throughput better than the conventional schemes. We also evaluate the performance using public wireless network services, such as HSDPA, WiMAX and W-CDMA, and verify that the proposed scheme can improve the aggregation throughput by iterating the learning cycle even for the public wireless networks. Our experimental results show that the proposed scheme achieves twice better aggregation throughput than the conventional schemes.

Maximum likelihood block signal detection employing QR decomposition and M-algorithm (QRM-MLBD) can significantly improve the bit error rate (BER) performance of single-carrier (SC) transmission while significantly reducing the computational complexity compared to maximum likelihood detection (MLD). However, its computational complexity is still high. In this paper, we propose the computationally efficient 2-step QRM-MLBD. Compared to conventional QRM-MLBD, the number of symbol candidates can be reduced by using preliminary decision made by minimum mean square error based frequency-domain equalization (MMSE-FDE). The BER performance achievable by 2-step QRM-MLBD is evaluated by computer simulation. It is shown that it can significantly reduce the computational complexity while achieving almost the same BER performance as the conventional QRM-MLBD.

In the analysis of maximum-likelihood decoding performance of low-density parity-check (LDPC) codes, the weight distribution is an important factor. We presented a probabilistic method for computing the weight distribution of LDPC codes, and showed results of computing the weight distribution of several LDPC codes. In this paper, we improve our previously presented method and propose a probabilistic computation method with reliability for the weight distribution of LDPC codes. Using the proposed method, we can determine the weight distribution with small failure probability.

A recursive and efficient method for generating binary vectors in non-increasing order of their likelihood for a set of all binary vectors is proposed. Numerical results on experiments show the effectiveness of this method. Efficient decoding algorithms with simulation results are also proposed as applications of the method.

This paper presents design of a novel high speed booth encoder-decoder in a 0.35 µm CMOS technology. Focusing on transistor level implementation of the new architecture and employing newly designed truth table, the gate level delay of the whole system is reduced to one logic gate plus one transistor delay which is the main advantage of the proposed circuit. Simulation results indicate high speed performance of the designed circuit and depict low power dissipation feature of implemented architecture which makes this work suitable for extensive use in high speed arithmetic blocks.

As process technology is scaled down, a typical system on a chip (SoC) becomes denser. In scaled process technology, process variation becomes greater and increasingly affects the SoC circuits. Moreover, the process variation strongly affects network-on-chips (NoCs) that have a synchronous network across the chip. Therefore, its network frequency is degraded. We propose a process-variation-adaptive NoC with a variation-adaptive variable-cycle router (VAVCR). The proposed VAVCR can configure its cycle latency adaptively on a processor core basis, corresponding to the process variation. It can increase the network frequency, which is limited by the process variation in a conventional router. Furthermore, we propose a variable-cycle pipeline adaptive routing (VCPAR) method with VAVCR; the proposed VCPAR can reduce packet latency and has tolerance to network congestion. The total execution time reduction of the proposed VAVCR with VCPAR is 15.7%, on average, for five task graphs.

Based on our previous work, this work presents a complete method for time-domain processing of frequency-domain data with evenly-spaced frequency indices, together with its application. The proposed method can be used to calculate the cross spectral and power spectral densities for the frequency indices of interest. A promising application for the time-domain processing of frequency-domain data, particularly for calculating the summation of frequency-domain cross- and auto-correlations in orthogonal frequency-division multiplexing (OFDM) systems, is studied. The advantages of the time-domain processing of frequency-domain data are 1) the ability to rapidly acquire the properties that are readily available in the frequency domain and 2) the reduced complexity. The proposed fast algorithm directly employs time-domain samples, and hence, does not need the fast Fourier transform (FFT) operation. The proposed algorithm has a lower complexity (required complex multiplications ∼ O(N)) than conventional techniques.

The k-edge-connectivity augmentation problem with bipartition constraints (kECABP, for short) is defined by “Given an undirected graph G=(V, E) and a bipartition π = {VB, VW} of V with VB ∩ VW = ∅, find an edge set Ef of minimum cardinality, consisting of edges that connect VB and VW, such that G'=(V, E ∪ Ef) is k-edge-connected.” The problem has applications for security of statistical data stored in a cross tabulated table, and so on. In this paper we propose a fast algorithm for finding an optimal solution to (σ + 1)ECABP in O(|V||E| + |V2|log |V|) time when G is σ-edge-connected (σ > 0), and show that the problem can be solved in linear time if σ ∈ {1, 2}.