摘要
由於具有高頻寬、高普及率以及容易擴充等優點，有線電視網路已然成為國家資訊基礎建設中不可或缺的一部份。除了政府相關部門制訂有線電視法等相關法規來規範有線電視業者外，同時為滿足上行通路的系統信號品質要求，要建構一雙向傳輸有線電視網路所必須考慮的層面相當多且複雜。整體來說，有效的提升有線電視網路的管理與規劃，傳統的有線電視網路將不僅是能夠提供電視節目的傳送，更可能是一種經濟有效的通訊網路系統。然而，將原本單向傳輸的有線電視網路擴充為互動式存取網路卻必須面對許多問題。另一方面，由於有線電視網路的管理與規劃具有相當的複雜性，因此，今日有線電視網路的設計，仍依賴網路規劃人員的經驗，而無法透過可驗證與重複實施的程序來加以規劃。因此，所得到的設計其網路服務品質往往是無法預測的，在傳統的電視節目傳輸上，或許較低的服務品質只是帶來較差的畫面品質，但是在資料傳輸時，卻可能成為極大的問題。如何能經濟有效的提升網路的效能，成了有線電視網路的重要議題。 在此論文中，我們將針對有線電視網路規劃問題進行探討，使用數學模型來描述此類網路規劃問題，並使用幾何規劃法作為基礎，以最佳化的方式提出適合的演算法。本論文的研究內涵與成果簡述如下： § 最小成本之有線電視網路規劃問題：考慮路由決策與訊號品質規範下所有給定有線電視用戶滿足有線電視服務的最小成本有線電視網路系統。我們成功的將此問題以數學模型進行描述，並提出適用幾何規劃法的修改數學模型，以進行最佳化為基礎演算法的發展。 § 有線電視網路規劃的單層解題程序：傳統的網路規劃方法僅考慮網路訊號品質的追蹤與計算，對於所規劃的網路成本並未能進行最佳化調整。即便有少數研究嘗試進行網路規劃問題的成本最小化，所得的結果仍不盡理想。本研究所發展的單層有線電視網路規劃演算法，考慮一次解決頭端至所有用戶端的有線電視網路成本最佳化。我們以修改式最陡梯度法改善了之前的結果，.成本降低幅度在51% 至92% 之間。此外，為求進一步改善計算的效率，降低所使用的計算時間，我們針對了修改式最陡梯度法的步幅起始值，分析與網路問題特性的關係。我們提出了步幅起始值的設定調整機制，大幅減少了所需的計算時間，而能達到相同的解題品質。 § 有線電視網路規劃的多層解題程序：對於較大型有線電視網路規劃問題，採用單層解題程序無法於合理時內解決時，我們需要將原問題拆解成數個較小的網路規劃問題，分層加以解決。根據我們的實驗結果，多層解題程序的計算時間平均為單層解題程序所花時間的40%，隨著網路大小的增加，多層解題程序所花的計算時間與單層解題程序相較差異快速增加。雖然計算速度提升，然多層解題程序犧牲了全域調整的可能性，這影響了所得到的解題品質。多層解題程序所獲得的最小成本，相較單層解題程序要高出2%至45%。 論文的最後，我們提出三個未來重要的延續研究議題，以供後續學者進行研究。這些議題包括：多層網路規劃法中各層間的調整機制、新應用環境下的有線電視網路規劃問題、以及混合式光纖電纜有線電視網路規劃問題。
並列摘要
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.