李圣普，王小輝

（平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，平頂山467002）

有線電視網(wǎng)絡(luò)布線路徑選擇算法研究與仿真*

李圣普，王小輝

（平頂山學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，平頂山467002）

有線電視網(wǎng)絡(luò)布線過程中，不但需要考慮網(wǎng)絡(luò)布線成本，還需要考慮線路安全風(fēng)險(xiǎn)。傳統(tǒng)的路線選擇模型僅僅以成本分析為基礎(chǔ)，很少考慮安全的風(fēng)險(xiǎn)因素，路線選擇存在較大缺失。提出基于粒子群離散變換算法的路徑選擇方法，根據(jù)最小二乘法相關(guān)原理，計(jì)算信號傳輸路徑危險(xiǎn)環(huán)境函數(shù)，獲取危險(xiǎn)程度擬合曲線，根據(jù)該函數(shù)得到信號傳輸路徑中的危險(xiǎn)程度。根據(jù)最小危害路徑選擇的目標(biāo)函數(shù)，對所有的待優(yōu)化變量進(jìn)行二進(jìn)制編碼，并針對編碼結(jié)果進(jìn)行離散化變換，實(shí)現(xiàn)有線電視網(wǎng)絡(luò)布線路徑的選擇。實(shí)驗(yàn)結(jié)果表明，利用改進(jìn)算法進(jìn)行網(wǎng)絡(luò)布線路徑選擇，降低了路徑協(xié)同誤差和路徑選擇誤差。

有線電視網(wǎng)絡(luò)；綜合布線；路徑選擇；智能規(guī)劃；危險(xiǎn)環(huán)境；最小二乘法

1 引 言

為了確保有線電視信號能夠安全順暢的到達(dá)目的地，有線電視網(wǎng)絡(luò)布線必須選擇最合適的路線。在信號傳輸過程中，需要對信號傳輸成本和信號傳輸風(fēng)險(xiǎn)進(jìn)行綜合考慮，制定最優(yōu)信號傳輸方案。但是在傳統(tǒng)的信號傳輸路徑選擇模型中，只考慮到信號傳輸成本，忽略了信號傳輸中的風(fēng)險(xiǎn)因素，因此這種傳統(tǒng)的信號傳輸路徑存在較大弊端。

有線電視網(wǎng)絡(luò)布線路徑選擇是指給定信號傳輸條件，以及起始和目標(biāo)的位置［1］，按照某一性能指標(biāo)，選擇一條從起始點(diǎn)到目標(biāo)點(diǎn)的路徑［2］，使有線電視網(wǎng)絡(luò)布線能安全到達(dá)目的地，是交通信號傳輸領(lǐng)域研究的核心問題之一［3］。對有線電視網(wǎng)絡(luò)布線路徑選擇方法進(jìn)行深入研究，可以提高有線電視網(wǎng)絡(luò)布線的安全性能［4］?，F(xiàn)階段，主要的有線電視網(wǎng)絡(luò)布線路徑選擇方法包括基于人工蜂群算法的路徑選擇方法［5］、基于蟻群算法的信號傳輸路徑選擇方法［6］和基于神經(jīng)網(wǎng)絡(luò)算法的信號傳輸路徑選擇方法［7］。其中，最常用的是基于人工蟻群算法的信號傳輸支路選擇方法［8］。由于信號傳輸路徑選擇方法擁有極為廣闊的發(fā)展空間，因此，受到了很多專家的重視［9］，成為大家研究的熱點(diǎn)問題，擁有巨大的發(fā)展?jié)摿Α?/p>

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

2 信號傳輸路徑選擇算法基礎(chǔ)

對信號傳輸線路的選擇關(guān)系到信號傳輸過程中的效率和安全。目前，在信號傳輸行業(yè)中，針對信號傳輸是一項(xiàng)十分復(fù)雜并重要的工作，普遍利用最優(yōu)路徑成本計(jì)算有線電視網(wǎng)絡(luò)布線路徑最優(yōu)解。基本原理如下：

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

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

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

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

上述式中，fiti表示第i個(gè)解的適應(yīng)度值。

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

計(jì)算有線電視網(wǎng)絡(luò)布線路徑的最優(yōu)解時(shí)，能夠利用以下過程描述最優(yōu)解的搜索過程：

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

b．利用格柵化方法對有線電視網(wǎng)絡(luò)布線的信號傳輸?shù)缆翻h(huán)境建立模型，并采集環(huán)境中的風(fēng)險(xiǎn)因素。

c．設(shè)置迭代次數(shù)的初始值G＝0。

d．在有線電視網(wǎng)絡(luò)布線信號傳輸?shù)膮^(qū)域內(nèi)隨機(jī)產(chǎn)生m個(gè)風(fēng)險(xiǎn)因素，利用公式（2）計(jì)算風(fēng)險(xiǎn)因素的適應(yīng)度值。危險(xiǎn)因素的位置位于前m／2個(gè)風(fēng)險(xiǎn)因素之內(nèi)，并與模型逐一對應(yīng)。設(shè)置標(biāo)志風(fēng)險(xiǎn)因素初始值為K（i）＝0，對同一支路的停留次數(shù)進(jìn)行記錄。

e．利用公式（1）進(jìn)行風(fēng)險(xiǎn)因素的搜索，并計(jì)算搜索解得的適應(yīng)度值，若搜索到的適應(yīng)度值大于之前的搜索結(jié)果，則將當(dāng)前的搜索值代替之前的搜索值，并將支路的位置確定為當(dāng)前位置。令K（i）＝0，不允許出現(xiàn)：K（i）＝K（i）＋1。

f．利用公式（2）對選擇的支路概率進(jìn)行計(jì)算，并確定支路。利用公式（3）將前一個(gè)路徑轉(zhuǎn)化為后一個(gè)路徑進(jìn)行核對。同時(shí)對支路周圍進(jìn)行搜索并標(biāo)記較優(yōu)支路的位置，對向量K進(jìn)行更新。

g．轉(zhuǎn)化條件是：K（i）＞Limit，完成轉(zhuǎn)化后，繼續(xù)進(jìn)行較優(yōu)支路的搜索。

h．將搜索到的最優(yōu)支路進(jìn)行記錄，最優(yōu)支路即算法的最優(yōu)解。

i．隨著迭代次數(shù)的增加，即G＝G＋1。若G＞Gmax，則當(dāng)前的解即為有線電視網(wǎng)絡(luò)布線通過的路徑點(diǎn)；并跳轉(zhuǎn)到步驟（j），否則跳轉(zhuǎn)到步驟（f）。

j．對此刻有線電視網(wǎng)絡(luò)布線已規(guī)劃窗口中的所有路徑點(diǎn)，能夠獲得此刻有線電視網(wǎng)絡(luò)布線行駛過的路徑，并將最后的有線電視網(wǎng)絡(luò)布線路徑點(diǎn)作為下一時(shí)刻支路的出發(fā)點(diǎn)，并跳轉(zhuǎn)至步驟（e）。

k．將有線電視網(wǎng)絡(luò)布線的起始點(diǎn)與最終點(diǎn)連接起來，得到有線電視網(wǎng)絡(luò)布線路徑。

有線電視網(wǎng)絡(luò)布線必須選擇最優(yōu)路線模型，以保證信號傳輸安全。但是，信號傳輸過程中，不但需要考慮信號傳輸成本和信號傳輸?shù)木€路，還需要考慮信號傳輸?shù)娘L(fēng)險(xiǎn)。傳統(tǒng)的路線選擇模型僅僅以成本分析為基礎(chǔ)，沒有加入信號傳輸?shù)娘L(fēng)險(xiǎn)因素，路線選擇存在較大缺失。

3 信號傳輸路徑選擇優(yōu)化方法理論

利用傳統(tǒng)的算法進(jìn)行信號傳輸路徑選擇時(shí)，主要考慮的是成本因素，而信號傳輸?shù)闹攸c(diǎn)在信號傳輸過程中的風(fēng)險(xiǎn)因素，會導(dǎo)致有線電視網(wǎng)絡(luò)布線在信號傳輸過程中出現(xiàn)各種未知的風(fēng)險(xiǎn)因素。針對傳統(tǒng)算法的缺陷，文中提出了一個(gè)基于粒子群離散變換算法的有線電視網(wǎng)絡(luò)布線路徑選擇方法。

該方法的首要問題是建立計(jì)算信號傳輸過程的風(fēng)險(xiǎn)因素函數(shù)。根據(jù)最小二乘算法的相關(guān)原理，能夠?qū)⒌玫降男蛄袛M合成曲線和曲線函數(shù)。最小二乘算法的優(yōu)點(diǎn)是在已知數(shù)據(jù)量較少的情況下擬合出精度很高的曲線和曲線函數(shù)。利用最小二乘算法結(jié)合灰色系統(tǒng)建模的相關(guān)理論，建立有線電視網(wǎng)絡(luò)布線路徑風(fēng)險(xiǎn)因素函數(shù)的過程如下：

設(shè)存在如下序列：

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

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

上述式中，

X（1）的緊鄰均值構(gòu)成的序列Z（1），

上述式中，

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

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

對有線電視網(wǎng)絡(luò)布線在信號傳輸過程中可能面臨的風(fēng)險(xiǎn)因素進(jìn)行調(diào)查，并將調(diào)查得到的數(shù)據(jù)作為原始數(shù)據(jù)，利用以下序列能夠描述調(diào)查得到的風(fēng)險(xiǎn)因素：

利用累加算子對得到的風(fēng)險(xiǎn)因素原始序列進(jìn)行處理，處理的過程如下：

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

最后將全部估計(jì)值進(jìn)行累減還原處理能夠得到有線電視網(wǎng)絡(luò)布線在信號傳輸過程中的風(fēng)險(xiǎn)因素函數(shù)。利用以下公式能夠描述：

利用上述方法能夠得到有線電視網(wǎng)絡(luò)布線在信號傳輸過程中危險(xiǎn)因素的擬合曲線函數(shù)，利用計(jì)算出的擬合值能夠?qū)η€函數(shù)模型進(jìn)行精度檢驗(yàn)。

在進(jìn)行有線電視網(wǎng)絡(luò)布線路徑選擇時(shí)，需要特別注意這兩點(diǎn)：合理選擇待優(yōu)化變量和明確搜索任務(wù)中的目標(biāo)函數(shù)。所以，在進(jìn)行最優(yōu)有線電視網(wǎng)絡(luò)布線路徑搜索時(shí)，應(yīng)先對各種風(fēng)險(xiǎn)因素將作為待優(yōu)化變量xijk，yik進(jìn)行編碼，將信號傳輸總路徑最小化作為目標(biāo)函數(shù)，則有線電視網(wǎng)絡(luò)布線路徑的目標(biāo)函數(shù)能夠利用組合優(yōu)化進(jìn)行描述。利用粒子群優(yōu)化算法能夠?qū)Υ齼?yōu)化變量的組合優(yōu)化搜索最優(yōu)解。

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

4 算法仿真結(jié)果分析

為了驗(yàn)證改進(jìn)算法的有效性，需要利用Matlab仿真軟件進(jìn)行一次仿真實(shí)驗(yàn)。設(shè)有線電視網(wǎng)絡(luò)布線的初始點(diǎn)是q1＝［25，47，32］T。

為了驗(yàn)證改進(jìn)算法的優(yōu)越性，需要進(jìn)行比對實(shí)驗(yàn)。

將以上實(shí)驗(yàn)得到的數(shù)據(jù)進(jìn)行整理匯總，能夠得到表1和表2所示數(shù)據(jù)。

表1 傳統(tǒng)算法實(shí)驗(yàn)數(shù)據(jù)結(jié)果

表2 改進(jìn)算法實(shí)驗(yàn)結(jié)果

在進(jìn)行實(shí)驗(yàn)時(shí)，利用不同算法進(jìn)行有線電視網(wǎng)絡(luò)布線的路徑選擇會產(chǎn)生誤差，利用圖1能夠描述不同算法的誤差。

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

試驗(yàn)分別利用改進(jìn)算法和傳統(tǒng)算法進(jìn)行有線電視網(wǎng)絡(luò)布線最小路徑選擇。實(shí)驗(yàn)結(jié)果如圖2所示。

根據(jù)上述實(shí)驗(yàn)結(jié)果可知，利用改進(jìn)算法進(jìn)行有線電視網(wǎng)絡(luò)布線最小路徑選擇，相對傳統(tǒng)的算法選擇誤差和協(xié)同誤差的收斂性能更優(yōu)越，能夠在較短時(shí)間內(nèi)收斂到零，充分體現(xiàn)出改進(jìn)算法的優(yōu)越性。

由以上的實(shí)驗(yàn)結(jié)果可知，利用改進(jìn)算法能夠避免傳統(tǒng)算法沒有考慮有線電視網(wǎng)絡(luò)布線在信號傳輸過程中風(fēng)險(xiǎn)因素的缺陷，能夠選擇最優(yōu)的最小危害信號傳輸路徑，效果令人滿意。

圖2 不同算法的對比實(shí)驗(yàn)結(jié)果

5 結(jié)束語

信號傳輸過程中，不但需要考慮信號傳輸成本和信號傳輸?shù)木€路，還需要考慮信號傳輸風(fēng)險(xiǎn)的因素。傳統(tǒng)的路線選擇模型僅僅以成本分析為基礎(chǔ)，很少考慮信號傳輸?shù)娘L(fēng)險(xiǎn)因素，路線選擇存在較大缺失。文中提出一種基于粒子群離散變換算法的有線電視網(wǎng)絡(luò)布線路徑選擇方法。利用最小二乘法算法計(jì)算信號傳輸?shù)穆窂轿ｋU(xiǎn)環(huán)境函數(shù)，能夠得到危險(xiǎn)程度擬合曲線，根據(jù)曲線函數(shù)能夠得到信號傳輸路徑中的風(fēng)險(xiǎn)因素。利用最小危害路徑選擇的目標(biāo)函數(shù)，對所有的待優(yōu)化變量進(jìn)行二進(jìn)制編碼，并針對編碼結(jié)果進(jìn)行離散化變換，實(shí)現(xiàn)有線電視網(wǎng)絡(luò)布線路徑的選擇。實(shí)驗(yàn)結(jié)果表明，粒子群離散變換算法與傳統(tǒng)算法相比，有較大的優(yōu)越性。因此，可以將這種算法廣泛應(yīng)用于有線電視網(wǎng)絡(luò)布線信號傳輸領(lǐng)域，對有線電視網(wǎng)絡(luò)布線路徑進(jìn)行合理選擇，從而有效減少信號傳輸過程中的風(fēng)險(xiǎn)。

［1］ 陳華志，謝存禧，曾德懷．基于神經(jīng)網(wǎng)絡(luò)的移動機(jī)器人路徑規(guī)劃算法的仿真［J］．華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（6）：56－60．Chen Hua－zhi，Xie Cun－xi，Zeng De－h(huán)uai．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ī)器人路徑規(guī)劃方法綜述［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］ 鞏敦衛(wèi)，耿娜，張勇．密集障礙物環(huán)境下基于凸包和微粒群優(yōu)化的機(jī)器人路徑規(guī)劃［J］．控制理論與應(yīng)用，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ī)器人路徑規(guī)劃方法［J］．計(jì)算機(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

河南省重點(diǎn)科技攻關(guān)項(xiàng)目（132102210443）

李圣普（1983－），男，河南省封丘縣人，碩士研究生，講師，主研方向：物聯(lián)網(wǎng)技術(shù)及應(yīng)用。

2014－12－15