Note: Descriptions are shown in the official language in which they were submitted.
CA 02907723 2015-09-18
SCALABLE REAL-TIME LOCATION DETECTION BASED ON
OVERLAPPING NEURAL NETWORKS
FIELD OF THE INVENTION
[0002] The
invention relates to wireless object location tracking and,
more particularly, to a system and method for object location detection
employing interrelated overlapping neural networks.
BACKGROUND OF THE INVENTION
[0003] Real Time Location Systems (RTLSs) track objects, typically by
associated tags. For
individuals, a badge is used for tracking in
environments such as health-care facilities, warehouses, and other areas
where location is important. Personnel badges and asset tags may include
Radio Frequency Identification (RFID) (passive or active), and
communicate with fixed or hand-held readers.
[0004] While known tags and communication standards such as Wi-Fi
(802.11) may hold the potential for full-scale deployment - tracking many
objects in real-time - in reality, they fall short. For example, accuracy is
impaired by an inability to overcome multipath effects of the tracking
environment. Time delays from processing bottlenecks result when
1
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
realistic quantities of objects are tracked. This leads to stale, inaccurate,
object location indications and even loss of tracking.
[0005] What is needed are systems to monitor the location of people and
items in real-time that scale with the requirements of the application.
SUMMARY OF THE INVENTION
[0006] Embodiments of the present invention include a system and
method for real-time location detection of a wireless transmitter.
Embodiments include an RFID tag or other communication device with
transmitting capability. While embodiments apply to indoor real-time
tracking, system deployment is not limited to this and systems can be
deployed outdoors, or in combination. Embodiments apply in other
scenarios.
[0007] An embodiment provides a scalable system for real-time location
determination of at least one object by sub-networks of interrelated neural
networks comprising at least one transmitting tag associated with each of at
least one object; a plurality of a priori defined interrelated location
classifier sub-networks comprising location classifier receivers; the
location classifier receivers configured to receive at least one transmission
from at least one transmitting tag; wherein the system is configured to
engage only one of the plurality of sub-networks to output a location of at
least one object; and whereby scaling of the system is achieved by
engaging only one sub-network of the plurality of sub-networks to output
the location for each of at least one object. In another embodiment the
sub-networks of interrelated neural networks overlap spatially. For a
following embodiment at least one transmitting tag is configured to receive
at least one physical measurement value from at least one router/base
station/access point and transmit at least one physical measurement value
to a system central server processing and command station. In subsequent
embodiments the system is configured to select a sub-network having the
2
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
greatest number of the location classifier receivers receiving at least one
transmission from at least one transmitting tag; and at least one
transmitting tag is configured to receive at least one signal from at least
one router/base station/access point. For additional embodiments the
system is configured to collect training and testing data for deployment;
use the training and testing data for system training and testing; and
perform adaptive error monitoring and tracking. In embodiments the
configuration for adaptive error monitoring and tracking comprises
monitoring tracking error through periodic adaptive cycles by correcting
network outputs based on readings from reference transmitters at known
locations. In included embodiments the system is configured to collect
sampled data comprising recording identification of routers that did not
receive a sampling packet from a particular spatial coordinate location. In
yet further embodiments the sub-networks are configured for training
comprising direct data, wherein the data is unfiltered or unsmoothed or
unfiltered and unsmoothed. In ongoing embodiments the sub-networks do
not spatially overlap.
[0008] An additional embodiment provides a method for scalable real-
time location determination of at least one object by sub-networks of
interrelated neural networks comprising the steps of defining the sub-
networks of interrelated neural networks a priori; collecting training data
by sampling; training the sub-networks of interrelated neural networks on
the training data; testing the sub-networks of interrelated neural networks
on the training data; operating the sub-networks of interrelated neural
networks, engaging only one of the sub-networks to output a location of the
at least one object; and adaptively monitoring and tracking errors. For a
following embodiment the sampling step comprises repeating the sampling
at specific time intervals to acquire temporal variations in an environment
related to RF signal propagation. In subsequent embodiments the step of
training the sub-networks is performed according to a scaled conjugate
gradient method, and backpropagation is used to obtain derivatives of
3
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
performance with respect to connection weights and bias vectors of the
sub-network. In embodiments a network response comprises re-scaling
input data; calculating initial intermediate results; passing a vector arg 1
through a function arg2; calculating subsequent intermediate results; and
re-scaling a last result. Included embodiments comprise processing
missing readings and extreme variations in received signal strength
indicator (RSSI) values with a Centroid k-means filter. Other embodiments
comprise processing extreme variations in received signal strength
indicator (RSSI) values with a median filter. Further embodiments
comprise processing extreme variations in received signal strength
indicator (RSSI) values with backfilling. In ensuing embodiments
computation of each of the sub-network's outputs comprises centering and
normalizing input data; calculating a network response; and calculating a
sub-network output tag position from a network output vector. In yet
further embodiments a sub-network transformation equation comprises / =
nni(rssii). In subsequent embodiments a neural layer response comprises si
= f(VV e_i,e se_i + be).
[0009] A yet further embodiment provides a scalable system for real-time
location determination of at least one object by overlapping sub-networks
of neural networks comprising at least one transmitting tag associated with
each of at least one object; the overlapping sub-networks comprising a
plurality of flexible topology, a priori defined, interrelated sub-network
location classifiers comprising receivers; receiving at least one
transmission from at least one transmitting tag at at least one of the
receivers; processing at least one received transmission in the overlapping
sub-networks of neural networks on at least one central processing and
command station; wherein only one of the sub-networks is engaged to
output a location of at least one object; and whereby the scaling is
achieved by engaging only one sub-network of the plurality of sub-
networks to output the location for each of at least one object.
4
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0 0 1 0] The features and advantages described herein are not all-
inclusive
and, in particular, many additional features and advantages will be apparent
to one of ordinary skill in the art in view of the drawings, specification,
and claims. Moreover, it should be noted that the language used in the
specification has been principally selected for readability and instructional
purposes, and not to limit the scope of the inventive subject matter.
BRIEF DESCRIPTION OF THE DRAWINGS
[0011] Figure 1 is a depiction of a system architecture configured in
accordance with an embodiment of the invention.
[0012] Figure 2 is a depiction of a flexibly uniform topology of an
overlapping multiple sub-network model configured in accordance with an
embodiment of the invention.
[0013] Figure 3 is a depiction of a mobile device / tag moving through
the topology of overlapping sub-networks configured in accordance with an
embodiment of the invention.
[0014] Figure 4 is a depiction of a configuration of a feed-forward neural
network architecture of each sub-network in accordance with an
embodiment of the invention.
[0015] Figure 5 is a depiction of a flow chart of system deployment
phases configured in accordance with an embodiment of the invention.
[0016] Figure 6 is a depiction of a flow chart of electromagnetic field
strength sampling configured in accordance with an embodiment of the
invention.
[0017] Figure 7 is a flow chart of overall operation steps configured in
accordance with an embodiment of the invention.
[0018] Figure 8 is a flowchart of network output computation steps
configured in accordance with an embodiment of the invention.
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0019]
Figure 9 is a flow chart of steps for network response of step 810
of Figure 8 configured in accordance with an embodiment of the invention.
[0020] Figure 10 is a flow chart of sampling steps configured in
accordance with an embodiment of the invention.
DETAILED DESCRIPTION
[0021]
Multiple, interrelated, neural networks provide real time location
data that scales to accurately track a large number of objects for real world
applications. System operation includes training, operation, and adaptive
error correction. Embodiments use two types of data to train a network.
One data type is generated data from mathematical models of indoor
electromagnetic field propagation. The other data type is from actual
sampled data inside the facility. Embodiments use either one type or the
other type of data, or both types can be merged and used simultaneously for
training. This
training is basically presenting the neural network a
plurality of different patterns for it to generate a representative transfer
function. Each pattern associates some physically measureable property
(for example electromagnetic signal strength, vibration, magnetic field
orientation, atmospheric pressure, acceleration, rotational rate, time of
arrival, or time of flight), with a position in three dimensional space.
Invention description particulars are organized in four sections including
System Architecture, Location Detection Model, Location Model
Deployment Configuration, and Data Collection System Training and
Network Generation. The system for real-time location detection consists
of three groups of components. I. Mobile devices to be tracked are
equipped with wireless transceivers capable of sending, and optionally for
receiving, data over pre-determined radio frequency (RF) band(s). II.
Router/base station/access point devices equipped with wireless
6
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
transceivers capable of sending and receiving data over one or more pre-
determined RF band(s) in order to communicate with mobile units. Routers
are combined into specific router groups, with each group forming a spatial
sub-network. Embodiments include non-spatial sub-networks, ex. by object
type. III. In embodiments, system central processing and command
station(s) perform data processing and implementation of computational
models that determine the mobile unit location. For embodiments, system
deployment consists of three phases: A comprising collection of training
and testing data; B comprising neural network training and testing; and
finally C comprising operation and network adaptive maintenance.
[0022] Embodiments use received signal strength indicator (RSSI)
measurements on the routers; alternative embodiments also use the RSSI
measured on the mobile units. As mentioned, in addition to
electromagnetic signal strength, vibration, magnetic field orientation,
atmospheric pressure, acceleration, rotational rate, time of arrival, and time
of flight are nonlimiting examples of other physical properties used.
[0023] In embodiments, modularity/scaling is implemented using
overlapping, a priori-defined sub-networks. By a priori, it is meant that
the layout of the sub-networks is defined before system operation begins.
The spatially overlapping organizational structure ensures that any
combination of inputs results in an adequate location determination. For
embodiments, a router can be in more than one sub-net. Selection of the
sub-network to be engaged for a particular tag is based on a count of
routers/access points and RF transceiver communication links. In
embodiments, the sub-network with the maximum count of such
communication links is selected. In embodiments, ties are resolved by
alternate selection. Advantages of this method include a smaller number of
classifiers (i.e. neural networks) necessary to cover a specific area. As
another example of advantages, the method has surprisingly reduced
memory requirements. No 'visibility matrix module' selection logic is
necessary.
7
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0024]
During regular run-time, missing readings from certain locations
as well as extreme variations in RSSI values are simultaneously handled by
the implementation of data backfilling, Centroid (k-means), and/or median
type filters. By centroid, it is meant the intersection of all hyperplanes in
n-dimensional space that divide a geometric shape into two parts of equal
moment. k-
means embodiments provide unexpectedly good results
considering the issues with computational difficulty (NP-hard) and the
sensitivity to the number of input clusters, k. NP-hard refers to non-
deterministic polynomial-time hard in computational complexity theory. In
embodiments, missing readings means zero RSSI values. In embodiments,
extreme variations means near minimum / maximum reading values or,
where readings are similar in value to each other, for example, double or
triple the similar value.
[0025] For embodiments, no filtering or smoothing operations are
implemented on training data sets. The approach is that for each particular
location, typical scenarios involve a large amount of data, and the
classifiers should exhibit tolerance, as much as possible, to extreme
scenario cases of missing data. Additionally, during the training phase,
there is no implementation of a missing data filter to get rid of extremely
small RSSI values. Finally, neural model targets and outputs can either be
continuous coordinates or discrete locations.
System Architecture
[0026] As previously introduced, embodiments of the system for real-time
location detection consist of three major groups of components. I. Mobile
devices to be tracked. These are equipped with wireless transmitters /
transceivers capable of sending and, for embodiments, receiving the data
over pre-determined radio frequency (RF) band(s).
[0027] II. Router/base station access point devices. In embodiments, these
are equipped with wireless transceivers capable of sending and receiving
8
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
data over pre-determined radio frequency (RF) band(s) in order to
communicate with mobile units. Embodiments of these devices are also
capable of relaying data received from mobile units to other system
modules via wired or wireless links.
[0028] III. System central processing and command station(s).
Embodiments perform the data processing and implementation of the
computational models that determine the mobile unit location in the system
central processing and command station(s). Embodiments of these stations
(typically a server type device) are also capable of sending specific
messages to all other units in the system.
[0029] FIG. 1 depicts an embodiment of a system architecture 100.
Components comprise Router/Base station access points 105, Mobile
devices 110, and Central Processing/Command station 115. Data transfer
between Central Processing/Command 115 and Mobile units 110 is relayed
via Router stations 105. The exchange of the information between router
stations and central processing/command units can be done via wired or
wireless links 120. The spatial topology of the system network (i.e. router
locations) is not fixed, but for embodiments needs re-training after router
relocation, and does not have to conform to any particular placement
selection rule. In embodiments, the placement of routers is governed by
actual in-field requirements and limitations. Each device in the system has
a unique identifier or address. In embodiments, communication between
various wireless system devices is accomplished through one or more
specific communication protocols assuming both non-synchronized
(pseudo-random transmissions) and synchronized operation (TDMA-like
operation).
Location Detection Model
[0030] Embodiments of the method for location detection are based on
the Received Signal Strength Indicator (RSSI) readings forwarded from
9
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
routers / base station access points and mobile transceivers that receive a
communications packet to/from the mobile unit. Nonlimiting examples of
other physical properties used embodiments of the location determining
method comprise vibration, magnetic field orientation, atmospheric
pressure, acceleration, rotational rate, time of arrival, and time of flight.
In embodiments, system routers are combined into specific router groups
with each group forming the spatial sub-networks for the system. Core
aspects of the location determination method are based on a neural network
based pattern recognition solution.
[0031] Nomenclature defines a system having N router units placed
throughout the indoor environment in a particular 3-D scheme. The
distribution of routers does not have to be strictly uniform and does not
have to conform to any specific grid structure. For embodiments, a sub-
network can be defined to include all N routers.
[0032] FIG. 2 is an example of a uniform-type router distribution 200
provided to more easily visualize 3-D system topology. In illustrating the
topology of the Overlapping Multiple Network Model, specific sub-network
components are distinguished with router-dots 205.
[0033] The particular example of the system shown in FIG. 2 presents a
network containing three sub-networks 210, 215, and 220. Sub-networks
can overlap - the case depicted in FIG. 2 shows the model with three sub-
networks having common routers. For some embodiments, a router can be
in more than one sub-net. In embodiments, overlap can be spatial and or
by any measured or defined parameter. Sub-network 215 routers are
depicted within a dashed outline. Each sub-network can contain any
number of routers and can also be isolated from the rest of the system
without actually overlapping with any other sub-network. Assume the
system has M sub-networks. The number of routers that belong to sub-
network i is Ni. Embodiments of the mobile device location method
assume that each system sub-network is associated with the transformation
described as:
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0034] / = nni(rssii) (2.1)
[0035] where / is the location vector, nni( ) is the neural-network
transformation function for a particular system sub-network and (rssii) is
the vector containing all Ni RSSI readings from routers/mobile transceivers
that belong to the sub-network i. Vector / has dimensions 3x1 and its
components correlate with detected coordinates of the particular mobile
transmitter. The neural network transfer function is typically a non-linear
transform (embodiments include linear models) that can be represented
through matrix-vector multiplication operations as well as additional
mapping of intermediate results. Exact neural mapping form depends on
the chosen parameters of neural networks associated with each sub-
network. Regarding terminology, distinctions between a particular neural
network assigned to the specific router sub-network and the router sub-
network itself will not necessarily be explicit.
[0036] FIG. 3 depicts a mobile device / tag moving through a topology
of overlapping sub-networks 300. The topology is from FIG. 2. Initial tag
location 305 is within sub-network 1 (heavy short dashed line) 310. Next
tag location 320, is within sub-network 2 (heavy long dashed line) 315.
Third tag location 330, is within sub-network 3 (heavy dot-dot-dash line)
325. In each case, for this embodiment, the sub-network having the
greatest number of routers receiving the tag's signal is engaged to perform
the location detection determination for the tag.
[0037] FIG. 4 depicts an embodiment for a feed forward neural network
architecture 400 of each sub-network. Components comprise Input 405,
410, and 415 to Data Pre-Processing 420; Layer 1 425; Layer p-1 430;
Layer p 435; Data Post-Processing 440; and Output 445, 450, and 455. The
network architecture depicted in FIG. 4 demonstrates a neural network of
feed-forward architecture, although no assumption or restriction is made
11
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
that could prevent using another type of neural model. Each sub-network
has Ni inputs, p layers (a p-layer network is commonly referred to as a
network with one output and p-1 hidden layers), and a maximum of three
outputs. An alternative embodiment comprises a 4th, time, dimension.
Embodiments use time not only for compensating for slow moving
variations in the environment, but also for making predictions. As a
nonlimiting example, embodiments of the system refine location accuracy
by observing set routines such as a nurse repeatedly traveling between the
nurse's station and exam rooms. Each neural layer has a certain number of
neurons - processing units - and their number can be different for different
network layers. The synaptic weights of the network, the transfer function
f( ), along with the bias vectors, determine the response of each neural
layer to the inputs received from the previous one or fed back from later
layers. This response can be described in a matrix form as:
[0038] Si = si_i + bi) (2.2)
[0039] where matrix represents the network connection matrix for
layers i-1 and i, si is the signal output from layer i, (si_i layer i-1) and b
i is
the bias vector in the form:
bom
[0040] b, = 1.)(1), 2
(2.3)
[0041] The number of neurons in layer i is denoted as nn i. The transfer
function f( ) can have one of the few standard forms. One example is the
tan-sigmoid transfer function:
[0042] f (x)= 2 2x 1 (2.4)
1+e
12
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0043] In embodiments, two blocks ¨ signal pre-processing 420 and
signal post-processing 440, are employed to normalize the data to the range
suitable for neural-network processing. Normalization parameters are
determined during network training and depend on the training data vectors
at the network input and target vectors at the network output. In the case
of embodiments of the model addressed herein, these parameters are
influenced by the effective RSSI range as received on sub-network routers
during the training phase.
[0044] FIG. 5 flowchart 500 depicts the three system deployment phases.
As mentioned, system deployment embodiments consist of three phases. A
comprising collection of training and testing data 505; B comprising
network / system training and testing 510; and finally C comprising
operation and network adaptive maintenance 515. After all router units are
installed in the particular environment, training data is collected through
physical measurement sampling, mathematical modeling, or a combination
of both. The sampling procedure consists of capturing the RF signal
characteristics from known locations determined by the x, y and z
coordinates in the space of interest. For
embodiments, sampling is
implemented through the transmission of bursts of packets from a given
location. Bursts contain a reasonable number of transmissions (10-30, for
example) in order to properly characterize the signal strength for given
location. The sampling process can potentially be repeated for specific
time intervals (hour(s), day, month...) in order to acquire temporal
variations in the environment that are related to RF signal propagation.
Each sampling packet has a unique identifier enabling the system to
recognize and interpret the packet structure. All routers that receive the
sampling packet extract the information content and relay it further to the
central server which stores the sampled data. The information of interest,
in embodiments, comprises the RSSI as received at each router/mobile
transceiver and current mobile transceiver location. Also, the information
13
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
on routers that did not receive the sampling packet from the particular (x,
y, z) location ¨ i.e. the routers that timeout - is recorded.
[0045] FIG. 6 is a flow chart 600 depicting overview steps of sampling
for an embodiment. During the sampling process, at start 605, a mobile
transceiver device (in embodiments an RFID tag) is physically moved
incrementally throughout the space of interest 610. Information about the
location of the sampling unit is sent to the central sever before each
sampling data burst is captured 615. In parallel, a mathematical model of
electromagnetic field propagation is generated for the space of interest 620,
and model space is sampled 625. The central server creates a network
training database containing the x, y, z location of the transceiver and a
corresponding set of RSSI readings from the modeled data or captured data
from mobile transceiver/system routers or a combination of both 630,
ending the sequence 635. The structure of an embodiment of this data set
is shown in Table 1.
[0046] Table 1 Sampling data structure
Tag X Y Z Router Router Router Router ... ...
ID 1.1 1.2 2.1 2.2
000B 17 236 17 -65 -68 -58 -57
000A 24 128 38 -48 -51 -61 -63
000B 26 324 17 NaN/-99 NaN/-99 -64 -61
000B 26 324 17 ... ...
[0047] In embodiments, the spatial locations of the training data
collection are either random or structured as a regular grid-like pattern.
For some embodiments, the sampling is taken about every 3 feet. Other
embodiments use a cluster of mobile transceivers with a single x, y, z
location selected.
[0048] Each system sub-network has its own spatial domain with
boundaries defined as:
14
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
XMIN < X < XMAX
[0049] (2.5)
Y MIN < Y < Y MAX
ZMIN <Z < ZMAX
[0050] The training of each sub-network is performed by using the
training data that belongs to that (sub-) network's domain. The inputs to
the network are feature vectors containing the RSSI (and / or other
parameter) values from the readers belonging to the specific network. The
target outputs are x, y and z coordinates of the tag associated with input
vector. An embodiment implementation of training is accomplished by
MATLAB Neural Toolbox . MATLAB and MATLAB Neural Toolbox
are registered trademarks of MathWorks, Inc., Corporation of California.
Training of the network is performed according to the scaled conjugate
gradient method, while backpropagation is used to obtain the derivatives of
performance with respect to the connection weights and bias vectors of the
network. The MATLAB Neural Toolbox implementations of neural
network training contain a model for data pre and post processing. Once
the training of the network is completed, several sets of
matrices/coefficients are generated. They represent the data pre and post
processing parameters, network connection weights, and network bias
vectors.
[0051] FIG. 7 flow chart 700 depicts overall operation steps including
start 705, obtaining EM field strength sample training data step 710,
obtaining data from random locations 715, training 720, and operation and
monitoring tracking error through adaptive cycles 725. Further details
follow.
[0052] Once training data is obtained 710, an additional set of data with
a format identical to the training data is obtained from random spatial
locations 715. This data set is employed to test network performance.
[0053] After the network is deployed, tracking error is monitored through
periodic adaptive cycles 725 by correcting the network outputs based on
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
readings from transmitters placed at known locations. These transmitters
are called reference units and they provide run-time training and adaptation
data.
Location Model Deployment Configuration
[0054] This section describes an embodiment of the method for
simulation of neural network outputs in order to determine the tag location
based on a set of received RSSI readings. For each system sub-network,
the processing application loads the content of text files representatively
denoted as follows: Bl, B2, B3, B4, IN, LW12, LW23, M, max X, max Y,
max Z, OUT, subnetConfig, targetMag, V, xMaxl, xMax2, xMinl, xMin2,
yMaxl, yMax2, yMinl, yMin2 (z). In embodiments, all of the above
mentioned files are generated during system training. For a system with
three hidden layers, they have the following interpretation:
[0055] Bl, B2, B3, B4 contain network bias vectors;
[0056] IN is the input connection weight matrix;
[0057] LW12 and LW23 are connection matrices between layers 1-2 and
2-3, respectively;
[0058] OUT is the connection matrix between layer 3 and output layer;
[0059] M and V are mean and variance normalization parameters for
input RSSI data, in embodiments;
[0060] max X, max _Y and max _Z are maximum coordinate spans in x, y
and z directions of the network;
[0061] subnetConfig contains the network configuration parameters
described in Table 2 below;
[0062] targetMag is the neural network maximum output;
[0063] xMaxl, xMax2, xMinl, xMin2, yMaxl, yMax2, yMinl, yMin2
(optionally z) are data normalization parameters used with, for example,
the MATLAB Neural Toolbox . These parameters are obtained based on
16
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
the maximum and minimum training data values as well as the desired data
range at the output of the input layer and the input of the output layer. The
structure of an embodiment of the subnet Configuration text file is depicted
in Table 2.
[0064] Table 2 Structure of a network configuration file
Field structure Explanation
Network name , 0.0 Network name , 0.0
Customer ID, 0 Customer unique identifier
Building ID, 0 Building unique identifier
xMin, 0.0 Minimum x coordinate covered by the network
xMax, 90.0 Maximum x coordinate covered by the network
yMin, 0.0 Minimum y coordinate covered by the network
yMax, 92.0 Maximum y coordinate covered by the network
zMin, 4.0 Minimum z coordinate covered by the network
zMax, 4.0 Maximum z coordinate covered by the network
MAC1 List of MACs of routers that are part of the
MAC2 particular network
...
[0065] FIG. 8 flowchart 800 depicts the steps whereby each of the
network's outputs is computed. For embodiments, this is accomplished by
implementing the steps of: A comprising centering and normalizing 805; B
comprising network response procedure 810; and C comprising network
output 815 (4 layer network assumed). Details follow.
A. Centering and Normalizing
[0066] Before being processed by the neural network, all RSSI data
represented by the vector inRssi [Ni x 1] is centered and normalized.
Embodiments of this process comprise:
[0067] a. Load normalization parameters M [Ni x 1] and V [Ni x 1]; and
[0068] b. Calculating centered-normalized vector as: in = (inRssi ¨ M)./V
17
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0069] where ¨ is standard matrix subtraction while ./ is per-element
vector division. For embodiments, the mean M and variance V
normalization vectors can be omitted (i.e. M is null vector while V is unit
vector); MATLAB Neural Toolbox can implement normalizing the input
data.
B. Network Response
[0070] After reading the input parameters, the following procedure yields
the network response for embodiments.
[0071] FIG. 9 flowchart 900 summarizes the steps included in the
network response procedure of FIG. 8, step 810. Network response steps
comprise: Re-scaling the input data 905, Calculating (initial) intermediate
result 910, Passing the vector argl through function arg2 915, Proceed with
calculation of the following (subsequent) intermediate results 920, and Re-
scaling the last result 925. Details of the network response steps follow.
[0072] 1. Re-scale the input data according to the formula:
[0073] outl = (yMax1-yMin1)*(in-xMin1)./(xMax1-xMin1) +yMinl
[0074] where: ./ represents per-element matrix division, - represents
per-element matrix subtraction, * represents scalar times matrix operation
and + represents addition of the constant term to each element of the
matrix;
[0075] 2. Calculate the (initial) intermediate result according to:
[0076] arg 1 = (IN*outl) + B1
[0077] where all operation are standard matrix operators;
[0078] 3. Pass the vector argl through function:
18
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[0079] arg2 = 2/(1+exp(-2*arg1))-1
[0080] where the transform is calculated on each element of argl;
[0081] 4. Proceed with calculation of the following (subsequent)
intermediate results:
[0082] arg3 = (LW12*arg2)+B2;
[0083] arg4 = tansig(arg3); where tansig(x) = 2/(1+exp(-2*x))-1
[0084] arg5 = (LW23*arg4)+B3;
[0085] arg6 = tansig(arg5);
[0086] arg7 = (OUT*arg6)+B4;
[0087] arg8 = tansig(arg7);
[0088] 5. Re-scale the last result according to the formula:
[0089] outFinal=(xMax2-xMin2).*(arg8-yMin2)./(yMax2-yMin2) +xMin2
[0090] where first ¨ is subtraction of two vectors, .* represents per
element multiplication of two matrices, arg8-yMin2 subtracts constant from
each vector component, ./ is per element division, and the last + is standard
vector + vector operation.
C. Network Output
[0091] The output of the network is a two or three component vector with
all components in the range [-1, 1]. The calculation of the (x, y) tag
position is accomplished by using the following procedure:
[0092] xFeet = (outFinal(1)/(2*targetMag)+0.5)*max X + xMin;
[0093] yFeet = (outFinal(2)/(2*targetMag)+0.5)*max Y + yMin;
[0094] zFeet = (outFinal(2)/(2*targetMag)+0.5)*max Z + zMin;
[0095] where xMin, yMin and zMin represent the minimum x, y and z
coordinates covered by the local (sub-) network. Parameters max X,
19
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
max _Y and max _Z are already provided in the (sub-) network parameter
files; they are:
[0096] max _X = xMax ¨ xMin;
[0097] max _Y = yMax ¨ yMin;
[0098] max _Z = zMax ¨ zMin;
[0099] where xMax, yMax and zMax represent maximum x and y
coordinates covered by the local network.
[00100] Note that if parameter max _Z is 0, the network has only two
active outputs and it covers only one floor (or only two dimensions). In
this case, the output zFeet can be set to:
[00101] zFeet = zMin;
[00102] The process of choosing the particular sub-network (out of all
possible sub-networks) to activate consists of choosing the sub-network
with highest number of routers that received packet(s) from the particular
transmitter (highest number of non NaN or -99 readings).
Data collection, System Training and Network Generation
[00103] The generation of system neural networks is performed, for
example, by using MATLAB based scripts such as:
[00104] ¨ train Overlap
[00105] ¨ test Overlap
[00106] ¨ create Golden Vector
[00107] ¨ exclude Data Points
[00108] ¨ merge Chip 12 (*)
[00109] A sampling procedure precedes the actual network training. This
process was initially described in the Location Detection Model section.
The sampling procedure is accompanied by careful coordinate verification
in the area where the system is installed. In embodiments, samplings are
distributed along a regular grid, with the distance between adjacent
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
samplings being 3 feet. In other embodiments, regular grid spacing is not
employed. For embodiments, a separate application (MapReader) reads a
map of the facility and displays the current coordinate. It can be used to
verify the sampling location, i.e. x, y and z coordinates. It is also possible
to use reference coordinate labels in each room of the facility for easier
orientation during the sampling process. In embodiments, the minimum
number of packets to process/receive during each sampling burst is 20 (this
can vary). Two groups of data are collected in embodiments: 1 a larger set
of sample training data sampled every three feet throughout the entire
installation space, and 2 a set of random points (100-200) that serve as test
data to validate the network training results. The following represents
embodiment details to address before and during the sampling procedure.
Sampling
[00110] FIG. 10 flowchart 1000 depicts more detailed steps of a sampling
method. Providing a sufficient number of sampling tags; Test / calibrate
the sampling tags to verify that they all produce similar RSSI readings an
all routers 1005. Preparing a map or maps of the facility where the system
will be installed 1010. In embodiments, the maps are exported into png
format, for example, if a MapReader application is used to validate the map
accuracy. After the origin point is chosen on the map, the map scale is
confirmed by choosing few points in the area (room corners or corner
points along large corridors if possible) and measuring the distance
between them while comparing those readings with map data. Sampling is
performed by using WiFi connectivity and PocketPC devices or laptop
computers, for example 1015. Facility WiFi access availability is
confirmed, ensuring that the sampling server application communicates
seamlessly with all PDAs and laptops that will be used during the sampling
procedure. The health status of readers should be confirmed and available
at all times in order to make sure that sampling data is valid 1020. There
should be clear separation of sampling zones (e.g. by rooms, corridors or
21
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
simply by the value of coordinates), and each zone should be assigned to
separate sampling team 1025. After the sampling procedure is completed,
network generation can take place 1030. In embodiments, setup files are
located in a net Config folder for system training software. Embodiment
examples are:
[00111] ¨ main config text file
[00112] ¨ test config text file
[00113] ¨ router config csv file
[00114] An embodiment of the structure of a main configuration text file
is given in Table 3.
[00115] Table 3 Structure of the main configuration text file
Field Name, Field Value (example) Explanation
train data file, Adata\traindata.csv Location and name of the file with
training data
¨ all locations are relative to the folder where
trainOverlap.m file resides.
test data file, Adata\testdata.csv Location and name of the file with test
data
router config file, Location and name of the file with the
list of the
routers in the system
AnetConfig\routerconfig.csv
Location and name of the base name for all
network config base name,
network names in the system. In this case for 2
AnetConfig\dhmc 102109 subnet networks would have dhmc 102109 subnet 1
and
dhmc 102109 subnet 2 networks to train.
num networks, 2 The number of networks in the system.
num neurons layer 1, 128 The number of neurons in layer 1 of each
network.
num neurons layer 2, 64 The number of neurons in layer 2 of each
network.
num neurons layer 3, 32 The number of neurons in layer 3 of each
network.
test network, true The flag specifying if the script
trainOverlap.m
will test the network(s) or not.
save data, true The flag specifying if the script
trainOverlap.m
will save trained network(s) or not.
22
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
create golden vector, false The flag specifying if the script
trainOverlap.m
will create golden vector data or not.
decimate data, 0 The parameter specifying if
the script
trainOverlap.m will decimate the input data ¨ if
>1 the decimation will take place and decimation
factor is actually this parameter itself.
fix unknowns, false The parameter specifying if -99 readings
(no
packet received) will be replaced with value
determined by MATLAB's fix unknowns function
from neural toolbox.
The name of the binary exclusion map ¨ the black
exclusion map name,
areas are zones where the tags can not be present
AnetConfig\DHMC 24 Grid Model_ in the system (exclusion zones).
patient ex
clusion 300dpi binary.png
excl map pixel origin x, 552 X location of the coordinate origin in
pixels on
the map (second MATLAB parameter for images).
excl map pixel origin y, 2212 Y location of the coordinate origin in
pixels on
the map (first MATLAB parameter for images).
excl origin real x, 0 X coordinate of the origin point in
feet.
excl origin real y, 0 Y coordinate of the origin point in
feet.
excl map pixel ref x, 3186 X location of the reference point in
pixels on the
map (second MATLAB parameter for images).
excl map pixel ref y, 2212 Y location of the reference point in
pixels on the
map (first MATLAB parameter for images).
excl ref real x, 333.7711 X coordinate of the reference point in
feet.
excl ref real y, 0 X coordinate of the reference point in
feet.
excl map floor coordinate, 43 Exclusion map floor coordinate.
[00116] Table 3 presents the structure of an embodiment of the main
configuration text file for configuration of the script for training overlap.
[00117] In embodiments, the comma separated values (csv) file for router
configuration contains the list of all deployed routers/readers in the system
and the structure of this file is shown in Table 4 (all fields in the file are
separated by commas).
23
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[00118] Table 4 Router configuration file structure
Physical Address Internet X Y Z
Version
Address coord. coord. coord.
00.1A.B8.00.02.1C 192.168.111.2 0 45 8 4
00.1A.B8.00.02.1E 192.168.111.3 55 41 8 4
00.1A.B8.00.02.2A 192.168.111.4 55 41 8 4
00.1A.B8.00.02.2C 192.168.111.5 55 41 8 4
...
...
===
=== ... ...
00.1A.B8.00.02.2E 192.168.111.6 55 41 8 4
[00119] In embodiments, before the network training is performed a
priori, the area where the system is deployed is divided into N potentially
overlapping networks. For each sub-network, a configuration file of the
structure described in Table 2 of the above section on Location Model
Deployment Configuration is created. In embodiments, these sub-network
files are named according to the name given by the network configuration
base name parameter in the main configuration text file. For example, if
the network configuration base name parameter has the value
"network Alpha" and the parameter num networks has a value of "3", then
three configuration files are created with the names: network Alpha 1,
network Alpha 2, and network Alpha 3.
[00120] In embodiments, network training is performed by running the
train Overlap script. During the training, the program selects appropriate
datasets for each system sub-network, trains each network, and saves
network coefficients and configuration files in a folder named "saved".
Each sub-network is saved in the separate subfolder whose name
corresponds to the name of that particular sub-network. These files are
provided to the tracking layer services during the final system deployment.
24
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
In embodiments, when the test network field in the main configuration text
file is set to true, the trained networks are tested by using the specified
testing data set. In embodiments, the resulting average absolute error is
displayed in a MATLAB prompt. Also, an absolute error histogram is
shown in a separate figure in embodiments. For large data sets (40,000
training samples), network training can involve approximately one-half
hour (3GHz quad core Intel Xeon processor w/ 4GB system RAM). Should
network training not converge, the training process is repeated. For
embodiments, nonconvergence is identified by the average absolute error
being relatively large (>12feet). In addition to network coefficients,
embodiments of the training program create a log file with the name
consisting of the network configuration base name parameter followed by
X and the date and time of training. For embodiments, this file contains
data such as router configuration, network coefficients, and network
configuration setup in the form of MATLAB variables that can be directly
loaded to the MATLAB workspace.
[00121] In embodiments, a separate script, test Overlap, is used to test any
previously trained network. The configuration file for this script is a test
configuration text file. The structure of embodiments of this file is shown
in Table 5.
[00122] Table 5 The structure of a test configuration text file
Field Name, Field Value (example) Explanation
test data file, Adata\testdata.csv Location and name of the file with
test data ¨ all locations are relative
to the folder where trainOverlap.m
file resides.
log file, Location and name of the file with
.\log\dhmc 102109 subnet X 201002 network to be tested ¨ the file is in
04T135702 mat format.
show bias, false The flag show bias displays the
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
actual location and the location
determined by the neural network.
show map error, false The flag show map error
determines if the test locations w/
errors beyond a threshold will be
shown on the map (red for
locations w/ error beyond
threshold).
error threshold, 15.0 Error threshold parameter in feet.
map name, The location and name of the map
AnetConfig\DHMC 24 grid Model 3 used to display error and possibly
sampling data.
00dpi.png
map pixel origin x, 552 The x coordinate of the pixel in the
map corresponding to the origin
point (second MATLAB
coordinate).
map pixel origin y, 2212 The y coordinate of the pixel in the
map corresponding to the origin
point (first MATLAB coordinate).
origin real x, 0 Origin x coordinate in feet.
origin real y, 0 Origin y coordinate in feet.
map pixel ref x, 3186 The x coordinate of the pixel
corresponding to the reference
point in the map.
map pixel ref y, 2212 The y coordinate of the pixel
corresponding to the reference
point in the map.
ref real x, 333.7711 The x coordinate of the reference
26
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
point in feet.
ref real y, 0 The y coordinate of the reference
point in feet.
map floor coordinate, 43 The floor coordinate of the map.
scatter sampling only, false The parameter used to show the
sampling data as the scatter plot on
the map.
exclusion map name, The location and name of the
AnetConfig\DHMC 24 Grid Model exclusion map ¨ the map is binary
patient exclusion 300dpi binary.png image with values 256 for allowed
locations and values 0 for
exclusion zones.
excl map pixel origin x, 552 The configuration data used for
exclusion map setup ¨ these
directly correspond to those used
for error/sampling map setup.
If
excl map pixel origin y, 2212
If
excl origin real x, 0
If
excl origin real y, 0
If
excl map pixel ref x, 3186
If
excl map pixel ref y, 2212
If
excl ref real x, 333.7711
If
excl ref real y, 0
If
excl map floor coordinate, 43
Table 5 The structure of a test configuration text file.
[00123] When running the test Overlap script file, for embodiments, the
average absolute error, number of wrong floor decisions, and absolute error
histogram are displayed, except when the parameter show sampling only
from the test configuration text file is set to true.
27
CA 02907723 2015-09-18
WO 2014/179529
PCT/US2014/036305
[00124] The foregoing description of the embodiments of the invention
has been presented for the purposes of illustration and description. It is
not intended to be exhaustive or to limit the invention to the precise form
disclosed. Many modifications and variations are possible in light of this
disclosure. It is intended that the scope of the invention be limited not by
this detailed description, but rather by the claims appended hereto.
28
