System and method for hierarchical clustering of wireless mobile network
A method, network system, and non-transitory computer readable medium that arrange a set of wireless mobile devices into a two-level clustering structure including a cluster in a first-level and a cluster in the second-level, based on node status registered and algorithm preinstalled in a back-end server, where each of the set of wireless mobile devices is assigned either one of a slave member of a cluster in the first-level, a master of a cluster in the first-level where the master is also a member of a cluster in the second-level, or a super master of a cluster in the second-level where a master of a cluster in the first-level is assigned as the super master. The two-level clustering structure is periodically updated. Only the super-masters are configured to communicate with the back-end server via a long-range connection to WLAN, while a short-range wireless interface is used for internal communications.
1. A method comprising:
registering a node status comprising a series number, a location, a battery level and an availability of a long-range connection to a wireless local area network (WLAN) for each of a set of wireless mobile devices, wherein
the set of wireless mobile devices is configured to communicate with a back-end server via the long-range connection to the WLAN, and internally via a short-range wireless interface;
arranging the set of wireless mobile devices into a two-level clustering structure comprising a cluster class selected from the group consisting of a first cluster in a first-level and a second cluster in a second-level, wherein each of the set of wireless mobile devices is assigned one of three positions in the first cluster or the second cluster:
1) a slave member of the first cluster in the first-level,
2) a master of the first cluster in the first-level where the master is also the slave member of the second cluster in the second-level, or
3) a super master of the second cluster in the second-level where the master of the first cluster in the first-level is assigned as the super master and the cluster class in the first-level is assigned as the cluster class in the second-level; and
updating the two-level clustering structure periodically based on the node status registered most recently, wherein each of the set of wireless mobile devices is reassigned either one of the three positions in clustering in a cluster,
wherein the super masters are configured to communicate with the back-end server via the long-range connection to the WLAN, and
a maximum cluster size given by a specification of the short-range wireless interface,
wherein the arranging includes:
obtaining a set of solutions minimizing an objective function Z; and
assigning each of the set of wireless mobile devices one of the three positions in the first cluster or the second cluster based on the set of solutions,
wherein the objective function Z is defined by below Equation (1) as:
Z=Σ i=1 N Σ j=1 N C ij X ij +Σ j=1 N F j Y j +Σ i=1 N Σ j=1 N C ij V ij +Σ j=1 N F j W j , (7)
and
obtaining the set of solutions minimizing the objective function is carried out by a processor having circuitry with instructions to solve a minimization problem, based on the node status registered and under constraints expressed with below equations (8)-(16),
Σ j=1 N X ij =1, i= 1 . . . N, (8)
Σ i=1 N X ij ≤PY j , j= 1 . . . N, (9)
Σ j=1 N C ij X ij ≤R, i= 1 . . . N, (10)
Σ j=1 N V ij ≤Y i , i= 1 . . . N, (11)
Σ i=1 N V ij ≤PW j , j= 1 . . . N, (12)
Σ j=1 N C ij V ij ≤RY j , i= 1 . . . N, (13)
W j ≤, j= 1 . . . N, (14)
W j ≤WF j , j= 1 . . . N, (15)
W j ≤BL j , j= 1 . . . N, (16)
and with below definitions (1)-(6),
WF
j
=
{
1
,
if
device
j
has
the
long
-
range
connection
to
WLAN
0
,
otherwise
(
1
)
BL
j
=
{
1
,
if
battery
level
of
device
j
is
≥
50
%
0
,
otherwise
(
2
)
X
ij
=
{
1
,
if
device
i
is
a
slave
member
belongs
to
master
j
0
,
otherwise
(
3
)
Y
j
=
{
1
,
if
device
j
is
assigned
as
a
master
0
,
otherwise
(
4
)
V
ij
=
{
1
,
if
master
i
is
a
slave
member
belongs
to
super
master
j
0
,
otherwise
(
5
)
W
j
=
{
1
,
if
master
j
is
assigned
as
a
super
master
0
,
otherwise
(
6
)
wherein, N denotes a total number of the wireless mobile devices or nodes, C ij denotes a distance between the i th node and the j th node, WF j denotes availability of the long-range connection to the WLAN for the j th node, BL j denotes battery level of the j th node, Y j denotes whether the j th node is assigned as the master, W j denotes whether the j th node is the super master, X ij denotes whether the i th node is the slave member of the first cluster in the first-level the master of which is the j th node, V ij denotes whether the master i is the slave member of the second cluster in the second-level where the super master of the cluster class is the j th node, F j denotes a fixed cost of each master and super master and is set equal to 100, P denotes the maximum cluster size including a cluster head, the maximum cluster size given by the specification of the short-range wireless interface, and R denotes a maximum distance range covered by the short-range wireless interface.