Roaming and transition patterns coding in wireless networks for cognitive visibility

• US 10,728,775 B2
• Filed: 05/08/2019
• Issued: 07/28/2020
• Est. Priority Date: 06/08/2017
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Savalle, Pierre-Andre, Mermoud, Gregory, Vasseur, Jean-Philippe, Cruz Mota, Javier
• Primary Examiner(s): Islam, Rownak
• Application Number:
  US16/406,535
• Publication Number:
  US 20190268784A1
• Time in Patent Office: 447 Days
• Field of Search: 370254
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 24/02 Arrangements for optimising operational condition
• CPC Class Codes: H04W 36/00835 Determination of neighbour cell lists
• CPC Class Codes: H04W 36/30 by measured or perceived connection quality data
• CPC Class Codes: H04W 36/32 by location or mobility data, e.g. speed data
• CPC Class Codes: H04W 40/22 using selective relaying for reaching a BTS [Base Transceiver Station] or an access point
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 locating network equipment
• CPC Class Codes: H04W 84/12 WLAN [Wireless Local Area Networks]

Abstract

In one embodiment, a device receives data regarding usage of access points in a network by a plurality of clients in the network. The device maintains an access point graph that represents the access points in the network as vertices of the access point graph. The device generates, for each of the plurality of clients, client trajectories as trajectory subgraphs of the access point graph. A particular client trajectory for a particular client comprises a set of edges between a subset of the vertices of the access point graph and represents transitions between access points in the network performed by the particular client. The device identifies a transition pattern from the client trajectories by deconstructing the trajectory subgraphs. The device uses the identified transition pattern to effect a configuration change in the network.

Claims

1. A method comprising:

receiving, at a device, data regarding usage of access points in a network by a plurality of clients in the network;

maintaining, by the device, an access point graph based on the data regarding usage of access points, wherein the access point graph represents the access points in the network as vertices of the access point graph;

generating, by the device and for each of the plurality of clients, client trajectories as trajectory subgraphs of the access point graph, wherein a particular client trajectory for a particular client comprises a set of edges between a subset of the vertices of the access point graph and represents transitions between access points in the network performed by the particular client;

identifying, by the device, a transition pattern from the client trajectories by deconstructing the trajectory subgraphs, wherein the identified transition pattern indicates that a particular access point is underutilized due to an occlusion condition; and

using, by the device, the identified transition pattern to effect a configuration change in the network that removes the occlusion condition.

2. The method as in claim 1, wherein using the identified transition pattern to effect a configuration change in the network comprises:

providing, by the device, an indication of the identified transition pattern to a user interface.

3. The method as in claim 1, wherein identifying the transition pattern from the client trajectories by deconstructing the trajectory subgraphs comprises:

performing, by the device, frequent subgraph mining on the subgraphs, to identify the transition pattern.

4. The method as in claim 1, wherein identifying the transition pattern from the client trajectories by deconstructing the trajectory subgraphs comprises:

representing, by the device, the edges of the subgraphs as entries in feature vectors for the trajectories; and

applying, by the device, dictionary learning to the feature vector entries for the trajectories, to identify the transition pattern.

5. The method as in claim 4, further comprising:

applying, by the device, a weighting to the feature vector entries to emphasize transitions of interest.

6. The method as in claim 1, wherein using the identified transition pattern to effect a configuration change in the network comprises:

providing, by the device, an indication of the identified transition pattern to a machine learning-based anomaly detector.

7. The method as in claim 1, wherein an end of a trajectory corresponds to an access point transition by a client for which a subsequent access point transition is not observed within a predefined amount of time.

8. An apparatus comprising:

one or more network interfaces to communicate with a network;

a processor coupled to the network interfaces and configured to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed configured to;

receive data regarding usage of access points in a network by a plurality of clients in the network;

maintain an access point graph based on the data regarding usage of access points, wherein the access point graph represents the access points in the network as vertices of the access point graph;

generate, for each of the plurality of clients, client trajectories as trajectory subgraphs of the access point graph, wherein a particular client trajectory for a particular client comprises a set of edges between a subset of the vertices of the access point graph and represents transitions between access points in the network performed by the particular client;

identify a transition pattern from the client trajectories by deconstructing the trajectory subgraphs, wherein the identified transition pattern indicates that a particular access point is underutilized due to an occlusion condition; and

use the identified transition pattern to effect a configuration change in the network that removes the occlusion condition.

9. The apparatus as in claim 8, wherein the apparatus uses the identified transition pattern to effect a configuration change in the network by:

providing an indication of the identified transition pattern to a user interface.

10. The apparatus as in claim 8, wherein the apparatus identifies the transition pattern from the client trajectories by deconstructing the trajectory subgraphs by:

performing frequent subgraph mining on the subgraphs, to identify the transition pattern.

11. The apparatus as in claim 8, wherein the apparatus identifies the transition pattern from the client trajectories by:

representing the edges of the subgraphs as entries in feature vectors for the trajectories; and

applying dictionary learning to the feature vector entries for the trajectories, to identify the transition pattern.

12. The apparatus as in claim 11, wherein the process when executed further comprises:

applying, by the device, a weighting to the feature vector entries to emphasize transitions of interest.

13. The apparatus as in claim 8, wherein the apparatus uses the identified transition pattern to effect a configuration change in the network by:

providing an indication of the identified transition pattern to a machine learning-based anomaly detector.

14. The apparatus as in claim 8, wherein an end of a trajectory corresponds to an access point transition by a client for which a subsequent access point transition is not observed within a predefined amount of time.

15. A tangible, non-transitory, computer-readable medium having software encoded thereon, the software when executed by a device configured to cause the device to perform a process comprising:

receiving, at the device, data regarding usage of access points in a network by a plurality of clients in the network;

maintaining, by the device, an access point graph based on the data regarding usage of access points, wherein the access point graph represents the access points in the network as vertices of the access point graph;

generating, by the device and for each of the plurality of clients, client trajectories as trajectory subgraphs of the access point graph, wherein a particular client trajectory for a particular client comprises a set of edges between a subset of the vertices of the access point graph and represents transitions between access points in the network performed by the particular client;

identifying, by the device, a transition pattern from the client trajectories by deconstructing the trajectory subgraphs, wherein the identified transition pattern indicates that a particular access point is underutilized due to an occlusion condition; and

using, by the device, the identified transition pattern to effect a configuration change in the network that removes the occlusion condition.

16. The tangible, non-transitory, computer-readable medium as in claim 15, wherein the apparatus uses the identified transition pattern to effect a configuration change in the network by:

providing an indication of the identified transition pattern to a user interface.

17. The tangible, non-transitory, computer-readable medium as in claim 15, wherein the apparatus identifies the transition pattern from the client trajectories by deconstructing the trajectory subgraphs by:

performing frequent subgraph mining on the subgraphs, to identify the transition pattern.

18. The tangible, non-transitory, computer-readable medium as in claim 15, wherein the apparatus identifies the transition pattern from the client trajectories by:

representing the edges of the subgraphs as entries in feature vectors for the trajectories; and

applying dictionary learning to the feature vector entries for the trajectories, to identify the transition pattern.

19. The tangible, non-transitory, computer-readable medium as in claim 18, wherein the process when executed further comprises:

applying, by the device, a weighting to the feature vector entries to emphasize transitions of interest.

20. The tangible, non-transitory, computer-readable medium as in claim 15, wherein the apparatus uses the identified transition pattern to effect a configuration change in the network by:

providing an indication of the identified transition pattern to a machine learning-based anomaly detector.