Network Planning Algorithms in CATV Networks
Date Issued
2006
Date
2006
Author(s)
Peng, Kuo-Wei
DOI
en-US
Abstract
An increasing number of new services are now running on CATV networks. The earliest CATV (Community Antenna Television) systems were constructed in small towns or semi-rural areas, where off-air television reception was poor or unavailable [. Because of their popularity and high bandwidth, CATV such networks have become one of the most popular technologies for providing a “last-mile” communication platform. The quality of CATV network systems depends to a large extent on the experience of the designers who must consider the performance constraints mandated by standards and government regulations. Consequently, the quality of CATV network design may be unreliable, and in many cases poor.
In this dissertation, we study CATV networks planning problems. Mathematical formulations are used to model the planning problems, and geometric programming method, based on the proposed mathematical formulations, is adopted to solve the network planning problems. The scope and contributions of this dissertation are highlighted by the following.
For the min-cost CATV networks planning problem, we propose a mathematical model to describe CATV networks planning problem. Based on some mathematical features of the model, some reformulations are necessary to solve the problem. The surrogate functions are used to reformulate the objective function and some constraints.
By applying some nonlinear programming techniques, the single layer solution procedure for CATV network planning problems is developed. Some computational experiments are described and explained. From the experiment results, the solution procedure we developed is better than previous works. The comparison showed that our solution procedure is better in most of cases. The improvements on minimum costs are ranged from 51% to 92%. Based on the experiment results, we get some important finding in this problem, especially about the parameters settings in solution procedure. By the setting rules presented in this chapter, the solution quality, both the minimum cost and the scalability of the problem, can be further improved.
From the analysis of the solution procedure, however, we still could not deal with problems with too many nodes. Therefore, a multilayer solution procedure is proposed in Chapter 4. By layering a large network into several smaller networks, we can divide the problem and conquer every sub problems in reasonable time. After that, we can treat each network as a macro user in upper layer, and construct the network planning problem for upper layer. By summation the costs of upper layer and every sub layers, we can get the total cost of the entire network. By the multilayer solution procedure, we can solve CATV network planning problems with more nodes. We have compared with the single-layer solution procedure and show that only 40% of time is needed in multi-layer solution procedure. On the other side, the minimum costs solved by multilayer solution procedure are ranged from 2% to 45% larger than single-layer solution procedure. By balancing the computation time and solution quality, the multilayer solution procedure still provides a way to solve a larger network in limited time.
Besides the costs and computing time, we have developed algorithms for placement of drop points. In order to improve the costs of CATV networks, the placement of drop points in clusters is adjusted by proposed globally adaptive placecment algorithm. Based on experiment results, the reduced costs ranges from 9% to 13%. With tradeoff between computing time and costs, we propose partially adaptive placement algorithm, which only adjust the leave nodes on upper layer networks. Compared with globally adjustment, the computing time is reduced to 61.5% and only 4.88% cost increased.
Finally, we point out three challenging issues to be tackled in the future. These issues include adjustment procedure between layers in multiplayer solution procedure, how to apply the solution procedures to other kinds of application environments, and modifications for HFC (Hybrid Fiber/Coax) networks.
Subjects
有線電視網路
史坦那樹
修改式最陡梯度法
多層解題程序
網路規劃
幾何規劃法
數學規劃
網路最佳化
CATV Network
Modified Steepest Descent Method
Multilayer Solution Procedure
Network Planning
Geometric Programming
Mathematical Modeling
Network Optimization
Type
other