System and method for identifying wireless devices using pulse fingerprinting and sequence analysis

• US 7,835,319 B2
• Filed: 05/09/2007
• Issued: 11/16/2010
• Est. Priority Date: 05/09/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Sugar, Gary L.
• Primary Examiner(s): Appiah; Charles N
• Assistant Examiner(s): Karikari; Kwasi
• Application Number:
  US11/746,275
• Publication Number:
  US 20070264939A1
• Time in Patent Office: 1,287 Days
• Field of Search: 455/462, 455/226.1, 455/67.11, 455/296
• US Class Current: 370/328
• CPC Class Codes: H04B 17/309 Measuring or estimating channel quality parameters

Abstract

Methods are provided for identifying devices that are sources of wireless signals from received radio frequency (RF) energy. RF energy is received at a device called a sensor device herein. Pulse metric data is generated from the received RF energy. The pulse metric data represents characteristics associated with pulses of received RF energy. The pulses are partitioned into groups based on their pulse metric data such that a group comprises pulses having similarities for at least one item of pulse metric data. Sources of the wireless signals are identified based on the partitioning process. The partitioning process involves iteratively subdividing each group into subgroups until all resulting subgroups contain pulses determined to be from a single source. At each iteration, subdividing is performed based on different pulse metric data than at a prior iteration. Ultimately, output data is generated (e.g., a device name for display) that identifies a source of wireless signals for any subgroup that is determined to contain pulses from a single source.

Claims

1. A method for identifying devices that are sources of wireless signals from received radio frequency (RF) energy, comprising:

receiving RF energy;

generating pulse metric data from the received RF energy, the pulse metric data representing characteristics associated with pulses of received RF energy;

partitioning the pulses into groups based on their pulse metric data, wherein partitioning comprises iteratively subdividing each group into subgroups until all resulting subgroups contain pulses determined to be from a single source, and at each iteration, said subdividing being performed based on different pulse metric data than at a prior iteration; and

identifying the sources of the received wireless signals based on the partitioning and generating as output data that identifies a source of wireless signals for any subgroup that is determined to contain pulses from a single source.

2. The method of claim 1, wherein said generating comprises generating pulse metric data comprising one or more protocol-specific characteristics or device-specific characteristics, and wherein partitioning comprises partitioning the pulse metric data for individual pulses base on the protocol-specific and device-specific characteristics.

3. The method of claim 1, wherein generating pulse metric data comprises generating protocol-specific characteristics comprising one or more of:

pulse type, protocol type indicated by one or more of a synchronization pattern, modulation type, data rate, frequency bandwidth, pulse duration, carrier frequency, center frequency, peak-to-average power ratio and frequency deviation.

4. The method of claim 1, wherein partitioning comprises partitioning the pulse metric data into groups based on pulse type to produce a plurality of pulse type specific groups each comprising pulse metric data having the same pulse type, and further subdividing each pulse type specific group into subgroups using partitioning rules that are unique to each pulse type.

5. The method of claim 4, wherein generating comprises generating pulse metric data comprising device-specific characteristics comprising one or more of:

pulse timestamp or start time, pulse power, carrier frequency, pulse ramp up time, pulse ramp down time, pulse timing period and phase if the pulse is synchronous or periodic, modulation start/stop times and modulation signature.

6. The method of claim 5, wherein said further subdividing comprises subdividing each pulse type specific group into subgroups based on protocol-specific characteristics or device-specific characteristics.

7. The method of claim 4, and further comprising examining the pulse metric data for each subgroup resulting from said further subdividing to determine whether the pulses after said subdividing were received from a single wireless transmitter.

8. The method of claim 7, wherein said examining comprises applying a test to the pulse metric data for a subgroup to determine whether the pulse metric data for a subgroup comprises pulses from a single source.

9. The method of claim 8, wherein identifying comprises generating as output data that identifies a source of wireless signals for any subgroup that is determined to contain pulse metric data for a single source.

10. The method of claim 7, wherein generating comprises generating a synchronicity pulse metric that represents a measure of synchronicity of pulses derived from arrival times of the pulses in a sequence, and wherein examining comprises examining the synchronicity pulse metric to determine whether a subgroup comprises pulses from a single source.

11. The method of claim 10, wherein generating the synchronicity pulse metric comprising computing min_T sdev{(t_n/T+0.5)mod 1, n=1, . . . , N} for pulse arrival times t₁, . . . , t_N.

12. The method of claim 11, and further comprising determining that pulses are synchronous with period T₀ and phase t₀ if T₀ minimizes the equation f(T)=sdev{(t_n/T+0.5)mod 1, n=1, . . . , N} over T with a synchronicity f(T₀) that falls below a pre-determined threshold, where t₀=mean {t_n/T_o mod 1, n=1, . . . , N}.

13. The method of claim 12, wherein generating comprises generating a periodicity pulse metric that represents a measure of periodicity of pulses derived from arrival times of the pulses.

14. The method of claim 13, wherein generating comprises generating the periodicity pulse metric for pulses with arrival t₁, . . . , t_N, as max_{M in {1, 2, . . . floor(T/tN)}} NMT·

p/t_N, where p is a probability of detecting a pulse.

15. The method of claim 14, and further comprising determining that pulses are periodic with period MT and phase t₀ if (a) the pulses are synchronous with period T₀, and (b) M maximizes max_{M in {1, 2, . . . floor (T/tN)}} NMT·

p/t_N with a periodicity that exceeds a pre-determined threshold, and where t₀=mean {t_n/(MT₀)mod 1, n=1, . . . , N}.

16. The method of claim 1, wherein identifying comprises identifying sources of wireless signals whose transmission protocol is known or unknown.

17. The method of claim 1, wherein receiving, generating and partitioning are performed by each of a plurality of different sensor devices, and wherein identifying is performed at a central computing device based on pulse metric data generated by each of the plurality of sensor devices.

18. The method of claim 17, wherein identifying comprises identifying whether pulses received at multiple sensor devices are from the same source based on similarities of the pulse metric data generated by two or more sensor devices for those pulses.

19. The method of claim 18, and further comprising said central computing device transmitting a message to each of the sensor devices to synchronize them with respect to a common clock such that said receiving generating and partitioning are performed by each of the plurality of sensor devices with respect to a common clock.

20. The method of claim 19, and further comprising said central computing device processing the pulse metric data from the plurality of sensor devices to adjust for offsets of system clocks among the plurality of sensor devices.

21. A method for identifying devices that are sources of wireless signals from received radio frequency (RF) energy, comprising:

receiving RF energy;

generating pulse metric data from the received RF energy, the pulse metric data representing characteristics associated with pulses of received RF energy, wherein generating comprises generating pulse metric data representing arrival times for pulses of RF energy and deriving candidate periods for the pulses;

partitioning the pulses into groups based on their candidate periods;

deriving phases for each of the groups of pulses that have been formed based on the candidate periods;

further subdividing the groups into subgroups based on phase; and

identifying the sources of the received wireless signals based on the subgroups formed by partitioning based on phase and other pulses remaining that were not grouped based on candidate period.

22. The method of claim 21, wherein identifying comprises identifying asynchronous sources from those pulses that were not included in a group formed based on candidate periods.

23. The method of claim 21, wherein identifying comprises identifying synchronous sources as corresponding to pulses contained in a group formed based on candidate periods.

24. The method of claim 21, wherein deriving candidate periods comprises computing autocorrelation values from the arrival times of the sequence of pulses and analyzing the autocorrelation values to identify the candidate periods.

25. The method of claim 24, wherein computing comprises computing a function that is a normalized product of harmonics of the autocorrelation values, and wherein said analyzing comprises analyzing results of said function for peaks where said peaks correspond to said candidate periods.

26. The method of claim 25, and further comprising storing said results of said function in a first buffer, and wherein computing further comprises removing from said results timestamp values that line up with each other after they are time shifted by candidate period Ti, and storing the timestamp values that were removed in a second buffer.

27. The method of claim 26, and further comprising computing a histogram of the timestamp values modulo Ti.

28. The method of claim 27, wherein deriving phases comprises identifying different timing phases as peaks in the histogram to form groups of pulses that appear to be received from a single source device.

29. The method of claim 28, wherein said removing, storing in said second buffer, computing the histogram and identifying phases as peaks are repeated for each candidate period.

30. The method of claim 29, wherein identifying further comprises identifying sources of wireless signals that are on the same time-synchronized wireless network by identifying pulses that have the same pulse period but their pulse phases and pulse durations are such that their transmissions do not overlap in time.

31. The method of claim 21, wherein generating comprises generating pulse metric data further comprising one or more of carrier frequency, modulation type, and power of the pulses, and wherein identifying comprises distinguishing wireless signal sources based further on one or more of carrier frequency, modulation type, and power.

32. A method for identifying devices that are sources of wireless signals from received radio frequency (RF) energy, comprising:

receiving RF energy;

generating pulse metric data from the received RF energy, the pulse metric data representing characteristics associated with pulses of received RF energy comprising carrier frequencies of pulses;

analyzing the carrier frequencies to determine a set of zero or more candidate frequency spacings to be used for identifying a hopset of a frequency hopping channelization scheme;

determining one or more channelization schemes associated with the pulses using the set of candidate frequency spacings and the carrier frequencies for the pulses, wherein a channelization scheme comprises a set of one or more transmit frequencies;

partitioning the pulses into groups based on their pulse metric data, wherein each group corresponds to a channelization scheme, and subdividing each group of pulses into subgroups based on differences between the carrier frequencies for pulses in the group and a particular one of the transmit frequencies for the corresponding channelization scheme; and

identifying a source of received wireless signals based on the one or more subgroups that result from the partitioning.

33. The method of claim 32, and further comprising determining whether a subgroup contains pulses that are from a single source for a channelization scheme.

34. The method of claim 32, wherein determining one or more channelization schemes comprises determining start frequency, stop frequency and frequency increment for a frequency hopping channelization scheme determined to be associated with the pulses.

35. The method of claim 32, and further comprising computing differences between carrier frequencies for a group of pulses and a nearest transmit frequency of the corresponding channelization scheme for that group of pulses, and wherein subdividing comprises subdividing the pulses into subgroups based on the differences.

36. The method of claim 32, and further comprising computing a histogram on the carrier frequencies for the pulses, and wherein said determining one or more channelization schemes comprises, for each candidate frequency spacing, determining whether there is a peak in the histogram at an integer multiple of the candidate frequency spacing, to thereby identify frequency hops associated with a frequency hopping channelization scheme.

37. The method of claim 32, wherein partitioning comprises assigning a pulse to a group associated with a frequency hopping channelization scheme when it is determined from the histogram that the carrier frequency of that pulse is at an integer multiple of a candidate frequency spacing.

38. The method of claim 37, wherein partitioning comprises forming zero or more groups of pulses associated with a fixed frequency channelization scheme and forming zero or more groups of pulses associated with a frequency hopping channelization scheme.

39. The method of claim 37, wherein subdividing comprises subdividing each of the groups of pulses to distinguish different sources using a fixed frequency channelization scheme and different sources using a frequency hopping channelization scheme.

40. A device that receives radio frequency (RF) energy and identifies devices that are sources of wireless signals in the RF energy, comprising:

a receiver that receives RF energy;

an analog-to-digital converter that converts received RF energy to a digital data; and

a processor coupled to the analog-to-digital converter and configured to;

generates generate pulse metric data from the digital data, the pulse metric data representing characteristics associated with pulses of RF energy;

partition the pulse metric data for individual pulses into groups based on their characteristics by iteratively subdividing each group into subgroups until all resulting subgroups contain pulse metric data for pulses determined to be from a single source, wherein at each iteration, subdividing is performed based on different pulse metric data than at a prior iteration; and

identify sources of wireless signals contained in the RF energy based on the groups and generate as output data that identifies a source of wireless signals for any subgroup that is determined to contain pulse metric data for a single source.

41. The device of claim 40, wherein the processor generates pulse metric data comprising one or more one or more protocol-specific characteristics or device-specific characteristics, and the processor partitions the pulse metric data for individual pulses base on the protocol-specific and device-specific characteristics.

42. The device of claim 40, wherein the processor is configured to partition the pulses into groups based on pulse type to produce a plurality of pulse type specific groups each comprising pulse metric data having the same pulse type, and to further subdivide each pulse type specific group into subgroups using partitioning rules that are unique to each pulse type.

43. The device of claim 42, wherein the processor is configured to generate pulse metric data comprising device-specific characteristics comprising one or more of:

pulse timestamp or start time, pulse power, carrier frequency, pulse ramp up time, pulse ramp down time, pulse timing period and phase if the pulse is synchronous or periodic, modulation start/stop times and modulation signature.

44. The device of claim 42, wherein the processor is configured to examine the pulse metric data for each subgroup resulting from further subdividing to determine whether the pulses after subdividing were received from a single wireless transmitter.

45. The device of claim 42, wherein the processor is configured to generate pulse metric data comprising data representing arrival times for pulses of RF energy and deriving candidate periods for the pulses, and to partition the pulses into groups based on their candidate periods.

46. A method for identifying devices that are sources of wireless signals from received radio frequency (RF) energy, comprising:

receiving RF energy;

generating protocol-specific pulse data and device-specific pulse data from the received RF energy;

sorting data for pulses into groups to form a group of pulses whose transmission protocol is known and a group of pulses whose transmission protocol is not known;

subdividing the group of pulses whose transmission protocol is not known into subgroups based on protocol-specific pulse data for those pulses to produce one or more subgroups, each subgroup comprising data for pulses having similar protocol-specific pulse data and thus corresponding to the same unknown transmission protocol;

assigning a protocol identifier to each subgroup that comprises pulse data for pulses from one or more devices using the same unknown transmission protocol;

iteratively subdividing each subgroup corresponding to an unknown transmission protocol into further subgroups based on device-specific pulse data until resulting subgroups contain pulses determined to be from a single device;

assigning a device identifier to each resulting subgroup containing pulses from a single device;

storing the protocol-specific pulse data for each protocol identifier;

generating protocol-specific pulse data and device-specific pulse data for RF energy received after said storing; and

comparing the protocol-specific pulse data with said stored pulse protocol-specific pulse data to determine when pulses of RF energy are received that match the pulse-specific pulse data for an unknown transmission protocol that has been recognized as a result of said subdividing, assigning and storing.

47. The method of claim 46, wherein generating protocol-specific pulse data comprises generating at least one of:

pulse type and protocol type, wherein the protocol type is indicated by one or more of a synchronization pattern, modulation type, data rate, frequency bandwidth, pulse duration, carrier frequency, peak-to-average power ratio and frequency deviation.

48. The method of claim 46, wherein generating protocol-specific pulse data comprises analyzing demodulated data derived from received RF energy to identify at least one pattern that is constant across multiple instances of pulses of RF energy from multiple devices, and wherein storing comprises storing said at least one pattern.

49. The method of claim 46, wherein generating device-specific pulse data comprises generating one or more of:

pulse timestamp or start time, pulse power, carrier frequency, pulse ramp up time, pulse ramp down time, pulse timing period and phase if the pulse is synchronous or periodic, modulation start/stop times and modulation signature.

50. The method of claim 46, wherein generating device-specific pulse data comprises analyzing demodulated data derived from received RF energy to identify at least one pattern that is constant for all pulses of RF energy that are determined to be associated with a single device but changes for pulses across multiple devices determined to have the same protocol-specific characteristics, and wherein storing comprises storing said at least one pattern and an associated device identifier assigned to the at least one pattern.

51. The method of claim 46, wherein assigning a device identifier comprises assigning one of a persistent device identifier and a non-persistent device identifier, wherein a persistent device identifier is assigned to a subgroup for a single device that is formed on the basis of device-specific pulse data that is substantially the same each time the corresponding device turns on and the non-persistent device identifier is assigned to a subgroup for a single device that is formed on the basis of device-specific pulse data that changes each time the corresponding device turns on.

52. A method for identifying devices that are sources of wireless signals from received radio frequency (RF) energy, comprising:

receiving RF energy;

generating protocol-specific pulse data and device-specific pulse data from the received RF energy;

sorting data for pulses into groups to form a group of pulses whose transmission protocol is known and a group of pulses whose transmission protocol is not known;

subdividing the group of pulses whose transmissions protocol is not known into subgroups based on protocol-specific pulse data to produce one or more subgroups, each subgroup comprising data for pulses having similar protocol-specific pulse data and thus corresponding to the same unknown transmission protocol;

assigning a protocol identifier to each subgroup that comprises pulse data for pulses from one or more devices using the same unknown transmission protocol;

iteratively subdividing each subgroup corresponding to an unknown transmission protocol into further subgroups based on device-specific pulse data until resulting subgroups contain pulses determined to be from a single device;

examining demodulated data for pulses from multiple subgroups determined to be from a single device and having the same protocol identifier to identify one or more bit fields that are constant across multiple packets from multiple subgroups having the same protocol identifier; and

storing said one or more bit fields as a synchronization pattern for a corresponding transmission protocol for use as one type of protocol-specific pulse data to group pulses for subsequently received RF energy.

53. The method of claim 52, and further comprising deriving a device address for a particular device from pulses for subgroups determined to be from a single device and which subgroups have the same protocol identifier, and storing the device address for use as device-specific pulse data to group pulses for subsequently received RF energy.

54. The method of claim 53, wherein deriving comprises analyzing demodulated data from pulses for subgroups determined to be from a corresponding single device and which subgroups have the same protocol identifier to identify a device address comprising data in a range or ranges of bit positions in the demodulated data that (i) does not correspond to the synchronization pattern, (ii) are constant across all packets from a subgroup determined to be from a corresponding single device having the same protocol identifier, and (iii) is unique across subgroups determined to be from a corresponding single device having the same protocol identifier.

55. A method for identifying sources of wireless signals from received radio frequency (RF) energy, comprising:

detecting pulses of RF energy;

determining carrier frequencies of the pulses;

analyzing the carrier frequencies to determine a set of zero or more candidate frequency spacings to be used for identifying a hopset of a frequency hopping channelization scheme;

determining one or more channelization schemes associated with the pulses using the set of candidate frequency spacings and the carrier frequencies for the pulses, wherein a channelization scheme comprises a set of one or more transmit frequencies;

partitioning pulses into groups, wherein each group corresponds to a channelization scheme;

subdividing each group of pulses into subgroups based on differences between the carrier frequencies for pulses in the group and a particular one of the transmit frequencies for the corresponding channelization scheme; and

identifying sources of wireless signals based on the subgroups formed by said subdividing.

56. The method of claim 55, and further comprising determining whether a subgroup contains pulses that are from a single source for a channelization scheme.

57. The method of claim 55, wherein determining one or more channelization schemes comprises determining start frequency, stop frequency and frequency increment for a frequency hopping channelization scheme determined to be associated with the pulses.

58. The method of claim 55, and further comprising computing differences between carrier frequencies for a group of pulses and a nearest transmit frequency of the corresponding channelization scheme for that group of pulses, and wherein subdividing comprises subdividing the pulses into subgroups based on the differences.

59. The method of claim 55, and further comprising computing a histogram on the carrier frequencies for the pulses, and wherein determining one or more channelization schemes comprises, for each candidate frequency spacing, determining whether there is a peak in the histogram at an integer multiple of the candidate frequency spacing, to thereby identify frequency hops associated with a frequency hopping channelization scheme.

60. The method of claim 55, wherein partitioning comprises assigning a pulse to a group associated with a frequency hopping channelization scheme when it is determined from the histogram that the carrier frequency of that pulse is at an integer multiple of a candidate frequency spacing.

61. The method of claim 60, wherein partitioning comprises forming zero or more groups of pulses associated with a fixed frequency channelization scheme and forming zero or more groups of pulses associated with a frequency hopping channelization scheme.

62. The method of claim 60, wherein subdividing comprises subdividing each of the groups of pulses to distinguish different sources using a fixed frequency channelization scheme and different sources using a frequency hopping channelization scheme.

63. A method for identifying sources of wireless signals from received radio frequency (RF) energy, comprising:

detecting pulses of RF energy;

determining arrival times for the pulses;

deriving candidate periods for the pulses based on the arrival times, wherein deriving candidate periods comprises computing autocorrelation values from the arrival times of the sequence of pulses and analyzing the autocorrelation values to identify the candidate periods;

partitioning pulses into groups on their candidate periods;

deriving phases for each of the groups of pulses that have been formed based on candidate periods;

partitioning the groups into subgroups based on their phases; and

identifying sources of wireless signals based on the subgroups formed by partitioning based on phase and other pulses remaining that were not grouped based on candidate period.

64. The method of claim 63, wherein identifying comprises identifying asynchronous sources from those pulses that were not included in a group formed based on candidate periods.

65. The method of claim 63, wherein identifying comprises identifying synchronous sources as corresponding to pulses contained in a group formed based on candidate periods.

66. The method of claim 63, wherein computing comprises computing a function that is a normalized product of harmonics of the autocorrelation values, and wherein said analyzing comprises analyzing results of said function for peaks where said peaks correspond to said candidate periods.

67. The method of claim 66, and further comprising storing said results of said function in a first buffer, and wherein computing further comprises removing from said results timestamp values that line up with each other after they are time shifted by candidate period Ti, and storing the timestamp values that were removed in a second buffer.

68. The method of claim 67, and further comprising computing a histogram of the timestamp values modulo Ti.

69. The method of claim 68, wherein deriving phases comprises identifying different timing phases as peaks in the histogram to form groups of pulses that appear to be received from a single source device.

70. The method of claim 69, wherein said removing, storing in said second buffer, computing the histogram and identifying phases as peaks are repeated for each candidate period.

71. The method of claim 70, wherein identifying further comprises identifying sources of wireless signals that are communicating on the same time-synchronized wireless network by identifying pulses that have the same pulse period but their pulse phases and pulse durations are such that their transmissions do not overlap in time.

72. The method of claim 63, wherein generating comprises generating pulse metric data further comprising one or more of carrier frequency, modulation type, and power of the pulses, and wherein identifying comprises distinguishing wireless signal sources based further on one or more of carrier frequency, modulation type, and power.