# US 11,029,413 B1 · Using SDP relaxation for optimization of the satellites set chosen for positioning

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

- Number: US 11,029,413 B1
- Document ID: US11029413B1
- Status: Granted
- Kind: B1
- Application number: 16/088,518
- Filed: 2018-04-18
- Published: 2021-06-17
- Granted: 2021-06-08
- Earliest claimed: 2018-04-18
- Assignees: Topcon Positioning Systems, Inc.
- Applicants: Topcon Positioning Systems, Inc.
- Inventors: Lev Borisovich Rapoport
- Web page: https://patentgrep.com/patent/US11029413B1

## CPC

- G01S 19/28: Satellite selection
- G01S 19/29: carrier {including Doppler,} related {(G01S19/246 takes precedence)}
- G01S 19/30: code related {(G01S19/246 takes precedence)}
- G01S 19/33: Multimode operation in different systems which transmit time stamped messages, e.g. GPS/GLONASS
- G01S 19/258: {relating to the satellite constellation, e.g. almanac, ephemeris data, lists of satellites in view}
- G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES

## Abstract

A method of determining coordinates, including receiving GNSS (global navigation satellite system) signals from at least five satellites, wherein at least two of the five satellites belong to one constellation, and the remaining satellites belong to at least one other constellation; processing the GNSS signals to measure code and phase measurements for each of the satellites and each of the GNSS signals; selecting a subset of the GNSS signals as an optimal set for coordinate calculation, where the selecting is based on Semi-Definite Programming (SDP) relaxation as applied to an optimization of a PDOP (positional dilution of precision) criterion; calculating coordinates of a receiver based on the code and phase measurements of the selected subset; and outputting the calculated coordinates. The total number of signals in the optimal set should not exceed the predefined number of m signals.

## Claims

### Claim 1

A method of determining coordinates, comprising:
receiving GNSS (global navigation satellite system) signals from at least five satellites, wherein at least two of the five satellites belong to one constellation, and the remaining satellites belong to at least one other constellation;
processing the GNSS signals to measure code and phase measurements for each of the satellites and each of the GNSS signals;
selecting a subset of the GNSS signals as an optimal set for coordinate calculation,
wherein the selecting is based on Semi-Definite Programming (SDP) relaxation as applied to an optimization of a PDOP (positional dilution of precision) criterion, wherein the SDP relaxation minimizes a linear criterion subject to a linear matrix inequality constraint;
calculating coordinates of a receiver based on the code and phase measurements of the selected subset; and
outputting the calculated coordinates.

### Claim 2 (depends on 1)

The method of claim 1, wherein the receiver is a standalone receiver.

### Claim 3 (depends on 1)

The method of claim 1, wherein the receiver operates in a smoothed standalone mode.

### Claim 4 (depends on 1)

The method of claim 1, wherein the receiver operates in a differential mode.

### Claim 5 (depends on 1)

The method of claim 1, wherein the linear criterion is
minS,Xtr(S)
and the linear matrix inequality constraint is
P
⁡
(
S
,
X
)
=
(
A
T
⁢
X
⁢
A
I
p
I
p
S
)
≽
0
,
where A is an M by p matrix of linearized navigation equations, and subject to algebraic inequality constraints
∑
i
=
1
M
⁢
x
i
≤
m
,
0
≤
x
i
≤
1
,
where p is a number of navigation parameters, M is a total number of available signals, and xi is a variable indicating that satellite i is selected if xi=1,
X
=
(
x
1
0
…
0
0
x
2
…
0
…
…
…
…
0
0
…
x
M
)
is a diagonal matrix composed of xi,
S is a symmetric auxiliary matrix,
m is the maximum number of signals allowed in the optimal set,
Ip is an identity matrix, and
stands for positive semidefiniteness.

### Claim 6 (depends on 5)

The method of claim 5, wherein the xi are non-binary, and are rounded to 0 or 1.

### Claim 7 (depends on 5)

The method of claim 5, wherein the SDP relaxation is used for computation of a lower bound by using a Branch and Bound technique.

### Claim 8

A GNSS (global navigation satellite system) navigation receiver, comprising:
a plurality of radio frequency tracts receiving GNSS signals from at least five satellites, wherein at least two of the five satellites belong to one constellation, and the remaining satellites belong to at least one other constellation;
a digital section including a processor configured to process the GNSS signals to measure code and phase measurements for each of the satellites and each of the GNSS signals;
the processor configured to select a subset of the GNSS signals as an optimal set for coordinate calculation,
wherein the selecting is based on Semi-Definite Programming (SDP) relaxation as applied to an optimization of a PDOP (positional dilution of precision) criterion, wherein the SDP relaxation minimizes a linear criterion subject to a linear matrix inequality constraint;
the processor configured to calculate coordinates of a receiver based on the code and phase measurements of the selected subset; and
the processor configured to output the calculated coordinates.

### Claim 9 (depends on 8)

The receiver of claim 8, wherein the receiver is a standalone receiver.

### Claim 10 (depends on 8)

The receiver of claim 8, wherein the receiver operates in a smoothed standalone mode.

### Claim 11 (depends on 8)

The receiver of claim 8, wherein the receiver operates in a differential mode.

### Claim 12 (depends on 8)

The receiver of claim 8, wherein the linear criterion is
minS,Xtr(S)
and the linear matrix inequality constraint is
P
⁡
(
S
,
X
)
=
(
A
T
⁢
X
⁢
A
I
p
I
p
S
)
≽
0
,
where A is an M by p matrix of linearized navigation equations, and subject to algebraic inequality constraints
∑
i
=
1
M
⁢
x
i
≤
m
,
0
≤
x
i
≤
1
,
where p is a number of navigation parameters, M is a total number of available signals, and xi is a variable indicating that satellite i is selected if xi=1,
X
=
(
x
1
0
…
0
0
x
2
…
0
…
…
…
…
0
0
…
x
M
)
is a diagonal matrix composed of xi,
S is a symmetric auxiliary matrix,
m is the maximal number of signals allowed in the optimal set,
Ip is an identity matrix, and
stands for positive semidefiniteness.

### Claim 13 (depends on 12)

The receiver of claim 12, wherein the xi are non-binary, and are rounded to 0 or 1.

### Claim 14 (depends on 12)

The receiver of claim 12, wherein the SDP relaxation is used for computation of a lower bound by using a Branch and Bound technique.

### Claim 15 (depends on 8)

The receiver of claim 8, wherein the radio frequency tracts are connected to a single antenna.

### Claim 16 (depends on 8)

The receiver of claim 8, wherein the radio frequency tracts are connected to multiple antennas.