US2009290508A1PendingUtilityA1
Method for optimizing network "Point of Presence" locations
Est. expiryMay 22, 2028(~1.8 yrs left)· nominal 20-yr term from priority
H04L 45/80H04L 12/2854
47
PatentIndex Score
0
Cited by
0
References
0
Claims
Abstract
A methodology for optimizing the placement of network “Points of Presence” (POPs) across the carrier's entire network (i.e., a “global” solution”) utilizes carefully constructed customer clustering and simulated annealing methodology to create a cost-efficient solution. The customer base is first partitioned into a plurality of clusters such that the customers within each cluster are closer to its centroid than the centroid of any other cluster (e.g., applying the k-means clustering algorithm or any other suitable method of partitioning the customer base). A linear algorithm process is used to minimize the costs associated with the number of placement of POPs within each cluster. A simulated annealing (SA) process is then used to iterate the entire set of potential POP locations until a compact, steady-state solution is achieved (or, alternatively, until a given number of iterations has been performed). In a preferred embodiment, a number of iterations are performed at each “temperature” in the simulating annealing process to further improve the result (this iterative process referred to in the art as “intensification”).
Claims
exact text as granted — not AI-modified1 . A method of optimizing the placement of a network carrier's “Point of Presences” (POPs) facility locations across a communication network, the method comprising the steps of:
a) identifying a plurality of N customer facilities to be served by the network carrier, a plurality of F potential POP facility locations and a plurality of S access suppliers available for providing communication between the customer facilities and the POP facilities; b) creating an initial solution Y initial for associating each customer facility with a POP facility location through an access supplier; and c) performing simulated annealing on the initial solution Y initial for a predetermined number of iterations to achieve an optimized placement solution for the plurality of POP facility locations.
2 . The method as defined in claim 1 , wherein the initial solution is created by:
partitioning the plurality of N customer facilities into a set of CL clusters; forming a locally optimized POP facility location solution for each cluster; and combining the set of CL locally optimized solutions to form the initial solution Y initial .
3 . The method as defined in claim 2 , where in performing the partitioning, each cluster is formed to have approximately the same number of customer facilities therein.
4 . The method as defined in claim 2 , where in performing the locally optimized POP facility location the follow steps are performed:
applying a linear algorithm process to obtain a minimal cost solution for the placement of at least one POP facility to service the customers within the cluster using a selected access supplier, for a given cluster i, the minimal cost solution defined as y(i) and the identified at least one POP facility defined as Y i .
5 . The method as defined in claim 2 wherein the plurality of N customer facilities are geographically partitioned into a plurality of CL separate customer clusters.
6 . The method as defined in claim 1 wherein a k-means clustering process is used to form a plurality of CL separate customer clusters.
7 . The method as defined in claim 6 , wherein the k-means clustering process comprises the steps of:
i) randomly assigning each customer to a cluster; ii) calculating the centroid C of each cluster; iii) for each customer facility, determining the closest centroid and, if the closest centroid is within a different cluster, moving the customer facility to that cluster; iv) repeating steps ii) and iii) until each customer facility is located in its closest cluster and no additional moves are performed in step iii); and v) defining the results of step iv) as the k-means clustering solution.
8 . The method as defined in claim 4 , wherein the following analysis is performed separately for each cluster in the plurality of CL clusters:
Min
∑
i
∉
N
∑
j
∈
F
∑
k
∈
S
(
C
ijk
+
C
ijk
′
·
t
)
x
ijk
+
∑
j
∈
F
(
f
j
+
f
j
′
·
t
)
y
j
,
where C ijk is the initial cost for providing service to customer circuit i to POP location j via supplier k, C ijk is the recurring costs for the same, t is the time period, f j is the initial cost for installing a POP facility at location j and f′ j is the recurring costs for maintaining a POP facility at location j.
9 . The method as defined in claim 8 wherein the analysis includes the following constraints:
∑
j
∈
F
∑
k
∈
S
x
ijk
=
1
∀
i
∈
N
such that each customer circuit served by exactly one POP facility via exactly one access supplier; and
x ijk ≦y j ∀ i ε N, j ε F, k ε S, such that a customer circuit is assigned to a POP facility j facility only if a POP facility is installed at location j.
10 . The method as defined in claim 1 , wherein in performing step c), the following steps are performed:
i) creating an alternative, nearby solution Y 1 relative to the initial solution Y initial generated in step e); ii) determining the minimal cost solution f(Y 1 ) for nearby solution Y 1 of step i); iii) comparing the difference between f(Y 1 ) and f(Y initial ) and, if Y 1 provides a lower cost, replace Y initial with Y 1 and move to step v), otherwise iv) performing a random operation to determine if Y 1 should replace Y initial as the lower cost solution; and v) repeating steps i)-iv) until an optimized solution is achieved.
11 . The method as defined in claim 10 wherein in performing step v), the process is repeated for a predetermined number of iterations.
12 . The method as defined in claim 10 wherein in performing step v), the process is repeated until a minimal difference between Y 1 and Y initial is achieved.
13 . The method as defined in claim 10 , wherein in performing step i), a neighborhood generation function is used to create the alternative, nearby solution.
14 . The method as defined in claim 13 wherein the neighborhood generation function comprises the following steps:
if the total number of POP facility locations is equal to plurality of F potential POP facility locations, removing a random POP facility and defining the result as nearby solution Y 1 ; otherwise, generating a random fraction between zero and one; and, for a random fraction in a first interval,
if the total number of POP facilities is greater than one, exchanging an open POP facility for a closed POP facility to create nearby solution Y 1 , otherwise
if the random fraction is within a second interval, adding one closed POP facility to the plurality of open POP facilities to create nearby solution Y 1 , otherwise
if the random fraction is within a third interval, exchanging an open POP facility for a closed POP facility to create nearby solution Y 1 , otherwise
if the random fraction is within a fourth interval, adding one closed POP facility to the plurality of open POP facilities to create nearby solution Y 1 , otherwise
removing one open POP facility to create nearby solution Y 1 .
15 . The method as defined in claim 10 , wherein steps iii)-v) are repeated at a predetermined temperature variable T 0 for a predefined number of t cycles, providing intensification of the solution.
16 . The method as defined in claim 15 wherein the number of cycles is shorted to be less than t if a predetermined number k 2 nearby solutions are selected as preferred solutions.
17 . The method as defined in claim 15 , wherein for each repetition of steps iii)-v) the temperature variable T 0 is modified as follows:
T
0
=
T
0
1
+
β
T
0
,
where
β is a predetermined fractional value.Join the waitlist — get patent alerts
Track US2009290508A1 — get alerts on status changes and closely related new filings.
We store only your email — no account needed. See our privacy policy.