Methods and apparatuses for quantifying the holistic value of an existing network of devices by measuring the complexity of a generated grammar

• US 9,600,465 B2
• Filed: 01/07/2015
• Issued: 03/21/2017
• Est. Priority Date: 01/10/2014
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Glickfield, Sarah, Guedalia, Isaac David
• Primary Examiner(s): Hudspeth, David
• Assistant Examiner(s): PATEL, SHREYANS A
• Application Number:
  US14/591,458
• Publication Number:
  US 20150199330A1
• Time in Patent Office: 804 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/30 Monitoring
• CPC Class Codes: G06F 11/3476 Data logging G06F11/14, G06F11/2205 take precedence
• CPC Class Codes: G06F 9/54 Interprogram communication
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G16Y 10/75 Information technology; Communication
• CPC Class Codes: G16Y 20/20 relating to the thing itself
• CPC Class Codes: H04L 69/06 Notations for structuring of protocol data, e.g. abstract syntax notation one [ASN.1]
• CPC Class Codes: H04W 4/70 Services for machine-to-machine communication [M2M] or machine type communication [MTC]

Abstract

Method and apparatuses for constructing a grammar to describe interactions among a plurality of devices in a network are disclosed. An aspect receives, by a network interface of a device, device capabilities of each of the plurality of devices, generates, by a reduced device list generator of the device, a reduced device list representing groupings of the plurality of devices based on the device capabilities, models, by an interaction sequence modeler of the device, one or more sequences of interactions among the plurality of devices using the reduced device list, constructs, by a grammar construction module of the device, the grammar based on the modeled one or more sequences of interactions, and stores the grammar in a memory of the device.

Claims

1. A method for constructing a grammar to describe interactions among a plurality of devices in a network, comprising:

receiving, by a network interface of a device, device capabilities of each of the plurality of devices;

generating, by a reduced device list generator of the device, a reduced device list representing groupings of the plurality of devices based on clustering the device capabilities, wherein a grouping of the plurality of devices comprises more than one device of the plurality of devices;

modeling, by an interaction sequence modeler of the device, one or more sequences of interactions among the plurality of devices based on assigning one or more interactions among a subset of the plurality of devices to one or more clusters of the plurality of clusters corresponding to the groupings of the plurality of devices represented by the reduced device list;

constructing, by a grammar construction module of the device, the grammar based on the modeled one or more sequences of interactions; and

storing the grammar in a memory of the device.

2. The method of claim 1, wherein the reduced device list generator performs the clustering of the device capabilities to generate the reduced list.

3. The method of claim 1, further comprising:

receiving one or more observation logs, the one or more observation logs including information about one or more interactions among the subset of the plurality of devices.

4. The method of claim 3, wherein the clustering comprises:

generating one or more feature vectors representing the received one or more observation logs; and

clustering the one or more feature vectors to generate the reduced device list.

5. The method of claim 1, further comprising:

receiving a log of the one or more interactions among the subset of the plurality of devices.

6. The method of claim 5, wherein the log is received from a device of the plurality of devices that is not involved in the one or more interactions.

7. The method of claim 5, wherein the modeling the one or more sequences of interactions comprises:

assigning a sequence of the one or more interactions to a sequence of one or more centroids of the plurality of clusters to model the one or more sequences of interactions.

8. The method of claim 1, wherein the device comprises an Internet of Things (IoT) server.

9. The method of claim 1, wherein the device comprises a supervisor device in the network other than an IoT server.

10. The method of claim 1, wherein the plurality of devices comprises a plurality of IoT devices.

11. An apparatus for constructing a grammar to describe interactions among a plurality of devices in a network, comprising:

a network interface configured to receive device capabilities of each of the plurality of devices;

a reduced device list generator configured to generate a reduced device list representing groupings of the plurality of devices based on the device capabilities being clustered, wherein a grouping of the plurality of devices comprises more than one device of the plurality of devices;

an interaction sequence modeler configured to model one or more sequences of interactions among the plurality of devices based on one or more interactions among a subset of the plurality of devices being assigned to one or more clusters of the plurality of clusters corresponding to the groupings of the plurality of devices represented by the reduced device list;

a grammar construction module configured to construct the grammar based on the modeled one or more sequences of interactions; and

a memory configured to store the grammar.

12. The apparatus of claim 11, wherein the reduced device list generator is further configured to cluster the device capabilities to generate the reduced list.

13. The apparatus of claim 11, wherein the network interface is further configured to receive one or more observation logs, the one or more observation logs including information about the one or more interactions among the subset of the plurality of devices.

14. The apparatus of claim 13, wherein the reduced device list generator being configured to cluster the device capabilities comprises the reduced device list generator being configured to:

generate one or more feature vectors representing the received one or more observation logs; and

cluster the one or more feature vectors to generate the reduced device list.

15. The apparatus of claim 11, wherein the network interface is further configured to receive a log of one or more interactions among the subset of the plurality of devices.

16. The apparatus of claim 15, wherein the log is received from a device of the plurality of devices that is not involved in the one or more interactions.

17. The apparatus of claim 15, wherein the interaction sequence modeler being configured to model one or more sequences of interactions comprises the interaction sequence modeler being configured to assign a sequence of the one or more interactions to a sequence of one or more centroids of the plurality of clusters to model the one or more sequences of interactions.

18. The apparatus of claim 11, wherein the apparatus comprises an Internet of Things (IoT) server.

19. The apparatus of claim 11, wherein the apparatus comprises a supervisor device in the network other than an IoT server.

20. The apparatus of claim 11, wherein the plurality of devices comprises a plurality of IoT devices.

21. An apparatus for constructing a grammar to describe interactions among a plurality of devices in a network, comprising:

means for receiving, by a network interface of a device, device capabilities of each of the plurality of devices;

means for generating, by a reduced device list generator of the device, a reduced device list representing groupings of the plurality of devices based on the device capabilities being clustered, wherein a grouping of the plurality of devices comprises more than one device of the plurality of devices;

means for modeling, by an interaction sequence modeler of the device, one or more sequences of interactions among the plurality of devices based on one or more interactions among a subset of the plurality of devices being assigned to one or more clusters of the plurality of clusters corresponding to the groupings of the plurality of devices represented by the reduced device list;

means for constructing, by a grammar construction module of the device, the grammar based on the modeled one or more sequences of interactions; and

means for storing the grammar in a memory of the apparatus.

22. The apparatus of claim 21, wherein the means for generating the reduced device list clusters the device capabilities to generate the reduced list.

23. The apparatus of claim 21, further comprising:

means for receiving one or more observation logs, the one or more observation logs including information about one or more interactions among the subset of the plurality of devices.

24. The apparatus of claim 23, wherein the means for clustering comprises:

means for generating one or more feature vectors representing the received one or more observation logs; and

means for clustering the one or more feature vectors to generate the reduced device list.

25. A non-transitory computer-readable medium for constructing a grammar to describe interactions among a plurality of devices in a network, comprising:

at least one instruction to receive, by a network interface of a device, device capabilities of each of the plurality of devices;

at least one instruction to generate, by a reduced device list generator of the device, a reduced device list representing groupings of the plurality of devices based on the device capabilities being clustered, wherein a grouping of the plurality of devices comprises more than one device of the plurality of devices;

at least one instruction to model, by an interaction sequence modeler of the device, one or more sequences of interactions among the plurality of devices based on one or more interactions among a subset of the plurality of devices being assigned to one or more clusters of the plurality of clusters corresponding to the groupings of the plurality of devices represented by the reduced device list;

at least one instruction to construct, by a grammar construction module of the device, the grammar based on the modeled one or more sequences of interactions; and

at least one instruction to store the grammar in a memory of the device.

26. The non-transitory computer-readable medium of claim 25, wherein the reduced device list generator clusters the device capabilities to generate the reduced list.

27. The non-transitory computer-readable medium of claim 25, further comprising:

at least one instruction to receive one or more observation logs, the one or more observation logs including information about one or more interactions among the subset of the plurality of devices.

28. The non-transitory computer-readable medium of claim 27, wherein the at least one instruction to cluster comprises:

at least one instruction to generate one or more feature vectors representing the received one or more observation logs; and

at least one instruction to cluster the one or more feature vectors to generate the reduced device list.

29. The non-transitory computer-readable medium of claim 25, further comprising:

at least one instruction to receive a log of one or more interactions among the subset of the plurality of devices.

30. The non-transitory computer-readable medium of claim 29, wherein the at least one instruction to model the one or more sequences of interactions comprises:

at least one instruction to assign a sequence of the one or more interactions to a sequence of one or more centroids of the plurality of clusters to model the one or more sequences of interactions.