# US 10,455,636 B2 · Link packing in mmWave networks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,455,636 B2
- Document ID: US10455636B2
- Status: Granted
- Kind: B2
- Application number: 15/678,681
- Filed: 2017-08-16
- Published: 2018-03-22
- Granted: 2019-10-22
- Earliest claimed: 2016-09-16
- Assignees: NEC Corporation
- Applicants: NEC Laboratories America, Inc.
- Inventors: Narayan Prasad; Mohammad Khojastepour; Sampath Rangarajan; Yasaman Ghasempour
- Web page: https://patentgrep.com/patent/US10455636B2

## CPC

- H04W 76/20: Manipulation of established connections
- H04B 17/336: Signal-to-interference ratio [SIR] or carrier-to-interference ratio [CIR]
- H04W 24/08: Testing, {supervising or monitoring} using real traffic
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- H04B: TRANSMISSION

## Abstract

A computer-implemented method for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem is presented. The computer-implemented 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.

## Claims

### Claim 1

A computer-implemented 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 signal-to-interference-plus-noise ratio (SINR) threshold, the SINR given as:
x
u
,
v
,
b
,
w
+
∑
u
′
∈
𝒰
,
b
′
∈
ℬ
,
v
′
∈
𝒱
,
w
′
∈
𝒲
(
u
′
,
v
′
,
b
′
,
w
′
)
≠
(
u
,
v
,
b
,
w
)
⁢
x
u
,
v
,
b
,
w
⁢
x
u
′
,
v
′
,
b
′
,
w
′
⁢
P
⁢

v
†
⁢
H
u
,
b
′
⁢
w
′

-
P
β
⁢
x
u
,
v
,
b
,
w
⁢

v
†
⁢
H
u
,
b
⁢
w

2
≤
0
,
∀
u
,
v
,
b
,
w
where x is an indicator variable, P is a transmit power, H is a channel matrix, u is a user, w is the transmit beamforming vector, v is the receive beamforming vector, b is the transmitting access point, and β is the SINR threshold.

### Claim 2 (depends on 1)

The method of claim 1, wherein the plurality of transmitters are transmission points (TPs) and the plurality of receivers are devices of users.

### Claim 3 (depends on 1)

The method of claim 1, wherein each active communication link satisfies:
∑
u
′
∈
𝒰
,
b
′
∈
ℬ
,
v
′
∈
𝒱
,
w
′
∈
𝒲
(
u
′
,
v
′
,
b
′
,
w
′
)
∈
⁢
Ψ
⁢
⁢
\
⁢
⁢
(
u
,
v
,
b
,
w
)
⁢
β

v
†
⁢
H
u
,
b
⁢
w

2
+
β
⁢
⁢
x
u
′
,
v
′
,
b
′
,
w
′
⁢
P
⁢

v
†
⁢
H
u
,
b
′
⁢
w
′

2
P
⁢

v
†
⁢
H
u
,
b
⁢
w

2
≤
1
where x is an indicator variable, P is a transmit power, H is a channel matrix, u is a user, w is the transmit beamforming vector, v is the receive beamforming vector, b is the transmitting access point, β is the SINR threshold, and ψ is remaining communication links.

### Claim 4 (depends on 1)

The method of claim 1, wherein the linear integer packing problem is reformulated as:
max
x
∈
{
0
,
1
}
⁢

Ψ

⁢
θ
T
⁢
x
,
Cx
≤
1
;
Dx
≤
1.
where θ is a vector of all weights, x is an indicator variable, ψ is remaining communication links, D is a matrix of dimensionality constraints, and C is a matrix of SINR constraints.

### Claim 5 (depends on 4)

The method of claim 4, wherein a maximum number of entries in each row of matrix C are set to zero and binary-valued packing constraints in the matrix D are minimized.

### Claim 6 (depends on 1)

The method of claim 1, wherein blockages due to obstacles in the mmWave network are permitted and factored into an iterative method that considers a sparse binary packing problem.

### Claim 7 (depends on 1)

The method of claim 1, wherein 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.

### Claim 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 signal-to-interference-plus-noise ratio (SINR) threshold, the SINR given as:
x
u
,
v
,
b
,
w
+
∑
u
′
∈
𝒰
,
b
′
∈
ℬ
,
v
′
∈
𝒱
,
w
′
∈
𝒲
(
u
′
,
v
′
,
b
′
,
w
′
)
≠
(
u
,
v
,
b
,
w
)
⁢
x
u
,
v
,
b
,
w
⁢
x
u
′
,
v
′
,
b
′
,
w
′
⁢
P
⁢

v
†
⁢
H
u
,
b
′
⁢
w
′

-
P
β
⁢
x
u
,
v
,
b
,
w
⁢

v
†
⁢
H
u
,
b
⁢
w

2
≤
0
,
∀
u
,
v
,
b
,
w
where x is an indicator variable, P is a transmit power, H is a channel matrix, u is a user, w is the transmit beamforming vector, v is the receive beamforming vector, b is the transmitting access point, and β is the SINR threshold.

### Claim 9 (depends on 8)

The system of claim 8, wherein the plurality of transmitters are transmission points (TPs) and the plurality of receivers are devices of users.

### Claim 10 (depends on 8)

The system of claim 8, wherein each active communication link satisfies:
∑
u
′
∈
𝒰
,
b
′
∈
ℬ
,
v
′
∈
𝒱
,
w
′
∈
𝒲
(
u
′
,
v
′
,
b
′
,
w
′
)
∈
⁢
Ψ
⁢
⁢
\
⁢
⁢
(
u
,
v
,
b
,
w
)
⁢
β

v
†
⁢
H
u
,
b
⁢
w

2
+
β
⁢
⁢
x
u
′
,
v
′
,
b
′
,
w
′
⁢
P
⁢

v
†
⁢
H
u
,
b
′
⁢
w
′

2
P
⁢

v
†
⁢
H
u
,
b
⁢
w

2
≤
1
where x is an indicator variable, P is a transmit power, H is a channel matrix, u is a user, w is the transmit beamforming vector, v is the receive beamforming vector, b is the transmitting access point, β is the SINR threshold, and ψ is remaining communication links.

### Claim 11 (depends on 8)

The system of claim 8, wherein the linear integer packing problem is reformulated as:
max
x
∈
{
0
,
1
}
⁢

Ψ

⁢
θ
T
⁢
x
,
Cx
≤
1
;
Dx
≤
1.
where θ is a vector of all weights, x is an indicator variable, ψ is remaining communication links, D is a matrix of dimensionality constraints, and C is a matrix of SINR constraints.

### Claim 12 (depends on 11)

The system of claim 11, wherein a maximum number of entries in each row of matrix C are set to zero and binary-valued packing constraints in the matrix D are minimized.

### Claim 13 (depends on 8)

The system of claim 8, wherein blockages due to obstacles in the mmWave network are permitted and factored into an iterative method that considers a sparse binary packing problem.

### Claim 14 (depends on 8)

The system of claim 8, wherein 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.

### Claim 15

A non-transitory computer-readable storage medium comprising a computer-readable program for establishing communication links in a millimeter wave (mmWave) network by solving a linear integer packing problem, wherein the computer-readable 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 signal-to-interference-plus-noise ratio (SINR) threshold, the SINR given as:
x
u
,
v
,
b
,
w
+
∑
u
′
∈
𝒰
,
b
′
∈
ℬ
,
v
′
∈
𝒱
,
w
′
∈
𝒲
(
u
′
,
v
′
,
b
′
,
w
′
)
≠
(
u
,
v
,
b
,
w
)
⁢
x
u
,
v
,
b
,
w
⁢
x
u
′
,
v
′
,
b
′
,
w
′
⁢
P
⁢

v
†
⁢
H
u
,
b
′
⁢
w
′

-
P
β
⁢
x
u
,
v
,
b
,
w
⁢

v
†
⁢
H
u
,
b
⁢
w

2
≤
0
,
∀
u
,
v
,
b
,
w
where x is an indicator variable, P is a transmit power, H is a channel matrix, u is a user, w is the transmit beamforming vector, v is the receive beamforming vector, b is the transmitting access point, and β is the SINR threshold.

### Claim 16 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein 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.

### Claim 17 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein each active communication link satisfies:
∑
u
′
∈
𝒰
,
b
′
∈
ℬ
,
v
′
∈
𝒱
,
w
′
∈
𝒲
(
u
′
,
v
′
,
b
′
,
w
′
)
∈
⁢
Ψ
⁢
⁢
\
⁢
⁢
(
u
,
v
,
b
,
w
)
⁢
β

v
†
⁢
H
u
,
b
⁢
w

2
+
β
⁢
⁢
x
u
′
,
v
′
,
b
′
,
w
′
⁢
P
⁢

v
†
⁢
H
u
,
b
′
⁢
w
′

2
P
⁢

v
†
⁢
H
u
,
b
⁢
w

2
≤
1
where x is an indicator variable, P is a transmit power, H is a channel matrix, u is a user, w is the transmit beamforming vector, v is the receive beamforming vector, b is the transmitting access point, β is the SINR threshold, and ψ is remaining communication links.

### Claim 18 (depends on 15)

The non-transitory computer-readable storage medium of claim 15, wherein the linear integer packing problem is reformulated as:
max
x
∈
{
0
,
1
}
⁢

Ψ

⁢
θ
T
⁢
x
,
Cx
≤
1
;
Dx
≤
1.
where θ is a vector of all weights, x is an indicator variable, ψ is remaining communication links, D is a matrix of dimensionality constraints, and C is a matrix of SINR constraints.