有线电视网络布线路径选择算法研究与仿真*

李圣普，王小辉

（平顶山学院计算机科学与技术学院，平顶山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