WO2023110066A1

WO2023110066A1 - Apparatus, system and method for dtoa localization

Info

Publication number: WO2023110066A1
Application number: PCT/EP2021/085793
Authority: WO
Inventors: Alexander KOBZANTSEV; Doron Ezri; Avi WEITZMAN
Original assignee: Huawei Technologies Co Ltd
Current assignee: Huawei Technologies Co Ltd
Priority date: 2021-12-15
Filing date: 2021-12-15
Publication date: 2023-06-22
Anticipated expiration: 2024-06-15

Abstract

The present disclosure discloses an apparatus for DTOA localization in a wireless network. The wireless network comprises a plurality of M network devices at determined locations and N user devices. The apparatus obtains, from each network device, a plurality of TOA measurements. Each TOA measurement is determined based on a signal transmitted by each user device within a same time frame. Based on the N×M TOA measurements, the apparatus estimates the locations of the N user devices by using a maximum likelihood algorithm and a linear programming method. Optionally, time synchronization between the M network devices may be achieved after the DTOA localization. In this way, there is no need to maintain clock synchronization among the M network devices prior to the DTOA localization. Therefore, the efficiency and simplicity of the DTOA localization may be achieved.

Description

APPARATUS, SYSTEM AND METHOD FOR DTOA LOCALIZATION

TECHNICAL FIELD

The present disclosure generally relates to the field of communication technology. The present disclosure proposes an apparatus, a related method, and a system for performing differential time of arrival (DTOA) localization in a wireless communication network.

BACKGROUND

Localization is becoming more and more essential, in particular, for location-based services. In a wireless communication network, the location of a client (or station) can be determined based on a TOA algorithm. A traditional TOA method normally requires two or more access points (APs) that measure the same signal propagating with respect to a client. A round trip delay (RTD) measurement representing a two-way propagating time measurement is obtained. Afterwards, the location of the client can be estimated by trilateration based on distance measurements obtained for each of the two or more APs, respectively.

Alternatively, a traditional DTOA method may be used in the wireless communication network to estimate the location of the client. The traditional DTOA method normally requires multiple APs at different locations, which simultaneously measure a single signal transmitted by the client. Each pair of an AP and the client may thereby produce a DTOA measurement, which represents a one-way propagating time measurement, and the DTOA measurement may define a hyperbola curve. The intersection of all the hyperbola curves can then be used as an estimation of the location of the client.

SUMMARY

The present disclosure is further based on the following considerations.

The traditional TOA method does not require time synchronization between the multiple APs, but requires collaboration protocols among the APs and the client, such as Ping-pong messages. The RTD may also produce a large amount of air traffic that could cause traffic congestion, which could be a bottleneck for the wireless communication network, especially for a high- density wireless network. The traditional DTOA method may not require any kind of two-way measurement, which may be more suitable for a high-density wireless network. However, it requires time synchronization between the multiple APs. Time synchronization requires additional effort, and can be an expensive and time-consuming procedure. Further, it would have to be conducted in an ongoing manner, in order to achieve a decent localization accuracy.

In view of the above, an objective of this disclosure is to provide a solution for wireless localization that requires neither a two-way measurement (e.g., RTD measurements) nor a complex time synchronization between APs.

This and other objectives are achieved by the solutions of the present disclosure, as described in the independent claims. Advantageous implementations are further defined in the dependent claims.

An idea described in the present disclosure is to exploit many-to-many transmissions in the wireless communication network. Using a large enough quantity of network transmissions, by a plurality of clients to the multiple APs, allows collecting enough TOA measurements to estimate a large number of unknown variables, including the clients’ locations and a clock mismatch between the APs. This can moreover be achieved with low complexity optimization algorithms.

A first aspect of the present disclosure provides an apparatus for estimating the locations of N user devices in a wireless communication network. The wireless communication network comprises M network devices at determined locations. N and M are positive integers larger than one. The apparatus is configured to obtain, from each of the M network devices, a plurality of TOA measurements, in which each TOA measurement is determined based on uplink data transmitted by each of the N user devices within a same time frame. Then, the apparatus is configured to estimate the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method. The signal may be transmitted by each of the N user devices to each of the M network devices within a short period of time, for example, within tens of milliseconds. The signal may be a broadcast message for all the M network devices. Alternatively, the signal may be a one-to-one message. Nevertheless, each of the M network devices may be configured to capture the signal in both situations. For example, one network device may be configured to capture the one-to- one message destined to other network devices by network packet sniffing. Generally, in both situations, the signal may be seen as broadcast by each of the N user devices to the M network devices.

The signal may be in response to a trigger message sent by each corresponding network device. Each network device may determine a time of arrival for each signal received. The TOA may be represented by a time tag. The TOA may be determined based on each network device’s own free-running clock. Any method commonly known in the field for determining TOA may be used in the present disclosure.

Optionally, the signal may be: an acknowledgment (ACK) message in response to a control message such as NDP or OFDMA trigger frame (TF), or a clear to send (CTS) message in response to a request to send (RTS) message.

Optionally, the apparatus may be further configured to send the estimated locations to the M network devices and/or further application servers. Optionally, the M network devices may be configured to feedback the estimated locations to the N user devices.

An advantage of the apparatus of the first aspect is that time (or clock) synchronization among the M network devices is not required. That is, the M network devices may or may not be synchronized. Moreover, the apparatus of the first aspect does not require any new protocol implementation, and may be based on any existing message flow. Moreover, the locations of the multiple user devices may be estimated through a single shot. Therefore, the efficiency of localization may be improved.

In a possible implementation form of the first aspect, N and M may fulfil the following equation: M > (3N-1)/(N-1). Optionally, M may be equal to ceil((3N-l)/(N-l)), in which ceil() denotes a ceiling function, or may be expressed as M=[(3N-1)/(N-1)].

By ensuring that M and N fulfill the condition laid down in the above equation, sufficient TOA measurements may be ensured to estimate the locations of the N user devices.

In a possible implementation form of the first aspect, when the M network devices are not synchronized, the apparatus may be further configured to estimate a set of time offsets based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using the linear programming method. Each time offset is indicative of a clock mismatch between two of the M network devices.

Optionally, one of the two network devices may be a reference network device, which is common for the whole deployment. That is, one of the M network devices may be set as the reference network device, and a time offset associated with each further network device may be determined based on the clock difference between the reference network device and the further network device.

Based on the set of time offsets, the M network devices may be synchronized. Though synchronization is not required for localization, the M synchronized network devices may be beneficial for other application scenarios. Therefore, time synchronization among the M network devices may be achieved along with the localization of the N user devices.

In a possible implementation form of the first aspect, N may be equal to two. For estimating the locations of the N user devices, the apparatus may be configured to: employ an exhaustive maximum likelihood algorithm to obtain a set of initial locations of the N user devices and a set of initial time offsets between the M network devices; and employ an iterative maximum likelihood algorithm by using the set of initial locations of the N user devices and the set of initial time offsets between the M network devices as inputs. In a possible implementation form of the first aspect, N may be larger than two. For estimating the locations of the N user devices, the apparatus may be configured to: employ the linear programming method to obtain a set of initial time offsets between the M network devices; and employ an iterative maximum likelihood algorithm by using the set of initial time offsets between the M network devices as an input.

In a possible implementation form of the first aspect, for estimating the locations of the N user devices, the apparatus may be further configured to employ a convex optimization algorithm in combination with the maximum likelihood algorithm.

In a possible implementation form of the first aspect, the wireless communication network may be a wireless local area network (WLAN).

A second aspect of the present disclosure provides a user device for a wireless communication network. The wireless communication network comprises M network devices, in which M is a positive integer larger than one. The user device is configured to: receive, from a corresponding network device of the M network devices, a signal for location estimation; and

- broadcast, to the M network devices in response to the signal, uplink data for determining a corresponding time of arrival, TOA measurement by each network device.

Optionally, the wireless communication network may comprise N user devices including the user device.

Optionally, the signal may comprise or indicate absolute time for broadcasting the uplink data. In this way, all the N user devices may be configured to transmit the uplink data at the same absolute time, or simultaneously. Alternatively, all the N user devices are configured to receive the signal from the M network devices simultaneously (within a first time frame, which is the same for all M network devices), so that all the N user devices may be configured to send the uplink data in response to the signal simultaneously (within a second time frame, which is the same for all N user devices). A third aspect of the present disclosure provides a network device for supporting location estimation of N user devices in a wireless communication network. The wireless communication network comprises M network devices including the network device, N and M are positive integers larger than one. The network device is configured to:

- transmit a signal to one or more of the N user devices; receive, from each of the N user devices, corresponding uplink data in response to the signal; determine a set of time of arrival, TOA, measurements based on the corresponding uplink data for each user device; and provide the set of TOA measurements to an apparatus for estimating the location of the N user devices.

Optionally, the signal may be used to indicate a localization operation to-be-performed in the wireless communication network.

Optionally, the network device may be configured to broadcast the signal to each of the N user devices.

Optionally, the signal may comprise or indicate absolute time in order to instruct all the N user devices to transmit the uplink data at the same absolute time, or simultaneously. Alternatively, the M network devices may be configured to send or broadcast the signal to the N user devices simultaneously.

Optionally, the signal may be any message that can be adapted to trigger a user device to send an uplink message. The signal may comprise a request to send (RTS) message and an OFDMA trigger frame (TF) of a WLAN.

A fourth aspect of the present disclosure provides a system for user device localization. The system comprises N user devices, M network devices, and an apparatus according to the first aspect or any implementation form thereof. N and M are positive integers larger than one. Each user device is configured to: receive a signal from a corresponding network device;

- broadcast uplink data to the M network devices in response to the signal. Each network device is configured to: receive the uplink data from the N user devices; determine a set of TOA measurements based on the uplink data for the N user devices; and provide the set of TOA measurements to the apparatus.

In a possible implementation form of the fourth aspect, the N user devices and the M network devices may be part of a plurality of overlapping basic service sets, OBSSs. The N user devices may have the N highest signal levels in the plurality of OBSSs.

A fifth aspect of the present disclosure provides a method for estimating locations of N user devices in a wireless communication network. The wireless communication network comprises M network devices at determined locations. N and M are positive integers larger than one. The method is performed by an apparatus and comprises the following steps: obtaining, from each network device, a plurality of time of arrival, TOA, measurements, wherein each TOA measurement is determined based on a signal transmitted by each user device within a same time frame; and estimating the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method.

In a possible implementation form of the fifth aspect, N and M may fulfill the following equation: M > (3N-1)/(N-1).

In a possible implementation form of the fifth aspect, when the M network devices are not synchronized, the method may further comprise estimating a set of time offsets based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using the linear programming method. Each time offset is indicative of a clock mismatch between two of the M network devices.

Optionally, one of these two network devices may be a reference network device, which is common for the whole deployment. In a possible implementation form of the fifth aspect, N may be equal to two. The step of estimating the locations of the N user devices may comprise: employing an exhaustive maximum likelihood algorithm to obtain a set of initial locations of the N user devices and a set of initial time offsets between the M network devices; and employing an iterative maximum likelihood algorithm by using the set of initial locations of the N user devices and the set of initial time offsets between the M network devices as inputs.

In a possible implementation form of the fifth aspect, N may be larger than two. The step of estimating the locations of the N user devices may comprise: employing the linear programming method to obtain a set of initial time offsets between the M network devices; and employing an iterative maximum likelihood algorithm by using the set of initial time offsets between the M network devices as an input.

In a possible implementation form of the fifth aspect, the step of estimating the locations of the N user devices may comprise employing a convex optimization algorithm in combination with the maximum likelihood algorithm.

In a possible implementation form of the fifth aspect, the wireless communication network may be a WLAN.

A sixth aspect of the present disclosure provides a method performed by a user device for a wireless communication network. The wireless communication network comprises M network devices, M is a positive integer larger than one, and the method comprises: receiving, from a corresponding network device of the M network devices, a signal for location estimation; and

- broadcasting, to the M network devices in response to the signal, uplink data for determining a corresponding time of arrival, TOA measurement by each network device.

A seventh aspect of the present disclosure provides a method performed by a network device for supporting location estimation of N user devices in a wireless communication network. The wireless communication network comprises M network devices including the network device, N and M are positive integers larger than one, and the method comprises:

- transmitting a signal to one or more of the N user devices; receiving, from each of the N user devices, a corresponding uplink data in response to the signal; determining a set of time of arrival, TOA, measurements based on the corresponding uplink data for each user device; and providing the set of TOA measurements to an apparatus for estimating the locations of the N user devices.

An eighth aspect of the present disclosure provides a method for estimating locations of N user devices in a wireless communication network. The wireless communication network comprises M network devices at determined locations. N and M are positive integers larger than one. The method comprises: receiving, by each user device, a signal from a corresponding network device;

- broadcasting, by each user device, uplink data to the M network devices in response to the signal; receiving, by each network device from the N user devices, the uplink data in response to the signal; determining, by each network device for each user device, a set of time of arrival, TOA, measurements based on the uplink data; providing, by each network device, the set of TOA measurements to an apparatus; obtaining, by the apparatus from each network device, the set of TOA measurements; and estimating, by the apparatus, the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method.

In a possible implementation form of the eighth aspect, N and M may fulfill the following equation: M > (3N-1)/(N-1).

In a possible implementation form of the eighth aspect, when the M network devices are not synchronized, the method may further comprise estimating, by the apparatus, a set of time offsets based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using the linear programming method. Each time offset is indicative of a clock mismatch between two of the M network devices.

In a possible implementation form of the eighth aspect, N may be equal to two. The step of estimating the locations of the N user devices may comprise: employing, by the apparatus, an exhaustive maximum likelihood algorithm to obtain a set of initial locations of the N user devices and a set of initial time offsets between the M network devices; and employing, by the apparatus, an iterative maximum likelihood algorithm by using the set of initial locations of the N user devices and the set of initial time offsets between the M network devices as inputs.

In a possible implementation form of the eighth aspect, N may be larger than two. The step of estimating the locations of the N user devices may comprise: employing, by the apparatus, the linear programming method to obtain a set of initial time offsets between the M network devices; and employing, by the apparatus, an iterative maximum likelihood algorithm by using the set of initial time offsets between the M network devices as an input.

In a possible implementation form of the eighth aspect, the step of estimating the locations of the N user devices may comprise employing, by the apparatus, a convex optimization algorithm in combination with the maximum likelihood algorithm.

In a possible implementation form of the eighth aspect, the wireless communication network may be a WLAN.

In a possible implementation form of the eighth aspect, the N user devices and the M network devices may be part of a plurality of OBSSs. The N user devices may have the N highest signal levels in the plurality of OBSSs.

A ninth aspect of the present disclosure provides a computer program comprising a program code for performing the method according to the fifth aspect or any implementation form thereof, when executed on a computer. A tenth aspect of the present disclosure provides a computer program comprising a program code for performing the method according to the sixth aspect or any implementation form thereof, when executed on a computer.

An eleventh aspect of the present disclosure provides a computer program comprising a program code for performing the method according to the seventh aspect or any implementation form thereof, when executed on a computer.

A twelfth aspect of the present disclosure provides a computer program comprising a program code for performing the method according to the eighth aspect or any implementation form thereof, when executed on a plurality of computers.

A thirteenth aspect of the present disclosure provides a computer-readable medium comprising instructions which, when executed by a computer, cause the computer to carry out the method according to any one of the fifth aspect or any implementation form thereof.

A fourteenth aspect of the present disclosure provides a computer-readable medium comprising instructions which, when executed by a computer, cause the computer to carry out the method according to any one of the sixth aspect or any implementation form thereof.

A thirteenth aspect of the present disclosure provides a computer-readable medium comprising instructions which, when executed by a computer, cause the computer to carry out the method according to any one of the seventh aspect or any implementation form thereof.

A fourteenth aspect of the present disclosure provides a computer-readable medium comprising instructions which, when executed by a plurality of computers, cause the computers to carry out the method according to any one of the eighth aspect or any implementation form thereof.

A fifteenth aspect of the present disclosure provides a chipset comprising instructions which, when executed by the chipset, cause the chipset to carry out the method according to any one of the fifth aspect or any implementation form thereof. A sixteenth aspect of the present disclosure provides a chipset comprising instructions which, when executed by the chipset, cause the chipset to carry out the method according to any one of the sixth aspect or any implementation form thereof.

A seventeenth aspect of the present disclosure provides a chipset comprising instructions which, when executed by the chipset, cause the chipset to carry out the method according to any one of the seventh aspect or any implementation form thereof.

An eighteenth aspect of the present disclosure provides a plurality of chipsets, each comprising instructions which, when executed by the chipsets, cause the chipsets to carry out the method according to any one of the eighth aspect or any implementation form thereof.

It has to be noted that all apparatus, devices, elements, units, and means described in the present application could be implemented in software or hardware elements or any kind of combination thereof. All steps which are performed by the various entities described in the present application as well as the functionalities described to be performed by the various entities are intended to mean that the respective entity is adapted to or configured to perform the respective steps and functionalities. Even if, in the following description of specific embodiments, a specific functionality or step to be performed by external entities is not reflected in the description of a specific detailed element of that entity, which performs that specific step or functionality, it should be clear for a skilled person that these methods and functionalities can be implemented in respective software or hardware elements, or any kind of combination thereof.

BRIEF DESCRIPTION OF DRAWINGS

The above-described aspects and implementation forms will be explained in the following description of specific embodiments in relation to the enclosed drawings, in which:

FIG. 1 shows a system according to the present disclosure;

FIG. 2 shows a signal model;

FIG. 3 shows a vector of distances APs and propagation time with respect to an STA;

FIG. 4A shows an application scenario of the present disclosure;

FIG. 4B shows an application scenario of the present disclosure; FIG. 5 shows a method according to the present disclosure;

FIG. 6 shows a method according to the present disclosure;

FIG. 7 shows a method according to the present disclosure;

FIG. 8 shows a method according to the present disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS

In the FIGs. 1-8, corresponding elements are labeled with the same reference signs, may share the same features, and may function likewise. Moreover, it is noted that the number of elements depicted in the FIGs. 1-8 are for illustration purposes only, and shall not be interpreted as limitations to embodiments of the present disclosure.

The present disclosure relates generally to a DTOA localization method without time synchronization. Instead, time synchronization may be achieved through the DTOA localization method. The DTOA localization method of the present disclosure is generally based on a plurality of user devices transmitting network frames simultaneously (or substantially simultaneously). The TOAs from each user device may be measured at each network device based on each network frame. Then an apparatus for performing the DTOA localization may be configured to take all the TOA measurements together into consideration and apply algorithms to the TOA measurements to estimate the locations, as well as time offsets among network devices optionally.

It is noted that DTOA in the present disclosure refers to “differential time of arrival” (DToA), which may be alternatively referred to “time difference of arrival” (TDoA or TDOA). That is, in the present disclosure, DTOA, DToA, TDOA and TDoA are the same. Moreover, the term “network device” may refer to an access point (AP) or base station, and the term “user device” may refer to a client, terminal, or station (STA).

FIG. 1 illustrates a system 100 for DTOA localization according to the present disclosure.

The system 100 comprises a plurality of network devices, a plurality of user devices, and an apparatus 110. The network devices and user devices may form a wireless communication network. The network devices are at determined locations. That is, their locations or coordinates are known to the apparatus 110. It is quite common in the wireless communication network that a user device may be configured to transmit one or more uplink frames of any time and to any destination in the wireless communication network. Those who are configured to transmit any type of uplink data (or uplink frame) simultaneously or in a short period of time in the wireless communication are exemplarily illustrated as N stations (STAs) 131, 132 in FIG. 1. Then, each of the M network devices is configured to receive (or capture) all uplink data from the N STAs in the wireless communication network. It is noted that it is possible for any network device in the wireless communication network to detect and capture any uplink data such as through network packet sniffing, even though some uplink data may be for a specific destination (e.g., for a specific network device). Based on the captured uplink data, at least a TOA measurement can be obtained by each network device.

For example, the wireless communication network may be a wireless local area network (WLAN), which bases on Wi-Fi protocols and comprises a plurality of network devices, such as routers and repeaters, and a plurality of stations such as wearable devices, mobile phones, and tablets.

As illustrated in FIG. 1, M network devices (or access points (APs)) 121-125 are configured to receive, from each STA 131 and 132, corresponding uplink data 141-145, 151-155 that is transmitted within a same time frame. M and N are positive integers larger than one. In FIG. 1, M=5 and N=2. Based on each uplink data, a corresponding TOA measurement may be determined, for example, based on a time tag comprised in each uplink data and each network device’s own clock. That is, for each network device, N TOA measurements may be obtained. Then, each network device 121-125 is configured to provide the determined N TOA measurements to the apparatus 110. The apparatus 110 are configured to obtain NXM TOA measurement. Then, the apparatus 110 are configured to estimate the locations of the N user devices based on the obtained NX M TOA measurements by using a maximum likelihood algorithm and a linear programming method.

Ideally, the uplink data 141-145, 151-155 shall be transmitted by the STAs 131, 132 simultaneously. In reality, the uplink data 141-145, 151-155 shall be transmitted within the same time frame such as tens of milliseconds. For example, the same time frame may be generally in the range of 0 to 100 milliseconds. Optionally, the same time frame may be in the range of 0 to 10 milliseconds, e.g., when a higher accuracy of DTOA localization is demanded or in order to achieve a more accurate DTOA localization.

Optionally, the M network devices may be configured to trigger the N user device to send the uplink data within the same time frame by sending a signal to the N user devices. The signal may indicate or comprise absolute time to allow all the N user devices to broadcast the uplink data at the absolute time. However, it is noted that if the M network devices are capable of collecting the uplink data from the N user devices, or if the M network devices have already collected sufficient uplink data within the same time frame such as tens of milliseconds, it is not necessary to send the signal by one or each of the M network devices.

That is, a possible embodiment of a system based on FIG. 1 is that:

- transmitting, by the N user devices 131, 132, uplink data 141-145, 151-155 within a same time frame, for example within tens of milliseconds; receiving, by the M network devices 121-125, the uplink data 141-145, 151-155; determining, by the M network devices 121-125, a plurality of (NxM) TOA measurements; providing, by the M network devices 121-125, the NxM TOA measurements to the apparatus 110; performing, by the apparatus 110, the DTOA localization according to the present disclosure.

Optionally, the apparatus 110 may be a standalone apparatus with respect to the M network devices. Alternatively, the apparatus 110 may be a unit attachable to one of the M network devices. Alternatively, the apparatus 100 may be an integrated unit inside one of the M network devices.

Optionally, the apparatus 110 and the M network devices may communicate via wired connections or wireless connections.

FIG. 2 shows a signal model. The signal model is built based on the system 100 of FIG. 1.

Similar elements shall share the same features and functions likewise. Based on the notations in FIG. 2, the signal model for obtaining one TOA measurement at each AP in the present disclosure can be generally defined as follows:

where m_t denotes one TOA measurement, which may be seen as a time tag when AP(s) receives the uplink frame from STA(t), r_t denotes a propagation time of the uplink frame from STA(t) to AP(s), T_t denotes transmit time indicating a time tag of STA(t) transmitting (or broadcast) the uplink frame, 6_S denotes a time offset of AP(s), and e_t denotes random measurement error between STA(t) and AP(s). In FIG.2, as an example, five network devices (APs) and two user devices (STAs) are illustrated.

Optionally, the time offset of AP(s) can be measured based on one of the M APs. Generally, any one of the M APs can be selected as a basis for measuring the time offset of AP(s), which shall be referred to as a reference AP. That is, the time offset of AP(s) may be determined based on clock difference between AP(s) and the reference AP, or represented as: 6_S = clock of AP(s) — clock of reference AP. Clearly, the reference AP has a time offset of zero. If the apparatus 110 is attached or integrated to one of the M APs, which shall be referred to as a master AP, then the master AP may be selected as the reference AP.

The M APs are deployed at determined locations, which may be represented as follows:

which may denote known Cartesian coordinates of AP s in a vector form, and s = 1 ... M. Optionally, other coordinate systems may be similarly used.

The N STAs are at unknown locations, which may be represented as follows:

T

Pt = [Px Py Pz]_s (3), which may denote unknown Cartesian coordinates of STA t in a vector form, and t = 1 . . . N. Optionally, other coordinate systems may be similarly used.

(5)

The propagation time r_t may be further defined as:

in which c is a constant equal to the speed of light in vacuum.

A vector form of all TO A measurements can be denoted as: m_t = r_t + l_Mr_t + 8 + e_t, t=l, 2, ...N (5), where: ments; ent errors.

In order to ensure sufficient equations to estimate all unknown parameters, the following condition shall preferably hold: M > (3N-1)/(N-1). A minimal configuration may be N=2 and M=5. Optionally, other configurations may be used, such as (N=5, M=5), or (N=10, M=10).

The apparatus 110 is configured to obtain all the TOA measurements m_t, and estimate the locations of the N STAs p_t based on m_t and locations of the M APs q_s. Optionally, time offsets 8 may also be estimated. As an example, a cost function for minimization can be given as follows for estimating p_t.

An objective is to find optimal estimates {p_t, 5} of {p_t, 8} that minimize the cost function, which can be formulated as follows:

The average transmit time f_t can be estimated by:

The cost function is then:

When using the following denotations:

the cost function can be further expressed as:

For estimating the time offset 8 of the M STAs,

Then, the cost function can be denoted as:

For low complexity, the apparatus 110 is configured to use a maximum likelihood algorithm and a linear programming method. The maximum likelihood algorithm may be seen as an optimization of multivariable non-linear cost function. The final estimate is highly dependent on the initial estimate.

When N=2, the initial estimate of the locations and of the N user devices and the time offsets may be obtained by exhaustive search. An exhaustive search may examine every search point inside a search region and find the best possible match. In this case, a 2N=4 dimensional search may be performed. The exhaustive search may also be referred to as an “exhaustive search based maximum likelihood”, or simply, “exhaustive maximum likelihood”.

For N>2, the multi-dimensional search used by the exhaustive search may become unfeasible due to a large amount of computation. Therefore, the following iterative maximum likelihood algorithm may be used:

Step 11 : Obtaining initial time offsets, e.g., through guessing, and then estimating the location for each client separately;

Step 12: Updating the timing offsets using the previously estimated clients locations;

Step 13: Repeating the iterations of steps 11 and 12 until convergence.

Mathematically, the iterative maximum likelihood algorithm performed by the apparatus may be represented as:

Step 21 : Obtaining initial time offsets 8^ G c^Mxl

Step 22: For each iteration, repeat: a. Estimating location for each target separately:

b. Updating timing: 8 = C^T (m — r) where m = [m fh ... m^]^T,

c. Evaluating the cost function value. d. Checking convergence. e. If not converged, go back to step 22. f. If converged, stop.

Optionally, for reducing computation complexity and improving accuracy, a linear programming method may be used by the apparatus 110 to obtain relatively accurate estimates of the initial time offsets, especially for N>2.

Using the linear programming method, the following minimization problem may be firstly solved by the apparatus 110: minl^S (16) subject to:

5(1) = 0

where d =

which is a vector of distances between APs.

As an illustration, FIG. 3 depicts a vector of distances

between AP(i) and AP(j), and propagation time

with respect to STA(t). Further, an example of matrix D may be as follows:

Dx can represent the difference of the vector whose entries are all possible differences of the entries of vector x. Optionally, the matrix D may be used to extract a difference of two TOA measurements, which may be represented as Dm_t. That is, elements in each row of the matrix D may correspond to the obtained TOA measurement matrix at M APs. Hence, the number of columns of the matrix D is M. The matrix D includes only one value of “1” and only one value of “-1” in each row, and the number of rows is the maximum number of AP pairs that can be formed among the M APs, which is 0.5-M-(M-l). For example, when M=5, an example of the matrix D may be as follows:

When M is equal to other values, a corresponding matrix D can be derived by applying a similar pattern shown in the above example.

A solution to the minimization problem may be achieved by convex multi-dimensional optimization algorithms such as “Interior Point” or “Trust Region Reflective”. It may be numerically solved using the fmincon() function of MATLAB® software. The MATLAB® is a registered trademark of The MathWorks, Inc.

FIGs. 4A and 4B each shows an application scenario of the present disclosure. FIG. 4A shows five APs and two clients (or STAs) involved in the DTOA localization, while FIG. 4B shows ten APs and ten STAs involved in the DTOA localization. The APs are at determined locations denoted by circle marks in FIGs. 4A and 4B, while the STAs are at undetermined locations denoted by square marks. These APs and STAs may be part of a wireless communication network and may be selected from a larger group of APs and a larger group of STAs comprised in the wireless communication network to perform the DTOA localization according to the present disclosure. That is, generally, the N user devices and the M network devices in the present disclosure may be part of a plurality of overlapping basic service sets (OBSSs). The N user devices may have the N highest signal levels in the plurality of OBSSs. It is noted that the apparatus for determining the locations of the STAs is not shown in FIGs. 4A and 4B. The apparatus may be located remotely, or may be part of or attached to one of the APs, as mentioned with respect to FIG.1.

In FIG. 4A, the two STAs are configured to broadcast uplink data within a same time frame, for example within ten milliseconds. The five APs receive the uplink data and obtain TOA measurements. Then, the five APs provide the TOA measurements to the apparatus for estimating the locations of STAs. As shown in FIG. 4 A, the apparatus may be configured to use the exhaustive search mentioned above for N=2 to obtain initial locations, and then use iterative maximum likelihood algorithm to obtain further estimates of the locations based on previously estimated locations iteratively until convergence.

In FIG. 4B, the ten APs may obtain TOA measurements similar to FIG. 4A. Then, the apparatus for estimating the locations of STAs may be configured to use the linear programming method mentioned above for N>2 to obtain initial estimates. Then, the apparatus may be configured to employ the iterative maximum likelihood algorithm to obtain further estimates of the locations based on previous estimates iteratively until convergence.

In FIGs. 4A and 4B, estimated locations of STAs during the iterative estimation process are denoted by cross marks. It can be seen that in FIG. 4A, during the iterative estimation process, the estimated locations of STAs are getting closer to the true locations of STAs. In FIG. 4B, the estimated locations of STAs are also getting closer to the true locations of STAs during the iterative estimation process and converge to the true locations of STAs at the end of the iterative estimation process. By comparison, it can be seen that the accuracy of the DTOA localization increases with the number of STAs and/or APs.

Optionally, time offsets among the APs in FIG. 4A and FIG. 4B may be obtained along with the final estimates of the locations of the STAs. In some other embodiments, different numbers of network devices and user devices may be used to facilitate the apparatus 110 of FIG. 1 to determine locations of the user devices and optionally, time offsets of the network devices. Table 1 shows a summary of performance comparison between DTOA localization in different scenarios, which are conducted in a same environment and based on the present disclosure.

Table a_e in Table 1 denotes the standard deviation of measurement error of TOA measurements, which is in the level of nanoseconds (e.g., 3 nanoseconds may be approximately translated into Im error in range measurement). It can be seen that the accuracy of localization and time synchronization increases with the number of APs and STAs. However, a larger number of APs and STAs may increase the computation complexity. Therefore, the actual number of APs and STAs involved in the DTOA localization may be determined by the apparatus 110 of FIG. 1, e.g., based on accuracy requirement and computation capability.

Preferably, in the present disclosure, all the user devices shall be configured to send the uplink data simultaneously or within a same time frame as short as possible. The shorter the same time frame is, the more accurate the DTOA localization can be.

Optionally, the apparatus 110 may be configured to notify each of the M network devices of a to-be-performed DTOA localization. Then, the M network devices may be configured to send a signal indicating the DTOA localization to the user devices. Specifically, one or more of the M network devices may not be connected (paired) with any user device, while one or more of the M network devices may be connected (paired) with one or more user devices. The signal indicating the DTOA localization may be transmitted to each user device by the corresponding connected network device. In response to the signal indicating the DTOA localization, the N user devices may be configured to simultaneously send (or broadcast) uplink data frame to all network devices within a same time frame.

It is noted that values in Table 1 are not deterministic. The values are given for the purposes of comparison and illustration and may be different for different radio environments. However, relative relationships shall exist similarly for a different radio environment.

FIG. 5 shows a diagram of a method 500 according to the present disclosure.

The method 500 is executed by an apparatus according to the apparatus 110 in FIG. 1. The method 500 comprises the following steps: step 501 : obtaining, from each network device, a plurality of TO A measurements, wherein each TOA measurement is determined based on a signal transmitted by each user device within a same time frame; and step 502: estimating the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method.

Optionally, the steps of the method 500 may share the same functions and details from the perspective of the apparatus 110 shown in the FIGs. 1-4 described above. Therefore, the corresponding method implementations are not described again at this point.

FIG. 6 shows a diagram of a method 600 according to the present disclosure.

The method 600 is executed by a user device according to one of the N user devices in FIG. 1. The method 600 comprises the following steps: step 601 : receiving, from a corresponding network device of the M network devices, a signal for location estimation; and step 602: broadcasting, to the M network devices in response to the signal, uplink data for determining a corresponding TOA measurement by each network device. Optionally, the steps of the method 600 may share the same functions and details from the perspective of the user device shown in the FIGs. 1-4 described above. Therefore, the corresponding method implementations are not described again at this point.

FIG. 7 shows a diagram of a method 700 according to the present disclosure.

The method 700 is executed by a network device according to one of the M network devices in FIG. 1. The method 700 comprises the following steps: step 701 : transmitting a signal to one or more of the N user devices; step 702: receiving, from each of the N user devices, a corresponding uplink data in response to the signal; step 703: determining a set of TOA measurements based on the corresponding uplink data for each user device; and step 704: providing the set of TOA measurements to an apparatus for estimating the locations of the N user devices.

Optionally, the steps of the method 700 may share the same functions and details from the perspective of the network device shown in the FIGs. 1-4 described above. Therefore, the corresponding method implementations are not described again at this point.

FIG. 8, which is formed by FIGs. 8A and 8B collectively, shows a diagram of a method 800 according to the present disclosure.

The method 800 is executed by corresponding elements of a system according to the system 100 in FIG. 1. The method 800 comprises the following steps: step 801 : receiving, by each user device, a signal from a corresponding network device; step 802: broadcasting, by each user device, uplink data to the M network devices in response to the signal; step 803 : receiving, by each network device from the N user devices, the uplink data in response to the signal; step 804: determining, by each network device for each user device, a set of TOA measurements based on the uplink data; step 805: providing, by each network device, the set of TOA measurements to an apparatus; step 806: obtaining, by the apparatus from each network device, the set of TOA measurements; step 807: estimating, by the apparatus, the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method.

Optionally, the steps of the method 800 may share the same functions and details from the perspective of the system 100 shown in the FIGs. 1-4 described above. Therefore, the corresponding method implementations are not described again at this point.

An application scenario of the present disclosure is providing location-based service to customers in a shopping mall. For example, a number of WLAN APs may be deployed inside the shopping mall to provide network connections to terminals of the customers. Since there are normally enough WLAN APs and terminals of customers, they may be collectively used to perform the DTOA localization through the apparatus 110 of FIG. 1 according to the present disclosure. In this way, there is no need to maintain synchronized clocks between WLAN APs at all times, especially prior to performing the DTOA localization. Instead, time synchronization may be optionally achieved as part of the result of the DTOA localization according to the present disclosure. Further, the locations of the user devices may be determined collectively in a single shot. In this way, the efficiency of wireless network localization may be improved, while clock synchronization requirement for the wireless network may be simplified.

It is noted that although the previous disclosure is mainly described with respect to a WLAN, the present disclosure may be applied to other types of wireless networks likewise, such as but not limited to a Bluetooth® (a trademark owned by the Bluetooth SIG) network (e.g., a Bluetooth mesh), Zigbee network, Internet of things (loT), WiMAX network, wireless ad hoc network, cellular or mobile network (e.g., a 2G, 3G, 4G, 5G network), and vehicle-to- everything (V2X) network. It is noted that each of the apparatus, network device, and user device of the present disclosure (as described above) may comprise processing circuitry configured to perform, conduct or initiate the various corresponding operations described herein, respectively. The processing circuitry may comprise hardware and software. The hardware may comprise analog circuitry or digital circuitry, or both analog and digital circuitry. The digital circuitry may comprise components such as application-specific integrated circuits (ASICs), field-programmable arrays (FPGAs), digital signal processors (DSPs), or multi-purpose processors. In one embodiment, the processing circuitry comprises one or more processors and a non-transitory memory connected to the one or more processors. The non-transitory memory may carry executable program code which, when executed by the one or more processors, causes the device to perform, conduct or initiate the operations or methods described herein, respectively.

It is further noted that the apparatus as shown in FIG. 1 of the present disclosure may be a single computing device, or may comprise a set of connected electronic devices or modules capable of computing with shared system memory. It is well-known in the art that such computing capabilities may be incorporated into many different devices or modules, and therefore the term “apparatus” may comprise a chip, chipset, computer, server, and the like.

The present disclosure has been described in conjunction with various embodiments as examples as well as implementations. However, other variations can be understood and effected by those persons skilled in the art and practicing the claimed subject matter, from the studies of the drawings, this disclosure and the independent claims. In the claims as well as in the description the word “comprising” does not exclude other elements or steps and the indefinite article “a” or “an” does not exclude a plurality. A single element or another unit may fulfill the functions of several entities or items recited in the claims. The mere fact that certain measures are recited in the mutual different dependent claims does not indicate that a combination of these measures cannot be used in an advantageous implementation.

Claims

1. An apparatus (110) for estimating locations of N user devices (131, 132) in a wireless communication network, wherein the wireless communication network comprises M network devices (121, 122, 123, 124, 125), N and M are positive integers larger than one, the M network devices (121, 122, 123, 124, 125) are at determined locations, and the apparatus (110) is configured to: obtain, from each network device, a plurality of time of arrival, TOA, measurements, wherein each TOA measurement is determined based on a signal (141-145, 151-145) transmitted by each user device within a same time frame; and estimate the locations of the N user devices (131, 132) based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices (121, 122, 123, 124, 125) by using a maximum likelihood algorithm and a linear programming method.

2. The apparatus (110) according to claim 1, wherein the M network devices (121, 122, 123, 124, 125) are not synchronized, and the apparatus (110) is further configured to estimate a set of time offsets based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices (121, 122, 123, 124, 125) by using the linear programming method, wherein each time offset is indicative of a clock mismatch between two of the M network devices (121, 122, 123, 124, 125).

3. The apparatus (110) according to claim 1 or 2, wherein N and M fulfil the following equation:

M > (3N-1)/(N-1).

4. The apparatus (110) according to any one of claims 1 to 3, wherein N=2 and for estimating the locations of the N user devices (131, 132), the apparatus (110) is configured to: employ an exhaustive maximum likelihood algorithm to obtain a set of initial locations of the N user devices (131, 132) and a set of initial time offsets between the M network devices (121, 122, 123, 124, 125); and

28 employ an iterative maximum likelihood algorithm by using the set of initial locations of the N user devices (131, 132) and the set of initial time offsets between the M network devices (121, 122, 123, 124, 125) as inputs.

5. The apparatus (110) according to any one of claims 1 to 3, wherein N>2 and for estimating the locations of the N user devices (131, 132), the apparatus (110) is configured to: employ the linear programming method to obtain a set of initial time offsets between the M network devices (121, 122, 123, 124, 125); and employ an iterative maximum likelihood algorithm by using the set of initial time offsets between the M network devices (121, 122, 123, 124, 125) as an input.

6. The apparatus (110) according to claim 5, wherein for estimating the locations of the N user devices (131, 132), the apparatus (110) is further configured to employ a convex optimization algorithm in combination with the maximum likelihood algorithm.

7. The apparatus (110) according to any one of claims 1 to 6, wherein the wireless communication network is a wireless local area network, WLAN.

8. A user device for a wireless communication network, wherein the wireless communication network comprises M network devices (121, 122, 123, 124, 125), M is a positive integer larger than one, and the user device is configured to: receive, from a corresponding network device of the M network devices (121, 122, 123, 124, 125), a signal for location estimation; and broadcast, to the M network devices (121, 122, 123, 124, 125) in response to the signal, uplink data for determining a corresponding time of arrival, TOA measurement by each network device.

9. A network device for supporting location estimation of N user devices (131, 132) in a wireless communication network, wherein the wireless communication network comprises M network devices (121, 122, 123, 124, 125) including the network device, N and M are positive integers larger than one, and the network device is configured to: transmit a signal to one or more of the N user devices (131, 132); receive, from each of the N user devices (131, 132), a corresponding uplink data in response to the signal; determine a set of time of arrival, TOA, measurements based on the corresponding uplink data for each user device; and provide the set of TOA measurements to an apparatus (110) for estimating the location of the N user devices (131, 132).

10. A system (100) for user device localization, the system comprising N user devices (131, 132), M network devices (121, 122, 123, 124, 125), and an apparatus (110) according to any one of claims 1 to 7, wherein N and M are positive integers larger than one, and each user device is configured to: receive a signal from one network device of the M network devices (121, 122, 123, 124, 125); and broadcast uplink data to the M network devices (121, 122, 123, 124, 125) in response to the signal, and wherein the M network devices (121, 122, 123, 124, 125) are at determined locations, and each network device is configured to: receive, from each of the N user devices (131, 132), corresponding uplink data in response to the signal; determine a set of time of arrival, TOA, measurements based on the corresponding uplink data for each user device; and provide the set of TOA measurements to the apparatus (110).

11. The system (110) according to claim 10, wherein the N user devices (131, 132) and the M network devices (121, 122, 123, 124, 125) are part of a plurality of overlapping basic service sets, OBSSs, and the N user devices (131, 132) have the N highest signal levels in the plurality of OBSSs.

12. A method (500) for estimating locations of N user devices in a wireless communication network, wherein the wireless communication network comprises M network devices, N and M are positive integers larger than one, the M network devices are at determined locations, the method is performed by an apparatus and comprises: obtaining (501), from each network device, a plurality of time of arrival, TOA, measurements, wherein each TOA measurement is determined based on a signal transmitted by each user device within a same time frame; and estimating (502) the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method.

13. A method (600) performed by a user device for a wireless communication network, wherein the wireless communication network comprises M network devices, M is a positive integer larger than one, and the method comprises: receiving (601), from a corresponding network device of the M network devices, a signal for location estimation; and broadcasting (602), to the M network devices in response to the signal, uplink data for determining a corresponding time of arrival, TOA, measurement by each network device.

14. A method (700) performed by a network device for supporting location estimation of N user devices in a wireless communication network, wherein the wireless communication network comprises M network devices including the network device, N and M are positive integers larger than one, and the method comprises: transmitting (701) a signal to one or more of the N user devices; receiving (702), from each of the N user devices, a corresponding uplink data in response to the signal; determining (703) a set of time of arrival, TOA, measurements based on the corresponding uplink data for each user device; and providing (704) the set of TOA measurements to an apparatus for estimating the locations of the N user devices.

15. A method (800) for estimating locations of N user devices in a wireless communication network, wherein the wireless communication network comprises M network devices, N and M are positive integers larger than one, the plurality of M network devices are at determined locations, and the method comprises: receiving (801), by each user device, a signal from a corresponding network device; broadcasting (802), by each user device, uplink data to the M network devices in response to the signal; receiving (803), by each network device from the N user devices, the uplink data in response to the signal; determining (804), by each network device for each user device, a set of time of arrival, TO A, measurements based on the uplink data; providing (805), by each network device, the set of TOA measurements to an apparatus; obtaining (806), by the apparatus from each network device, the set of TOA measurements; and estimating (807), by the apparatus, the locations of the N user devices based on the plurality of TOA measurements obtained from each network device and the locations of the M network devices by using a maximum likelihood algorithm and a linear programming method.

16. A computer program comprising a program code for performing the method according to any one of claims 12 to 15, when executed on a computer.

32