This paper investigates the wireless information surveillance in a suspicious millimeter wave (mmWave) wireless communication system via the spoofing relay based proactive eavesdropping approach. Specifically, the legitimate monitor in the system acts as a relay to simultaneously eavesdrop and send spoofing signals to vary the source transmission rate. To maximize the effective eavesdropping rate, an optimization problem for both hybrid precoding design and power distribution is formulated. Since the problem is fractional and non-convex, we resort to the Dinkelbach method to equivalently reduce the original problem into a series of non-fractional problems, which is still coupling. Afterwards, based on the BCD-type method, the non-fractional problem is reduced to three subproblems with two introduced parameters. Then the GS-PDD-based algorithm is proposed to obtain the optimal solution by alternately optimizing the three subproblems and simultaneously updating the introduced parameters. Numerical results verify the effectiveness and superiority of our proposed scheme.

Given a graph G=(V,E), where V and E are vertex and edge sets of G, and a subset VNT of vertices called a non-terminal set, the minimum spanning tree with a non-terminal set VNT, denoted by MSTNT, is a connected and acyclic spanning subgraph of G that contains all vertices of V with the minimum weight where each vertex in a non-terminal set is not a leaf. On general graphs, the problem of finding an MSTNT of G is NP-hard. We show that if G is a series-parallel graph then finding an MSTNT of G is linearly solvable with respect to the number of vertices.

Pre-weighting based Contention Resolution Diversity Slotted ALOHA-like (PW-CRDSA-like) schemes with joint multi-user multi-slot detection (JMMD) algorithm are proposed to improve the throughput of random access (RA) in geostationary earth orbit (GEO) satellite networks. The packet and its replicas are weighted by different pre-weighting factors at each user terminal, and are sent in randomly selected slots within a frame. The correlation of channels between user terminals and satellite node in different slots are removed by using pre-weighting factors. At the gateway station, after the decoding processing of CRDSA, the combinations of remained signals in slots that can construct virtual multiple-input multiple-output (MIMO) signal models are found and decoded by the JMMD algorithm. Deadlock problems that can be equivalent to virtual MIMO signal models in the conventional CRDSA-like schemes can be effectively resolved, which improves the throughput of these CRDSA-like schemes. Simulation results show that the PW-CRDSA-like schemes with the JMMD significantly outperform the conventional CRDSA-like schemes in terms of the throughput under equal packet loss ratio (PLR) conditions (e.g. PLR =10-2), and as the number of the transmitted replicas increases, the throughput of the PW-CRDSA-like schemes also increases, and the normalized maximum throughput of the PW-CRDSA-5 (i.e., PW-CRDSA with 5 replicas) scheme can reach 0.95.

We study the problem of transforming one (vertex) c-coloring of a graph into another one by changing only one vertex color assignment at a time, while at all times maintaining a c-coloring, where c denotes the number of colors. This decision problem is known to be PSPACE-complete even for bipartite graphs and any fixed constant c ≥ 4. In this paper, we study the problem from the viewpoint of graph classes. We first show that the problem remains PSPACE-complete for chordal graphs even if c is a fixed constant. We then demonstrate that, even when c is a part of input, the problem is solvable in polynomial time for several graph classes, such as k-trees with any integer k ≥ 1, split graphs, and trivially perfect graphs.

Let G=(V,E) be an unweighted simple graph. A distance-d independent set is a subset I ⊆ V such that dist(u, v) ≥ d for any two vertices u, v in I, where dist(u, v) is the distance between u and v. Then, Maximum Distance-d Independent Set problem requires to compute the size of a distance-d independent set with the maximum number of vertices. Even for a fixed integer d ≥ 3, this problem is NP-hard. In this paper, we design an exact exponential algorithm that calculates the size of a maximum distance-3 independent set in O(1.4143n) time.

The mapping optimization problem in Network-on-Chip (NoC) is constraint and NP-hard, and the deterministic algorithms require considerable computation time to find an exact optimal mapping solution. Therefore, the metaheuristic algorithms (MAs) have attracted great interests of researchers. However, most MAs are designed for continuous problems and suffer from premature convergence. In this letter, a binary metaheuristic mapping algorithm (BMM) with a better exploration-exploitation balance is proposed to solve the mapping problem. The binary encoding is used to extend the MAs to the constraint problem and an adaptive strategy is introduced to combine Sine Cosine Algorithm (SCA) and Particle Swarm Algorithm (PSO). SCA is modified to explore the search space effectively, while the powerful exploitation ability of PSO is employed for the global optimum. A set of well-known applications and large-scale synthetic cores-graphs are used to test the performance of BMM. The results demonstrate that the proposed algorithm can improve the energy consumption more significantly than some other heuristic algorithms.

In this paper, we show the explicit formula of the recurrence relation for the Tower of Hanoi on the star graph with four vertices, where the perfect tower of disks on a leaf vertex is transferred to the central vertex. This gives the solution to the problem posed at the 17th International Conference on Fibonacci Numbers and Their Applications[11]. Then, the recurrence relation are generalized to include the ones for the original 4-peg Tower of Hanoi and the Star Tower of Hanoi of transferring the tower from a leaf to another.

The Machine-to-Machine (M2M) service network platform accommodates M2M communications traffic efficiently by using tree-structured networks and the computation resources deployed on network nodes. In the M2M service network platform, program files required for controlling devices are placed on network nodes, which have different amounts of computation resources according to their position in the hierarchy. The program files must be dynamically repositioned in response to service quality requests from each device, such as computation power, link bandwidth, and latency. This paper proposes a Program File Placement (PFP) method for the M2M service network platform. First, the PFP problem is formulated in the Mixed-Integer Linear Programming (MILP) approach. We prove that the decision version of the PFP problem is NP-complete. Next, we present heuristic algorithms that attain sub-optimal but attractive solutions. Evaluations show that the heuristic algorithm based on the number of devices that share a program file reduces the total number of placed program files compared to the algorithm that moves program files based on their position.

Softwarized networks are expected to be utilized as a core network for the 5th Generation (5G) mobile services. For the mobile core network architecture, service chaining is expected to be utilized for dynamically steering traffic across multiple network functions. In this paper, for dynamic multipath service chaining, we propose a greedy-based VNF placement algorithm. This method can provide multipath service chaining so as to utilize the node resources such as CPU effectively while decreasing the cost about bandwidth and transmission delay. The proposed algorithm consists of four difference algorithms, and VNFs are placed appropriately with those algorithm. Our proposed algorithm obtains near optimal solution for the formulated optimization problem with a greedy algorithm, and hence multipath service chains can be provided dynamically. We evaluate the performance of our proposed method with simulation and compare its performance with the performances of other methods. In numerical examples, it is shown that our proposed algorithm can provide multipath service chains appropriately so as to utilize the limited amount of node resources effectively. Moreover, it is shown that our proposed algorithm is effective for providing service chaining dynamically in large-scale network.

We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.

Order preserving matching refers to the problem of reporting substrings in the text which are order-isomorphic to the pattern. In this paper, we show a simple heuristic which runs in linear time on average, based on finding the largest elements in each substring and checking their locations against that of the pattern. It is easy to implement and experimental results showed that the running time grows linearly.

Unitary operator discrimination is a fundamental problem in quantum information theory. The basic version of this problem can be described as follows: Given a black box implementing a unitary operator U∈S:={U1, U2} under some probability distribution over S, the goal is to decide whether U=U1 or U=U2. In this paper, we consider the query complexity of this problem. We show that there exists a quantum algorithm that solves this problem with bounded error probability using $lceil{sqrt{6} heta_{ m cover}^{-1}} ceil$ queries to the black box in the worst case, i.e., under any probability distribution over S, where the parameter θcover, which is determined by the eigenvalues of $U_1^dagger {U_2}$, represents the “closeness” between U1 and U2. We also show that this upper bound is essentially tight: we prove that for every θcover > 0 there exist operators U1 and U2 such that any quantum algorithm solving this problem with bounded error probability requires at least $lceil{rac{2}{3 heta_{ m cover}}} ceil$ queries under uniform distribution over S.

This paper proposes a novel distributed proximal minimization algorithm for constrained optimization problems over fixed strongly connected networks. At each iteration, each agent updates its own state by evaluating a proximal operator of its objective function under a constraint set and compensating the unbalancing due to unidirectional communications. We show that the states of all agents asymptotically converge to one of the optimal solutions. Numerical results are shown to confirm the validity of the proposed method.

MU-MIMO (Multi-User Multiple Input and Multiple Output) has been considered as a fundamental technology for simultaneous communications between a base station and multiple users. This is because it can generate a large virtual MIMO channel between a base station and multiple user terminals with effective utilization of wireless resources. As a method of implementing MU-MIMO downlink, Block Diagonalization (BD) was proposed in which the transmission weights are determined to cancel interference between multiple user terminals. On the other hand, Block Maximum Signal-to-Noise ratio (BMSN) was proposed which determines the transmission weights to enhance the gain for each user terminal in addition to the interference cancellation. As a feature, BMSN has a pseudo-noise for controlling the null depth to the interference. In this paper, to enhance further the BMSN performance, we propose the BMSN algorithm that has the pseudo-noise determined according to receiver SNR. As a result of computer simulation, it is confirmed that the proposed BMSN algorithm shows the significantly improved performance in evaluation of bit error rate (BER) and achievable bit rate (ABR).

The k-edge-connectivity augmentation problem for a specified set of vertices (kECA-SV for short) is defined by “Given a graph G=(V, E) and a subset Γ ⊆ V, find a minimum set E' of edges such that G'=(V, E ∪ E') has at least k edge-disjoint paths between any pair of vertices in Γ.” Let σ be the edge-connectivity of Γ (that is, G has at least σ edge-disjoint paths between any pair of vertices in Γ). We propose an algorithm for (σ+1)ECA-SV which is done in O(|Γ|) maximum flow operations. Then the time complexity is O(σ2|Γ||V|+|E|) if a given graph is sparse, or O(|Γ||V||BG|log(|V|2/|BG|)+|E|) if dense, where |BG| is the number of pairs of adjacent vertices in G. Also mentioned is an O(|V||E|+|V|2 log |V|) time algorithm for a special case where σ is equal to the edge-connectivity of G and an O(|V|+|E|) time one for σ ≤ 2.

We propose a new method of differential fault attack, which is based on the nibble-group differential diffusion property of the lightweight block cipher MIBS. On the basis of the statistical regularity of differential distribution of the S-box, we establish a statistical model and then analyze the relationship between the number of faults injections, the probability of attack success, and key recovering bits. Theoretically, time complexity of recovering the main key reduces to 22 when injecting 3 groups of faults (12 nibbles in total) in 30,31 and 32 rounds, which is the optimal condition. Furthermore, we calculate the expectation of the number of fault injection groups needed to recover 62 bits in main key, which is 3.87. Finally, experimental data verifies the correctness of the theoretical model.

With the development of spaceborne synthetic aperture radar (SAR), ultra-high spatial resolution has become a hot topic in recent years. The system with high spatial resolution requests large range bandwidths and long azimuth integration time. However, due to the long azimuth integration time, many problems arise, which cannot be ignored in the operational ultra-high resolution spotlight mode. This paper investigates two critical issues that need to be noticed for the full-aperture processing of ultra-high resolution spaceborne SAR spotlight data. The first one is the inaccuracy of the traditional hyperbolic range model (HRM) when the system approaches decimeter range resolution. The second one is the azimuth spectral folding phenomenon. The problems mentioned above result in significant degradation of the focusing effect. Thus, to solve these problems, a full-aperture processing scheme is proposed in this paper which combines the superiorities of two generally utilized processing algorithms: the precision of one-step motion compensation (MOCO) algorithm and the efficiency of modified two-step processing approach (TSA). Firstly, one-step MOCO algorithm, a state-of-the-art MOCO algorithm which has been applied in ultra-high resolution airborne SAR systems, can precisely correct for the error caused by spaceborne curved orbit. Secondly, the modified TSA can avoid the phenomenon of azimuth spectrum folding effectively. The key point of the modified TSA is the deramping approach which is carried out via the convolution operation. The reference function, varying with the instantaneous range frequency, is adopted by the convolution operation for obtaining the unfolding spectrum in azimuth direction. After these operations, the traditional wavenumber domain algorithm is available because the error caused by spaceborne curved orbit and the influence of the spectrum folding in azimuth direction have been totally resolved. Based on this processing scheme, the ultra-high resolution spaceborne SAR spotlight data can be well focused. The performance of the full-aperture processing scheme is demonstrated by point targets simulation.

To optimize the performance of FIR filters that have low computation complexity, this paper proposes a hybrid design consisting of two optimization levels. The first optimization level is based on cyclic-shift synthesis, in which all possible sub filters (or windowed sub filters) with distinct cycle shifts are averaged to generate a synthesized filter. Due to the fact that the ripples of these sub filters' transfer curves can be individually compensated, this synthesized filter attains improved performance (besides two uprushes occur on the edges of a transition band) and thus this synthesis actually plays the role of ‘natural optimization’. Furthermore, this synthesis process can be equivalently summarized into a 3-step closed-form procedure, which converts the multi-variable optimization into a single-variable optimization. Hence, to suppress the uprushes, what the second optimization level (by Differential Evolution (DE) algorithm) needs to do is no more than searching for the optimum transition point which incurs only minimal complexity . Owning to the combination between the cyclic-shift synthesis and DE algorithm, unlike the regular evolutionary computing schemes, our hybrid design is more attractive due to its narrowed search space and higher convergence speed . Numerical results also show that the proposed design is superior to the conventional DE design in both filter performance and design efficiency, and it is comparable to the Remez design.

Dynamic linear feedback shift registers (DLFSRs) are a scheme to transfer from one LFSR to another. In cryptography each LFSR included in a DLFSR should generate maximal-length sequences, and the number of switches transferring LFSRs should be small for efficient performance. This corresponding addresses on searching such conditioned DLFSRs. An efficient probabilistic algorithm is given to find such DLFSRs with two or four switches, and it is proved to succeed with nonnegligible probability.

In order to improve an imaging performance of a sparse array radar system we propose an optimization method to find a new antenna array layout. The method searches for a minimum of the cost function based on a 3D point spread function of the array. We found a solution for the simulated problem in a form of the new layout for the antenna array with more sparse middle-point distribution comparing with initial one.