基于Tile自组装模型的最大匹配问题算法研究

Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n²)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.     

一种基于QoE量化评估的服务选择算法

针对如何为互联网用户从多个相同或相似的服务中进行选择的问题,提出了一种新的服务选择算法:基于QoE(Quality of Experience)量化评估的服务选择算法(A Service Selecting Algorithm Based on Quantified QoE Evaluation,ASSABQ).该算法基于一种层次化评分模型,从历史评分中学习获取用户偏好,根据多种评价因素计算每个可用服务的满意度,并选择满意度最高的服务给用户.与已知算法相比,ASSABQ算法的复杂度从O(n²)下降到O(n).仿真实验结果表明,在相同应用场景下,采用ASSABQ算法得到的用户满意度比已知算法提高约10%.     

A low power scheduling scheme with resources operating at multiplevoltages

This paper presents resource and latency constrained scheduling algorithms to minimize power/energy consumption when the resources operate at multiple voltages (5 V, 3.3 V, 2.4 V, and 1.5 V). The proposed algorithms are based on efficient distribution of slack among the nodes in the data-flow graph. The distribution procedure tries to implement the minimum energy relation derived using the Lagrange multiplier method in an iterative fashion. Two algorithms are proposed, 1) a low complexity O(n²) algorithm and 2) a high complexity O(n² log(L)) algorithm, where n is the number of nodes and L is the latency. Experiments with some HLS benchmark examples show that the proposed algorithms achieve significant power/energy reduction. For instance, when the latency constraint is 1.5 times the critical path delay, the average reduction is 39%     

On broadcasting with cooperative diversity in multi-hop wireless networks

Cooperative diversity facilitates spatio-temporal communications without requiring the deployment of physical antenna arrays. While physical layer studies on cooperative diversity have been extensive, higher layer protocols which translate the achievable reduction in the SNR per bit for a given target BER, into system wide performance enhancements are yet to mature. The challenge is that appropriate higher layer functions are needed in order to enable cooperative diversity at the physical layer. We focus on network-wide broadcasting with the use of cooperative diversity in ad hoc networks. We design a novel distributed network-wide broadcasting protocol that takes into account the physical layer dependencies that arise with cooperative diversity. We perform extensive simulations that show that our protocol can outperform the best of the noncooperative broadcasting protocols by: (a) achieving up to a threefold increase in network coverage and, (b) by decreasing the latency incurred during the broadcast by about 50%. We also construct an analytical model that captures the behavior of our protocol. Furthermore, we show that computing the optimal solution to the cooperative broadcast problem is NP-complete and construct centralized approximation algorithms. Specifically, we construct an O(N ^epsi)-approximation algorithm with a computational complexity of O(N4/epsi); we also construct a simpler greedy algorithm.. The costs incurred with these algorithms serve as benchmarks with which one can compare that achieved by any distributed protocol     

双向中继系统用户联合预编码与检测算法研究

双向中继协同通信系统的两用户节点通过中继节点相互交换信息,显示了其在频谱效率上的优势。在系统装备多天线的情况下,为进一步改善误比特率性能,论文提出一种基于格规约算法的用户联合预编码与检测算法。该算法通过一次复数域格规约处理来提高信道增益矩阵的正交性,预编码和检测算法联合应用处理后的矩阵,中继节点仅需要对接收信号进行求模运算和放大转发,算法的复杂度主要集中在两用户节点上。仿真结果显示:相比于传统的预编码和检测算法,用户联合预编码与检测算法在计算复杂度仅增加了对信道增益矩阵一次格规约计算的前提下,可显著降低系统的误比特率,提高分集增益,具有工程实用价值。     

Multiuser decoding for multibeam systems

An iterative multiuser decoding algorithm for co-channel BPSK/QPSK users in a multibeam system is presented. The approach can be applied to the return link of multibeam satellites and to terrestrial systems with sectored base-station antennas. It allows the reuse of the same spectrum in each beam. The algorithm is based on the extension of turbo-decoding techniques to the iterative decoding of parallel users. Simulation results show one can asymptotically achieve single user performance in a high multiuser interference environment; often this includes some diversity gain. The complexity of the algorithm is approximately O(2^K+2^κ) operations per bit per iteration where K is the number of co-channel users and κ is the constraint length of the forward error correction code     

基于自组装的N皇后问题DNA计算算法

N皇后问题是理论计算机科学中一个经典的NP难问题.自Adleman首次运用DNA计算来解决NP问题以来,DNA计算已成为计算机科学的研究热点之一,现有N皇后问题的DNA计算机算法多基于粘贴和剪接模型,存在生化操作复杂度和实验误差较高等问题.本文提出了一种基于DNA自组装模型来求解N皇后问题的DNA计算方法.算法通过减少实验操作步骤数,降低了生化解的错误率.算法使用的tiles分子块种类为O（n²）,生化操作复杂性为O（1）,其中n为皇后的个数.与求解N皇后问题的其它DNA算法的对比分析表明,本算法可提高生化解的准确性,降低算法生化实验的复杂度,具有良好的易操作性.     

Energy-efficient relay selection and optimal relay location in cooperative cellular networks with asymmetric traffic

Energy-efficient communication is an important requirement for mobile relay networks due to the limited battery power of user terminals. This paper considers energy-efficient relaying schemes through selection of mobile relays in cooperative cellular systems with asymmetric traffic. The total energy consumption per information bit of the battery-powered terminals, i. e. , the mobile station(MS)and the relay, is derived in theory. In the joint uplink and downlink relay selection(JUDRS)scheme we proposed, the relay which minimizes the total energy consumption is selected. Additionally, the energy-efficient cooperation regions are investigated, and the optimal relay location is found for cooperative cellular systems with asymmetric traffic. The results reveal that the MS-relay and the relay-base station(BS)channels have different influence over relay selection decisions for optimal energy-efficiency. Information theoretic analysis of the diversity-multiplexing tradeoff(DMT)demonstrates that the proposed scheme achieves full spatial diversity in the quantity of cooperating terminals in this network. Finally, numerical results further confirm a significant energy efficiency gain of the proposed algorithm comparing to the previous best worse channel selection and best harmonic mean selection algorithms.     

Low complexity detection algorithm based on optimized Neumann series for massive MIMO system

An optimized Neumann series ( NS ) approximation isdescribed based on Frobenius matrix decomposition, this method aims to reduce the high complexity, which caused by the large matrix inversion of detection algorithm in the massive multiple input multiple output (MIMO) system. The large matrix in the inversion is decomposed into the sum of the hollow matrix and a Frobenius matrix, and the Frobenius matrix has the diagonal elements and the first column of the large matrix. In order to ensure the detection performance approach to minimum mean square error (MMSE) algorithm, the first three terms of the series approximation are needed, which results in high complexity as O(K³), where K is the number of users. This paper further optimize the third term of the series approximation to reduce the computational complexity from O(K³) to O(K²). The computational complexity analysis and simulation results show that the performance of proposed algorithm can approach to MMSE algorithm with low complexity O(K²).     

A utility-based capacity optimization framework for achieving cooperative diversity in the hierarchical converged heterogeneous wireless networks

A hierarchical convergence mechanism for the heterogeneous wireless communication system via the heterogeneous cooperative relay node is presented in this paper, in which the techniques of cooperative communication and wireless relay are utilized to improve performances of the individual user and the overall converged networks. In order to evaluate the benefits of the proposal, a utility-based capacity optimization framework for achieving the heterogeneous cooperative diversity gain is proposed. The heterogeneous cooperative capacity, relay selection and power allocation theoretical models are derived individually. The joint optimization model for relay selection and power allocation is presented as well. Owing to the computation complexity, the sub-optimal cooperative relay selection algorithm, the sub-optimal power allocation algorithm and the sub-optimal joint algorithm are determined to approach the maximum overall networks' spectrum efficiency. These proposed algorithms are designed in conformance to guarantee the equivalent transmission rates of the different wireless access networks. The simulation results demonstrate that the utility-based capacity model is available for the heterogeneous cooperative wireless communication system, and the proposed algorithms can improve performances by achieving the cooperative gain and taking full advantage of the cross-layer design. Copyright © 2008 John Wiley & Sons, Ltd.     

An improved stochastic gradient algorithm for principal componentanalysis and subspace tracking

We propose a new stochastic gradient algorithm for principal component analysis and subspace tracking, requiring O(nm) operations per update, where n is the number of input signals, and m is the signal subspace dimension. A parallel version with problem size independent throughput is obtained at the expense of O(n²) additional flops     

Beam interference suppression in multi-cell millimeter wave communications

Due to the increase in the number of users, beam switching is used for suppressing interference, which leads to higher computational complexity in multi-cell millimeter wave communications. In order to resolve this problem, a beam interference model is introduced, and a lower complexity beam interference suppression algorithm based on user grouping is proposed. The proposed algorithm operates beam switching and multi-cell cooperative transmission for a part of the users when there exists beam interference due to high user density. In particular, considering the distinct interference suffered by each user, the proposed dual-threshold user grouping method can effectively solve the frequent switching problem at the base station caused by multi-cell cooperative transmission in multi-cell environments. Simulation results show that the proposed algorithm can reduce the computational complexity of beam switching and approach ideal system capacity, compared with conventional interference suppression algorithms that do not involve grouping of users.     

Fast and stable least-squares approach for the design of linearphase FIR filters

We present a new numerical algorithm for solving the normal equations associated with the least-squares design of linear phase FIR filters. The usual solution methods have a computational complexity of O(N³). Moreover, solving the normal equations with Gaussian elimination commonly yields numerical errors, especially when the filter is long. Here, we convert a least-squares method into the problem of constructing a system of orthonormal functions. The proposed design algorithm needs only O(N²) computations, and numerical errors can be reduced. Some examples are given to show the performance of the algorithm     

Registering Landsat images by point matching

Image registration of Landsat Thematic Mapper scenes with translational and rotational differences is studied. Two major steps of image registration, control-point selection and control-point matching, are emphasized. In control-point selection, the properties that a good control point should satisfy are defined. Several potential control-point candidates are suggested, and methods are discussed for extracting them from the input image. In control-point matching, a relaxation algorithm proposed in the literature is improved by reducing its time complexity from O(n⁴) to O(n³ ), where n is the number of control points. The matching algorithm also uses a two-way matching concept which utilizes the inherent symmetry property of the point-matching problem. The robustness of the proposed algorithm was demonstrated through simulation experiments by evaluating a matching index. Experimental results on Landsat images show that the proposed method produces results comparable to those obtained by an experienced photointerpreter     

Testing complex couplings in multiport memories

In this paper, the effects of simultaneous write access on the fault modeling of multiport RAMs are investigated. New fault models representing more accurately the actual faults in such memories are then defined. Subsequently, a general algorithm that ensures the detection of all faults belonging to the new fault model is proposed. Unfortunately, the obtained algorithms are of O(n²) complexity which is not practical for real purposes. In order to reduce the complexity of the former test algorithm a topological approach has been developed. Finally, a BIST implementation of one of the proposed topological algorithms is presented     

QoS-guaranteed multi-relay selection and power allocation optimization in cooperative systems

This paper investigates the relay selection and power allocation problem in multi-user based cooperative networks, where intermediate relay nodes help source forward information to destination using decode-and-forward (DF) relaying protocol. Specifically, we propose a novel multi-relay nodes selection strategy taking both instantaneous channel state information (I-CSI) and residual energy into consideration, by which 'emergence' diversity gain can be achieved and the imbalance of resource utilization can be overcome. Besides, using Largangian dual-primal decomposition and subgradient projection approach, an optimal power allocation algorithm at source and cooperative relay nodes is presented with the constraints of each user's individual quality of service (QoS) requirements and system total transmit power. Theoretical analysis and simulation results demonstrate that the proposed scheme can significantly improve energy efficiency, while guaranteeing a good balance between achievable data rate and average network lifetime with relatively low implementation complexity.     

Dynamic resource allocation in mobile heterogeneous cellular networks

User mobility is a challenging issue in macro and femto cellular networks for the fifth-generation and newer mobile communications due to the time-varying interference and topology experienced. In this paper, we consider an OFDMA-based two-tier network with one macro cell and several femto cells, wherein each macro user and/or femto user can leave or enter its serving cell frequently, referred to as user mobility. A resource allocation problem with different rate requirements of mobile users is then formulated. Assuming well knowledge of the user locations and the channel state information, we propose a dynamic algorithm with static and dynamic parts for a better trade-of between computational complexity and system throughput. The static algorithm, named interference weighted cluster algorithm in this paper, is based on the graph theory to cluster the femtocells by minimizing the interference between clusters, while the dynamic algorithm is to deal with the user mobility by sharing the resource blocks under the constraints of rate requirements. Numerical results are demonstrated to show the effectiveness of the proposed dynamic resource allocation algorithm in terms of capacity, computational time, and outage probability.

     

Low complexity affine MMSE detector for iterative detection-decoding MIMO OFDM systems

Iterative turbo processing between detection and decoding shows near-capacity performance on a multiple-antenna system. Combining iterative processing with optimum front-end detection is particularly challenging because the front-end maximum a posteriori (MAP) algorithm has a computational complexity that is exponential. Sub-optimum detector such as the soft interference cancellation linear minimum mean square error (SIC-LMMSE) detector with near front-end MAP performance has been proposed in the literature. The asymptotic computational complexity of SIC-LMMSE is O(n_t ²n_r + n_tn_r ³ + n_tM_c2^Mc) per detection-decoding cycle where n_t is number of transmit antenna, nr is number of receive antenna, and Mc is modulation size. A lower complexity detector is the hard interference cancellation LMMSE (HIC-LMMSE) detector. HIC-LMMSE has asymptotic complexity of O(n_t ²n_r + n_tM_c2^Mc) but suffers extra performance degradation. In this paper, two front-end detection algorithms are introduced that not only achieve asymptotic computational complexity of O(n_t ²n_r + n_tn_r ² [Gamma (beta) + 1] + n_tM_c2^Mc) where Gamma(beta) is a function with discrete output {-1, 2, 3, ...,n_t} and O(n_tM_c2^Mc) respectively. Simulation results demonstrate that the proposed low complexity detection algorithms offer exactly same performance as their full complexity counterpart in an iterative receiver while being computational more efficient.     

Diversity Evaluation of Two-Port Antenna System for a Mobile Terminal

Next-generation mobile communication systems require high data transmission rate and low bit error rate, but multi-path fading still stands as a major problem. Antenna diversity techniques can overcome the problem. In this paper, we thoroughly study the antenna diversity performance on a mobile terminal through theoretical analysis, computer simulations, and practical prototype measurements. Specifically, a genetic methodology is developed to accurately evaluate the diversity gain achieved in the mobile terminal from both power level approach and correlation approach. Throughout the simulations and measurements, we demonstrate that it is beneficial to implement antenna diversity on mobile terminal side, and high diversity gain can be achieved when the antennas are placed in the terminals properly. Moreover, further improvement of the diversity gain can be obtained from the implementation of the matching networks.     

Competitive Resource Sharing Based on Game Theory in Cooperative Relay Networks

This letter considers the problem of resource sharing among a relay and multiple user nodes in cooperative transmission networks. We formulate this problem as a sellers’ market competition and use a noncooperative game to jointly consider the benefits of the relay and the users. We also develop a distributed algorithm to search the Nash equilibrium, the solution of the game. The convergence of the proposed algorithm is analyzed. Simulation results demonstrate that the proposed game can stimulate cooperative diversity among the selfish user nodes and coordinate resource allocation among the user nodes effectively.