油田水电站通信系统中网路最短路径的计算

琼州学院网络与教育技术中心

油田水电站通信系统中网路最短路径的计算

王乙人

琼州学院网络与教育技术中心

油田水电站通信系统网路最短路径算法包括最小生成树算法、狄克斯特拉算法和网路最大流最短路径传输算法。最小生成树算法主要用于水电站接收设备传输路径的选择，可查询由接收设备至终端设备的最短传输线路。该算法可将每个站点的距离矢量的竖列划去，在横向排中寻找最小传输距离；最后，将每行的数据进行排列相加，得出接收设备与终端设备的最短传输距离。狄克斯特拉最短路径运算方法主要用于油田水电站通信站点互通距离计算。网络最大流传输路径算法可用于通信数据信息传输线路的选择，寻找传输至数据处理系统的最短线路，保证其他各条通信线路的正常使用。

网路；最小生成树算法；最大流控制；水电站；通信系统

1 通信系统网路最短路径算法

1.1 最小生成树算法

在油井网路水电站通信系统中，最小生成树的运算流程为：首先，找到水电站通信网路中的节点，将各个节点之间的传输距离进行标注。接着，将所标的数值从小到大进行有序排列，选出序列中最小的加权值。最后，将加权值依次排列，查看所构成的传输通信线路是否构成回路。假如在排列过程中构成回路，则舍去该边的传输路径，在此基础上寻找另一条传输路径。若水电站通信传输系统中共包含n个传输节点，则构成的传输线路共有n-1条，将传输路径的有效值相加，便构成了最小生成树。

1.2 狄克斯特拉最短路径算法

油井水电站通信传输系统中，另一种寻找最短路径的算法称为狄克斯特拉算法。这种算法在运算模式上比最小生成树的逻辑性更强，主要用于水电站数据信息传输系统中。该方法首先对传输节点的有效距离进行标注，将端点标为0，终点标为∞，最后找端点至终点的最短距离。如图1所示，s点至2节点的有效距离为10，2点至5节点的有效距离为1，5点至t节点的有效距离为20，s点至3节点的有效距离为15，s点至4节点的有效距离为8，4点至6节点的有效距离为7，3点至5节点的有效距离为9，5点至6节点的有效距离为2，6点至7节点的有效距离为30，3点至6节点的有效距离为2，3点至4节点的有效距离为4。s至节点3的传输路径有s—2—5—3，s—3，s—4—3，s—4—6—3；s—2—5—3传输路径的距离为19，s—3的传输距离为15，s—4—3的传输路径距离为12，s—4—6—3的传输路径距离为17。s至节点5的传输路径有s—2—5，s—3—5，s—4—3—5，s—2—3—5；s—2—5的传输距离为11，s—3—5的传输距离为24，s—4—3—5的传输距离为21，s—2—3—5的传输距离为27。s至节点5的传输最短路径为s—2—5。然后再找出节点5至终点t的传输路径，其中包括5—t，5—6—t；5—t的传输路径过程中，传输的有效距离为20；5—6—t的传输路径过程中，传输的有效距离为32。因此s—t最短传输路径为31。

图1 狄克斯特拉最短路径算法

1.3 网路最大流最短路径传输算法

水电站通信系统中网路最大流的最短路径传输算法利用的是寻找增广链的方式，保证传输路径中正向的传输链路为非饱和边，反向边为非零流边。油田水电站通信系统中有多个网路站点，每个站点彼此之间的传输路线不同。假设油田水电站通信系统站点有n个，传输的路线便存有n2-1条。若油田系统中存有的站点有6个，每个站点传输的路线都配有坐标值，其中s站点传输路线的坐标值为

（8，4），（7，4）；1站点传输路线的坐标值为（9，7），（5，1）；2站点传输路线的坐标值为（2，0），（9，，5）；3站点传输路线的坐标值为（6，1），（10，4）。由站点s出发至节点t的传输路径有：s—1—3—t，s—1—2—4—t，s—1—2—4—3—t，s—1—3—4—t，4条传输线路。将4条传输路径长度的最大值相加便得出最大流的传输距离。

2 最短传输路径算法的应用

由于油田通信系统传输线路较多，当传输较多的数据信息时会造成通信线路的堵塞，进而隔断了信息传输线路，使数据信息失真。最小生成树算法主要用于水电站接收设备传输路径的选择。由于通信系统中终端设备与传输设备间隔距离较长，数据在传输过程中容易出现延时效应，造成数据信息大量地堆积在通信线路中。而最小生成树算法可查询由接收设备至终端设备的最短传输线路，将每个油田通信站点的接收设备连成一个矢量的矩阵，每个站点与站点之间的传输都能在矩阵规划中明确地体现出来。该算法可将每个站点的距离矢量的竖列划去，在横向排中寻找最小传输距离。最后，将每行的数据进行排列相加，得出接收设备与终端设备的最短传输距离。

狄克斯特拉最短路径运算方法主要用于油田水电站通信站点互通距离计算。假设油田水电站通信系统是独立划分的，在同一条通信线路上进行数据信息传输，那么很可能会造成通信系统中内部的数据网络无法进行有效共享，出现数据信息泛洪现象。由于没有进行线路的划分，各个终端处理器传输的数据信息将会大量地堆积在传输信道内，服务台无法获取准确的有效信息，大量的数据信息传输至各条线路，使得每个终端系统都能接收传输的数据信息，造成传输信道资源的浪费。

网络最大流传输路径算法可用于通信数据信息传输线路的选择，寻找传输至数据处理系统的最短线路，保证其他各条通信线路的正常使用。

3 结语

传统油田水电站通信系统在传输数据信息时存有严重问题，主要是因为数据信息在传输线路上难以找到最短的传输路径，造成数据信息大量的堆积在传输信道内，使终端系统无法获取有效的数据信息。通过对油田网络最大流控制技术在水电站通信系统中的应用分析，表明该技术能确保传输数据信息的安全，提高通信系统的稳定性。

（栏目主持 杨 军）

10.3969/j.issn.1006-6896.2014.9.019