有線電視網絡布線路徑選擇算法研究與仿真*

李圣普，王小輝

（平頂山學院計算機科學與技術學院，平頂山467002）

有線電視網絡布線路徑選擇算法研究與仿真*

李圣普，王小輝

（平頂山學院計算機科學與技術學院，平頂山467002）

有線電視網絡布線過程中，不但需要考慮網絡布線成本，還需要考慮線路安全風險。傳統的路線選擇模型僅僅以成本分析為基礎，很少考慮安全的風險因素，路線選擇存在較大缺失。提出基于粒子群離散變換算法的路徑選擇方法，根據最小二乘法相關原理，計算信號傳輸路徑危險環境函數，獲取危險程度擬合曲線，根據該函數得到信號傳輸路徑中的危險程度。根據最小危害路徑選擇的目標函數，對所有的待優化變量進行二進制編碼，并針對編碼結果進行離散化變換，實現有線電視網絡布線路徑的選擇。實驗結果表明，利用改進算法進行網絡布線路徑選擇，降低了路徑協同誤差和路徑選擇誤差。

有線電視網絡；綜合布線；路徑選擇；智能規劃；危險環境；最小二乘法

1 引 言

為了確保有線電視信號能夠安全順暢的到達目的地，有線電視網絡布線必須選擇最合適的路線。在信號傳輸過程中，需要對信號傳輸成本和信號傳輸風險進行綜合考慮，制定最優信號傳輸方案。但是在傳統的信號傳輸路徑選擇模型中，只考慮到信號傳輸成本，忽略了信號傳輸中的風險因素，因此這種傳統的信號傳輸路徑存在較大弊端。

有線電視網絡布線路徑選擇是指給定信號傳輸條件，以及起始和目標的位置［1］，按照某一性能指標，選擇一條從起始點到目標點的路徑［2］，使有線電視網絡布線能安全到達目的地，是交通信號傳輸領域研究的核心問題之一［3］。對有線電視網絡布線路徑選擇方法進行深入研究，可以提高有線電視網絡布線的安全性能［4］。現階段，主要的有線電視網絡布線路徑選擇方法包括基于人工蜂群算法的路徑選擇方法［5］、基于蟻群算法的信號傳輸路徑選擇方法［6］和基于神經網絡算法的信號傳輸路徑選擇方法［7］。其中，最常用的是基于人工蟻群算法的信號傳輸支路選擇方法［8］。由于信號傳輸路徑選擇方法擁有極為廣闊的發展空間，因此，受到了很多專家的重視［9］，成為大家研究的熱點問題，擁有巨大的發展潛力。

粒子群算法是由Eberhart和Kennedy提出的一種智能化優化算法，該算法具有搜索機制較為簡單，收斂速度快，運算量小等優點，在近幾年被廣泛應用到解決各種復雜問題中，并被證明比遺傳算法等傳統的搜索算法性能更優越。為了避免傳統方法的弊端，必須利用新的方法選擇有線電視網絡布線路徑。粒子群算法在進行大規模搜索時，能夠避免陷入局部最優解的缺陷，因此，非常適合應用到復雜的危運路徑的選擇方面。為此，根據粒子群算法的原理，提出一種基于粒子群離散變換算法的有線電視網絡布線路徑選擇方法。

2 信號傳輸路徑選擇算法基礎

對信號傳輸線路的選擇關系到信號傳輸過程中的效率和安全。目前，在信號傳輸行業中，針對信號傳輸是一項十分復雜并重要的工作，普遍利用最優路徑成本計算有線電視網絡布線路徑最優解。基本原理如下：

設線路的初始數量是mxi（1，2，．．．，m），線路在人工搜索中表示解的集合，用xi（1，2，．．．，m）表示，其中每個解都可以用d維向量描述。對路徑進行搜索時，循環搜索之路，首先根據對應的解對鄰域進行一次搜索，如果搜索到的解比原來的解更優越，則將搜索到的解代替原來的解；所有的搜索全部結束時，會利用通知的方式將信息傳達給路徑選擇模型，模型根據與支路信息量相關的概率選擇支路。確定支路路徑后，利用相似鄰域的搜索方法，在搜索過程中不斷保留較好的解，持續重復這種搜索方式，直至搜索到最優的路徑選擇結果。

在搜索支路的過程中，能夠利用以下公式確定支路的更新位置：

上式中，k∈（1，2，．．．，SN），j∈（1，2，．．．，d），是任意選擇下標。rij∈［－1 1］中間一個任意數，其主要作用是決定xij鄰域范圍的大小，在搜索逐漸接近最優解的過程中，鄰域的范圍會越來越小。

利用以下公式能夠描述選擇支路概率Pi：

上述式中，fiti表示第i個解的適應度值。

若在搜索經過有限次循環之后，得到的解仍然沒有變化，則能夠判定此解已經成為局部最優解。這個位置的解將會被舍棄，與該位置對應的支路將轉化為待更新路徑，搜索新的支路。利用以下公式能夠描述這種轉化過程。

計算有線電視網絡布線路徑的最優解時，能夠利用以下過程描述最優解的搜索過程：

a．對參數進行初始化。在初始化時，需要確定算法可行解的數量m，最大迭代次數Gmax和最大限制次數Limit值。

b．利用格柵化方法對有線電視網絡布線的信號傳輸道路環境建立模型，并采集環境中的風險因素。

c．設置迭代次數的初始值G＝0。

d．在有線電視網絡布線信號傳輸的區域內隨機產生m個風險因素，利用公式（2）計算風險因素的適應度值。危險因素的位置位于前m／2個風險因素之內，并與模型逐一對應。設置標志風險因素初始值為K（i）＝0，對同一支路的停留次數進行記錄。

e．利用公式（1）進行風險因素的搜索，并計算搜索解得的適應度值，若搜索到的適應度值大于之前的搜索結果，則將當前的搜索值代替之前的搜索值，并將支路的位置確定為當前位置。令K（i）＝0，不允許出現：K（i）＝K（i）＋1。

f．利用公式（2）對選擇的支路概率進行計算，并確定支路。利用公式（3）將前一個路徑轉化為后一個路徑進行核對。同時對支路周圍進行搜索并標記較優支路的位置，對向量K進行更新。

g．轉化條件是：K（i）＞Limit，完成轉化后，繼續進行較優支路的搜索。

h．將搜索到的最優支路進行記錄，最優支路即算法的最優解。

i．隨著迭代次數的增加，即G＝G＋1。若G＞Gmax，則當前的解即為有線電視網絡布線通過的路徑點；并跳轉到步驟（j），否則跳轉到步驟（f）。

j．對此刻有線電視網絡布線已規劃窗口中的所有路徑點，能夠獲得此刻有線電視網絡布線行駛過的路徑，并將最后的有線電視網絡布線路徑點作為下一時刻支路的出發點，并跳轉至步驟（e）。

k．將有線電視網絡布線的起始點與最終點連接起來，得到有線電視網絡布線路徑。

有線電視網絡布線必須選擇最優路線模型，以保證信號傳輸安全。但是，信號傳輸過程中，不但需要考慮信號傳輸成本和信號傳輸的線路，還需要考慮信號傳輸的風險。傳統的路線選擇模型僅僅以成本分析為基礎，沒有加入信號傳輸的風險因素，路線選擇存在較大缺失。

3 信號傳輸路徑選擇優化方法理論

利用傳統的算法進行信號傳輸路徑選擇時，主要考慮的是成本因素，而信號傳輸的重點在信號傳輸過程中的風險因素，會導致有線電視網絡布線在信號傳輸過程中出現各種未知的風險因素。針對傳統算法的缺陷，文中提出了一個基于粒子群離散變換算法的有線電視網絡布線路徑選擇方法。

該方法的首要問題是建立計算信號傳輸過程的風險因素函數。根據最小二乘算法的相關原理，能夠將得到的序列擬合成曲線和曲線函數。最小二乘算法的優點是在已知數據量較少的情況下擬合出精度很高的曲線和曲線函數。利用最小二乘算法結合灰色系統建模的相關理論，建立有線電視網絡布線路徑風險因素函數的過程如下：

設存在如下序列：

上述式中，X（0）（k）≥0，k＝1，2，．．．，n

x（0）的l－AGO序列x（1）能夠利用以下公式描述：

上述式中，

X（1）的緊鄰均值構成的序列Z（1），

上述式中，

利用上述公式得到最小二乘的估計數列，能夠利用以下公式描述：

對上述公式計算，將得到的值作為累加算子，并代入以下公式，對求得數據的估計值進行還原：

對有線電視網絡布線在信號傳輸過程中可能面臨的風險因素進行調查，并將調查得到的數據作為原始數據，利用以下序列能夠描述調查得到的風險因素：

利用累加算子對得到的風險因素原始序列進行處理，處理的過程如下：

首先對X（0）利用1－AGO算子處理能夠得到X（1）；然后對X（1）利用緊鄰均值處理能夠得到Z（1）；

最后將全部估計值進行累減還原處理能夠得到有線電視網絡布線在信號傳輸過程中的風險因素函數。利用以下公式能夠描述：

利用上述方法能夠得到有線電視網絡布線在信號傳輸過程中危險因素的擬合曲線函數，利用計算出的擬合值能夠對曲線函數模型進行精度檢驗。

在進行有線電視網絡布線路徑選擇時，需要特別注意這兩點：合理選擇待優化變量和明確搜索任務中的目標函數。所以，在進行最優有線電視網絡布線路徑搜索時，應先對各種風險因素將作為待優化變量xijk，yik進行編碼，將信號傳輸總路徑最小化作為目標函數，則有線電視網絡布線路徑的目標函數能夠利用組合優化進行描述。利用粒子群優化算法能夠對待優化變量的組合優化搜索最優解。

在利用粒子群優化算法尋求路徑的最優解之前，需要將對信號傳輸過程中的風險因素xij，i∈N，j∈M作為待優化變量進行編碼。文中利用二進制編碼的方法對待優化變量進行編碼。在利用粒子群算法進行最優解的搜索中，需要將連續的粒子群與離散的粒子群進行映射。進行映射時，首先需要將連續的粒子個體轉化為離散的粒子個體，對于全部獨立的粒子進行賦值處理，正數取值為1，負數取值為0，利用這種方法能夠得到離散的二進制粒子：

4 算法仿真結果分析

為了驗證改進算法的有效性，需要利用Matlab仿真軟件進行一次仿真實驗。設有線電視網絡布線的初始點是q1＝［25，47，32］T。

為了驗證改進算法的優越性，需要進行比對實驗。

將以上實驗得到的數據進行整理匯總，能夠得到表1和表2所示數據。

表1 傳統算法實驗數據結果

表2 改進算法實驗結果

在進行實驗時，利用不同算法進行有線電視網絡布線的路徑選擇會產生誤差，利用圖1能夠描述不同算法的誤差。

圖1 不同算法路徑選擇的誤差

試驗分別利用改進算法和傳統算法進行有線電視網絡布線最小路徑選擇。實驗結果如圖2所示。

根據上述實驗結果可知，利用改進算法進行有線電視網絡布線最小路徑選擇，相對傳統的算法選擇誤差和協同誤差的收斂性能更優越，能夠在較短時間內收斂到零，充分體現出改進算法的優越性。

由以上的實驗結果可知，利用改進算法能夠避免傳統算法沒有考慮有線電視網絡布線在信號傳輸過程中風險因素的缺陷，能夠選擇最優的最小危害信號傳輸路徑，效果令人滿意。

圖2 不同算法的對比實驗結果

5 結束語

信號傳輸過程中，不但需要考慮信號傳輸成本和信號傳輸的線路，還需要考慮信號傳輸風險的因素。傳統的路線選擇模型僅僅以成本分析為基礎，很少考慮信號傳輸的風險因素，路線選擇存在較大缺失。文中提出一種基于粒子群離散變換算法的有線電視網絡布線路徑選擇方法。利用最小二乘法算法計算信號傳輸的路徑危險環境函數，能夠得到危險程度擬合曲線，根據曲線函數能夠得到信號傳輸路徑中的風險因素。利用最小危害路徑選擇的目標函數，對所有的待優化變量進行二進制編碼，并針對編碼結果進行離散化變換，實現有線電視網絡布線路徑的選擇。實驗結果表明，粒子群離散變換算法與傳統算法相比，有較大的優越性。因此，可以將這種算法廣泛應用于有線電視網絡布線信號傳輸領域，對有線電視網絡布線路徑進行合理選擇，從而有效減少信號傳輸過程中的風險。

［1］ 陳華志，謝存禧，曾德懷．基于神經網絡的移動機器人路徑規劃算法的仿真［J］．華南理工大學學報（自然科學版），2003，31（6）：56－60．Chen Hua－zhi，Xie Cun－xi，Zeng De－huai．Simulation of a Neural Network based Path Planning Algorithm for Mobile Robot［J］．Joumal of South China University of Teehnology（Natural Seience Edition），2003，31（6）：56－60．

［2］ 張穎，吳成東，原寶龍．機器人路徑規劃方法綜述［J］．控制工程，2003，10（1）：152－155．ZHANG Ying，WU Cheng－dong，YUAN Bao－long．Review of robot path planning method［J］．Control Engineering of China，2003，10（1）：152－155．

［3］ Kevin M Stebbing．the application of genetic algorithms to path planning for mobile robots［D］．AThesis Submitted to the University of Wales for the Degree of Magister in Scientica，2012．［4］ Mansor MA，Morris AS．Path planning in unknownenvironment with obstacles using virtual window［J］．Journal of IntelligentandRoboticSystems，2009，14（24）：235－251．

［5］ Zavlangas PG，Tzafestas SG．Industrial robot navigation and obstacle avoidance employing fuzzy logic［J］．Journal of Intelligent and Robotic Systems，2010，6（27）：85－97．

［6］ Ioannis K Nikolos，Kimon P Valavanis，Nikos C Tsourveloudis，et al．Evolutionary algorithm based offline／online path planning for UAV Navigation［C］．IEEE transactions on systems，man，and cybernetics－part B：Cybernetics，2013，33（6）：898－912．

［7］ Avneesh S，Erik A，Sean C，et al．Real－time path planning in dynamic virtual environment using multi－agent navigation graphs［J］．IEEE Trans on Visualization and Computer Graphics，2008，14（3）：526－530．

［8］ 鞏敦衛，耿娜，張勇．密集障礙物環境下基于凸包和微粒群優化的機器人路徑規劃［J］．控制理論與應用，2012，29（5）：609－616．GONG Dun－wei，GENG Na，ZHANG Yong．Robot path planning in environments with dence obstacles based on convex hull and particle swarm optimization［J］．Control Theory＆Application，2012，29（5）：609－616．

［9］ 何娟，涂中英，牛玉剛．一種遺傳蟻群算法的機器人路徑規劃方法［J］．計算機仿真，2010，27（3）：170－175．HE Juan，TU Zhong－ying，NIU Yu－gang．A Method of Mobile Robotic Path Planning Based on Integrating of GA and ACO［J］．Computer simulation，2010，27（3）：170－175．

Cable Television Network Wiring Route Choice Model in the Simulation

Li Shengpu，Wang Xiaohui
（College of Computer Science and Technology，Pingdingshan University，Pingdingshan 467002，China）

The optimal route model must be chosen for the cable television network wiring to ensure the transportation safety．However，in the wiring process of the cable television network，not only the transportation cost but also the risk factors should be considered．There are some defects in the traditional route choice model based on cost analysis because of the safety factors rarely be considered．The routing choice method，based on particle swarm discrete transform algorithm，is proposed．According to the principle of least square method related，the dangerous environment function of the transportation route is calculated，the fitting curve is obtained，and the dangerous degree in the transportation route is got．According to the objective function of minimum harm route choice，the binary encoding is conducted for all variables to be the optimized and the discretization is carried out for coding transform．The experimental results show that the improved algorithm is used for cable television network wiring route choice to reduce the error in route coordination and the path choice．

Cable Television Network；Integrated wiring；Route choice；Intelligent planning；Dangerous environment；The least square method

10．3969／j．issn．1002－2279．2015．04．013

TP391

B

1002－2279（2015）04－0049－04

河南省重點科技攻關項目（132102210443）

李圣普（1983－），男，河南省封丘縣人，碩士研究生，講師，主研方向：物聯網技術及應用。

2014－12－15