PSEUDO-RANDOM SEQUENCES

BACKGROUND

Some known systems exist for positioning and navigation with mobile devices. For example, such systems include Global Navigation Satellite Systems (GNSS) such as Global Positioning Systems (GPS), the Russian GLObal NAvigation Satellite System (GLONASS), BeiDou, Radio Frequency Identification (RFID) location mechanism, Bluetooth/Bluetooth Low Energy (BLE) location mechanism, Mobile Network location system, and more.

Some of these technologies are unidirectional, whereby the device can find its location, but this is performed by the device receiving signals from, for example satellites. Another means of communication may be used so that the user of the location information can be given the location information.

Other detectors, such as RFID and Bluetooth, provide short-distance identification.

SUMMARY

According to an aspect of some embodiments of the present invention there is provided a network including a network interface adapted to receive a time stamped segment of a randomly generated value sequence from at least one base station, the randomly generated value sequence is generated by at least one first random value generator executed on a user equipment device. The timed stamped segment may be a segment received from the user equipment device and time stamped by the at least one base station.

The network further includes a processor adapted to execute at least one second random value generator correlated with the first random value generator. The second random value generator is for generating at least one reference value sequence. The processor is adapted to identify a match between the time stamped segment and a time correlated reference segment of the at least one reference value sequence, and determine a location of the user equipment device according to the match and location data received from the at least one base station.

According to some embodiments of the present invention, the at least one first random value generator and the at least one second random value generator execute a common function for generating the randomly generated value sequence and the reference value sequence, respectively. In some embodiments, the at least one first random value generator and the at least one second random value generator generate the randomly generated value sequence and the time correlated reference segment by combining a unique key with a periodically increasing number.

According to some embodiments of the present invention, the network interface is adapted to receive possibly incomplete location data calculated by signal analysis performed by the at least one base station, wherein the processor is adapted to determine the location with the use of the location data.

According to some embodiments of the present invention, the number of symbols within the segment or the mean period between the segments can be adjusted, so that a length of at least one of the segments is insufficient for reliably identifying the device without other context stored within the processor. In some embodiments, the randomly generated value sequence includes a plurality of random interludes between a plurality of transmitted segments.

According to another aspect of some embodiments of the present invention there is provided a method including receiving a time stamped segment of a randomly generated value sequence from at least one base station, the randomly generated value sequence is generated by at least one first random value generator executed on a user equipment device, executing at least one random second value generator for generating at least one reference value sequence, identifying a match between the time stamped segment and a time correlated reference segment of the at least one reference value sequence, and determining a location of the user equipment device according to the match and location data received from the at least one base station, wherein the at least one first random value generator and the at least one random second value generator are correlated.

According to another aspect of some embodiments of the present invention there is provided a base station device including a wireless receiver adapted to receive a signal comprising a segment of a randomly generated value sequence generated by at least one first random value generator executed by a user equipment device, a processor adapted to extract location data of the user equipment by an analysis of the signal, decode the segment from the signal and time stamp the segment for creating a time stamped segment, and an interface adapted to transmit the time stamped segment and the location data to a network node so as to allow the network node to determine a location of the user equipment device. The location data may be selected from a group including time of arrival (ToA), angle of arrival (AoA), and received signal strength indicator (RSSI).

Unless otherwise defined, all technical and/or scientific terms used herein have the same meaning as commonly understood by one of ordinary skill in the art to which the invention pertains. Although methods and materials similar or equivalent to those described herein can be used in the practice or testing of embodiments of the invention, exemplary methods and/or materials are described below. In case of conflict, the patent specification, including definitions, will control. In addition, the materials, methods, and examples are illustrative only and are not intended to be necessarily limiting.

BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWINGS

Some embodiments of the invention are herein described, by way of example only, with reference to the accompanying drawings. With specific reference now to the drawings in detail, it is stressed that the particulars shown are by way of example and for purposes of illustrative discussion of embodiments of the invention. In this regard, the description taken with the drawings makes apparent to those skilled in the art how embodiments of the invention may be practiced.

In the drawings:

FIG. 1 is a schematic flowchart illustrating a method for locating a device according to some embodiments of the present invention;

FIG. 2 is a schematic illustration of an exemplary network according to some embodiments of the present invention; and

FIG. 3 is a more detailed schematic illustration of a base station according to some embodiments of the present invention.

DETAILED DESCRIPTION

Mobile device location systems that utilize battery-powered, bi-directional devices may consume much power and therefore may have relatively short battery life. For other devices such as RFID that generate their transmit power from an induced current, the range is limited. Receive-only devices may still have to transmit their information back to some network, possibly using an additional technology, which may draw more power.

Transmit-only devices within for location systems may require sending of full identification (ID) information, which may be both insecure and power consuming, because of the usually big size of full ID data. The ID of the device may be revealed and the device may be tracked by unfriendly base stations, and unless other measures are taken, the ID may be replayed.

Some embodiments of the present invention provide a long range location network and method that detects location of an active device without requiring bi-directional communication. In some embodiments, transmit-only communication may suffice for the location detection. In particular, a network interface according to some embodiments of the present invention may estimate a location of a device by comparing received segments of value sequences generated pseudo-randomly to a reference sequence, wherein both the reference and received sequences a generated using a same device-associated key a same pseudo-random method.

Before explaining at least one embodiment of the invention in detail, it is to be understood that the invention is not necessarily limited in its application to the details of construction and the arrangement of the components and/or methods set forth in the following description and/or illustrated in the drawings and/or the Examples. The invention is capable of other embodiments or of being practiced or carried out in various ways.

The present invention may be a network, a method, and/or a computer program product. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention.

The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing.

Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network.

The computer readable program instructions may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention. Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions.

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions.

According to some embodiments of the present invention, a network including a network interface and one or more processor(s) determines and updates a location of a user equipment device according to correlation between two pseudo-randomly generated values, as describe in more detail herein below.

Reference is now made to FIG. 1, which is a schematic flowchart illustrating a method 100 for locating a device according to some embodiments of the present invention. In a secured process for determining a location of a device, according to some embodiments of the present invention, values sent by the device are interpretable for location determination only by a dedicated network interface. For example, the values cannot be re-used and/or replayed and the device cannot be identified by interception of the values by foreign/unfriendly stations. Additionally, some embodiments of the present invention enable more frequent location updates than known location systems, with reduced power consumption. For example, such advantages may be enabled by use of smaller signals relative to known location system. A schematic illustration of an exemplary location network 200 according to some embodiments of the present invention, is shown with reference to FIG. 2. According to some embodiments of the present invention, a user equipment device 30 generates pseudo-randomly a pseudo-random value sequence, for example, by an approximately random value generator 32, such as, for example, a pseudo random number generator (PR G) or a deterministic random bit generator (DRBG), executed on device 30, for example by a processor 35. A pseudo-random value sequence may be a number sequence with statistical qualities of a random number such as, for example, an approximately equal distribution of numerals across a long pseudo-random value sequence. Generator 32 may generate the pseudo-random value sequence by using a deterministic process. Device 30 may be a transmission only device or any other mobile communication device, for example, that uses a cellular communication network.

It will be appreciated that throughout the present description, a pseudo-random or an approximately random value, sequence and/or generation of a sequence may also be shortly referred to as a random value, sequence and/or generation of a sequence, respectively.

More specifically, device 30 may include a storage unit 31, storing a device-exclusive key 33 and a sequence number 34. Device-exclusive key 33 may be exclusively associated with the specific user device 30. Sequence number 34 may change predictably. For example, sequence number 34 may increase or decrease in predictable periods, for example periodically. Key 33 together with sequence number 34 may form a seed input received by pseudo-random value generator 32. For example, generator 32 may encrypt the momentary sequence number 34 with key 33 in order to generate a pseudo-random value sequence.

Processor 35 may snip from the momentary generated pseudo-random values sequence respective segments 36, for example with varying segment lengths and/or time intervals between segments 36, and to couple to each segment 36 a corresponding time offset measured and/or determined by a timer 37. The varying segment lengths and/or time offsets may be generated by a certain predetermined suitable probability distribution, for example, in order to refrain from too long or too short segment lengths and/or time offsets. The varying segment lengths and/or time offsets may prevent a malicious attack, for example by preventing from an attacker repeating the transmission.

Accordingly, user device 30 may transmit to at least one base station 20 a transmission that may include a segment 36 or a series of segments 36 with varying segment lengths and/or time intervals between segments 36. For example, a transmission symbol rate and/or period between the transmitted segments 36 may be tuned according to a desired frequency in which the location determination is updated, and/or according to a desired length of segments 36. Further reference is now made to Fig. 3, which is a more detailed schematic illustration of a base station 20 according to some embodiments of the present invention. Base station 20 may include a receiver 21, for example a wireless receiver, a processor 23 and an interface 25. Receiver 21 may receive a signal including segment 36 of pseudo-randomly generated value sequence. For example, the pseudo-randomly generated value sequence may be generated by a pseudo- random value generator executed by a user equipment device, as described in detail herein above. In some embodiments, channel hopping may be used for secured communication with base station 20.

For example, base station 20 receives from device 30 a transmission including segment 36 or a series of segments 36 of the pseudo-random generated value sequence. The transmission may also include a time offset determined by timer 37 and/or the channel used for transmission.

Processor 23 may use a decoder 24 to decode segment 36 from the signal. Then, processor 23 may perform time stamping of segment 36 for creating a time stamped segment 36a, including segment 36 along with a time-stamp. For example, base station 20 couples a respective time stamp(s) to segment(s) 36, for example by a timer 22, for example according to the received time offset and/or the time of receiving segment(s) 36 at base station 20. Then, base station 20 produces a time stamped segment 36a or a series of time stamped segments 36a of the pseudo-randomly generated value sequences.

Processor 23 may produce location data 26 indicative of the location of device 30, for example extract location data 26 from the received signal. Location data 26 may include, for example, Time of Arrival (ToA) data, Angle of Arrival (AoA) data, Received Signal Strength Indicator (RSSI) and/or any other suitable location data indicative of a location of a user equipment device. Location data 26 may facilitate determination of a location of device 30 by a receiving network node, as described in detail herein below. In some embodiments of the present invention, base station 20 produces location data 26 by performing signal analysis, for example at least on a received pilot signal, by ToA measurement, AoA measurement, triangulation, trilateration, RSSI, and/or any other suitable location estimation method.

Interface 25 may communicate with at least one network node (not shown) such as, for example, a network interface 10 and/or a processor 12 described in detail herein. Interface 25 may transmit time stamped segment 36a and/or location data 26, for example to a network node. The network node may, for example, determine a location of user equipment device 30 based on the time stamped segment 36a and/or location data 26, for example as described in more detain herein below. Referring back to FIG. 2, Network 200 may include a network interface 10, a processor 12 and a storage unit 16. Storage unit 16 may include a user device keys storage 13, storing a plurality of device-exclusive keys, including key 33, each associated exclusively with another user device.

As indicated in block 110, network interface 10 may receive, for example, from at least one base station 20, a time stamped segment 36a and a location data 26. In some embodiments of the present invention, time stamped segments 36a are generated and/or transmitted such that a number of symbols in a segment 36a and/or a mean time interval between time stamped segments 36a can vary and/or be adjusted, so that a length of segment 36a may not suffice for reliably identifying a device, or the location of device 30, for example without other context stored within processor 12 and/or received by processor 12, such as prior location data 26, or data from other base stations. In some embodiments of the present invention, network interface

10 may rely on location data 26 from multiple base stations 20 in order to more accurately determine a location of device 30.

Processor 12 may execute a reference pseudo-random value generator 14, correlated with pseudo-random value generator 32, as described in more detail herein. As indicated in block 120, processor 12 may generate a reference value sequence by reference value generator 14, and produce from the reference value sequence a time-correlated reference segment, time correlated with time-stamped segment 36a, for example based on the correlation between pseudo-random value generator 32 and reference value generator 14. For example, in some embodiments of the present invention, pseudo-random value generator 32 and reference value generator 14 execute a common function for generating pseudo-random value sequence 36 and the reference value sequence, respectively. In some embodiments of the present invention, pseudo-random value generator 32 and reference value generator 14 generate pseudo-random sequence segment 36 and the reference value sequence, respectively, by combining a common unique key such as key 33, with a predictably changing number matching to varying sequence 34. For example, varying sequence 34 may be a public varying sequence stored concurrently in user device 30 and in storage 16, for example, as sequence 11. Sequence 34 and sequence

11 may vary concurrently and in the same manner. In some embodiments, sequence 11 may be slightly time-drifted relative to sequence 34.

In some embodiments, processor 12 generates and/or stores in storage 16, for example, in search space data storage 15, a search space of potentially matching reference segments to a certain time-stamped segment 36a. For example, search space storage 15 may also include location probability distributions, based on which the search space may be made. For example, processor 12 generates by pseudo-random value generator 32 multiple reference segments that may potentially match a received time-stamped segment 36a. For example, processor 12 may produce the reference segments according to estimated time range in which time-stamped segment 36a was received, for example estimated based on the time stamp received from base station 20.

Matching between time-stamped segment 36a and the time-correlated reference segment may indicate a location of device 30, for example when analyzed along with location data 26. Location data 26 may include, for example, the location of base station 20 and angle and/or round trip time of arrival of signals from device 30. Based on the location data, processor 12 may estimate the area from which sequence segment 36 arrived, and therefore, for example, which devices most possibly sent sequence segment 36. For example, processor 12 may use the area estimation for deciding which keys 33 to use for generation of the reference segment.

A match is made, for example, by finding overlap between time-stamped segment 36a and the reference segment. By receiving a series of time-stamped segments 36a, the probability that no matching is identified is reduced.

As described in detail above, device 30 produces the pseudo-random sequence so that the sequence is predictable by processor 12, for example by using sequence 11 and key 33. In some exemplary embodiments of the present invention, the length of a sequence segment 36 is also predictable. For example, the length of a segment 36 may be decided by a predictable pseudo-random method. In such cases, processor 12 produces the predictable reference segment with the corresponding predictable length, and may try to identify a match in both sequence and length between the time stamped segment 36a and at least one of the reference segments. In some other embodiments, the length of segment 36 is not predictable by processor 12. For example, that segment 36 may be first N bits of the sequence, wherein N is unpredictable to processor 12. In such cases, processor 12 may compare segment 36a to a full length sequence generated by sequence 11 and key 33, wherein a first N bits of the full length sequence should match segment 36a.

As indicated in block 130, processor 12 may identify a match between the time stamped segment 36a and at least one of the reference segments. For example, a match between a time stamped segment 36a and at least one of the reference segments may enable processor 12 to identify, for example according to the key used for generation of the reference segment, the identity of device 30. As indicated in block 140, processor 12 may then determine a momentary location of user equipment device 30 according to the match between time-stamped segment 36a and the time-correlated reference segment and, for example, according to location data 26 received from base station 20. For example, according to a measure of overlap between time- stamped segment 36a and the reference segment, processor 12 may deduce a distance made by a signal from device 30 to network interface 10.

Processor 12 may determine the momentary location of device 30, for example, by estimating the distance between base station 20 and device 30 according to the time of arrival of signals from device 30, a known location of base station 20, and/or the received signal power. The direction in which device 30 is located may be estimated by angle of arrival information received from base station 20. In some embodiments, more than one base station 20 may receive transmissions from the same device 30 and may provide to processor 12 the time of arrival and/or angle of arrival, which may enhance the accuracy of the location estimation.

In some embodiments, once a momentary location of device 30 is determined, and based on the known key 33 and sequence 11, processor 12 estimates what the next received segment 36a would be and in what time delay from the last segment 36a. For example, processor 12 may predict the next segment 36a by carrying out a Hidden Markov Model (HMM) prediction of the next segment 36a based on the last received segment 36a. The prediction may facilitate the generation by processor 12 of the search space of the potentially matching reference segments to the next time-stamped segment 36a.

The descriptions of the various embodiments of the present invention have been presented for purposes of illustration, but are not intended to be exhaustive or limited to the embodiments disclosed. Many modifications and variations will be apparent to those of ordinary skill in the art without departing from the scope and spirit of the described embodiments. The terminology used herein was chosen to best explain the principles of the embodiments, the practical application or technical improvement over technologies found in the marketplace, or to enable others of ordinary skill in the art to understand the embodiments disclosed herein.

As used herein the term "about" refers to ± 10 %.

The terms "comprises", "comprising", "includes", "including", "having" and their conjugates mean "including but not limited to". This term encompasses the terms "consisting of and "consisting essentially of.

The phrase "consisting essentially of means that the composition or method may include additional ingredients and/or steps, but only if the additional ingredients and/or steps do not materially alter the basic and novel characteristics of the claimed composition or method.

As used herein, the singular form "a", "an" and "the" include plural references unless the context clearly dictates otherwise. For example, the term "a compound" or "at least one compound" may include a plurality of compounds, including mixtures thereof.

The word "exemplary" is used herein to mean "serving as an example, instance or illustration". Any embodiment described as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments and/or to exclude the incorporation of features from other embodiments.

The word "optionally" is used herein to mean "is provided in some embodiments and not provided in other embodiments". Any particular embodiment of the invention may include a plurality of "optional" features unless such features conflict.

Throughout this application, various embodiments of this invention may be presented in a range format. It should be understood that the description in range format is merely for convenience and brevity and should not be construed as an inflexible limitation on the scope of the invention. Accordingly, the description of a range should be considered to have specifically disclosed all the possible subranges as well as individual numerical values within that range. For example, description of a range such as from 1 to 6 should be considered to have specifically disclosed subranges such as from 1 to 3, from 1 to 4, from 1 to 5, from 2 to 4, from 2 to 6, from 3 to 6 etc., as well as individual numbers within that range, for example, 1, 2, 3, 4, 5, and 6. This applies regardless of the breadth of the range.

Whenever a numerical range is indicated herein, it is meant to include any cited numeral (fractional or integral) within the indicated range. The phrases "ranging/ranges between" a first indicate number and a second indicate number and "ranging/ranges from" a first indicate number "to" a second indicate number are used herein interchangeably and are meant to include the first and second indicated numbers and all the fractional and integral numerals therebetween.

It is appreciated that certain features of the invention, which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention, which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination or as suitable in any other described embodiment of the invention. Certain features described in the context of various embodiments are not to be considered essential features of those embodiments, unless the embodiment is inoperative without those elements. All publications, patents and patent applications mentioned in this specification are herein incorporated in their entirety by reference into the specification, to the same extent as if each individual publication, patent or patent application was specifically and individually indicated to be incorporated herein by reference. In addition, citation or identification of any reference in this application shall not be construed as an admission that such reference is available as prior art to the present invention. To the extent that section headings are used, they should not be construed as necessarily limiting.