Low Complexity User Scheduling,Ordering and Transmit Covariance Matrix Optimization Algorithms for Successive Zero-Forcing Precoding

In this paper we consider user scheduling, ordering and transmit covariance matrix optimization problems under successive zero-forcing (SZF) precoding for multiuser multiple-input multiple-output downlink. We propose a heuristic user scheduling metric and an intermediate user grouping technique to develop a low complexity greedy scheduling algorithm. A suboptimal user ordering technique is also proposed for transmit covariance matrix optimization under SZF. Proposed algorithm is of low complexity, but performs closely to the highly complex exhaustive search algorithm. For transmit covariance optimization under SZF, a dirty paper coding based algorithm has been previously proposed, which is computationally very complex. In this paper, we propose a suboptimal but much simplified algorithm, which employs an iterative procedure similar to a known multiple access channel (MAC) covariance optimization algorithm, but does not involve multiple levels of covariance matrix transformations. With the proposed suboptimal user ordering the exhaustive search through all possible user orders is avoided during transmit covariance matrix optimization resulting in a significant complexity reduction, and without a significant performance penalty. Simulation results show that the proposed algorithm performs very close to the known algorithm in the low SNR region.     

MU-MIMO下行链路基于关联干扰的先验式用户调度

该文针对MU-MIMO下行(广播)信道提出一种基于空间子信道关联干扰的先验式调度算法。该方法将用户调度转换为子信道的选择问题,通过综合考虑候选子信道的传输增益,以及候选者与已选的和潜在的、将来可能被选中的子信道间的相互干扰,获得一组相互干扰较小的子信道。仿真结果表明,合理地选取关联干扰参数,该算法能够获得计算复杂度与传输性能的良好折中,有效改善系统和速率。     

Joint power control and user scheduling for backbone-assisted industrial wireless networks with successive interference cancellation

In a backbone-assisted industrial wireless network (BAIWN), the technology of successive interference cancellation (SIC) based non-orthogonal multiple access (NOMA) provides potential solutions for improving the delay performance. Previous work emphasizes minimizing the transmission delay by user scheduling without considering power control. However, power control is beneficial for SIC-based NOMA to exploit the power domain and manage co-channel interference to simultaneously serve multiple user nodes with the high spectral and time resource utilization characteristics. In this paper, we consider joint power control and user scheduling to study the scheduling time minimization problem (STMP) with given traffic demands in BAIWNs. Specifically, STMP is formulated as an integer programming problem, which is NP-hard. To tackle the NP-hard problem, we propose a conflict graph-based greedy algorithm, to obtain a sub-optimal solution with low complexity. As a good feature, the decisions of power control and user scheduling can be made by the proposed algorithm only according to the channel state information and traffic demands. The experimental results show that compared with the other methods, the proposed method effectively improves the delay performance regardless of the channel states or the network scales.

     

Resource Allocation and Adaptive Modulation in Uplink SC-FDMA Systems

In this paper, we study joint power and sub-channel allocation, and adaptive modulation in Single Carrier Frequency Division Multiple Access (SC-FDMA) which is adopted as the multiple access scheme for the uplink in the 3GPP-LTE standard. A sum-utility maximization problem is considered. Unlike OFDMA, in addition to the restriction of allocating a sub-channel to one user at most, the multiple sub-channels allocated to a user in SC-FDMA should be consecutive as well. This renders the resource allocation problem prohibitively difficult and the standard optimization tools (e.g., Lagrange dual approach widely used for OFDMA, etc.) can not help towards its optimal solution. We propose a novel optimization framework for the solution of this problem which is inspired from the recently developed canonical duality theory. We first formulate the optimization problem as binary-integer programming problem, and then transform this binary-integer programming problems into a continuous space canonical dual problem that is a concave maximization problem. Based on the solution of the continuous space dual problem, we derive joint power and sub-channel allocation algorithm whose computational complexity is polynomial. We provide conditions under which the proposed algorithms are optimal. We also propose an adaptive modulation scheme which selects an appropriate modulation strategy for each user. We compare the proposed algorithm with the existing algorithms in the literature to assess their performance. The results show a tremendous performance gain.     

Rate scheduling in multiple antenna downlink wireless systems

We consider scheduling strategies for multiantenna and multibeam cellular wireless systems for high-speed packet data services on the downlink. We establish a fundamental connection between the stability region of the queuing system and the set of feasible transmission rates, which provides the basis for the scheduling algorithm proposed in this paper. Transmission using adaptive steerable beams and fixed sector beams are considered and average delay versus throughput results are obtained through simulations for the proposed scheduling scheme in each case. While in single antenna systems multiuser diversity gains are achieved by the scheduling algorithms that transmit to a single user in each scheduling interval, our results show that with multiple antennas, transmitting to a carefully chosen subset of users has superior performance. The multiantenna scheduling problem is closely related to the problem of coordinated scheduling for transmission through multiple base stations, where a user can receive signals from several base stations simultaneously. We consider the special case when three single-antenna base stations are allowed to cooperate and transmit to the users in the triangular region between the base stations and propose scheduling strategies that demonstrate significant gains.     

Pilot scheduling algorithm based on cell classification-cross entropy for massive MIMO

The massive MIMO system is equipped with a large number of antennas at the base station to serve many users, but it is affected by the inter-cell interference which called pilot contamination. A pilot scheduling scheme was designed to reduce the effect of pilot contamination. Pilot scheduling problem belongs to the arrangement optimization problem, and the algorithm computational complexity of greedy algorithm to search the optimal solution is greatly. In order to reduce the influence of the interference of the community, a new pilot scheduling schemes was proposed by so this article using cell classification and cross entropy(CE) mechanism to reduce the effect of pilot contamination on the system. The simulation results show that the proposed algorithm can not only improve the performance of the system, but also reduce the computational complexity.     

Reducing computational complexity using transmitter correlation value‐assisted schedulers in multiuser MIMO uplink

In this paper, a threshold bounded antenna selection scheduler (TBS) and a computational complexity bounded antenna selection scheduler (CCBS) are proposed to reduce computational complexity in multiple input multiple output (MIMO) uplink. In contrast to previous works, a spatially correlated MIMO channel model is considered and a transmitter correlation value (TCV) is newly introduced to assist the antenna selection in addition to the channel gain. For the TBS or CCBS, with predetermined threshold of TCV or ratio of successful antennas (RSAs), full searching (FS) and sub searching (SS) are applied more efficiently to user equipments (UEs) compared with previous schedulers. As a result, the number of candidate antennas in the scheduling set can be reduced, which translates into a lower computational complexity in terms of number of evaluated antenna combinations. Additionally, compared with the TBS, the peak computational complexity can be further reduced by the CCBS. Simulation results show that with proposed schedulers the computational complexity can be reduced by at least 50% with an acceptable compromise of capacity. Copyright © 2010 John Wiley & Sons, Ltd.     

An efficient algorithm for generalized SS/TDMA scheduling with satellite cluster and intersatellite links

We consider the satellite cluster scheduling problem, which is one of the most interesting problems in the satellite communication scheduling area. This problem is known to be NP-complete, and a couple of heuristic algorithms have been developed. In this paper, we suggest another algorithm for this problem which has the same computational complexity as the best existing one and provides much better solution quality. Extensive computational simulation results are reported.     

基于列生成的毫米波多连接链路配置调度算法

多连接技术允许用户同时建立和保持与多个小区/接入点的连接,通过网络元素之间的协调在吞吐量和可靠性方面大幅提高网络性能。针对毫米波通信中超高频段的链路中断问题,研究了多连接基于链路配置的调度算法,以提高链路调度效率,降低复杂度。首先,在系统模型中采用链路配置作为优化变量;其次,设计了多连接比例公平的调度准则;最后,提出一种基于列生成算法的链路配置调度优化算法,利用Dantzig-Wolfe分解将原问题分解为限制主问题和定价问题,并结合分支定界方法获得最优解。仿真结果表明,所提算法能够在数值上逼近全局最优,并且比现有的毫米波蜂窝网络链路调度方案增益平均提高40%以上。     

Optimal and Approximate Mobility-Assisted Opportunistic Scheduling in Cellular Networks

This paper considers the problem of scheduling multiple users in the downlink of a time-slotted cellular data network. For such a network, opportunistic scheduling algorithms improve system performance by exploiting time variations of the radio channel. We present novel optimal and approximate opportunistic scheduling algorithms that combine channel fluctuation and user mobility information in their decision rules. The algorithms modify the opportunistic scheduling framework of Liu et al., (1993) with dynamic constraints for fairness. These fairness constraints adapt according to the user mobility. The adaptation of constraints in the proposed algorithms implicitly results in giving priority to the users that are in the most favorable locations. The optimal algorithm is an offline algorithm that precomputes constraint values according to a known mobility model. The approximate algorithm is an online algorithm that relies on the future prediction of the user mobility locations in time. We show that the use of mobility information in opportunistic scheduling increases channel capacity. We also provide analytical bounds on the performance of the approximate algorithm using the fundamental inequality of Dyer et al., (1986) for linear programs. Simulation results on high data rate (HDR) illustrate the usefulness of the proposed schemes for elastic traffic and macrocell structures     

A Low Complexity Algorithm for Subcarrier-and-Bit Allocation in OFDMA-Based LTE Systems

In this paper, we propose optimum and sub-optimum resource allocation and opportunistic scheduling solutions for orthogonal frequency division multiple access (OFDMA)-based multicellular systems. The applicability, complexity, and performance of the proposed algorithms are analyzed and numerically evaluated. In the initial setup, the fractional frequency reuse (FFR) technique for inter-cell interference cancellation is applied to classify the users into two groups, namely interior and exterior users. Adaptive modulation is then employed according to the channel state information (CSI) of each user to meet the symbol error rate (SER) requirement. There then, we develop subcarrier-and-bit allocation method, which maximizes the total system throughput subject to the constraints that each user has a minimum data rate requirement. The algorithm to achieve the optimum solution requires high computational complexity which hinders it from practicability. Toward this end, we propose a suboptimum method with the complexity extensively reduced to the order of O(NK), where N and K denote the total number of subcarriers and users, respectively. Numerical results show that the proposed algorithm approaches the optimum solution, yet it enjoys the features of simplicity, dynamic cell configuration, adaptive subcarrier-and-bit allocation, and spectral efficiency.     

A joint resource optimization and adaptive modulation framework for uplink single‐carrier frequency‐division multiple access systems

In this paper, we study joint resource allocation and adaptive modulation in single‐carrier frequency‐division multiple access systems, which is adopted as the multiple access scheme for the uplink in the 3GPP Long Term Evolution standard. We formulate an adaptive modulation and sum‐cost minimization (JAMSCmin) problem. Unlike orthogonal frequency‐division multiple access, in addition to the restriction of allocating a subchannel to one user at most, the multiple subchannels allocated to a user in single‐carrier frequency‐division multiple access systems should be consecutive as well. This renders the resource allocation problem prohibitively difficult and the standard optimization tools (e.g., Lagrange dual approach widely used for orthogonal frequency‐division multiple access, etc.) cannot help towards its optimal solution. We propose a novel optimization framework for the solution of this problem that is inspired from the recently developed canonical duality theory. We first formulate the optimization problem as binary‐integer programming (BIP) problem and then transform this BIP problem into continuous space canonical dual problem that is the concave maximization problem. Based on the solution of the canonical dual problem, we derive joint resource allocation and adaptive modulation algorithm, which has polynomial time complexity. We provide conditions under which the proposed algorithm is optimal. We compare the proposed algorithm with the existing algorithms in the literature. The results show a tremendous performance gain. Copyright © 2013 John Wiley & Sons, Ltd.     

Iterative Approximate Linear Programming Decoding of LDPC Codes With Linear Complexity

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.      

毫米波通信低复杂度波束选择和用户调度算法

针对毫米波混合波束成形系统中用户调度方案复杂度过高的问题,提出两种低复杂度的波束选择和用户调度联合优化算法。混合波束成形架构使得用户调度问题面临着新的挑战,变成了模拟波束选择和用户调度的联合优化问题。考虑发送端无法获得完美信道状态信息的实用场景,采用基于固定码本的波束训练方案获取等效信道状态信息,引入调用指示函数将联合优化问题建模成非凸组合优化规划,分别以粒子群优化和贪婪算法为核心,提出两种低复杂度的次优解决方法。仿真结果表明,相较穷举搜索,所提算法能在性能和复杂度之间取得很好的折中。      

Adaptation, Coordination, and Distributed Resource Allocation in Interference-Limited Wireless Networks

A sensible design of wireless networks involves striking a good balance between an aggressive reuse of the spectral resource throughout the network and managing the resulting co-channel interference. Traditionally, this problem has been tackled using a ldquodivide and conquerrdquo approach. The latter consists in deploying the network with a static or semidynamic pattern of resource reutilization. The chosen reuse factor, while sacrificing a substantial amount of efficiency, brings the interference to a tolerable level. The resource can then be managed in each cell so as to optimize the per cell capacity using an advanced air interface design. In this paper, we focus our attention on the overall network capacity as a measure of system performance. We consider the problem of resource allocation and adaptive transmission in multicell scenarios. As a key instance, the problem of joint scheduling and power control simultaneously in multiple transmit-receive links, which employ capacity-achieving adaptive codes, is studied. In principle, the solution of such an optimization hinges on tough issues such as the computational complexity and the requirement for heavy receiver-to-transmitter feedback and, for cellular networks, cell-to-cell channel state information (CSI) signaling. We give asymptotic properties pertaining to rate-maximizing power control and scheduling in multicell networks. We then present some promising leads for substantial complexity and signaling reduction via the use of newly developed distributed and game theoretic techniques.     

Proportional Fair Space–Time Scheduling for Wireless Communications

We extend the proportional fair (PF) scheduling algorithm to systems with multiple antennas. There are$K$client users (each with a single antenna) and one base station (with$n_R$antennas). We focus on the reverse link of the system, and assume a slow-fading channel where clients are moving with pedestrian speed. Qualcomm's original PF scheduling algorithm satisfies the PF criteria only when the communication is constrained to one user at a time with no power waterfilling. However, the original PF algorithm does not generalize easily when we have$n_R$receive antennas at the base station. In this paper, we shall formulate the PF scheduling design as a convex optimization problem. One challenge is in the optimal power allocation over the multiantenna multiaccess capacity region, which is still an open problem. For practical consideration, we consider multiuser minimum mean-square error processing at the base station. To obtain first-order insight, we propose an asymptotically optimal PF scheduling solution. Using the proposed PF solution for a multiantenna base station, the system capacity is enhanced by exploiting the multiuser selection diversity, as well as the distributed multiple-input multiple-output configuration. It is found that the PF scheduler achieves a good balance between fairness and system capacity gain.     

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.     

Incremental scheduling algorithms for WDM/TDM networks with arbitrary tuning latencies

We focus on all-optical broadcast and select slotted WDM networks. Each network user is equipped with one tunable transmitter and one fixed receiver; full connectivity is achieved by tuning transmitters to all different wavelengths available in the optical spectrum. Tuning latencies are considered to be not negligible with respect to the slot time. A network controller allocates fixed size slots in a TDM/WDM frame according to requests issued by users via signalling procedures. User requests are accommodated in the frame incrementally, as soon as they are received by the network controller. Since we aim at an incremental solution, we impose a transparency constraint in the scheduling algorithm: new user requests may be accepted only without affecting existing allocations, otherwise they are refused. We propose a novel scheduling algorithm that may route some flows from source to destination through some intermediate nodes, following a multi-hop approach. A formal definition of an optimal transparent incremental scheduling algorithm is provided as an integer linear programming problem. The optimal incremental scheduling algorithm is NP-hard. Thus, a heuristic quasi-optimal scheduling algorithm is proposed, and its complexity is evaluated. Performance results show that significant benefits can be achieved with respect to traditional single-hop approaches and to other multi-hop approaches.     

Relax online resource allocation algorithms for D2D communication

Maximizing the system sumrate by sharing the resource blocks among the cellular user equipments and the D2D (device to device) pairs while maintaining the quality of service is an important research question in a D2D communication underlaying cellular networks. The problem can be optimally solved in offline by using the weighted bipartite matching algorithm. However, in long‐term evolution and beyond (4G and 5G) systems, scheduling algorithms should be very efficient where the optimal algorithm is quite complex to implement. Hence, a low complexity algorithm that returns almost the optimal solution can be an alternative to this research problem. In this paper, we propose 2 less complex stable matching–based relax online algorithms those exhibit very close to the optimal solution. Our proposed algorithms deal with fixed number of cellular user equipments and a variable number of D2D pairs those arrive in the system online. Unlike online matching algorithms, we consider that an assignment can be revoked if it improves the objective function (total system sumrate). However, we want to minimize the number of revocation (ie, the number of changes in the assignments) as a large number of changes can be expensive for the networks too. We consider various offline algorithms proposed for the same research problem as relaxed online algorithms. Through extensive simulations, we find that our proposed algorithms outperform all of the algorithms in terms of the number of changes in assignment between 2 successive allocations while maintaining the total system sumrate very close to the optimal algorithm.     

一种公平的多天线多小区联合调度算法

为了能够以较小的实现复杂度有效减少多天线蜂窝系统中的小区间干扰,同时保证系统中的用户公平性,提出一种新的多小区联合调度算法,提出的算法的复杂度远远低于最优多小区联合调度算法。该算法将系统分簇并在每个簇内按一定比例选择部分平均速率较低的用户,之后在簇内按照给定的优化目标进行联合调度。仿真结果表明：与单小区调度算法相比,提出的多小区联合调度算法可以显著增加系统平均速率,而且可以取得与单小区调度算法类似的用户公平性。