Link packing in mmWave networks

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
2
Assignments
First Claim
1. A computerimplemented method executed on a processor for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem, the method comprising:
 determining active communication links between a plurality of transmitters and a plurality of receivers, each of the communication links represented by a receiving user, a transmitting access point, a transmit beamforming vector, and a receive beamforming vector;
setting each active communication link to have any arbitrary chosen weight or priority; and
setting a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints, wherein the constraints include;
for each active communication link at least a minimum coverage is ensured;
a limit is set on a number of active communication links sharing a common TP;
a limit is set on a number of streams assigned to a TP, transmit beam pair; and
a total number of scheduled active communication links in which a TP is a transmitting node does not exceed a predefined threshold, andwherein the link quality threshold is a signaltointerferenceplusnoise ratio (SINR) threshold, the SINR given as;
2 Assignments
0 Petitions
Accused Products
Abstract
A computerimplemented method for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem is presented. The computerimplemented method includes determining active communication links between a plurality of transmitters and a plurality of receivers, setting each active communication link to have any arbitrary chosen weight or priority, and setting a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints. Detected phantom constraints are mitigated by introducing new constraints with binary coefficients and by modifying one or more existing constraints by setting a number of coefficients within the existing constraints to zero.
43 Citations
No References
TECHNIQUES TO CONTROL TRANSMIT POWER FOR A SHRED ANTENNA ARCHITECTURE  
Patent #
US 20110263214A1
Filed 06/29/2011

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

SYSTEMS FOR COMMUNICATING USING MULTIPLE FREQUENCY BANDS IN A WIRELESS NETWORK  
Patent #
US 20120243638A1
Filed 03/30/2012

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

Beam combination methods and systems for adapting communication links to varying channel conditions  
Patent #
US 8,510,433 B2
Filed 11/08/2010

Current Assignee
NEC Corporation

Sponsoring Entity
NEC Corporation

APPARATUS AND METHOD FOR CONTROL CHANNEL BEAM MANAGEMENT IN A WIRELESS SYSTEM WITH A LARGE NUMBER OF ANTENNAS  
Patent #
US 20130286960A1
Filed 03/15/2013

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

COMMUNICATION DEVICE AND COMMUNICATION METHOD USING MILLIMETERWAVE FREQUENCY BAND  
Patent #
US 20140073337A1
Filed 09/10/2013

Current Assignee
Electronics and Telecommunications Research Institute

Sponsoring Entity
Electronics and Telecommunications Research Institute

Device, system and method of discovering wireless communication devices  
Patent #
US 8,818,278 B2
Filed 06/27/2012

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

METHOD FOR ACQUIRING SYSTEM FRAME NUMBER BY TERMINAL, TERMINAL, AND MOBILE COMMUNICATION SYSTEM  
Patent #
US 20150358957A1
Filed 11/03/2014

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

INTER/INTRA RADIO ACCESS TECHNOLOGY MOBILITY AND USERPLANE SPLIT MEASUREMENT CONFIGURATION  
Patent #
US 20160057687A1
Filed 01/16/2015

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

APPARATUS, SYSTEM AND METHOD OF DYNAMIC ALLOCATION OF RADIO RESOURCES TO WIRELESS COMMUNICATION LINKS OF A PLURALITY OF TYPES  
Patent #
US 20160255613A1
Filed 12/19/2013

Current Assignee
Intel IP Corporation

Sponsoring Entity
Intel IP Corporation

LOW COMPLEXITY SCMA/LDS DETECTION SYSTEMS AND METHODS  
Patent #
US 20160254937A1
Filed 02/27/2015

Current Assignee
Huawei Technologies Co. Ltd.

Sponsoring Entity
Huawei Technologies Co. Ltd.

SIGNALING FOR MILLIMETER WAVE INTERFERENCE AND SCHEDULING  
Patent #
US 20160269087A1
Filed 08/18/2015

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

TECHNIQUES FOR BEAM SHAPING AT A MILLIMETER WAVE BASE STATION AND A WIRELESS DEVICE AND FAST ANTENNA SUBARRAY SELECTION AT A WIRELESS DEVICE  
Patent #
US 20160198474A1
Filed 08/10/2015

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

DYNAMIC MEDIUM ACCESS CONTROL SWITCHING  
Patent #
US 20160323888A1
Filed 11/25/2015

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

System and Method for MultiLevel Beamformed NonOrthogonal Multiple Access Communications  
Patent #
US 20160353424A1
Filed 05/28/2015

Current Assignee
Futurewei Technologies Incorporated

Sponsoring Entity
Futurewei Technologies Incorporated

WIRELESS COMMUNICATION DEVICE, WIRELESS COMMUNICATION METHOD, CONTROL DEVICE, AND CONTROL METHOD  
Patent #
US 20170208525A1
Filed 01/12/2017

Current Assignee
Panasonic Corporation

Sponsoring Entity
Panasonic Corporation

MULTILAYER BEAMFORMING IN MILLIMETERWAVE MULTIPLEINPUT/MULTIPLEOUTPUT SYSTEMS  
Patent #
US 20170244451A1
Filed 06/21/2016

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

SYSTEM AND METHOD OF CONNECTED MODE DISCONTINUOUS OPERATION IN BEAMFORMED SYSTEM  
Patent #
US 20170251518A1
Filed 02/24/2017

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

System and Method for Millimeter Wave Communications  
Patent #
US 20170295502A1
Filed 04/06/2016

Current Assignee
Futurewei Technologies Incorporated

Sponsoring Entity
Futurewei Technologies Incorporated

A MACROASSISTED MULTICONNECTIVITY SCHEME IN MULTIRAT CELLULAR SYSTEMS  
Patent #
US 20170303286A1
Filed 04/15/2016

Current Assignee
Hfi Innovation Inc.

Sponsoring Entity
Hfi Innovation Inc.

FACILITATING INTERFERENCE MANAGEMENT IN MULTICELL AND MULTIUSER MILLIMETER WAVE CELLULAR NETWORKS  
Patent #
US 20170311187A1
Filed 04/22/2016

Current Assignee
City University of Hong Kong

Sponsoring Entity
City University of Hong Kong

Network Architecture, Methods, and Devices for a Wireless Communications Network  
Patent #
US 20170331670A1
Filed 05/13/2016

Current Assignee
Telefonaktiebolaget LM Ericsson

Sponsoring Entity
Telefonaktiebolaget LM Ericsson

Network Architecture, Methods, and Devices for a Wireless Communications Network  
Patent #
US 20170331577A1
Filed 05/13/2016

Current Assignee
Telefonaktiebolaget LM Ericsson

Sponsoring Entity
Telefonaktiebolaget LM Ericsson

Method and Communication Device for Performing Link Adaptation  
Patent #
US 20170332433A1
Filed 12/05/2014

Current Assignee
Telefonaktiebolaget LM Ericsson

Sponsoring Entity
Telefonaktiebolaget LM Ericsson

ACCESS CONTROL METHOD AND APPARATUS FOR USE IN MOBILE COMMUNICATION  
Patent #
US 20180020382A1
Filed 07/13/2017

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

NONUNIFORM TRANSMISSION OF SYNCHRONIZATION SIGNALS  
Patent #
US 20180054790A1
Filed 03/17/2017

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

RADAR DEVICE  
Patent #
US 20180074181A1
Filed 09/04/2015

Current Assignee
Panasonic Intellectual Property Management Co. Ltd.

Sponsoring Entity
Panasonic Intellectual Property Management Co. Ltd.

Link Packing in mmWave Networks  
Patent #
US 20180084600A1
Filed 08/16/2017

Current Assignee
NEC Corporation

Sponsoring Entity
NEC Corporation

UplinkAssisted Mobility Procedure In Millimeter Wave Communication Systems  
Patent #
US 20180132158A1
Filed 11/01/2017

Current Assignee
MediaTek Inc.

Sponsoring Entity
MediaTek Inc.

INDICATING A RANGE OF BEAM CORRESPONDENCE IN A WIRELESS NODE  
Patent #
US 20180132252A1
Filed 07/31/2017

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

POWER CONTROL IN MILLIMETERWAVE CONNECTION INITIATION  
Patent #
US 20180176869A1
Filed 12/19/2016

Current Assignee
Intel Corporation

Sponsoring Entity
Intel Corporation

POWERADAPTIVE SIDELINK DATA TRANSMISSIONS  
Patent #
US 20180176747A1
Filed 08/11/2017

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

METHOD OF SELECTING PLURALITY OF SETS OF OPTIMAL BEAM PAIRS IN WIRELESS COMMUNICATION SYSTEM  
Patent #
US 20180205435A1
Filed 01/16/2018

Current Assignee
Samsung Electronics Co. Ltd.

Sponsoring Entity
Samsung Electronics Co. Ltd.

MANAGING ANALOG BEAMS IN MMWAVE NETWORKS  
Patent #
US 20180213415A1
Filed 01/18/2018

Current Assignee
NEC Corporation

Sponsoring Entity
NEC Corporation

Distributed Phased Arrays Based MIMO (DPAMIMO) for Next Generation Wireless User Equipment Hardware Design and Method  
Patent #
US 20180219587A1
Filed 01/30/2018

Current Assignee
Wei Xu, Yiming Huo, Xiaodai Dong

Sponsoring Entity
Wei Xu, Yiming Huo, Xiaodai Dong

BEAMFORMING IN A MUMIMO WIRELESS COMMUNICATION SYSTEM WITH RELAYS  
Patent #
US 20180234157A1
Filed 01/28/2018

Current Assignee
RF DSP Inc.

Sponsoring Entity
RF DSP Inc.

ELECTRONIC APPARATUS AND METHOD IN WIRELESS COMMUNICATION SYSTEM  
Patent #
US 20180262918A1
Filed 12/14/2017

Current Assignee
Sony Corporation

Sponsoring Entity
Sony Corporation

MOBILE COMMUNICATION SYSTEM USING SUBCODING TECHNIQUES  
Patent #
US 20180270016A1
Filed 08/23/2016

Current Assignee
Intel IP Corporation

Sponsoring Entity
Intel IP Corporation

NULL RESOURCE ELEMENTS FOR DYNAMIC AND BURSTY INTERCELL INTERFERENCE MEASUREMENT IN NEW RADIO  
Patent #
US 20180359069A1
Filed 05/31/2018

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

METHOD AND SYSTEM FOR LIMITING COLLISIONS IN CELLULAR NETWORKS  
Patent #
US 20180367999A1
Filed 12/23/2015

Current Assignee
Telecom Italia SPA

Sponsoring Entity
Telecom Italia SPA

Methods for maintaining lineofsight communications  
Patent #
US 10,165,426 B1
Filed 06/22/2017

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

System and Method for Adaptive Beamforming Communication  
Patent #
US 20190013847A1
Filed 07/07/2017

Current Assignee
Mitsubishi Electric Research Laboratories

Sponsoring Entity
Mitsubishi Electric Research Laboratories

BEAM INDICATION DURING RANDOM ACCESS CHANNEL (RACH) PROCEDURE  
Patent #
US 20190029049A1
Filed 07/17/2018

Current Assignee
Qualcomm Inc.

Sponsoring Entity
Qualcomm Inc.

ADAPTIVE NETWORK DISCOVERY SIGNALING  
Patent #
US 20190104465A1
Filed 04/03/2018

Current Assignee
Sony Corporation

Sponsoring Entity
Sony Corporation

18 Claims
 1. A computerimplemented method executed on a processor for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem, the method comprising:
determining active communication links between a plurality of transmitters and a plurality of receivers, each of the communication links represented by a receiving user, a transmitting access point, a transmit beamforming vector, and a receive beamforming vector; setting each active communication link to have any arbitrary chosen weight or priority; and setting a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints, wherein the constraints include; for each active communication link at least a minimum coverage is ensured; a limit is set on a number of active communication links sharing a common TP; a limit is set on a number of streams assigned to a TP, transmit beam pair; and a total number of scheduled active communication links in which a TP is a transmitting node does not exceed a predefined threshold, and wherein the link quality threshold is a signaltointerferenceplusnoise ratio (SINR) threshold, the SINR given as;  View Dependent Claims (2, 3, 4, 5, 6, 7)
 8. A system for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem, the system comprising:
a memory; and a processor in communication with the memory, wherein the processor is configured to; determine active communication links between a plurality of transmitters and a plurality of receivers, each of the communication links represented by a receiving user, a transmitting access point, a transmit beamforming vector, and a receive beamforming vector; set each active communication link to have any arbitrary chosen weight or priority; and set a minimum link quality threshold for each active communication link and subject each active communication link to constraints, wherein the constraints include; for each active communication link at least a minimum coverage is ensured; a limit is set on a number of active communication links sharing a common TP; a limit is set on a number of streams assigned to a TP, transmit beam pair; and a total number of scheduled active communication links in which a TP is a transmitting node does not exceed a predefined threshold, and wherein the link quality threshold is a signaltointerferenceplusnoise ratio (SINR) threshold, the SINR given as;  View Dependent Claims (9, 10, 11, 12, 13, 14)
 15. A nontransitory computerreadable storage medium comprising a computerreadable program for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem, wherein the computerreadable program when executed on a computer causes the computer to perform the steps of:
determining active communication links between a plurality of transmitters and a plurality of receivers, each of the communication links represented by a receiving user, a transmitting access point, a transmit beamforming vector, and a receive beamforming vector; setting each active communication link to have any arbitrary chosen weight or priority; and setting a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints, wherein the constraints include; for each active communication link at least a minimum coverage is ensured; a limit is set on a number of active communication links sharing a common TP; a limit is set on a number of streams assigned to a TP, transmit beam pair; and a total number of scheduled active communication links in which a TP is a transmitting node does not exceed a predefined threshold, wherein the link quality threshold is a signaltointerferenceplusnoise ratio (SINR) threshold, the SINR given as;  View Dependent Claims (16, 17, 18)
1 Specification
This application claims priority to Provisional Application No. 62/395,561, filed on Sep. 16, 2016, incorporated herein by reference in its entirety.
The present invention relates to millimeter wave (mmWave) communication technology and, more particularly, to link packing in mmWave networks.
Millimeterwave communication technology refers to a technology using an electromagnetic wave whose wavelength is one centimeter to one millimeter (corresponding to a frequency range of 30 GHz to 300 GHz) to communicate. Currently, civil millimeter wave communication technology mainly uses a spectrum whose frequency band is about 60 GHz. The biggest advantage of 60 GHz technology is very wide transmission bandwidth and in a vicinity of 60 GHz it can provide up to 5 GHz transmission bandwidth, where an occupied working frequency can be used without authorization. Because the electromagnetic spectrum is a strong absorption peak close to the 60 GHz range, electromagnetic wave propagation decay in this frequency range is very large, and thus a typical transmission distance of the 60 GHz communication technology is no more than 10 meters. This electromagnetic propagation property not only defines that the application scenario of the 60 GHz communication technology is primarily an indoor environment, but also makes spatial multiplexing become possible.
A computerimplemented method for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem is presented. The method includes determining active communication links between a plurality of transmitters and receivers, setting each active communication link to have any arbitrary chosen weight or priority, and setting a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints. Detected phantom constraints are mitigated by introducing new constraints with binary coefficients and by modifying one or more existing constraints by setting a number of coefficients within the existing constraints to zero.
A system for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem is presented. The system includes a memory and a processor in communication with the memory, wherein the processor is configured to determine active communication links between a plurality of transmitters and receivers, set each active communication link to have any arbitrary chosen weight or priority, and set a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints. Detected phantom constraints are mitigated by introducing new constraints with binary coefficients and by modifying one or more existing constraints by setting a number of coefficients within the existing constraints to zero.
A nontransitory computerreadable storage medium including a computerreadable program for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem is presented, wherein the computerreadable program when executed on a computer causes the computer to perform the steps of determining active communication links between a plurality of transmitters and receivers, setting each active communication link to have any arbitrary chosen weight or priority, and setting a minimum link quality threshold for each active communication link and subjecting each active communication link to constraints. Detected phantom constraints are mitigated by introducing new constraints with binary coefficients and by modifying one or more existing constraints by setting a number of coefficients within the existing constraints to zero.
These and other features and advantages will become apparent from the following detailed description of illustrative embodiments thereof, which is to be read in connection with the accompanying drawings.
The disclosure will provide details in the following description of preferred embodiments with reference to the following figures wherein:
In the exemplary embodiments of the present invention, link packing for millimeter wave (mmWave) networks is presented. Each link is a 4tuple determined by a choice of receiving user, transmitting access point, transmit beamforming vector, and receive beamforming vector. The exemplary embodiments of the present invention seek to optimize a weighted sum over active communication links, where each communication link is permitted to have any arbitrarily chosen weight or priority and where an active communication link satisfies a minimum link quality threshold. The formulation models a scenario where blockages due to arbitrarily placed obstacles in a propagation environment are allowed to occur, where it is noted that mmWave transmissions are susceptible to blockages. This is a departure from classical link packing problems where only a signal attenuation based on propagation distance is modeled. The exemplary embodiments of the present invention exploit a sparsity induced by a directional nature of propagation due to beamforming and significant signal attenuation due to high path penetration and reflection losses. The exemplary embodiments of the present invention exploit this sparsity to express link quality constraints as packing constraints.
In the exemplary embodiments of the present invention, a general link packing problem for millimeter wave (mmWave) networks is formulated by maximizing a weighted sum of active communication links, where a communication link is formed by receiving user information, transmitting nodes or points (TP), and transmit and receive beamformers. All active communication links meet a minimum signaltointerferenceplusnoise ratio (SINR) threshold and are subject to other constraints.
An imposed practical constraint can include a “one datastream” per scheduled user constraint. Justification is that a number of radiofrequency (RF) chains at any user is one. Another imposed practical constraint can include dimensionality constraints where there is a limit on a number of active links sharing the same TP and there is a limit on a number of streams assigned to the same (TP, transmit beam) pair. This is accomplished by exploiting sparsity in mmWave networks by manipulating highly directional transmission and by manipulating limited diffraction, high path penetration, and reflection losses. A feature of the formulated problem involves allowing for arbitrary blockages and not making assumptions on channel gains in order to design deterministic lowcomplexity algorithms with performance guarantees.
In the exemplary embodiments of the present invention, an iterative algorithm or method is constructed that considers an alternate formulation which is a column sparse binary packing problem. The method outperforms other heuristics and guarantees a constant factor approximation for input instances that are likely to occur in mmWave networks. The exemplary embodiments of the present invention can be used to improve spectral efficiency by allowing more communication links to simultaneously coexist and can be used to improve revenue by determining a large set of high priority communication links that can simultaneously coexist.
A plurality of users (UE1, UE2, UE3, UE4) are located within a mmWave network or propagation environment. Transmit and receive beams (Beam 1, Beam 2, Beam 3) are transmitted between the plurality of users and transmission points (TP1, TP2, TP3). A blockage may be present within the mmWave network such that it blocks beams 1, 2, 3 from being received by the user (UE4).
The mmWave system can be described as follows: Let U be a set of users and B denote a set of transmission points (TPs). For simplicity, it is assumed that each user is equipped with Nr receive antennas and each TP is equipped with Nt transmit antennas. Let W and V denote the codebook of transmit analog beamforming vectors used by each TP and a codebook of analog receive beamforming vectors used by each user, respectively. Each vector in W is a Nt×1 unit norm vector with constantmagnitude elements, whereas each vector in V is a Nr×1 unit norm vector with constantmagnitude elements.
Let x_{u,v,b,w }be an indicator variable that is one if user u∈ is scheduled to receive data using receive beam vector v∈ whereas the data for that user is transmitted by b∈B using transmit beam vector w∈, and zero otherwise.
Henceforth the following 4tuple is used:
(u,v,b,w),∀u∈,b∈B,v∈,w∈,_{t }
This represents the aforementioned link, with θ_{u,v,b,w}>0 denoting its weight or priority. Thus, x_{u,v,b,w}=1 implies that the communication link is active, while x_{u,v,b,w}=0 implies otherwise.
The corresponding link SINR, sinr(u, v, b, w), is defined as:
where P>0 is a transmit power per beam and H_{u,b}, ∀ u∈, b∈B denotes a channel matrix modeling a propagation path from TP b to user u.
The link packing problem is now posed as follows:
Note that the objective in (2) denotes a sum of active communication link weights. The four constraints depicted in (2) are explained as follows:
The first constraint requires that SINRs of all active communication links be at least β, where β is an SINR threshold. This is a constraint of this problem that for each active communication link at least a certain minimum rate (coverage) is ensured.
The second constraint enforces that each user can be scheduled in at most one active communication link. This constraint models a typical scenario where each user has only one radiofrequency (RF) chain due to, e.g., cost constraints.
The third constraint imposes that any (TP, transmit beam) pair, (b, w), can be scheduled in at most one active communication link. This constraint is based on mmWave directional propagation conditions. Indeed, in mmWave systems, each transmit beam is typically matched to one receive beam at a user, which yields a significantly higher receive signal strength compared to other choices of receive beamformers. Then, in such a scenario, since the receive beamformer for all data streams coscheduled (superposed) on a common transmit beam will be identical, linear processing at the user is not sufficient to overcome a high path loss plus an interference from other coscheduled streams. Thus, superposing two or more data streams on a same or common transmit beam requires served users to perform successive interference cancellation, which in turn necessitates sophisticated processing by them as well as signaling (from the TPs to each user) of multiple relevant parameters (such as coding rates, modulations, CRC bits) pertaining to other coscheduled users.
Another constraint requires that a total number of scheduled links in which TP b is a transmitting node cannot exceed a given Lb≥1. This constraint can address a power budget as well as a number of RF chains at each TP. An identical transmit power per beam is assumed. This is mainly for convenience and results derived can be generalized.
A direct approach for solving (2) is thus considered.
SINR constraints can be rewritten as:
Upon doing so, (2) can be transformed to a binary integer program with a linear objective but with bilinear constraints that are also mixed, since coefficients in the above constraints are both positive and negative. Further, even upon relaxing the binary value constraints, a nonconvex optimization problem is obtained.
A first observation is that without loss of optimality, all links for which the SINR threshold β cannot be achieved, are discarded even when no other link is scheduled, e.g., each link (u, v, b, w) such that P∥v^{†}H_{u,b}w∥^{2}<β can be safely discarded.
The ground set including all links that remain is denoted by Ψ (e.g., that when active alone can at least equal the SINR threshold).
Further, let x=[x_{u,v,b,w}]_{∀(u,v,b,w)∈Ψ} denote a vector of indicator variables of all links in Ψ and let θ denote a vector of all their weights. Next, the last three constraints in (2) are collected and represented as the following linear packing constraints (which shall be referred to as dimensionality constraints),
Dx≤1 (3)
Proceeding similarly, it can be deduced that for any link in (u, v, b, w)∈Ψ to be active, it needs to satisfy:
A Ψ×Ψ matrix C is defined with one row for each link in Ψ such that the row corresponding to the link (u, v, b, w) has coefficient c^{u,v,b,w}=[c_{u′,v′,b′,w′}^{u,v,b,w}]_{∀(u′,v′,b′,w′)∈Ψ}. Therefore, the condition in (4) for a link to be active can be written as c^{u,v,b,w}x≤1.
An alternate formulation can now be offered:
The following result reveals the structure in (5) and is a conservative formulation.
In a first proposition, the formulation in (5) is a linear binary integer packing problem and yields a lower bound to (2). For mmWave networks, (5) is also a column sparse packing problem.
The proof is given as: It is seen that (5) has a linear objective and linear constraints in which all coefficients are nonnegative (hence linear packing constraints). Note that (5) enforces an SINR constraint for each link in (u, v, b, w)∈Ψ. This SINR constraint is indeed required when the communication link is active, e.g., when x_{u,v,b,w}=1. However, when the communication link is set to be inactive, x_{u,v,b,w}=0, the formulation in (5) still forces satisfaction of an unnecessary constraint c^{u,v,b,w}x≤1. Consequently, a feasible region of (5) is subsumed by the one in (2), which implies that (5) yields a lower bound to (2).
Notice that each link (u, v, b, w)∈Ψ appears (has a strictly positive coefficient) in only three constraints in D. More importantly, in mmWave networks each link (u, v, b, w)∈Ψ appears in only a few constraints in C as well. The latter assertion holds because each user in a mmWave network can in general receive a sufficiently strong signal strength from only a very few (TP, transmit beam) combinations and for only the appropriately matched receive beamformers. Thus, a link (u, v, b, w)∈Ψ is present as an interferer in only a few SINR constraints involving other users.
Henceforth, unnecessary SINR constraints in (5) due to which optimal solutions of (2) are precluded, are referred to as phantom constraints. In particular, an SINR constraint for a link (u, v, b, w)∈Ψ for which c^{u,v,b,w}x>1 for which for good choices of x that have x_{u,v,b,w}=0, are classified as phantom constraints. Note that these good choices are all feasible with respect to (2) and include each optimal solution to (2) which has the link (u, v, b, w)∈Ψ be inactive. In other words, the SINR constraint for a link (u, v, b, w)∈Ψ in (5) is a phantom constraint if it precludes optimal solutions to (2) in which (u, v, b, w) is inactive. Hence, for any such optimal solution, {circumflex over (x)}, a violation c^{u,v,b,w}{circumflex over (x)}>1 is presented even though {circumflex over (x)}_{u,v,b,w}=0.
There is no apriori access to the optimal solution set for (2). As a result, the set of good choices include nonoptimal solutions as well. Thus, a constraint is deemed to be phantom or not based on necessary conditions. The approach in the following is to resolve as many phantom constraints in (5) as possible, while at the same time retaining the integer packing form of (5).
Towards this end, two steps are offered to address or mitigate the problem of phantom constraints.
This is performed by initializing: C˜=C and D˜=D.
Consider a constraint for link (u, v, b, w)∈Ψ enforced by a row {tilde over (c)}^{u,v,b,w }in {tilde over (C)}. Since each user can be present in at most one active link (a constraint which is enforced by a row in {tilde over (D)}) the following can be set {tilde over (c)}_{u′,v′,b′,w′}^{u,v,b,w}=0, ∀(u′, v′, b′, w′)≠(u, v, b, w):u′=u.
In an analogous manner, since each (TP, transmit beam) pair can be present in at most one active link, a constraint that is also enforced by another row in {tilde over (D)}, the following can be set:
{tilde over (c)}_{u′,v′,b′,w′}^{u,v,b,w}=0,∀(u′,v′,b′,w′)≠(u,v,b,w):(b′,w′)=(b,w).
Addressing TypeI incompatibility constraints is now described. After performing the aforementioned procedure, consider the 3 constraints for link (u, v, b, w)∈Ψ enforced by a row {tilde over (c)}^{u,v,b,w }in {tilde over (C)}.
Suppose there is another link (u′, v′, b′, w′)∈Ψ such that {tilde over (c)}_{u,v,b,w}^{u,v,b,w}+{tilde over (c)}_{u′,v′,b′,w′}^{u,v,b,w}>1.
Then, clearly the links (u, v, b, w), (u′, v′, b′, w′)∈Ψ cannot both be active. Note also that the user and receive beam u′, v′ in that other communication link are immaterial since interference seen by the link of interest is invariant to them, e.g., the coefficients {tilde over (c)}_{u″,v″,b′,w′}^{u,v,b,w }for all u″, v″:(u″,v″,b′,w′)∈Ψ are identical.
Thus, without loss of optimality, a constraint x_{u,v,b,w}+Σ_{(u″,v″,b′,w′∈Ψ\(u,v,b,w)}^{u″∈u,v″∈v }x_{u″,v″,b′,w′}≤1 can be introduced as a row in the matrix {tilde over (D)}.
Note that in formulating this constraint, the pair (b′, w′) can itself be present in at most one active link. Simultaneously, the following is set {tilde over (c)}_{u″,v″,b′,w′}^{u,v,b,w}=0, ∀(u″,v″,b′, w′)∈Ψ\(u, v, b, w). Moreover, the following is set
To summarize, without loss of optimality, a constraint with binary coefficients in {tilde over (D)} is first introduced that enforces at most one among a set of mutually incompatible links that can be chosen. Then the contribution is removed from any such link to the SINR constraint of any other incompatible link.
Next, after obtaining the matrices {tilde over (C)}, {tilde over (D)} in hand, the process refers to the constraints enforced by {tilde over (C)} as SINR constraints and those enforced by {tilde over (D)} as the expanded dimensionality constraints.
The following problem is now posed:
In a second proposition, the formulation in (6) is a linear binary integer packing problem that subsumes a feasible region of (5) and yields a lower bound to (2). For mmWave networks (6) is also a column sparse packing problem.
The proof is given as: Note that both the steps performed to obtain matrices {tilde over (C)} and {tilde over (D)} ensure that a feasibility with respect to (2) is maintained. Indeed, the expanded dimensionality constraints enforced using {tilde over (D)} by themselves do not alter the feasible region of (2). However, the SINR constraints in {tilde over (C)} can still include phantom constraints. Nevertheless, by setting some of the coefficients in these SINR constraints to be zero, the problem of phantom constraints is mitigated and the feasible region compared to (5) is expanded. Next, conditions under which (2) and (6) are equivalent are obtained and an efficient approximation method is provided for the problem in (6).
Regarding certificate of optimality, assume that any two formulations are equivalent if their respective optimal objective values are identical. Thus, if at least one optimal solution of (2) is feasible (and hence optimal) for (6), (2) and (6) are deemed equivalent. To derive conditions under which (2) and (6) are equivalent, let Γ^{u,v,b,w}=θ^{T}{tilde over (x)}, where {tilde over (x)} is a feasible solution to (2) with {tilde over (x)}_{u,v,b,w}=0 (that is obtained using any method at hand).
Examples of such methods are detailed below.
Note that Γ^{u,v,b,w}=0, can always be set if a solution is not at hand.
In a third proposition, the formulations in (6) and (2) are equivalent when the following conditions hold.
For every communication link (u, v, b, w)∈Ψ, the following is derived:
The proof is given as: consider any link (u, v, b, w)∈Ψ and note that the condition in (7) can be checked by solving a linear program. To show that the condition in (7) is sufficient for the link SINR constraint to not be a phantom constraint, it is assumed that (7) is satisfied. Then, any optimal solution of (2), {circumflex over (x)}, which has link (u, v, b, w)∈Ψ to be inactive, e.g., x_{u,v,b,w}=0, cannot be precluded by SINR constraint in {tilde over (C)} corresponding to link (u, v, b, w)∈Ψ. This is because {circumflex over (x)} is a feasible solution for maximization in (7), from which it can be deduced that {tilde over (c)}^{u,v,b,w}{circumflex over (x)}≤1. Since this holds for all links in Ψ, it can be deduced that the proposition holds true.
Note that while the conditions in (7) are checkable in polynomial time, it is of interest to have conditions that are simpler to check. Towards this end, for each link (u, v, b, w)∈Ψ a row vector,
Let x_{G}^{u,v,b,w }denote a vector obtained using a classical greedy method to suboptimally solve the maximization problem in (8). Further, let sum−top−n{.} denote the operator, which returns a sum of the first n elements with the n largest magnitudes in an input nonnegative sequence. The following result is offered that outlines readily checkable sufficiency conditions based on the one in (8).
In a fourth proposition, the set of all links in Ψ that satisfy the dimensionality constraints in (8) (or equivalently all binary valued vectors x:Dx≤1) can be expressed as an intersection of three partition matroid constraints. Thus, maximization in (8) is maximization of a modular function subject to three partition matroid constraints.
Consequently, a simple sufficient condition for (6) and (2) to be equivalent is given by:
Another, sufficient condition for (6) and (2) to be equivalent is given by:
Note that there are at least three ways in which the ground set of all links Ψ can be partitioned into nonoverlapping subsets. The first one partitions Ψ based on distinct users, the second one based on distinct (TP, transmit beam) pairs, and the third one based on distinct TPs. The three types of constraints imposed by D consider these three partitions, respectively, and impose limits on cardinalities of subsets in those partitions. Thus, each type constraint imposed by D is a partition matroid constraint, and hence maximization in (8) is maximization of a modular function subject to three partition matroid constraints.
It can now be deduced that (9) is true since the classical greedy method guarantees a 1=3 approximation factor for maximization in (8). Finally, (10) is true since each one of the three terms A_{1}^{u,v,b,w}, A_{2}^{u,v,b,w}, A_{3}^{u,v,b,w }is an upper bound to the maximization in (8) since it is obtained by solving the maximization problem after dropping two out of the three types of constraints.
The exemplary embodiments of the present invention propose an efficient iterative method to solve (6). In each iteration, this method solves a column sparse integer packing problem, over a ground set {hacek over (Ψ)}, in order to add to a set of chosen links , at hand. In particular, is a set of all communication links that have been classified active so far and the problem of interest in each iteration is given by,
In a first iteration, the following is set: {hacek over (Ψ)}=Ψ, =ϕ (where φ denotes the empty set), with Č={tilde over (C)}, Ď={tilde over (D)}, =1 & ď=1, where {tilde over (C)}, {tilde over (D)} are defined as in (6). After obtaining a solution {hacek over (x)} to (11), is added to all links that have been classified as active in {hacek over (x)}. Further, the following is updated, ľ→ľ−Č{hacek over (x)} and ď→ď−Ď{hacek over (x)}. Then, the links selected in {hacek over (x)} are removed from {hacek over (Ψ)} and the corresponding columns are removed from matrices Č, Ď. In addition, the following two operations are performed before proceeding to the next iteration:
In a pruning step, any link in (u, v, b, w)∈{hacek over (Ψ)} that upon being set active violates either the SINR constraints enforced by Č, ľ for any chosen link in or itself, or violates the constraints enforced by Ď, ď, is expurgated from {hacek over (Ψ)}. In particular, let {hacek over (y)} be an {hacek over (Ψ)}×1 vector that is zero everywhere but 1 in the position corresponding to link of interest (u, v, b, w).
Then, if the following is true:
č^{u′,v′,b′,w′}{hacek over (y)}>ľ^{u′,v′,b′,w′} for any(u′,v′,b′,w′)∈,
Or if the following is true:
č^{u,v,b,w}{hacek over (y)}>ľ^{u,v,b,w},
Or if any constraint in the following equation is violated:
Ď{hacek over (y)}≤ď,
Then the link of interest is removed from {hacek over (Ψ)}. The underlying reasoning is that such a link cannot be selected (given that those in have been selected) while retaining feasibility.
TypeI incompatibility constraints are addressed as follows: This step is performed after replacing Ψ with {hacek over (Ψ)} and {tilde over (C)}, {tilde over (D)} with Č, Ď, respectively. In addition, for any link of interest (u, v, b, w)∈{hacek over (Ψ)}, another link (u′, v′, b′, w′)∈{hacek over (Ψ)} is now deemed incompatible if:
č_{u,v,b,w}^{u,v,b,w}+c_{u′,v′,b′,w′}^{u,v,b,w}>ľ^{u,v,b,w}.
The aforementioned procedure is summarized below. Before commenting on the approximation guarantee of the method, procedures to solve (11) in each iteration are presented. Note that since (11) is a linear binary integer packing problem, there exist approximation methods that offer guarantees which scale inversely with a columnsparsity level. These methods involve solving an LP relaxation of (11) followed by either deterministic oblivious rounding or randomized oblivious rounding. The following optimality result holds for the method presented above.
The method includes a polynomial time algorithm that is monotonic across all iterations. Further, for all input instances for which an optimality certificate can be asserted, the methods offer a Ω(1/L^{sparse}) guarantee with respect to (2), where L^{sparse }is the worstcase columnsparsity in (6) over all such instances. It is noted that LP rounding followed by greedy oblivious rounding yields good solutions to (11).
In this section, a refinement to (6) is presented, which seeks to narrow a gap between (6) and (2) by further mitigating phantom constraints. Clearly, this stage should not be applied if it is found that any one of the conditions in (7) or those in Proposition 4 are satisfied. The refinement described is along the lines of the one used to address TypeI incompatibility constraints and is referred to as addressing TypeII incompatibility constraints.
In particular, the process starts from the formulation in (6) with matrices {tilde over (C)}, {tilde over (D)} in hand. Then, each row is considered as follows: {tilde over (c)}^{u,v,b,w }or {tilde over (C)}.
It is then determined whether two distinct (TP, transmit beam) pairs exist, (b′, w′), (b″, w″), such that the following condition holds:
{tilde over (c)}_{u,v,b,w}^{u,v,b,w}+{tilde over (c)}_{u′,v′,b′,w′}^{u,v,b,w}+c_{u″,v″,b″,w″}^{u,v,b,w}>1, (12)
Recall that {tilde over (c)}_{u′,v′,b′,w′}^{u,v,b,w }and {tilde over (c)}_{u″,v″,b″,w″}^{u,v,b,w }are identical, respectively, for all choices of user and receive beams (u′, v′) and (u″, v″), such that the corresponding 4tuples (links) are in Ψ.
Now, if (12) holds, then this can be deduced from the two distinct (TP, transmit beam) pairs, (b′, w′), (b″, w″), where at most one can be present in the set of active links, when the link (u, v, b, w) is chosen to be active.
Consequently, the following constraint is added as a row in the matrix {tilde over (D)}.
In addition, row {tilde over (c)}^{u,v,b,w }of {tilde over (C)} can be split into two rows. The first row is identical to {tilde over (c)}^{u,v,b,w }except that all coefficients {tilde over (c)}_{u′,v′,b′,w′}^{u,v,b,w }that correspond to links in Ψ whose (TP, transmit beam) pair is (b′, w′) are set to zero. Similarly the second of the two rows is identical to {tilde over (c)}^{u,v,b,w }except that here all coefficients {tilde over (c)}_{u″,v″,b″,w″}^{u,v,b,w }that correspond to links in Ψ whose (TP, transmit beam) pair is (b″, w″) are set to zero. The reasoning used here is that since only one of the two pairs can be present in an active link when the link (u, v, b, w) is active, the SINR constraint can be split into two constraints, each of which accounts for interference from only one of those two (TP, transmit beam) pairs.
Using the matrices {tilde over (C)}, {tilde over (D)} obtained after addressing the TypeII incompatibility constraints, the process can proceed exactly as before by formulating the problem in (6).
Note that since a feasible region has been expanded (while maintaining feasibility with respect to (2)), the conditions in (7) (or those in Proposition 4) are more likely to be satisfied. Finally, the following result is offered to compute an upper bound to the original problem in (2).
In a fifth proposition, an upper bound to (2) can be determined by solving the following LP:
Further, if any of the sufficient conditions in (7) or in Proposition 4 are satisfied, then an upper bound to (2) can be determined by solving the following LP:
A tighter upper bound can be obtained if the TypeII incompatibility constraints are addressed as well.
At block 201, transmit, via a plurality of transmitters, transmit beams.
At block 203, receive, via a plurality of receivers, receive beams.
At block 205, determine active communication links between the plurality of transmitters and receivers.
At block 207, set each active communication link to have any arbitrary chosen weight or priority.
At block 209, set a minimum link quality threshold for each active communication link.
The processing system includes at least one processor (CPU) 204 operatively coupled to other components via a system bus 202. A cache 206, a Read Only Memory (ROM) 208, a Random Access Memory (RAM) 210, an input/output (I/O) adapter 220, a network adapter 230, a user interface adapter 240, and a display adapter 250, are operatively coupled to the system bus 202. Additionally, mmWave network 201 and block 303 for maximizing a weighted sum of active communication links are operatively coupled to the system bus 202.
A storage device 222 is operatively coupled to system bus 202 by the I/O adapter 220. The storage device 222 can be any of a disk storage device (e.g., a magnetic or optical disk storage device), a solid state magnetic device, and so forth.
A transceiver 232 is operatively coupled to system bus 202 by network adapter 230.
User input devices 242 are operatively coupled to system bus 202 by user interface adapter 240. The user input devices 242 can be any of a keyboard, a mouse, a keypad, an image capture device, a motion sensing device, a microphone, a device incorporating the functionality of at least two of the preceding devices, and so forth. Of course, other types of input devices can also be used, while maintaining the spirit of the present invention. The user input devices 242 can be the same type of user input device or different types of user input devices. The user input devices 242 are used to input and output information to and from the processing system.
A display device 252 is operatively coupled to system bus 202 by display adapter 250.
Of course, the mmWave network processing system may also include other elements (not shown), as readily contemplated by one of skill in the art, as well as omit certain elements. For example, various other input devices and/or output devices can be included in the system, depending upon the particular implementation of the same, as readily understood by one of ordinary skill in the art. For example, various types of wireless and/or wired input and/or output devices can be used. Moreover, additional processors, controllers, memories, and so forth, in various configurations can also be utilized as readily appreciated by one of ordinary skill in the art. These and other variations of the mmWave network processing system are readily contemplated by one of ordinary skill in the art given the teachings of the present invention provided herein.
As will be appreciated by one skilled in the art, aspects of the present invention may be embodied as a system, method or computer program product. Accordingly, aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, microcode, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module” or “system.” Furthermore, aspects of the present invention may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.
Any combination of one or more computer readable medium(s) may be utilized. The computer readable medium may be a computer readable signal medium or a computer readable storage medium. A computer readable storage medium may be, for example, but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a nonexhaustive list) of the computer readable storage medium would include the following: an electrical connection having one or more wires, a portable computer diskette, a hard disk, a random access memory (RAM), a readonly memory (ROM), an erasable programmable readonly memory (EPROM or Flash memory), an optical fiber, a portable compact disc readonly memory (CDROM), an optical data storage device, a magnetic data storage device, or any suitable combination of the foregoing. In the context of this document, a computer readable storage medium may be any tangible medium that can include, or store a program for use by or in connection with an instruction execution system, apparatus, or device.
A computer readable signal medium may include a propagated data signal with computer readable program code embodied therein, for example, in baseband or as part of a carrier wave. Such a propagated signal may take any of a variety of forms, including, but not limited to, electromagnetic, optical, or any suitable combination thereof. A computer readable signal medium may be any computer readable medium that is not a computer readable storage medium and that can communicate, propagate, or transport a program for use by or in connection with an instruction execution system, apparatus, or device.
Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.
Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including an object oriented programming language such as Java, Smalltalk, C++ or the like and conventional procedural programming languages, such as the “C” programming language or similar programming languages. The program code may execute entirely on the user'"'"'s computer, partly on the user'"'"'s computer, as a standalone software package, partly on the user'"'"'s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user'"'"'s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).
Aspects of the present invention are described below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the present invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks or modules.
These computer program instructions may also be stored in a computer readable medium that can direct a computer, other programmable data processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer readable medium produce an article of manufacture including instructions which implement the function/act specified in the flowchart and/or block diagram block or blocks or modules.
The computer program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus or other devices to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks or modules.
It is to be appreciated that the term “processor” as used herein is intended to include any processing device, such as, for example, one that includes a CPU (central processing unit) and/or other processing circuitry. It is also to be understood that the term “processor” may refer to more than one processing device and that various elements associated with a processing device may be shared by other processing devices.
The term “memory” as used herein is intended to include memory associated with a processor or CPU, such as, for example, RAM, ROM, a fixed memory device (e.g., hard drive), a removable memory device (e.g., diskette), flash memory, etc. Such memory may be considered a computer readable storage medium.
In addition, the phrase “input/output devices” or “I/O devices” as used herein is intended to include, for example, one or more input devices (e.g., keyboard, mouse, scanner, etc.) for entering data to the processing unit, and/or one or more output devices (e.g., speaker, display, printer, etc.) for presenting results associated with the processing unit.
The foregoing is to be understood as being in every respect illustrative and exemplary, but not restrictive, and the scope of the invention disclosed herein is not to be determined from the Detailed Description, but rather from the claims as interpreted according to the full breadth permitted by the patent laws. It is to be understood that the embodiments shown and described herein are only illustrative of the principles of the present invention and that those skilled in the art may implement various modifications without departing from the scope and spirit of the invention. Those skilled in the art could implement various other feature combinations without departing from the scope and spirit of the invention. Having thus described aspects of the invention, with the details and particularity required by the patent laws, what is claimed and desired protected by Letters Patent is set forth in the appended claims.