US9877205B2ActiveUtilityA1
Wireless network deployment method, apparatus and system
Est. expiryOct 31, 2034(~8.3 yrs left)· nominal 20-yr term from priority
H04W 16/18
71
PatentIndex Score
2
Cited by
6
References
17
Claims
Abstract
A wireless network deployment method, apparatus and system where the includes: initializing the wireless network to determine a deployment area and the number of access points needing to be deployed; initializing positions of the access points, and dividing the deployment area into grids; calculating a virtual force of each access point based on signal coverage of each grid; calculating a movement position of each point according to the virtual force; performing edge controlling on each point; and terminating processing when a terminating condition is satisfied. A deployment process is simulated as a dynamic physical process, movement of the access points along a direction of a resultant force of all repulsion forces and attractive forces is controlled following the principle that an overlapping covered area produces a repulsion force and an uncovered area produces an attractive force.
Claims
exact text as granted — not AI-modifiedWhat is claimed is:
1. A wireless network deployment apparatus, which is included in a computer system, comprising:
a memory that stores a plurality of instructions; and
a processor coupled to the memory and configured to execute the instructions to:
initialize a wireless network to determine a deployment area of the wireless network and a number of access points needing to be deployed;
initialize positions of the access points, and divide the deployment area into grids;
calculate a virtual force on each access point in the wireless network based on signal coverage of each grid;
calculate a movement position of each access point according to the virtual force on each access point;
perform edge control on each access point; and
judge whether a terminating condition is satisfied, and terminate processing when the terminating condition is satisfied to obtain movement positions of the access points,
wherein, a wireless network is deployed in accordance with the movement positions of the access points,
wherein, the virtual force on each access point comprises attractive forces and repulsive forces produced by the grids in a neighboring area of each access point,
wherein the processor is configured to execute the instructions to:
calculate the signal coverage of each grid to determine a set of access points covering each grid;
search a neighboring area of each access point;
determine whether a type of a grid in the neighboring area is one of being not covered by any access point, being covered by the access point only, being covered by other access points, and being covered by the access point and other access points in an overlapped manner; and
calculate the virtual force according to types of the grids in the neighboring area.
2. The apparatus according to claim 1 , wherein the processor is configured to execute the instructions tot:
expand a grid where the access point is located using the grid where the access point is located as a center to obtain an edge area, the grid where the access point is located being a searched area;
expand the edge area, until grids in the edge area one of go beyond the deployment area and are covered by other access points only to obtain an expanded area, the edge area becoming the searched area; and
judge whether the expanded area is not empty, and perform expansion taking the expanded area as a new edge area when the expanded area is not empty, otherwise, take a current searched area as the neighboring area of the access point.
3. The apparatus according to claim 1 , wherein the processor is configured to execute the instructions to:
calculate attractive forces produced by the grids in the neighboring area that are not covered by any access point to the access point;
calculate repulsive forces produced by the grids in the neighboring area that are covered by the access point and other access points in an overlapped manner to the access point; and
add up the attractive forces produced by the grids in the neighboring area that are not covered by any access point to the access point and the repulsive forces produced by the grids in the neighboring area that are covered by the access point and other access points in an overlapped manner to the access point to obtain the virtual force of the access point.
4. The apparatus according to claim 1 , wherein the processor is configured to execute the instructions to:
calculate friction forces produced by the grids in the neighboring area that are covered by the access point only to the access point;
calculate an adjustment coefficient of a movement step of the access point according to the friction forces; and
calculate the movement position of the access point according to a position of the access point before the access point moves, the movement step of the access point, the adjustment coefficient and the virtual force of the access point.
5. The apparatus according to claim 1 , wherein the processor is configured to execute the instructions to:
determine a set of grids located at each boundary of the deployment area in the neighboring area; and
determine whether the access point is able to proceed with moving towards each boundary according to a control function of each boundary and a set of the grids of each boundary.
6. A wireless network deployment method, executed by a wireless network deployment apparatus included in a computer system comprising a memory and a processor coupled to the memory, comprising:
initializing the wireless network to determine a deployment area of the wireless network and a number of access points needing to be deployed;
initializing positions of the access points, and dividing the deployment area into grids;
calculating a virtual force on each access point in the wireless network based on signal coverage of each grid;
calculating a movement position of each access point according to the virtual force of each access point;
performing edge control on each access point; and
terminating processing when a terminating condition is satisfied to obtain movement positions of the access points,
wherein, a wireless network is deployed in accordance with the movement positions of the access points,
wherein, the virtual force on each access point comprises attractive forces and repulsive forces produced by the grids in a neighboring area of each access point,
wherein the calculating a virtual force on each access point in the wireless network based on signal coverage of each grid comprises:
calculating the signal coverage of each grid to determine a set of access points covering each grid;
searching a neighboring area of each access point;
determining whether a type of a grid in the neighboring area is one of being not covered by any access point, being covered by the access point only, being covered by other access points and being covered by the access point and other access points in an overlapped manner; and
calculating the virtual force of the access point according to types of the grids in the neighboring area.
7. The method according to claim 6 , wherein the searching
a neighboring area of each access point comprises:
expanding a grid where the access point is located using the grid where the access point is located as a center to obtain an edge area, the grid where the access point is located being a searched area;
expanding the edge area, until grids in the edge area one of go beyond the deployment area and are covered by other access points only to obtain an expanded area, the edge area becoming the searched area; and
performing expansion taking the expanded area as a new edge area when the expanded area is not empty, otherwise, taking a current searched area as the neighboring area of the access point.
8. The method according to claim 6 , wherein the calculating the virtual force of the access point according to the types of the grids in the neighboring area comprises:
calculating attractive forces produced by the grids in the neighboring area that are not covered by any access point to the access point;
calculating repulsive forces produced by the grids in the neighboring area that are covered by the access point and other access points in an overlapped manner to the access point; and
adding up the attractive forces produced by the grids in the neighboring area that are not covered by any access point to the access point and the repulsive forces produced by the grids in the neighboring area that are covered by the access point and other access points in an overlapped manner to the access point to obtain the virtual force of the access point.
9. The method according to claim 8 , wherein a formula for calculating the attractive forces comprises:
F
i
,
j
=
P
i
,
j
-
P
I
P
i
,
j
-
P
I
;
where, C i,j is the grid covered by no access point, P i,j is a position of the grid C i,j , and P l is a position of the access point.
10. The method according to claim 8 , wherein a formula for calculating the repulsive forces comprises:
F
p
,
q
=
P
I
-
P
c
P
I
-
P
c
;
where, C p,q is a grid covered by the access point and other access points in an overlapped manner, P C is a central position of all access points covering the grid C p,q , and P l is a position of the access point.
11. The method according to claim 8 , wherein a formula for calculating the virtual force comprises:
F
I
=
∑
C
ij
∈
B
I
0
w
i
,
j
F
i
,
j
+
∑
C
qp
∈
B
I
2
w
p
,
q
F
p
,
q
;
where, w i,j and w p,q are weighted values, w i,j ε[0,1], w p,q ε[0,1], B I 0 is a set of grids in the neighboring area not covered by any access point, and B I 2 is a set of grids in the neighboring area covered by the access point and the other access points in an overlapped manner.
12. The method according to claim 6 , wherein the calculating a movement position of each access point according to the virtual force of each access point comprises:
calculating friction forces produced by the grids in the neighboring area that are covered by the access point only to the access point;
calculating an adjustment coefficient of a movement step of the access point according to the friction forces; and
calculating a movement position of the access point according to a position of the access point before the access point moves, the movement step of the access point, the adjustment coefficient and the virtual force of the access point.
13. The method according to claim 12 , wherein a formula for calculating the friction forces comprises:
F I f =|B I 3 |;
where, B I 1 is a set of grids in the neighboring area covered only by the access point, and is the number of the grids in the neighboring area covered only by the access point.
14. The method according to claim 12 , wherein a formula for calculating the adjustment coefficient comprises:
k I =1− F I f /F max f ;
where, F max f is a maximum value of the friction forces to which all the access points in the wireless network are subjected.
15. The method according to supplement 12, wherein a formula for calculating the movement position comprises:
P
I
′
=
P
I
+
k
I
Δ
P
F
I
F
I
;
where, P′ I is a position of the access point after moving, P I is the position of the access point before moving, ΔP is a movement step of the access point, F I is the virtual force of the access point, and k l is the adjustment coefficient.
16. The method according to claim 7 , wherein the performing edge control on each access point includes:
determining a set of grids located at each boundary of the deployment area in the neighboring area; and
determining whether the access point is able to proceed with moving towards each boundary according to a control function of each boundary and the set of the grids of each boundary.
17. A computer system, including a wireless network deployment apparatus, the wireless network deployment apparatus comprising:
a memory that stores a plurality of instructions; and
a processor coupled to the memory and configured to execute the instructions to:
initialize a wireless network to determine a deployment area of the wireless network and a number of access points needing to be deployed;
initialize positions of the access points, and divide the deployment area into grids;
calculate a virtual force on each access point in the wireless network based on signal coverage of each grid;
calculate a movement position of each access point according to the virtual force of each access point;
perform edge control on each access point; and
terminate processing when a terminating condition is satisfied to obtain movement positions of the access points,
wherein, a wireless network is deployed in accordance with the movement positions of the access points,
wherein, the virtual force on each access point comprises attractive forces and repulsive forces produced by the grids in a neighboring area of each access point,
wherein the processor is configured to execute the instructions to:
calculate the signal coverage of each grid to determine a set of access points covering each grid;
search a neighboring area of each access point;
determine whether a type of a grid in the neighboring area is one of being not covered by any access point, being covered by the access point only, being covered by other access points, and being covered by the access point and other access points in an overlapped manner; and
calculate the virtual force according to types of the grids in the neighboring area.Join the waitlist — get patent alerts
Track US9877205B2 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.