Homogeneous Network Optimization
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Text
Staged Type Wrappers
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152. DOI: 10.15514/ISPRAS201628(6)10
Automatic Analysis, Decomposition and Parallel Optimization of
Large
Homogeneous
Networks
ISPRAS Open 2016
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X.
HUAWEI TECHNOLOGIES CO., LTD.
www.huawei.com
Presentation of the new algorithm of Homogeneous Network Optimization
1
5 October 2015
S1
A0
Signals of sector antennas A0 – A7
A1
A2
A3
A4
A5
A6
A7
Homogeneous Networks
Element Crossroad Switch Antenna
Optimized integral index Average speed of traffic Average power of
prevalent radio signal
Correlation formula
for 2 elements 1 / (1 + [elements quantity on the shortest path]) 1 / (distance between antennas)
Wireless
Wired
Communication Networks
Road network
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
The life of the modern world essentially depends on the work of the large artificial networks, such as networks of roads, pipelines, wired and wireless communication systems. The support of their effective functioning requires permanent screening and optimization. The network consists of the active elements, such as crossroads, switches or antennas, and can be optimized by the integral indices, such as average speed of traffic in crossroads or switches, or average power of prevalent radio signal of antennas. To perform optimization the large networks are decomposed into subnets on the basis of correlation between their elements.
2
5 October 2015
Background: Sector Planning with full optimization
Graphbased representation
Homogeneous network is represented as a weighted complete graph, where
each vertex corresponds to network element
each edge has weight equals to correlation between correspondent elements
Optimization loop:
Decomposition of network into subnets by the rule of minimal sum of crossing edges weights
Parallel optimization of subnets
Update of network parameters
Main drawback:
Crossing edges are ignored => poor accuracy
Optimization of
all parameters
DECOMPOSITION
While stopping criterion isn’t met
Thread
Thread
Full network
2
 Subnets
Element
Agenda

1
2
1
1
1
1
1
1
2
2
2
2
2
2
UPDATE
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
For example in the method of sector planning with full optimization the Homogeneous Network is represented as a weighted complete graph, where each vertex corresponds to network element and each edge has weight equals to correlation between connected elements. In optimization loop : 1) Network is decomposed into subnets by the rule of minimal sum of crossing edges weights; 2) Subnets are optimized in parallel processes; 3) Network parameters are updated. Main drawback: crossing edges are ignored, and so accuracy of optimization is poor.
3
5 October 2015
Idea 1: Alternative splitting
Optimization
While stopping criterion
is not met
Thread
Thread
Thread
Thread
Split by split
Advantage: All crossing edges are taken into account
Discard light edges
under threshold
Alternative splits
Full
network
Reduced network
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
 Subnets
Element
Agenda

1
2
3
4
UPDATE NETWORK
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
Idea 1: alternative splitting. In complete graph of network the light edges under predefined threshold are discarded and we've got reduced network. Then network is decomposed into alternative splits. Algorithm iterates through these splits, and perform optimization of subnets in separate threads.
4
5 October 2015
COMBINE NONOVERLAPPING SUBNETS
Idea 2: Independent optimization
Advantage: Parallel optimization of the fully independent elements
Reduced
network
FOR EVERY OPTIMIZED UNIT FIND SUBNET
 Subnets
 Border element
 Optimized unit
Agenda
2
2
2
2
1
1
1
1
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
Idea 2: independent optimization. In reduced network the optimized units are selected. For every unit we find subnet consisting of optimized unit and all connected to it elements. Then nonoverlapping subnets are combined into alternative splits. In every split only independent elements are optimized. As you can see while we move through all splits we optimize all elements, but every optimization effects only independent parts of network. Advantage: parallel optimization of the most independent elements.
5
5 October 2015
Splitting with threshold
Idea 3: Regulation of threshold
Threshold increasing
O p t i m i z a t i o n
1 subnet
2 subnets
3 subnets
Optimized unit = 2 elements
Advantage: Optimization process is regulated by threshold
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
Idea 3: regulation of threshold. Decomposition begins with the minimal level of threshold and as a result just one subnet is selected in every split . As you can see the optimized unit consists of 2 elements and all other elements are connected to it. When threshold is increased then the number of subnets is increased and their complexity is decreased. Advantage: optimization process is regulated by threshold.
6
5 October 2015
Optimization of
independent elements
UPDATE NETWORK
If stopping criterion
is not met
Thread
Thread
Alternative splits of network into nonoverlapping subnets for optimized units:
Split by split
DISCARD EDGES UNDER THRESHOLD
DECOMPOSITION
Full cycle of alternative splitting with regulated threshold
If threshold under limit increase its value and continue
Reduced network
…
1
1
1
2
2
2
1
1
2
Full network
 Subnets
 Border element
 Optimized unit
Agenda
1
1
1
1
1
2
2
2
2
2
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
The full cycle of alternative splitting with regulated threshold includes discarding of edges under threshold, alternative splitting of reduced network on the basis of optimized units, parallel optimization of the most independent parts of networks as long as optimization gives improvement. After that, the threshold is increased and optimization is performed on the next level of splitting.
7
5 October 2015
Optimization process regulation
Start
Quantity of alternative calculations
Complexity
Rough search of global optimum in small number of complex subnets (avoiding of stuck in local optimum)
Precise search of optimums in big number of simple subnets (maximal precision at the end)
Quantity
Strength of distant interactions
Precision of
optimizing
procedure
Subnets
Quantity of processes = available cores
Precision of optimization
End
Usage of all computational resources on computer / cluster
Colored arrows ( ) – increase (up) or decrease (down) of parameter value
Empty arrows – impact on optimization process
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
Optimization process regulation includes increase of networks quantity and decrease of the number of alternative calculations during optimization process, so that the quantity of parallel processes equals to quantity of available cores and we use all computational resources available on computer or cluster. From other side, the complexity of subnets and the strength of their distant interactions are decreased and we increase precision of optimizing procedure. As a result during optimization the accuracy is increased and we progressively move from rough search of global optimum in small number of complex subnets to precise search of optimum in big number of simple subnets. In such way we avoid the stack in local optimum at the beginning of optimization and have the best precision at the end.
8
5 October 2015
Optimization of mobile network coverage and quality
High optimization complexity:
300 antennas * 4 parameters, n states of parameter => n1200 states
Regulated parameters of sector antenna: power, height, tilt, azimuth
Initial subnet
Optimized subnet
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
To demonstrate the efficiency of proposed approach, the optimization of mobile network is implemented with visualization of quality of radio signal. As you can see the sector antennas transmit radio signal (green and yellow colors). In initial network there are red problem areas with low quality of radio signal. Every antenna was optimized by 4 regulated parameters, each with n states. So, the number of states of full network is n^1200 – optimization complexity is high. After optimization is finished the red areas are disappeared and the quality of radio signals is increased.
2014/9/8
9
16 October 2015
Alternative splitting vs. Sector planning
n – number of optimized areas in network
Pi – the power of the prevalent signal in ith area
Ii – the power of the other (interfering) signals in ith area
Ni – other noise in ith area
Optimized integral index – average Signal to Interference plus Noise Ratio:
Optimizing procedure – modified Simulated Annealing:
procedure optimize(S0, precision) {
Snew := S0
step := maxStep ∙ (1 – precision)
Sgen := random neighbor of S0 within step
t := T(1 – precision)
if A(E(S0), E(Sgen), t) ≥ random(0, 1) then Snew := Sgen
Output: state Snew
}
S0, Sgen, Snew – current, generated, new states of subnet
maxStep – maximal value of step
T, E, A – temperature, energy, acceptance functions
9 times faster
1 hour – SINR 15 % higher (p < 0.01)
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
As an optimized integral index we use Signal to Interference plus Noise Ratio (SINR). As an optimizing procedure – modified Simulated Annealing, which takes as input precision parameter. On the plot you can see that the alternative splitting gives speedup 9 times, and after 1 hour shows better quality of radio signal – SINR is 15 % higher in logarithmic scale.
10
5 October 2015
Benefits of Independent optimization of alternatives
Faster optimization due to reduction of optimization complexity and efficient usage of all computational resources
Better quality of optimization due to progressive shift of optimization strategy from rough search of global optimum at the beginning of optimization process to precise search of optimum at the end of optimization
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152.
Thus, the benefits of proposed method for independent optimization of alternatives: 1) Faster optimization due to reduction of optimization complexity and efficient usage of all computational resources; 2) Better quality of optimization due to progressive shift of optimization strategy from rough search of global optimum at the beginning of optimization process to precise search of optimum at the end of optimization.
11
5 October 2015
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X. Automatic Analysis, Decomposition and Parallel Optimization of Large Homogeneous Networks // Proc. ISP RAS, 2016, vol. 28, issue 6, pp. 141152. DOI: 10.15514/ISPRAS201628(6)10
Automatic Analysis, Decomposition and Parallel Optimization of
Large
Homogeneous
Networks
ISPRAS Open 2016
Ignatov D.Yu., Filippov A.N., Ignatov A.D., Zhang X.
HUAWEI TECHNOLOGIES CO., LTD.
www.huawei.com
Presentation of the new algorithm of Homogeneous Network Optimization
12
5 October 2015
Comments