[go: up one dir, main page]

WO2014082686A1 - Method for determining powers and locations of radio transmitters - Google Patents

Method for determining powers and locations of radio transmitters Download PDF

Info

Publication number
WO2014082686A1
WO2014082686A1 PCT/EP2012/074174 EP2012074174W WO2014082686A1 WO 2014082686 A1 WO2014082686 A1 WO 2014082686A1 EP 2012074174 W EP2012074174 W EP 2012074174W WO 2014082686 A1 WO2014082686 A1 WO 2014082686A1
Authority
WO
WIPO (PCT)
Prior art keywords
powers
locations
sensors
radio transmitters
value
Prior art date
Application number
PCT/EP2012/074174
Other languages
French (fr)
Inventor
Jaap Van De Beek
Andreas Polydoros
Ioannis DAGRES
Liljana GAVRILOVSKA
Vladimir ATANASOVSKI
Daniel DENKOVSKI
Original Assignee
Huawei Technologies Sweden Ab
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Huawei Technologies Sweden Ab filed Critical Huawei Technologies Sweden Ab
Priority to CN201280077285.8A priority Critical patent/CN104871615A/en
Priority to PCT/EP2012/074174 priority patent/WO2014082686A1/en
Publication of WO2014082686A1 publication Critical patent/WO2014082686A1/en

Links

Classifications

    • GPHYSICS
    • G01MEASURING; TESTING
    • G01SRADIO 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
    • G01S5/00Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations
    • G01S5/02Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using radio waves
    • G01S5/0205Details
    • G01S5/0242Determining the position of transmitters to be subsequently used in positioning
    • HELECTRICITY
    • H04ELECTRIC COMMUNICATION TECHNIQUE
    • H04WWIRELESS COMMUNICATION NETWORKS
    • H04W64/00Locating users or terminals or network equipment for network management purposes, e.g. mobility management
    • H04W64/003Locating users or terminals or network equipment for network management purposes, e.g. mobility management locating network equipment

Definitions

  • the present invention relates to a method for determining powers and locations of radio transmitters. Furthermore, the invention also relates to a computer program, a computer program product, and a central processing unit thereof.
  • Passive transmitter localization via sensor networks is an important topic for many wireless applications since localization of unknown radio sources is likely to become a key component in future, next generation radio communication networks. Endowed with the capability to sense and record radio-activity in the surrounding environment, central operators or other relevant radio network management entities can then efficiently plan, decide upon and execute respective actions by their networks.
  • the environmental awareness that comes with the knowledge of unknown transmitters' locations is likely to become instrumental in future self-organizing networks where, for instance, the power, frequency or other crucial radio parameters are (automatically) adapted based on the environmental knowledge gathered from massive-scale sensor networks and their affiliated measurements ("observations", "observed data”).
  • Next-generation cellular networks for instance can benefit from such self-organizing capabilities through increased cost efficiency (the reduction of the operational expenses, OPEX) and through increased spectrum and energy efficiency.
  • Benefits can result for operators and regulators alike; the first to improve network operation, the second to detect and locate malicious and non-licensed spectrum users.
  • FIG. 1 illustrates the problem scenario that is addressed by the present invention.
  • two or more active radio transmitters operate in a certain frequency band.
  • the location, power, type or any other relevant parameter of these radio transmissions is unknown.
  • the number of active radio transmitters is also unknown.
  • a possibly high number of distributed sensors perform measurements of the Received Signal Strength (RSS) caused by these unknown transmitters at the respective sensor locations and forward these respective measurements to a central network node.
  • the forwarded measurements may contain relevant labels such as the time of the measurements, the frequency band of the measurements, the location/coordinates of the sensor etc.
  • RSS Received Signal Strength
  • a common problem arising in these multi-transmitter scenarios is the complexity in distinguishing components of the measured RSS due to different radio transmitters. This complicates multi-transmitter localization problem. The problem is then to accurately determine the unknown number, the unknown power(s) and the unknown location(s) of the radio transmitters in the area.
  • Transmitter(s) localization techniques based on RSS are the most popular ones because of their simplicity and direct applicability to commercial off-the-shelf radio hardware.
  • the literature extensively addresses the problem of single-source localization with the multiple source case receiving far less attention due to its inherent difficulty owed to:
  • ML Maximum Likelihood
  • POCS Projection On Convex Sets
  • SDP Semi-Definite Programming
  • An object of the present invention is to provide a solution which mitigates or solves the drawbacks and problems of prior art solutions.
  • Another object of the invention is to provide simplified solution to the above problem.
  • any method according to the present invention can be executed as a computer program in processing means, and may be comprised in a computer program product.
  • the present invention provides a solution having an improved computational complexity (e.g. compared to the full-blown ML approach). Further, the present solution has better performance in terms of higher accuracy of the estimations compared to prior art solutions.
  • Fig. 1 shows an example problem scenario for 2 radio transmitters and 5 sensors in which the 2 transmitters operate at unknown locations in an area.
  • the 5 distributed sensors measure received signal strength from the radio transmitters and forward measurements to a central processing unit;
  • Fig. 2 shows a flow chart of an embodiment of the present invention.
  • the present invention relates to a method for determining powers and locations of active radio transmitters in an area based on received signal strengths measured at a number of sensors distributed over the area.
  • this particular problem leads to very complex mathematical problems but the present method provides a simplified model which is possible to solve.
  • the received power at sensor z is, in linear scale (small letters signifying linear scale):
  • RSSi j P j + L Q - PL (Xj, Si ) + Ui (2)
  • L 0 is a reference path loss and n £ is the log-normal shadow-fading component with variance ⁇ 2 and PL(x j , s ⁇ ) is a suitable deterministic path loss function.
  • PL(x j , s ⁇ ) is a suitable deterministic path loss function.
  • PLixp St 10g log 10 J
  • d 0 is the reference distance, typically close to the transmitter chosen such that the path loss at d 0 (in free space) equals L 0 , and is the path loss exponent.
  • the eq. (1) becomes a sum of log-normal variables and, with the standard Gaussian approximation for the sum of log-normal variables to approximate (1), the received power at sensor i is Gaussian distributed with mean ⁇ and variance a :
  • the problem solved by the present invention is to then find the locations and powers collected in the vector ⁇ from a (large) number N s of observed values rsS j .
  • N s the number of observed values
  • RSS RSS 2 , ... , is the vector of observed measurements
  • the inventors have however imposed an approximation for each received power sample, which allows the mapping of the original problem to the Gaussian Mixture Model (GMM) fitting problem.
  • the GMM is a probabilistic model representing the appearance of several Gaussian variables underlying the observed data. It is a probabilistic model for representing the presence of subpopulations within an overall population without requiring that an observed-dataset should identify the sub-population to which any individual observation belongs.
  • Each observed data sample is modelled as having been generated by one of a group of Gaussian distributions (typically, with different means and variances); however, unknown by which at the time of observation. The process of associating the collected observations to these distributions and also finding their corresponding moments is usually referred to as "clustering".
  • the model not only represents the means and variances of the component Gaussian distributions, but also the prior probability (or prior mixture weight) for each of the components indicating the prior probability that an observed sample originates from that particular component.
  • the present approximation consists of assigning one dominant source per sensor. If it is assumed that a single source contributes most of the measured power to each sensor, then:
  • Empirical experience has shown this to be valid, especially for indoor scenarios where the path loss is a higher number.
  • each signal measurement is assumed to originate from exactly one of the unknown Gaussian distributions.
  • the means of the K components are parameterized by i, because the mean value of each mode at the z ' -th sensor depends on its position.
  • the ML problem can now be solved with the EM algorithm. So, by using the EM algorithm on the measured signal strengths at the sensors the above stated problem can be solved as a simpler ML problem, i.e. GMM. It is noted that the EM algorithm has never before been used for solving this type of problem.
  • Table 1 Algorithm for EM-GMM based localization of K radio transmitters sources from N s sensor measurements for channel model in eq. (2) (where d 0 and L 0 are the reference distance and power loss, a is the path loss exponent and the variance of the log-normal shadow-fading component is ⁇ 2 ).
  • an initial estimate of the positions and powers in the vector ⁇ and the weights Wj are computed (for instance at random). These initialized values completely determine the RSS.
  • the (scalar) likelihood of this initial solution ⁇ is also computed.
  • the probabilities that a measurement i is due to radio transmitter j is then computed.
  • estimate of the positions and powers in the vector ⁇ and the weights Wj are re-computed, now using the probabilities of the expectation- step.
  • the scalar likelihood of the solution ⁇ is computed and if this likelihood exhibits an increase higher than a certain threshold value ⁇ , (which can be an arbitrary small number heuristically chosen to control the convergence), and a new iteration is started by jumping back to the expectation step.
  • a certain threshold value ⁇ (which can be an arbitrary small number heuristically chosen to control the convergence)
  • the maximization step involves an optimization step, but, in contrast to the original ML-search, this step now involves a standard non-linear weighted Least-Squares (LS) problem, usually encountered in the problem of localizing a single transmitter source. Regardless of the searching algorithm employed to solve this optimization, the complexity of this search grows only linearly with the number of transmitters K.
  • LS Least-Squares
  • the number of radio transmitters K may also be determined which is another advantage with the present method. So far it has been assumed the number of radio sources K is known. Since the actual number is typically not known in advance, either the Akaike Information Criterion (AIC) or the Minimum Description Length (MDL) principle is applied.
  • AIC Akaike Information Criterion
  • MDL Minimum Description Length
  • Table 2 EM-GMM localization for unknown number of radio transmitter sources.
  • L(K) is the likelihood value computed in step d) above.
  • L(K) is the likelihood value computed in step d) above.
  • the sensors are distributed over the area and may comprise only one receive antenna each. There is no restriction to the distribution of the sensors in the area so they can e.g. be random or deterministic.
  • the radio transmitters it is assumed that they operate in overlapping frequency bands, and often in the same frequency band(s).
  • the radio transmitters can be base stations of a cellular operating system such as LTE.
  • any method according to the present invention may also be implemented in a computer program, having code means, which when run by processing means causes the processing means to execute the steps of the method.
  • the computer program is included in a computer readable medium of a computer program product.
  • the computer readable medium may comprises of essentially any memory, such as a ROM (Read-Only Memory), a PROM (Programmable Read-Only Memory), an EPROM (Erasable PROM), a Flash memory, an EEPROM (Electrically Erasable PROM), or a hard disk drive.
  • the invention also relates to a central processing unit arranged to execute the present method. It is therefore realised that the central processing unit may be modified, mutatis mutandis, according to different embodiments of the present method.
  • the central processing unit comprises processing means for processing data and memory means for storing data, and further comprises suitable means such as receiving means and transmitting means for receiving and transmitting data, such as received signal strengths measured at the sensors.
  • the present device is further arranged to use the above described EM method for determining the powers P j and locations Xj of the plurality of radio transmitters based on the plurality of received signal strengths measured at sensors.
  • the central processing unit may according to an embodiment be integrated in a communication node of a radio access network (RAN), e.g. a base station or a radio network controller.
  • RAN radio access network
  • the central processing unit may according to an embodiment be integrated in a communication node of a radio access network (RAN), e.g. a base station or a radio network controller.
  • the central processing unit may instead be implemented in, and being a part of an operation and management (O&M) entity controlled by mobile operators.
  • O&M operation and management
  • the information about the number, locations and powers of the radio transmitters is directly available at the network level which means that the information can be used for the beneficial operation and management of the radio network.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

The present invention relates to a method for determining powers and locations of j = 1,..., K numbers of radio transmitters based on a plurality of received signal strengths measured at i = 1,..., N s number of sensors, where K and N s are positive integers and K 2 and N s ≥ 1, respectively; the method comprising the step of: using the expectation-maximization (EM) method for determining the powers P j and locations X j of the j = 1,..., K numbers of radio transmitters based on the plurality of received signal strengths measured at the i = 1,..., N s number of sensors. Furthermore, the invention also relates to a computer program, a computer program product, and a central processing unit thereof.

Description

METHOD FOR DETERMINING POWERS AND LOCATIONS OF RADIO
TRANSMITTERS
Technical Field
The present invention relates to a method for determining powers and locations of radio transmitters. Furthermore, the invention also relates to a computer program, a computer program product, and a central processing unit thereof.
Background of the Invention
Passive transmitter localization via sensor networks is an important topic for many wireless applications since localization of unknown radio sources is likely to become a key component in future, next generation radio communication networks. Endowed with the capability to sense and record radio-activity in the surrounding environment, central operators or other relevant radio network management entities can then efficiently plan, decide upon and execute respective actions by their networks.
In general, the environmental awareness that comes with the knowledge of unknown transmitters' locations is likely to become instrumental in future self-organizing networks where, for instance, the power, frequency or other crucial radio parameters are (automatically) adapted based on the environmental knowledge gathered from massive-scale sensor networks and their affiliated measurements ("observations", "observed data"). Next-generation cellular networks for instance can benefit from such self-organizing capabilities through increased cost efficiency (the reduction of the operational expenses, OPEX) and through increased spectrum and energy efficiency.
Benefits can result for operators and regulators alike; the first to improve network operation, the second to detect and locate malicious and non-licensed spectrum users.
Most projections and forecasts about future cellular networks predict a huge increase of the number of radio transmitters. A key enabler to providing higher data rates is the densification of network infrastructure, i.e. more transmitters per unit area. Figure 1 illustrates the problem scenario that is addressed by the present invention. In an area of interest, two or more active radio transmitters operate in a certain frequency band. The location, power, type or any other relevant parameter of these radio transmissions is unknown. The number of active radio transmitters is also unknown. A possibly high number of distributed sensors perform measurements of the Received Signal Strength (RSS) caused by these unknown transmitters at the respective sensor locations and forward these respective measurements to a central network node. The forwarded measurements may contain relevant labels such as the time of the measurements, the frequency band of the measurements, the location/coordinates of the sensor etc.
A common problem arising in these multi-transmitter scenarios is the complexity in distinguishing components of the measured RSS due to different radio transmitters. This complicates multi-transmitter localization problem. The problem is then to accurately determine the unknown number, the unknown power(s) and the unknown location(s) of the radio transmitters in the area.
Transmitter(s) localization techniques based on RSS are the most popular ones because of their simplicity and direct applicability to commercial off-the-shelf radio hardware. However, the literature extensively addresses the problem of single-source localization with the multiple source case receiving far less attention due to its inherent difficulty owed to:
i. the lack of commercial scenarios where multiple non-orthogonal sources overlap in the same band, and
ii. the rather high cost for deploying many sensors, which is a necessary condition for accurate localization.
However, the potential for cognitive-radio applications (see coexistence issues in IEEE 802.19 and 802.22) plus the decreasing cost of sensors are changing this reality. A number of approaches to the localization problem exist in the art. ML estimation
Maximum Likelihood (ML) is a popular estimation approach due to its asymptotic optimality. However, the likelihood function in a log-normal propagation environment typically possesses multiple maxima, thus resulting in a non-convex optimization problem. This becomes the most significant drawback of the ML approach. Standard techniques for such non-convex optimization tend to be very complex. In addition, computation increases exponentially with the number of sources which is another major drawback with the ML estimation.
The problem of local maxima for a single source has been addressed via Projection On Convex Sets (POCS). The algorithm is of low complexity, robust to local maxima and possesses a distributable computation. The distance estimates also employ RSS, but the algorithm can also be used for any positioning method where sensor-source distance estimates are somehow available. The method, named "circular" POCS, performs well when the (single) source node is located inside the sensor convex hull defined by the outer perimeter nodes in the sensor network. It also requires knowledge of parameters such as path loss and transmission power. The disadvantage with this solution is that it solves the single-source case only.
Another method for addressing the non-convexity of conventional ML is the Semi-Definite Programming (SDP) relaxation technique. The idea here is to convert the non-convex quadratic-distance constraints into linear constraints by introducing a relaxation that removes the quadratic term in the formulation. The SDP method has been only applied to the single- source case. In addition, the transmit power of the radio transmitters must be known.
Approaches with simplified channel models and known number of sources
For multiple sources, research has mostly focused on the AWGN model, which is valid for acoustic sources. The same AWGN model has been applied to radio applications, but this is an over-simplification for log-normal shadowing environments. Other prior art proposes a global optimization methodology. A clustering algorithm has been introduced based on k- means, for enhancing convergence and reducing overall complexity. For the same AWGN model, a quasi EM method has been proposed. All the above techniques assume knowledge of the number of sources. The inherent sparsity (small number of sources, large number of measurements) has been exploited in order to improve estimation by suitably modifying the Least- Absolute Shrinkage and Selection Operator (LASSO).
Grid-based approaches The first attempt at a full-blown ML was by approximating the sum of log-normal random variables. The challenge of not knowing the number of sources was addressed by placing a large number of hypothetical sources on a grid (i.e. each grid point corresponds to a potential source), thus leading to over-fitting issues. Mentioned over-fitting issues lead to bad performance.
Other approaches
Other prior art solves the problem by adopting a deterministic approach. The disadvantage here is that no shadow fading is taken into account and the robustness of the method in such environments suffers.
Thus, there is a need in the art for an improved method for determining powers and locations of radio transmitters in an area. Summary of the Invention
An object of the present invention is to provide a solution which mitigates or solves the drawbacks and problems of prior art solutions. Another object of the invention is to provide simplified solution to the above problem. According to a first aspect of the invention, the above mentioned objects are achieved by a method for determining powers and locations of j = 1, ... , K numbers of radio transmitters based on a plurality of received signal strengths measured at i = 1, ... , NS number of sensors, where K and Ns are positive integers and K≥ 2 and Ns ≥ 1, respectively; the method comprising the step of:
using the expectation-maximization method for determining the powers Pj and locations
Xj of the j = 1, ... , K numbers of radio transmitters based on the plurality of received signal strengths measured at the i = 1, ... , Ns number of sensors.
Preferred embodiments of the invention are defined in the appended dependent claims. Any method according to the present invention can be executed as a computer program in processing means, and may be comprised in a computer program product. According to a second aspect of the invention, the above mentioned objects are achieved with a central processing unit comprising processing means for processing data and memory means for storing data, and further comprising receiving means and transmitting means for receiving and transmitting data, respectively, the central processing unit being arranged to determining powers and locations of j = 1, ... , K numbers of radio transmitters based on a plurality of received signal strengths measured at i = 1, ... , NS number of sensors, where K and Ns are positive integers and K≥ 2 and Ns ≥ 1, respectively, by further being arranged to use the expectation-maximization method for determining the powers Pj and locations Xj of the j = 1, ... , K numbers of radio transmitters based on the plurality of received signal strengths measured at the i = 1, ... , Ns number of sensors.
The present invention provides a solution having an improved computational complexity (e.g. compared to the full-blown ML approach). Further, the present solution has better performance in terms of higher accuracy of the estimations compared to prior art solutions.
Further applications and advantages of the invention will be apparent from the following detailed description.
Brief Description of the Drawings
The appended drawings are intended to clarify and explain different embodiments of the present invention in which:
Fig. 1 shows an example problem scenario for 2 radio transmitters and 5 sensors in which the 2 transmitters operate at unknown locations in an area. The 5 distributed sensors measure received signal strength from the radio transmitters and forward measurements to a central processing unit; and
Fig. 2 shows a flow chart of an embodiment of the present invention.
Detailed Description of the Invention
To achieve the aforementioned and other objects, the present invention relates to a method for determining powers and locations of active radio transmitters in an area based on received signal strengths measured at a number of sensors distributed over the area. As mentioned above, this particular problem leads to very complex mathematical problems but the present method provides a simplified model which is possible to solve.
With reference to the problem statement, the received power at sensor z is, in linear scale (small letters signifying linear scale):
rsst =∑f=1 rssi (1) where K is the number of radio transmitters (radio sources) in an area. A standard log- distance model for the received energy RSSt j (capital letters signifying scale in dB) of the z'-th sensor at location st from source j with transmit power Pj at distance dt j is
RSSij = Pj + LQ - PL (Xj, Si) + Ui (2) where L0 is a reference path loss and n£ is the log-normal shadow-fading component with variance σ2 and PL(xj, s^) is a suitable deterministic path loss function. One possible choice of this function is
\\x-— s \\
PLixp St) = 10g log10 J where d0 is the reference distance, typically close to the transmitter chosen such that the path loss at d0 (in free space) equals L0, and is the path loss exponent.
Using eq. (2), the eq. (1) becomes a sum of log-normal variables and, with the standard Gaussian approximation for the sum of log-normal variables to approximate (1), the received power at sensor i is Gaussian distributed with mean έ and variance a :
β55έ~Ν(μέ (β), σέ 2 (0)) (3) The means and variances are:
Figure imgf000008_0001
and
μ. (0) = c-1
Figure imgf000008_0002
- - c a {e) + - ca2 (5)
where
mi (ej) = Pj - PL(xj, si) (6) is the mean energy received at the z'-th sensor when only the j-th source is active, Θ = [x±, yi, 2 > ?2,— ' χκΎκ> PR] is me J- T-length vector of the parameters to be estimated (x-coordinate, y-coordinate, and power), σ2 is the common shadow fading variance and c = (In 10)/10 is a dB-scale normalization constant.
Using this signal model, the problem solved by the present invention is to then find the locations and powers collected in the vector Θ from a (large) number Ns of observed values rsSj. Each of the Ns sensors gives one such observation.
One solution to the problem is found by the ML estimation, which involves the minimization of the negative log-likelihood function with respect to 0 (see [14]):
arg min L (RSS; 0) (7)
Θ
where RSS = RSS2, ... ,
Figure imgf000009_0001
is the vector of observed measurements and
L (RSS; 0) = In (inaf (0)) + *5 ff > (8) where Ns is the number of sensors in the area. This minimization (search for 0) involves non- convex optimization of dimension 3K with multiple minima. In general this minimization is prohibitively complex.
The inventors have however imposed an approximation for each received power sample, which allows the mapping of the original problem to the Gaussian Mixture Model (GMM) fitting problem. The GMM is a probabilistic model representing the appearance of several Gaussian variables underlying the observed data. It is a probabilistic model for representing the presence of subpopulations within an overall population without requiring that an observed-dataset should identify the sub-population to which any individual observation belongs. Each observed data sample is modelled as having been generated by one of a group of Gaussian distributions (typically, with different means and variances); however, unknown by which at the time of observation. The process of associating the collected observations to these distributions and also finding their corresponding moments is usually referred to as "clustering". Typically, a GMM involves random variable y modelled as a weighted sum of Gaussian variables, i.e. : y~∑f=1 w^N^j, a ~) . The model not only represents the means and variances of the component Gaussian distributions, but also the prior probability (or prior mixture weight) for each of the components indicating the prior probability that an observed sample originates from that particular component. The present approximation consists of assigning one dominant source per sensor. If it is assumed that a single source contributes most of the measured power to each sensor, then:
rsSi « maxj rss; j (9)
Empirical experience has shown this to be valid, especially for indoor scenarios where the path loss is a higher number. For example, assume that a sensor is at the same rough distance from two equal-power sources. Then the sum received power will just be 3dB above the single- source one. This 3 dB falls well within the usual indoor shadowing standard deviation. With this assumption the model becomes a GMM. Namely, using eq. (9) (in dB), the measurements are then approximated as Ns independent, identically distributed samples RSS , RSS2 , . .. , RSSNs , derived from a GMM with K components of associated parameters 8t =
Furthermore, each signal measurement is assumed to originate from exactly one of the unknown Gaussian distributions. The means of the K components are parameterized by i, because the mean value of each mode at the z'-th sensor depends on its position.
The EM algorithm applied to estimation of the unknown parameters μ^ , af , and Wj of the GMM is
Figure imgf000010_0001
We apply it here to the localization problem and model derived in the previous section for the particular case where the variance for all Gaussian components are the same: af = σ2 for all
]
The log-likelihood function of the G
L (RSS; Θ) = (e), a2)j
Figure imgf000010_0002
where the variances are no longer functions of the distances, since the shadowing is modeled to be the same for all transmitters. Hence, by carefully study the above stated problem and by making the above mentioned assumptions, the ML problem can now be solved with the EM algorithm. So, by using the EM algorithm on the measured signal strengths at the sensors the above stated problem can be solved as a simpler ML problem, i.e. GMM. It is noted that the EM algorithm has never before been used for solving this type of problem.
The method steps of an embodiment of the present invention (for a fixed number of radio transmitters) are given in the flow chart of Figure 2 and Table I below.
Table 1 : Algorithm for EM-GMM based localization of K radio transmitters sources from Ns sensor measurements for channel model in eq. (2) (where d0 and L0 are the reference distance and power loss, a is the path loss exponent and the variance of the log-normal shadow-fading component is σ2).
Input: number of sources K, measurements RSS s£ for i = 1, ... , Ns
Output: locations $j, powers Pj, for j = 1, ... , K, and likelihood L.
a) (Initialization step) Initialize the iteration-index m = 0, and, for all j = Ι, .,. , Κ, choose initial estimates: (powers), x ^ (locations), along with initial weights
Figure imgf000011_0001
Compute the initial means
Figure imgf000011_0002
and the initial log-likelihood
Figure imgf000011_0003
b) (Expectation-step) For all i = 1, ... , Ns, and j = 1, ... , K,
Compute
Figure imgf000011_0004
c) (Maximization step) Compute the new weight-estimates yJ s (m)
(m+1) _
w J, γΚ yNs v(m) ' (weights)
For each _/ = 1, ... , K, compute the location-estimate +1) = (locations)
Figure imgf000012_0001
where
Figure imgf000012_0002
Finally, for each j = 1, ... , K, compute P- = Pj ( ) ), (powers) d) (Convergence step) Compute the means
μ «+1) = _ Lq _ PL (^+1)j S .) and the log-likelihood σ2))
Figure imgf000012_0003
if |L^m+1^— Z m) I < 5 (a fixed predetermined threshold)
increase m: m = m + 1 (m is the iteration index) and return to step b, otherwise
output J,- = xjm+1) and Pj = Py (m+1) for ; = 1, AT, and L = Z m+1) .
In the first initialization-step, an initial estimate of the positions and powers in the vector Θ and the weights Wj are computed (for instance at random). These initialized values completely determine the RSS. The (scalar) likelihood of this initial solution Θ is also computed.
In the expectation step, for the assumed RSS, the probabilities that a measurement i is due to radio transmitter j is then computed. In the maximization step, estimate of the positions and powers in the vector Θ and the weights Wj are re-computed, now using the probabilities of the expectation- step.
In the convergence step, the scalar likelihood of the solution Θ is computed and if this likelihood exhibits an increase higher than a certain threshold value δ, (which can be an arbitrary small number heuristically chosen to control the convergence), and a new iteration is started by jumping back to the expectation step.
The specific equations involved in each of the steps are shown in Table I. The maximization step involves an optimization step, but, in contrast to the original ML-search, this step now involves a standard non-linear weighted Least-Squares (LS) problem, usually encountered in the problem of localizing a single transmitter source. Regardless of the searching algorithm employed to solve this optimization, the complexity of this search grows only linearly with the number of transmitters K.
According to a preferred embodiment of the invention, the number of radio transmitters K may also be determined which is another advantage with the present method. So far it has been assumed the number of radio sources K is known. Since the actual number is typically not known in advance, either the Akaike Information Criterion (AIC) or the Minimum Description Length (MDL) principle is applied.
The basic idea is to run the method in Table I for different number of assumed number of transmitters K and choose the number K for which the likelihood is highest. Since the likelihood increases with K, both the AIK and the MDL method in the literature provide the means to normalize the likelihood with respect to K and are used in a stopping criterion in a sequential search for K. In Table 2 the further method steps of the proposed localization algorithm without a prior assumption on the number of radio transmitters K is summarized.
Table 2: EM-GMM localization for unknown number of radio transmitter sources. Input: RSS st for i = 1, ... , Ns.
Output: K and $j 5 Pj for j = 1, ... , K.
1. Set K = 1. Then execute EM-GMM and store the resulting likelihood as L (l). 2. Increase K: K = K + 1. Then execute EM-GMM and store the resulting likelihood as L (K) .
Compute C(K) = -L (K) + K (AlC-method),
or compute C(K) =—L (K) + - \og Ns (MDL-method).
3. if C(K) < C(K - 1) return to step 2,
otherwise output K, and the estimates Xj , Pj for j = 1, ... , K obtained in the most recent execution of the EM-GMM method.
In either of the cases, the EM-algorithm is run for increasing K, starting with K=l, and stopped as soon as the criterion- value stops decreasing, that is when:
C(K) ≥ C (K - l) (1 1)
The value for the criterion typically decreases when K= \ , 2,... However, for a certain value of K the decrease stops and the algorithm is terminated.
According to another embodiment of the invention the AIC computes:
C(K) = -L(K) + K (12)
where L(K) is the likelihood value computed in step d) above.
According to yet another embodiment of the invention the MDL computes:
C0O = -L0O + ^ log Ns (13)
where L(K) is the likelihood value computed in step d) above.
The sensors are distributed over the area and may comprise only one receive antenna each. There is no restriction to the distribution of the sensors in the area so they can e.g. be random or deterministic. Regarding the radio transmitters it is assumed that they operate in overlapping frequency bands, and often in the same frequency band(s). For example, the radio transmitters can be base stations of a cellular operating system such as LTE.
Furthermore, as understood by the person skilled in the art, any method according to the present invention may also be implemented in a computer program, having code means, which when run by processing means causes the processing means to execute the steps of the method. The computer program is included in a computer readable medium of a computer program product. The computer readable medium may comprises of essentially any memory, such as a ROM (Read-Only Memory), a PROM (Programmable Read-Only Memory), an EPROM (Erasable PROM), a Flash memory, an EEPROM (Electrically Erasable PROM), or a hard disk drive.
Moreover, the invention also relates to a central processing unit arranged to execute the present method. It is therefore realised that the central processing unit may be modified, mutatis mutandis, according to different embodiments of the present method. The central processing unit comprises processing means for processing data and memory means for storing data, and further comprises suitable means such as receiving means and transmitting means for receiving and transmitting data, such as received signal strengths measured at the sensors. The present device is further arranged to use the above described EM method for determining the powers Pj and locations Xj of the plurality of radio transmitters based on the plurality of received signal strengths measured at sensors.
The central processing unit may according to an embodiment be integrated in a communication node of a radio access network (RAN), e.g. a base station or a radio network controller. By integrating the central processing unit in the communication node of a RAN the cost can be reduced.
However, the central processing unit may instead be implemented in, and being a part of an operation and management (O&M) entity controlled by mobile operators. Thereby, the information about the number, locations and powers of the radio transmitters is directly available at the network level which means that the information can be used for the beneficial operation and management of the radio network.
Finally, it should be understood that the present invention is not limited to the embodiments described above, but also relates to and incorporates all embodiments within the scope of the appended independent claims.

Claims

1. Method for determining powers and locations of j = 1, ... , K numbers of radio transmitters based on a plurality of received signal strengths measured at i = 1, ... , Ns number of sensors, where K and Ns are positive integers and K≥ 2 and Ns ≥ 1, respectively; the method comprising the step of:
using the expectation-maximization (EM) method for determining the powers Pj and locations Xj of the j = 1, ... , K numbers of radio transmitters based on the plurality of received signal strengths measured at the i = 1, ... , Ns number of sensors.
2. Method according to claim 1 , wherein the received power at sensor i in linear scale is rssi rsSi , and the method further comprises the step of:
assuming that rss^ « maxj rss; j .
3. Method according to claim 2, wherein the step of using involves the steps of:
a) determining K number of initial powers and locations for the K number of radio transmitters, and determining an initial likelihood value based on the initial powers and locations;
b) computing a probability gamma yfy for each sensor-radio transmitter pair i,j based on the plurality of received signal strengths measured at the i = 1, ... , Ns number of sensors; c) determining updated K number of powers p -m+ ) and locations Xjm+1) based on the probability gamma for each sensor-radio transmitter pair
d) determining a likelihood value L^m+1^ based on the updated K number of powers p(.m+1 an(j iocatjons ^rn+1'); and e) repeating steps b) - d) above m times until a convergence criterion based on the likelihood-value is satisfied, where m is the iteration index.
4. Method according to claim 3, wherein step a) involves:
computing the initial likelihood value as,
L = ∑£1 ln (∑ =1 w(0)N ((«55i | ,((:), 2
i,J where N
Figure imgf000017_0001
and variance σ2 evaluated for the value RSSt, and denotes a weight value associated with the jth transmitter.
5. Method according to claim 3, wherein step b) involves:
com uting the probability gamma for each sensor-radio transmitter pair i,j as,
where and
Figure imgf000017_0002
variance σ2 evaluated for the value RSST , and denotes a weight value associated with the jth transmitter.
6. Method according to claim 3, wherein step c) involves:
computing the updated K number of locations Xjm+ 1^ and the associated K number of powers Pj \ Xj ) as, +1) = arg
Figure imgf000017_0003
(RSS, - Pj{x) + PL{x, sd) where Ρ,Ο) = -^^ Σ -Ι^ - PLfa s )2,
^i=i Yi ,j
and where PL(x, s ) is a deterministic path loss function and st is the location of the ith sensor.
Method according to claim 3, wherein step d) involves:
computin the likelihood value L^m+1^ as,
L(m+i) 1)N ((/?55i| [ ( +1), 2 where denotes the Gaussian distribution function with mean
Figure imgf000017_0004
μΐ^+1^ and variance σ2 evaluated for the value RSSt, and Wj m+1^ denotes a weight value associated with the jth transmitter.
8. Method according to claim 3, wherein the convergence criterion is compared to a threshold value δ such that
Figure imgf000018_0001
- < δ.
9. Method according to claim 3, wherein the steps a) - d) are repeated for an assumed number of radio transmitters until a stop criterion is satisfied so as to obtain the number of radio transmitters K.
10. Method according to claim 9, wherein the stop criterion is the Akaike information criterion (AIC) and based on the value of: C(K) =—L (K) + K, where L (K) is the likelihood value Z °) determined in step d).
1 1. Method according to claim 9, wherein the stop criterion is the Minimum Description Length (MDL) criterion and based on the value of: C(K) =—L (K) + - log Ns, where L(K) is the likelihood value determined in step d).
12. Method according to claim 1 , wherein the method further comprises the step of: receiving the plurality of received signal strengths measured at i = 1, ... , NS number of sensors.
13. Method according to claim 1 , wherein the i = 1, ... , NS number of sensors are distributed over an area.
14. Method according to claim 1 , wherein the i = 1, ... , NS number of sensors only comprises one receiving antenna each.
15. Method according to claim 1 , wherein the j = 1, ... , K numbers of radio transmitters operates in overlapping frequency bands.
16. Computer program, characterised in code means, which when run by processing means causes said processing means to execute said method according to any of claims 1-15.
17. Computer program product comprising a computer readable medium and a computer program according to claim 16, wherein said computer program is included in the computer readable medium, and comprises of one or more from the group: ROM (Read-Only Memory), PROM (Programmable ROM), EPROM (Erasable PROM), Flash memory, EEPROM (Electrically EPROM) and hard disk drive.
18. Central processing unit comprising processing means for processing data and memory means for storing data, and further comprising receiving means and transmitting means for receiving and transmitting data, respectively, the central processing unit being arranged to determining powers and locations of j = 1, ... , K numbers of radio transmitters based on a plurality of received signal strengths measured at i = 1, ... , NS number of sensors, where K and Ns are positive integers and K≥ 2 and Ns ≥ 1, respectively, by further being arranged to use the expectation-maximization (EM) method for determining the powers Pj and locations Xj of the j = 1, ... , K numbers of radio transmitters based on the plurality of received signal strengths measured at the i = 1, ... , Ns number of sensors.
19. Central processing unit according to claim 18, wherein said central processing unit is integrated in a communication node of a radio access network (RAN).
20. Central processing unit according to claim 18, wherein said central processing unit is part of an operation and management (O&M) entity.
PCT/EP2012/074174 2012-11-30 2012-11-30 Method for determining powers and locations of radio transmitters WO2014082686A1 (en)

Priority Applications (2)

Application Number Priority Date Filing Date Title
CN201280077285.8A CN104871615A (en) 2012-11-30 2012-11-30 Method for determining powers and locations of radio transmitters
PCT/EP2012/074174 WO2014082686A1 (en) 2012-11-30 2012-11-30 Method for determining powers and locations of radio transmitters

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/EP2012/074174 WO2014082686A1 (en) 2012-11-30 2012-11-30 Method for determining powers and locations of radio transmitters

Publications (1)

Publication Number Publication Date
WO2014082686A1 true WO2014082686A1 (en) 2014-06-05

Family

ID=47504842

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/EP2012/074174 WO2014082686A1 (en) 2012-11-30 2012-11-30 Method for determining powers and locations of radio transmitters

Country Status (2)

Country Link
CN (1) CN104871615A (en)
WO (1) WO2014082686A1 (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
RU2757672C1 (en) * 2020-11-24 2021-10-20 Акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" Machine-oriented method for local positioning of ground objects based on rangefinder calculations

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN107454618A (en) * 2017-05-27 2017-12-08 柳州天艺科技有限公司 More primary user's localization methods based on EM

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8213389B2 (en) * 2008-04-15 2012-07-03 Apple Inc. Location determination using formula
US8644843B2 (en) * 2008-05-16 2014-02-04 Apple Inc. Location determination
US8519889B2 (en) * 2009-07-21 2013-08-27 Research In Motion Limited Method and apparatus for estimating location of a wireless station using multi-beam transmission

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
JILL K NELSON ET AL: "An EM Technique for Multiple Transmitter Localization", INFORMATION SCIENCES AND SYSTEMS, 2007. CISS '07. 41ST ANNUAL CON FERENCE ON, IEEE, PI, 1 March 2007 (2007-03-01), pages 610 - 615, XP031131933, ISBN: 978-1-4244-1063-7 *
JILL K NELSON ET AL: "Estimating multiple transmitter locations from power measurements at multiple receivers", ACOUSTICS, SPEECH AND SIGNAL PROCESSING, 2009. ICASSP 2009. IEEE INTERNATIONAL CONFERENCE ON, IEEE, PISCATAWAY, NJ, USA, 19 April 2009 (2009-04-19), pages 2761 - 2764, XP031459841, ISBN: 978-1-4244-2353-8 *
NELSON J K ET AL: "A Quasi EM Method for Estimating Multiple Transmitter Locations", IEEE SIGNAL PROCESSING LETTERS, IEEE SERVICE CENTER, PISCATAWAY, NJ, US, vol. 16, no. 5, 1 May 2009 (2009-05-01), pages 354 - 357, XP011253703, ISSN: 1070-9908 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
RU2757672C1 (en) * 2020-11-24 2021-10-20 Акционерное общество "Калужский научно-исследовательский институт телемеханических устройств" Machine-oriented method for local positioning of ground objects based on rangefinder calculations

Also Published As

Publication number Publication date
CN104871615A (en) 2015-08-26

Similar Documents

Publication Publication Date Title
Wang et al. Cooperative RSS-based localization in wireless sensor networks using relative error estimation and semidefinite programming
Jang et al. Indoor positioning technologies without offline fingerprinting map: A survey
Wang et al. RSSI-based bluetooth indoor localization
Yan et al. An improved NLOS identification and mitigation approach for target tracking in wireless sensor networks
Wu et al. Location estimation via support vector regression
Wang et al. Cramer-Rao bounds for joint RSS/DoA-based primary-user localization in cognitive radio networks
EP3161505B1 (en) Efficient location determination of wireless communication devices using hybrid localization techniques
Matic et al. Tuning to your position: FM radio based indoor localization with spontaneous recalibration
WO2012099905A2 (en) Method and apparatus for learning of the parameters of a fingerprint prediction map model
AU2006321675A1 (en) System and method for computing the position of a mobile device operating in a wireless network
Xiao et al. Study of fingerprint location algorithm based on WiFi technology for indoor localization
Shih et al. Intelligent radio map management for future WLAN indoor location fingerprinting
Manickam et al. Range‐based localisation of a wireless sensor network using Jaya algorithm
Wang et al. IWKNN: An effective Bluetooth positioning method based on Isomap and WKNN
Cheng et al. Integrated factor graph algorithm for DOA-based geolocation and tracking
Zhu et al. Localisation algorithm with node selection under power constraint in software‐defined sensor networks
Denkovski et al. Practical assessment of RSS-based localization in indoor environments
Mabunga et al. Utilization of different wireless technologies’ rssi for indoor environment classification using support vector machine
Munadhil et al. Distance estimation-based PSO between patient with Alzheimer’s disease and beacon node in wireless sensor networks
Aravecchia et al. Gaussian process for rss-based localisation
WO2014082686A1 (en) Method for determining powers and locations of radio transmitters
Liu et al. A wireless location system in LTE networks
US20220129767A1 (en) Transmitter identifying apparatus, transmitter identifying method, and program
Yilmaz et al. Sensor placement algorithm for radio environment map construction in cognitive radio networks
Kordi et al. Survey of Indoor Localization Based on Deep Learning.

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 12810128

Country of ref document: EP

Kind code of ref document: A1

NENP Non-entry into the national phase

Ref country code: DE

122 Ep: pct application non-entry in european phase

Ref document number: 12810128

Country of ref document: EP

Kind code of ref document: A1