PARTITIONING METHOD AND APPARATUS FOR PARTITIONING A PLURALITY OF WIRELESS ACCESS POINTS INTO MANAGEMENT CLUSTERS

Abstract

The partitioning method includes determining for each access point of access points a centrality parameter based on the obtained neighbour information, and partitioning access points into a first management cluster and at least one further management cluster by including in the first management cluster a first access point as a primary member, the first access point having the highest centrality parameter, and any neighbouring access point of the first access point as a secondary member; and for each further access point of points except the first access point, in order of descending centrality parameter, forming a further management cluster by including in the further management cluster the respective further access point as the primary member and, as one of the secondary members, any neighbouring access point sensed by the respective further access point which has not been included as one of the secondary members in another management cluster.

Claims

1. A partitioning method for partitioning a plurality of wireless access points into a plurality of management clusters of access points, wherein each management cluster of the plurality of management clusters comprises at least one access point of the plurality of access points, the partitioning method comprising: obtaining from each access point of the plurality of access points neighbour information comprising at least, an access point identifier of each neighbouring access point which is sensed by said respective access point, and a signal strength indicator corresponding to said sensed neighbouring access point; determining for each access point of the plurality of access points a centrality parameter based on the obtained neighbour information, wherein the centrality parameter is representative for an amount of influence the respective access point has within the plurality of access points; and partitioning the plurality of access points into a first management cluster and at least one further management cluster by, forming the first management cluster by including in said first management cluster a first access point as primary member, said first access point having the highest centrality parameter from among the plurality of access points, and any neighbouring access point sensed by said first access point as a secondary member; and for each further access point of the plurality of access points except the first access point, in order of descending centrality parameter, forming a further management cluster by including in said further management cluster said respective further access point as the primary member and, as one of the secondary members, any neighbouring access point sensed by said respective further access point which has not been included as one of the secondary members in another management cluster.

2. The partitioning method according to claim 1, wherein the determining the centrality parameter comprises representing the plurality of access points as a graph, based on the obtained neighbour information, wherein each access point is represented by a vertex and wherein an edge between vertices represents that corresponding access points sense each other, and wherein the centrality parameter of a particular access point is representative for an amount of shortest paths running trough the vertex corresponding to said particular access point.

3. The partitioning method according to claim 1, or 2 further comprising: obtaining, from each access point within a formed management cluster activity, information representative for an amount of data consumption of said respective access point; and determining a management cluster activity level of said formed management cluster based on the obtained activity information; and reforming said formed management cluster when the management cluster activity level is higher than a first activity threshold.

4. The partitioning method according to claim 3, wherein the reforming said formed management cluster comprises evicting at least one secondary member from said formed management cluster such that the cluster activity level of said reformed management cluster is equal or below the first activity threshold, wherein said at least one evicted secondary member is selected based on neighbour information obtained from the primary member of said formed management cluster.

5. The partitioning method according to claim 4 further comprising: assigning the at least one evicted secondary member to another formed cluster, wherein the at least one evicted secondary member is sensed by the primary member of the other formed cluster, and wherein the primary member of the reformed cluster has a higher centrality parameter as compared to the primary member of the other formed cluster.

6. The partitioning method according to claim 3, wherein an access point is included as the primary member in a primary management cluster and as one of the secondary members in a secondary management cluster, the method comprising: determining a combined activity level of the primary management cluster and the secondary management cluster based on the obtained activity information from each access point included in the primary and secondary management clusters; and in response to the combined activity level being below a second activity threshold, assigning the primary member and the secondary members of the primary management cluster to the secondary management cluster; or in response to the combined activity level being equal to or higher than the second activity threshold: evicting the primary member of the primary management cluster from the secondary management cluster.

7. The partitioning method according to claim 3, wherein the obtaining activity information, determining the management cluster activity level and reforming the formed management cluster are executed periodically.

8. A partitioning apparatus for partitioning a plurality of wireless access points into a plurality of management clusters of access points, wherein each management cluster of the plurality of management clusters comprises at least one access point of the plurality of access points, the partitioning apparatus comprising: at least one processor configured to obtain from each access point of the plurality of access points neighbour information comprising at least, an access point identifier of each neighbouring access point which is sensed by said respective access point, and a signal strength indicator corresponding to said sensed neighbouring access point; the processor configured to determine for each access point of the plurality of access points a centrality parameter based on the obtained neighbour information, wherein the centrality parameter is representative for an amount of influence the respective access point has within the plurality of access points; and the processor configured to partition the plurality of access points into a first management cluster and at least one further management cluster and configured to, form the first management cluster by including in said first management cluster a first access point as a primary member, said first access point having the highest centrality parameter from among the plurality of access points, and any neighbouring access point sensed by said first access point as a secondary member; and for each further access point of the plurality of access points except the first access point, in order of descending centrality parameter, form a further management cluster by including in said further management cluster said respective further access point as the primary member and, as one of the secondary members, any neighbouring access point sensed by said respective further access point which has not been included as one of the secondary members in another management cluster.

9. The partitioning apparatus according to claim 8, wherein the processor is configured to determine the centrality parameter by representing the plurality of access points as a graph, based on the obtained neighbour information, wherein each access point is represented by a vertex and wherein an edge between vertices represents that corresponding access points sense each other, and wherein the centrality parameter of particular access point is representative for an amount of shortest paths running trough the vertex corresponding to said particular access point.

10. The partitioning apparatus according to claim 8, wherein the processor is configured to obtain, from each access point within a formed management cluster, activity information representative for an amount of data consumption of said respective access point; the processor is configured to determine a management cluster activity level of said formed management cluster based on the obtained activity information; and the processor is configured to reform said formed management cluster when the management cluster activity level is higher than a first activity threshold.

11. The partitioning apparatus according to claim 10, wherein the processor is configured to reform said formed management cluster by evicting at least one secondary member from said formed management cluster such that the cluster activity level of said reformed management cluster is equal or below the first activity threshold, wherein the processor is configured to select the at least one evicted secondary member based on neighbour information obtained from the primary member of said formed management cluster.

12. The partitioning apparatus according to claim 11, wherein the processor is configured to assign the at least one evicted secondary member to another formed cluster, wherein the at least one evicted secondary member is sensed by the primary member of the other formed cluster, and wherein the primary member of the reformed cluster has a higher centrality parameter as compared to the primary member of the other formed cluster.

13. The partitioning apparatus according to claim 10, wherein an access point is included as the primary member in a primary management cluster and as the secondary member in a secondary management cluster, the processor being configured to: determine a combined activity level of the primary management cluster and the secondary management cluster based on the obtained activity information from each access point included in the primary and secondary management clusters; assign the primary member and the secondary members of the primary management cluster to the secondary management cluster if the combined activity level is below a second activity threshold; or evict the primary member of the primary management cluster from the secondary management cluster if the combined activity level is equal to or higher than the second predetermined activity threshold.

14. The partitioning apparatus according to claim 10 wherein the processor is configured to monitor a state of the formed management clusters and to periodically perform operations of partitioning apparatus.

15. A computer readable medium storing computer-executable program of instructions, which when executed by a computer, cause the computer to perform the method of claim 1.

Description

BRIEF DESCRIPTION OF THE FIGURES

[0035] The accompanying drawings are used to illustrate presently preferred non-limiting exemplary embodiments of devices of the present invention. The above and other advantages of the features and objects of the present invention will become more apparent and the present invention will be better understood from the following detailed description when read in conjunction with the accompanying drawings, in which:

[0036] FIGS. 1A-1B schematically illustrate flowcharts of exemplary embodiments of a partitioning method according to the present invention;

[0037] FIG. 2 schematically illustrates a graph representation of a plurality of wireless access points;

[0038] FIGS. 3A-3B schematically illustrate flowcharts of further exemplary embodiments of a partitioning method according to the present invention;

[0039] FIG. 4 schematically illustrates a flowchart further specifying the embodiments of the partitioning method as illustrated in FIGS. 3A and 3B;

[0040] FIG. 5 schematically illustrates a flowchart of an alternative embodiment of a partitioning method according to the present invention;

[0041] FIGS. 6A-6C schematically illustrate a plurality of access points which have been partitioned in a plurality of management clusters;

[0042] FIG. 7 schematically illustrates an exemplary embodiment of a partitioning method according to the present invention;

[0043] FIG. 8 schematically illustrates an exemplary embodiment of a partitioning apparatus according to the present invention; and

[0044] FIG. 9 schematically illustrates another exemplary embodiment of a partitioning apparatus according to the present invention.

DESCRIPTION OF EMBODIMENTS

[0045] FIG. 1A illustrates a partitioning method 100 for partitioning a plurality of wireless access points into a plurality of management clusters of access points, wherein each management cluster of the plurality of management clusters comprises at least one access point of the plurality of access points. The partitioning method 100 comprises a step 110 of obtaining from each access point of the plurality of access points neighbour information, the neighbour information comprising at least an access point identifiers (ID) of any neighbouring access point which is sensed by the respective access point; and a signal strength indicator corresponding to the sensed neighbouring access point. In other words, for a particular wireless access point it can be determined which access points of the plurality of access points are neighbouring access points of that particular access point and for each of those neighbouring access points it can be determined how strong its signal is perceived at that particular access point. Preferably the access points of the plurality of access points are managed by a managing operator and are provisioned by the TR-181 standard, such that data collection, preferably periodic data collection, is enabled. In an embodiment the neighbour information corresponds with obtaining from the access points the TR-181 parameter Device.WiFi.NeighboringWiFiDiagnostic.Result.{i}., which may be collected by each of the wireless access points by performing a Wi-Fi scan, and consequently be obtained from the access points by the managing operator. This way access point identifiers such as service set identifier (SSID) and/or basic service set identifier (BSSID), and signal strength indicators such as received signal strength indicator (RSSI) regarding neighbouring access points may be conveniently obtained.

[0046] The partitioning method 100 further comprises the step 120 of determining for each access point of the plurality of access points a centrality parameter based on the above described obtained neighbour information. The centrality parameter is a measure of the connectedness of an access point, or in other words the centrality parameter is representative for an amount of influence the respective access point has within the plurality of access points. As an illustrative example it is noted that the centrality parameter of an access point having a lot of neighbouring access points will typically have a larger centrality parameter as compared to an access point having no neighbouring access point. Although it is not just the amount of neighbouring access points which determines the centrality parameter, but also a more general positioning of an access point within the plurality of access points. The term positioning does not refer to the merely spatial location or position of an access point, but rather to how an access point is related to other access points within the plurality of access point. In this case, also a relation towards neighbouring access points of neighbouring access points may be taken into account to determine the centrality parameter.

[0047] The partitioning method 100 further includes step 130 of partitioning the plurality of access points into management clusters or groups, based on both the obtained neighbour information and the determined centrality parameter. Step 130 is further specified in FIG. 1B by step 131 of forming a first management cluster, step 132 of forming a first further management cluster, and step 133 of forming a second further management cluster. Note that depending on the amount of access points comprised in the plurality of access points and the topology thereof either less or more further management clusters may be formed in a similar way. The term management cluster is used to describe a group of access points, wherein a management cluster has one central access point, also referred to as primary member of the management cluster, and one or more neighbouring access points, also referred to as secondary members of the management cluster. Taking this into account a management cluster can be said to be formed around a central access point functioning as primary member, wherein neighbouring access points of the central access point function as secondary members in the management cluster. In other words, each secondary member in a management cluster is a neighbouring access point of the primary member of that management cluster, i.e. each secondary member can be sensed by the primary member. As described earlier, for each access point of the plurality of access points a centrality parameter may be determined. In the following, for the sake of brevity, when the wording centrality parameter is used in connection with a management cluster, this is to be interpreted as the centrality parameter of the access point functioning as primary member of the management cluster.

[0048] Step 131 of forming the first management cluster may be performed by including in the first management cluster a first access point as primary member, said first access point having the highest centrality parameter from among the plurality of access points, and any neighbouring access point sensed by said first access point as secondary member. In other words, the first management cluster is formed around the access point with the highest centrality parameter, by including in the management cluster all neighbouring access points which are sensed by the access point having the highest centrality parameter. In this context, the wording first access point and first management cluster refer to the access point with the highest centrality parameter and to the corresponding management cluster wherein the first access point functions as primary member. Accordingly, the wording further access point and further management cluster refer to an access point not having the highest centrality parameter and to the corresponding management cluster wherein the further access point functions as primary member. Rank words or ordinals such as first, second, third, . . . may be added to the wordings further access point and further management cluster to indicate a mutual relation regarding centrality parameter, i.e. the first further access point has a centrality parameter value which is lower than the centrality parameter value of the first access point but higher than the centrality parameter value of the second further access point, and so on.

[0049] Steps 132 and 133 include, for each further access point of the plurality of access points except the first access point, in order of descending centrality parameter, forming a further management cluster by including in said further management cluster said respective further access point as primary member and, as secondary member, any neighbouring access point sensed by said respective further access point which has not been included as secondary member in another management cluster. More in particular, during step 132 a first further management cluster is formed around the first further access point, and all neighbouring access points which are sensed by the first further access point are included in the first further management cluster except for those neighbouring access points which are sensed by the first further access point but are already included in an earlier formed management cluster, in this particular case, in the first management cluster. In a similar way, during step 133 a second further management cluster is formed around the second further access point, and all neighbouring access points which are sensed by the second further access point are included in the second further management cluster except for those neighbouring access points which are sensed by the second further access point but are already included in an earlier formed management cluster, in this particular case, in the first management cluster or in the first further management cluster. Similar steps as 132 and 133 may be carried out for any other further access point included in the plurality of access points. This way a partitioning into management clusters is provided wherein each access point of the plurality of access points is either included in only one management cluster, or in two management clusters. The latter case may arise when a particular access points is included in one management cluster as a primary member, and in another management cluster as a secondary member. In other words, one access point can be both a central access point of one management cluster and a neighbouring access point of another management cluster.

[0050] According to an embodiment, determining the centrality parameter comprises representing the plurality of access points as a graph, based on the obtained neighbour information, wherein each access point 201 is represented by a vertex or node and wherein an edge between vertices represents that corresponding access points sense each other. According to this embodiment the centrality parameter of an access point is representative for an amount of shortest paths running trough the vertex corresponding to the access point. FIG. 2 schematically illustrates such a graph representation of a plurality of wireless access points. Access points 201 are access points which are managed by the managing operator, and access points 202 are so called alien access points which are not managed by the managing operator. The partitioning method according to the invention is based on a centrality parameter as described above. When the wireless access points are represented in a graph, the centrality parameter of an access point might correspond with a betweenness centrality (BC) of a vertex or node corresponding to the access point in the graph. Given a list of access points and the results of their Wi-Fi scans, i.e. obtained neighbour information, a graph can be created in which each access point is a vertex while edges between access point denote if the access points are connected, i.e. visible to each other in their Wi-Fi scan, as illustrated in FIG. 2. Most of the vertices 201 will be managed by the managing operator (full vertices), while other non-managed nodes are considered as alien access points 202 (outlined vertices). In partitioning access points into clusters, a first challenge is to determine what should be the starting point, or more in particular the central access point or vertex, for each cluster. To address this challenge, the betweenness centrality of the nodes in the graph may be calculated and be sorted in descending order, wherein the node having the highest BC comes first. Betweenness centrality is the measure of the connectedness of a node. For every pair of vertices in a connected graph, there exists at least one shortest path between the vertices such that the number of edges that the path passes through is minimized. The betweenness centrality for each vertex is the number of these shortest paths that pass through the vertex. In conclusion the betweenness centrality is a measure of the number of shortest paths that pass through a given vertex and therefore is representative for an influence the corresponding access point has within the plurality of access points.

[0051] FIGS. 3A and 3B schematically illustrate flowcharts of further exemplary embodiments of a partitioning method according to the present invention which include the step 340 of obtaining from the access points activity information being representative for an amount of data consumption of said respective access point. As illustrated in FIG. 3A this step can be executed after all management clusters have been formed in step 330. In such an embodiment, activity information may be obtained at that point from each access point within a formed management cluster to determine an activity level of that management cluster in step 350, or alternatively activity information may have been obtained earlier, e.g. along with step 310 of obtaining neighbour information of the access points, temporarily stored and then retrieved for the access points which have been included in the management cluster for which the activity level will be determined during step 350. In FIG. 3B an alternative embodiment is illustrated, wherein the activity information is obtained during step 340, at an early stage, and wherein after formation of the first management cluster during step 331, the activity level of the first management cluster is determined during step 350a. This is different from the embodiment as illustrated in FIG. 3A wherein activity levels are only determined after all management clusters have been formed, whereas in FIG. 3B the activity level of a management cluster is determined directly after formation of the respective management cluster. This is illustrated by steps 331 and 350a, respectively corresponding with the formation and activity level determination of the first management cluster, by steps 332 and 350a, respectively corresponding with the formation and activity level determination of the first further management cluster, and by steps 333 and 350c, respectively corresponding with the formation and activity level determination of the second further management cluster.

[0052] The partitioning method according to FIGS. 3A and 3B further comprises step 350, 350a, 350b, 350c of determining a management cluster activity level of the formed management cluster based on the obtained activity information. The activity information of an access point may correspond to an amount of data consumption of the access point and/or correspond with an amount of data traffic passing through the access point. When the access points are provisioned by the TR-181 standard, useful TR-181 parameters corresponding to activity information may be Device.WiFi.Radio.{i}.Stats.BytesSent and Device.WiFi.Radio.{i}.Stats.BytesReceived.

[0053] The illustrated embodiment in FIGS. 3A and 3B further include comparing the determined activity level with a predefined activity threshold at step 360, 360a, 360b, 360c and reforming the formed management cluster when the management cluster activity level is higher than the predetermined activity threshold at step 370, 370a, 370b, 370c. If the determined activity level of the management cluster is equal to or lower than the predetermined activity threshold no action should be taken. It is clear for the skilled person that an activity level of a management cluster may be determined based on the obtained activity information of each access point within the management cluster. When the activity information is for example an amount of data traffic per access point, the activity level of a management cluster may be determined by adding up the amounts of data traffic from each access point within the management cluster. Dotted arrows 375, 375a, 375b, 375c illustrate that after reforming a management cluster during step 370, 370a, 370b, 370c, the activity level of the reformed management cluster may be determined again during step 350, 350a, 350b, 350c and compared to the predetermined activity threshold during step 360, 360a, 360b, 360c to create a feedback loop. Step 370, 370a, 370b, 370c of reforming the management cluster will be further elaborated below in connection to FIG. 4.

[0054] FIG. 4 schematically illustrates an embodiment of the partitioning method according to the invention wherein reforming 370 said formed management cluster comprises evicting 371 at least one secondary member from said formed management cluster such that the cluster activity level of said reformed management cluster is equal or below the first predetermined activity threshold. The at least one secondary member which gets evicted is selected based on neighbour information obtained from the primary member of formed management cluster. More in particular, it is the secondary member which is considered to be furthest away from the primary member of the formed management cluster in terms of signal strength that gets evicted.

[0055] The embodiment of FIG. 4 further comprises step 380 of assigning the at least one evicted secondary member to a further management cluster, wherein the at least one evicted secondary member is sensed by the primary member of the further management cluster, and wherein the primary member of the reformed management cluster has a higher centrality parameter as compared to the primary member of the further management cluster. In other words, the evicted secondary member may be included into a further management cluster having a lower centrality parameter value as compared to the management cluster it was evicted from.

[0056] When executing one of the partitioning methods as described in connection with the flow charts of FIGS. 1 to 4, it may arise that an access point is included into two management clusters. If this is the case, the embodiment according to FIG. 5 may be applied. FIG. 5 schematically illustrates an alternative embodiment of a partitioning method according to the present invention wherein an access point is included as a primary member in a primary management cluster and as a secondary member in a secondary management cluster. The wording primary management cluster is used here to indicate that the access point is included in that particular management cluster as central access point, i.e. primary member. The wording secondary management cluster is used here to indicate that the access point is included in that particular management cluster as a neighbouring access point, i.e. secondary member. The partitioning method includes step 590 of determining a combined activity level of the primary management cluster and the secondary management cluster. This can be done based on the obtained activity information from each access point included in the primary and secondary management clusters. In step 591 the combined activity level is compared with a predetermined activity threshold. This activity threshold may or may not be the same as the earlier mentioned activity threshold with reference to steps 360, 360a, 360b, 360c in FIGS. 3A, 3B and 4. If the combined activity level is below the predetermined activity threshold, the primary management cluster may be merged with the secondary management cluster by assigning the primary member and secondary members of the primary management cluster to the secondary management cluster. However, if the combined activity level is equal to or higher than the predetermined activity threshold the primary member of the primary management cluster is evicted from the secondary management cluster.

[0057] The method of FIG. 5 as described above, in combination with any one of the partitioning methods as described earlier, results in a partitioning of access points wherein each access point belongs to one management cluster, either as a primary member or as a secondary member. FIGS. 6A-6C schematically illustrate examples of such network partitioning results. More in particular, FIG. 6A illustrates a network partitioning wherein all access points have been partitioned into three management clusters and wherein no overlap exists between the formed management clusters. FIG. 6B illustrates a similar partitioning result wherein all access points but one have been included in one of three management clusters. However, the single access point may be considered as forming a management cluster on its own. Alternatively, the single access point may be incorporated in one of the three formed management clusters. FIG. 6C illustrates a network partitioning result wherein all access points have been incorporated into two management clusters without any overlap arising between the two management clusters.

[0058] FIG. 7 schematically illustrates an exemplary embodiment of a partitioning method according to the present invention. As earlier described, the idea of embodiments of the invention is to derive management clusters or cliques of managed access points such that access points belonging to the same management cluster have a high mutual dependency, whereas the access points from different clusters have negligible mutual dependency. This way of forming management clusters would solve issues regarding coverage overlapping, and consequently problems of contention and interference. Further to this, embodiments of the partitioning method according to the invention are concerned with the monitoring, preferably online monitoring of the management cluster formation such that after a first step of initial clustering, events such as newly installed access points, intensified activity levels, and/or relocated access points can be taken into account and management clusters can be reformed or reconfigured accordingly.

[0059] As described in connection to FIG. 2 the concept of betweenness centrality (BC) is used in embodiments of the partitioning method wherein the access points are represented as vertices on a graph. More in particular the BC is a useful parameter to determine a starting point, or starting access point for management cluster formation as will be described below with regard to the embodiment of the partitioning method as illustrated in FIG. 7. In summary, the exemplary embodiment of FIG. 7 comprises the following steps:

[0060] step 710 of data collection;

[0061] step 720 of betweenness centrality calculation;

[0062] step 730 of initial management cluster formation;

[0063] step 791 of management cluster merging;

[0064] step 792 of management cluster formation exposing; and

[0065] steps 755 and 770 of management cluster monitoring.

[0066] This sequence of steps allows for management clusters to be formed and to be monitored after formation. Each step will be further elaborated below.

[0067] During step 710, data is collected or obtained from all access points which are managed by the managing operator. The type of data that is being collected may include, but is not limited to the following exemplary TR-181 parameters regarding activity information: Device.WiFi.Radio.{i}.Stats.BytesSent and Device.WiFi.Radio.{i}.Stats.BytesReceived, and regarding neighbour information: Device.WiFi.NeighboringWiFiDiagnostic.Result.{i}..

[0068] During step 720, using neighboring Wi-Fi statistics, for each of the vertices, i.e. Wi-Fi access points, the betweenness centrality is calculated. Given a list of access points and the result of their Wi-Fi scans, a graph can be created in which each access point is a vertex while edges between access points denote that they are connected, i.e. visible to each other via their Wi-Fi scan. Once the graph has been created, the betweenness centrality (BC) of each node and corresponding access point can be calculated, using the following formula for BC. Betweenness centrality of a vertex or node v is the sum of the fraction of all-pairs shortest paths that pass through v:

[00001]$c_B\left(v\right)=\underset{s,tV}{.Math.}.Math.\frac{\left(s,tv\right)}{\left(s,t\right)}$

[0069] wherein is the set of nodes, (s,t) is the number of shortest (s,t)-paths, and (s,t|v) is the number of those paths passing through some node v other than s,t.

[0070] If s=t, then (s,t)=1, and if vs,t, then (s,t|v)=0.

[0071] This way, betweenness centrality is considered to be a measure of the connectedness of a node. The BC measure of the nodes in the graph provides a starting point to form initial management clusters.

[0072] During step 730, initial management cluster formation is performed based on the obtained neighbour information, i.e. via a Wi-Fi scan, and on the determined centrality parameter, i.e. the BC metric as calculated in step 720. Initial cluster formation comprising following substeps; [0073] I. Listing the nodes in descending order with respect to their BC. Denote this list as C [0074] II. Looping iteratively through each node I in C. [0075] III. Recording all neighbours of the node I. Denote the neighbours as N{I}. [0076] IV. Looping iteratively through each neighbor in N{I}; [0077] V. IF n.sup.i is not in some existing managing cluster C{I.sup.\}, adding n.sup.i to cluster C{I}. This condition is automatically fulfilled for the first node I in the list C, i.e. the node or access point with the highest BC.

[0078] Step 730 will result in a list of initial management clusters with high BC nodes as their centroid/center, i.e. primary member. In addition, some nodes might be the center of a management cluster themselves and also belong, as secondary member, to another management cluster with a different primary member.

[0079] In step 791, management cluster merging is performed. This step describes how to handle a node J, being the primary member of management cluster C{J} but also a secondary member of the management cluster C{I}. As described earlier in connection to FIG. 5 and step 591 two options are possible: [0080] option 592 of moving the node J and all of the nodes in C{J} to C{I}, thereby effectively merging management clusters C{I} and C{J}, and consequently removing C{J}; or [0081] option 593 of removing the node J from C{I} and keep it in place in C{J}.

[0082] A preferred criteria upon which to decide which option to select and whether or not to merge clusters is the activity level or activity index. The activity level is determined by data traffic within the respective management cluster. Assume for example that a predefined activity threshold is given by A. If by adding J and all of the nodes of cluster C{J} to cluster C{I}, the overall activity level of cluster C{I} given by A{I} does not exceed A, then it is safe to merge them.

[0083] It is clear to the skilled person that, as per step 730 of initial clustering, it is not feasible that any given node can belong to two clusters without being the center of either one of them. In the following, the options 592 and 593 as introduced earlier are described in more detail. [0084] I. Determining the list of nodes that belong to more than one cluster. Denote the list as T; [0085] II. Looping iteratively through the list T: [0086] (i) Each node T.sup.j in T, belongs to a cluster C{J}, of which it is the center, and a cluster C{I}, of which it is not the center; [0087] (ii) If the sum of activity levels of C{J} and C{I} is below a given activity threshold level A, i.e. (A{J}+A{I}<A) assign all members of cluster C{J} to cluster C{I}, and remove cluster C{J} (option 592); [0088] (iii) Otherwise, exclude the node J from cluster C{I} (option 593).

[0089] This approach will result in a list of clusters whose members do not belong to more than one cluster as illustrated in FIGS. 6A-6C.

[0090] In step 792 of cluster formation exposing a set of determined management clusters may be made available to an optimization engine for further management on network, access point and/or cluster level.

[0091] In steps 755 and 770, the wireless access points within the network are being monitored with respect to the cluster formation as carried trough during steps 730 and 791. A cluster reconfiguration according to step 770 may be triggered in two cases according to step 755. According to a first case a change of activity level of a management cluster may arise, and according to a second case, a change of location of a node in a management cluster may arise. In the following, either case is considered.

[0092] In the first case that the activity level A{K} of a management cluster C{K} exceeds the threshold A, a cluster reconfiguration or reformation may be triggered. Depending on particular monitor requirements, the activity level needs to exceed the threshold A continuously for a longer period of time, or just once to trigger the cluster reconfiguration. It is clear to the skilled person that any other monitoring requirement may be implemented in a similar way. Reconfiguration includes decomposing the management cluster C{K} into at least two management clusters. If the management cluster C{K} was made by merging the original clusters C{K} and C{L} in accordance with step 791, then the solution would be to revert to the original cluster formation. If the cluster C{K} was not formed by merging, the following sequence of steps are executed: [0093] I. Selecting the cluster C{K} with center node K, where A{K}>A; [0094] II. Starting evicting nodes in C{K} farthest away from K, in terms of signal strength (dBm), till the activilty level of A{K} goes below A; [0095] III. For all nodes evicted from C{K}, assigning them to any cluster C{K+1}, . . . , C{K+N} to whose center they are visible. Precisely, each evicted node can be assigned to any cluster C{K+1}, . . . , C{K+N}, if it is a neighbour of the center node of these clusters, where (K+1), . . . , (K+N) denote the clusters whose centers have lower BC than K.

[0096] It is clear to the skilled person that the evicted nodes undergoing reassignment could not possibly have initially gone to clusters C{K+1}, . . . , C{K+N} because of the way the initial clustering according to step 730 has been designed, more in particular see substep V.

[0097] In case that there is a change in location of one or more access points, cluster reconfiguration has to be triggered. Such cluster reconfiguration based on location change, can be accomplished straightforwardly by assigning the access point which has changed location to the cluster whose center is closest to the new location of the relocated node. In this process, preferably the earlier described limitation regarding activity levels of management clusters must be satisfied.

[0098] However, if the relocated node was itself a cluster center, a further step should be undertaken since the nodes belonging to that so called stranded cluster need to be revisited. A management cluster whose center, or primary member has changed locations is referred to as stranded cluster. The following sequence of steps describes an embodiment to cope with stranded clusters; [0099] I. For a stranded cluster C{S}, sorting all the nodes in descending values of BC; [0100] II. Applying the initial clustering algorithm of step 730 described above to all those nodes. This will cause new clusters to emerge; [0101] III. If there are any nodes that are left unassigned after Step II, then for those nodes, follow the step exactly similar to the step III of the algorithm described in the case of reconfiguring clusters when activity levels exceed the activity threshold. As per that step, J would be the node that has changed it location and C{J} would be the stranded cluster.

[0102] Note that steps 710, 720, 730, 791 and 792 can be repeated periodically, while the monitoring unit for detecting the change in activity level and/or access point location within step 755 of online cluster monitoring triggers cluster reconfiguration when needed.

[0103] FIG. 8 schematically illustrates an exemplary embodiment of a partitioning apparatus 800 for partitioning a plurality of wireless access points 801 into a plurality of management clusters of access points 801, wherein each management cluster of the plurality of management clusters comprises at least one access point 801 of the plurality of access points. The partitioning apparatus comprises an information obtaining unit 810 configured to obtain from each access point 801 of the plurality of access points neighbour information. The neighbour information comprising at least an access point identifier of each neighbouring access point which is sensed by said respective access point; and a signal strength indicator corresponding to said sensed neighbouring access point. The partitioning apparatus 800 further comprises a determining unit 820 configured to determine for each access point 801 of the plurality of access points a centrality parameter based on the obtained neighbour information. The centrality parameter is representative for an amount of influence the respective access point has within the plurality of access points. The partitioning apparatus further comprises a partitioning unit 830 configured to partition the plurality of access points 801 into a first management cluster and at least one further management cluster. To achieve this, the partitioning unit 830 is configured form the first management cluster by including in said first management cluster a first access point as primary member. The first access point is selected as having the highest centrality parameter from among the plurality of access points 801. In addition to the first access point any neighbouring access point sensed by said first access point is included in the first management cluster as a secondary member. The partitioning unit 830 is further configured to, for each further access point of the plurality of access points 801 except the first access point, in order of descending centrality parameter, form a further management cluster by including in said further management cluster said respective further access point as primary member and, as secondary member, any neighbouring access point sensed by said respective further access point which has not been included as secondary member in another management cluster.

[0104] Preferably the determining unit 820 is configured to determine the centrality parameter by representing the plurality of access points as a graph, based on the obtained neighbour information, wherein each access point is represented by a vertex and wherein an edge between vertices represents that corresponding access points sense each other. The centrality parameter of an access point is representative for an amount of shortest paths miming trough the vertex corresponding to said access point.

[0105] Preferably, the information obtaining unit 810 is configured to obtain from each access point within a formed management cluster activity information being representative for an amount of data consumption of said respective access point. In such an embodiment, the determining unit 820 is configured to determine a management cluster activity level of said formed management cluster based on the obtained activity information, and the partitioning unit 830 is configured to reform said formed management cluster when the management cluster activity level is higher than a first predetermined activity threshold.

[0106] Preferably, the partitioning unit 830 is configured to reform said formed management cluster by evicting at least one secondary member from said formed management cluster such that the cluster activity level of said reformed management cluster is equal or below the first predetermined activity threshold, wherein the partitioning unit is configured to select the at least one secondary member based on neighbour information obtained from the primary member of said formed management cluster.

[0107] Preferably, the partitioning unit is configured to assign the at least one evicted secondary member to another formed cluster, wherein the at least one evicted secondary member is sensed by the primary member of the other formed cluster, and wherein the primary member of the reformed cluster has a higher centrality parameter as compared to the primary member of the other formed cluster.

[0108] FIG. 9 schematically illustrates another exemplary embodiment of a partitioning apparatus 900 according to the present invention further comprising a monitoring unit 990 configured to monitor a state of the formed management clusters and to trigger the information obtaining unit 810, 910, the determining unit 820, 920 and the partitioning unit 830, 930 at predetermined moments in time.

[0109] A benefit of embodiments of the partitioning method and apparatus according to the invention is in its ability to partition the network into clusters of managed access points which can be optimized independently. The level of correlation between any two access points belonging to different management clusters is minimal or non-existing.

[0110] Embodiments of the partitioning method and apparatus according to the invention exploit neighboring Wi-Fi scan data, thereby creating Wi-Fi landscape maps, i.e. network graph, as an input for the partitioning method and apparatus. Embodiment of the partitioning method are able to take into account new managed or non-managed access point, as well as an eventual relocation of an access point and accordingly adapt and/or reform management clusters. Furthermore, embodiments of the partitioning method and apparatus take into accounts the activity and demand of an access point, when assigning the respective access point to a particular management cluster.

[0111] A person of skill in the art would readily recognize that steps of various above-described methods can be performed by programmed computers. Herein, some embodiments are also intended to cover program storage devices, e.g., digital data storage media, which are machine or computer readable and encode machine-executable or computer-executable programs of instructions, wherein said instructions perform some or all of the steps of said above-described methods. The program storage devices may be, e.g., digital memories, magnetic storage media such as a magnetic disks and magnetic tapes, hard drives, or optically readable digital data storage media. The program storage devices may be resident program storage devices or may be removable program storage devices, such as smart cards. The embodiments are also intended to cover computers programmed to perform said steps of the above-described methods.

[0112] The description and drawings merely illustrate the principles of the present invention. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the present invention and are included within its scope. Furthermore, all examples recited herein are principally intended expressly to be only for pedagogical purposes to aid the reader in understanding the principles of the present invention and the concepts contributed by the inventor(s) to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the present invention, as well as specific examples thereof, are intended to encompass equivalents thereof.

[0113] The functions of the various elements shown in the figures, including any functional blocks labelled as processors or units, may be provided through the use of dedicated hardware as well as hardware capable of executing software in association with appropriate software. When provided by a processor, the functions may be provided by a single dedicated processor, by a single shared processor, or by a plurality of individual processors, some of which may be shared. Moreover, explicit use of the term processor or controller should not be construed to refer exclusively to hardware capable of executing software, and may implicitly include, without limitation, digital signal processor (DSP) hardware, network processor, application specific integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for storing software, random access memory (RAM), and non volatile storage. Other hardware, conventional and/or custom, may also be included. Similarly, any switches shown in the figures are conceptual only. Their function may be carried out through the operation of program logic, through dedicated logic, through the interaction of program control and dedicated logic, or even manually, the particular technique being selectable by the implementer as more specifically understood from the context.

[0114] It should be appreciated by those skilled in the art that any block diagrams herein represent conceptual views of illustrative circuitry embodying the principles of the present invention. Similarly, it will be appreciated that any flowcharts, flow diagrams, state transition diagrams, pseudo code, and the like represent various processes which may be substantially represented in computer readable medium and so executed by a computer.

[0115] It should be noted that the above-mentioned embodiments illustrate rather than limit the present invention and that those skilled in the art will be able to design alternative embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word comprising does not exclude the presence of elements or steps not listed in a claim. The word a or an preceding an element does not exclude the presence of a plurality of such elements. The present invention can be implemented by means of hardware comprising several distinct elements and by means of a suitably programmed computer. In claims enumerating several means, several of these means can be embodied by one and the same item of hardware. The usage of the words first, second, third, etc. does not indicate any ordering or priority. These words are to be interpreted as names used for convenience.

[0116] In the present invention, expressions such as comprise, include, have, may comprise, may include, or may have indicate existence of corresponding features but do not exclude existence of additional features.

[0117] Whilst the principles of the present invention have been set out above in connection with specific embodiments, it is to be understood that this description is merely made by way of example and not as a limitation of the scope of protection which is determined by the appended claims.