一种采用基于Delaunay三角剖分的空间网络编码的网络传输方法

摘要

本发明公开了一种采用基于Delaunay三角剖分的空间网络编码的网络传输方法，适用于包含N个终端点的传输网络；包括初始化步骤、Delaunay预处理步骤、形成子矩形步骤、子矩形划分步骤、求平衡前线性规划最优解步骤、调整中继点到平衡位置步骤、求平衡后线性规划最优解步骤和Delaunay后处理步骤；通过采用Delaunay三角剖分得到斯坦纳点和增补的斯坦纳点作为候选的中继点，并通过非均匀划分得到候选的中继点，从上述候选的中继点中选出最优的中继点，对选出中继点的位置进行微调以进一步降低代价，从而得到采用空间网络编码的网络传输方案，解决现有技术中仅基于非均匀划分的空间网络编码方法中，当中继点与终端点非均匀密度分布时求线性规划最优解时计算量大的问题，进一步有效提升网络传输的总体性能。

说明书

技术领域

本发明属于网络信息传输技术领域，更具体地，涉及一种采用基于 Delaunay三角剖分的空间网络编码的网络传输方法。

背景技术

网络编码是网络信息论的重要分支之一，其基本思想是允许网络中间 节点参与编译码，可提升吞吐量、提高带宽利用率并降低算法复杂度；网 络编码理论提出信息流概念，指出通过编译码压缩信息流以提升吞吐量， 网络编码也称为网络信息流。

空间网络编码研究的是几何空间中的网络编码，也称为空间信息流。 此处几何空间指欧几里得空间。空间信息流允许加入额外的中继点及其相 连链路，而前述网络信息流则不允许。空间网络编码的典型优势是在空间 中采用网络编码的代价可严格小于空间中采用路由的代价；在空间中采用 多播路由，相当于欧几里得斯坦纳最小树问题，已经证明该问题是非确定 性多项式困难(NP-Hard)问题，解决该问题的方法复杂度较高；在空间中 采用网络编码，其代价可严格小于空间中的最优多播路由的代价，典型实 例是五角星网络。可见，空间网络编码与空间路由存在本质差别，说明研 究空间网络编码的重要性和必要性；其中，中继点是指为达到具有最小代 价的网络通信目标所增加的通信节点，其个数和位置是任意的；为达到具 有最小代价的网络传输，中继点的位置范围应在终端点所确定的凸包内(包 括凸包边界)；凸包是指二维空间中包含终端点集的最小凸多边形。

考虑欧几里得空间中采用空间网络编码的网络传输问题：对于任意给 定的终端点集合，并允许添加额外的中继点，通信目标是要求实现具有最 小代价的多播网络。现有技术中有一种基于均匀划分的空间网络编码的网 络传输方法，其基本内容包括对给定的终端点所形成的约束矩形进行均匀 划分得到矩形格子，取每个矩形格子中心作为候选的中继点，针对所有终 端点和中继点构建完全图，然后构建基于信息流的线性规划数学模型并求 线性规划最优解；逐步增大均匀划分的数量，所求拓扑逼近最优拓扑，最 后采用力学平衡的方法求解中继点的最优位置；其中，终端点指网络通信 中位置固定的节点，包括一个信源节点和至少一个信宿节点，分别称为信 源终端点和信宿终端点；完全图是指任意两点间都有一条链路的简单图； 简单图指既不存在有环链路也不存在多重链路的图。

该方法存在如下不足：当给定的终端点与终端点之间存在非均匀密度 分布时，此时采用均匀划分后矩形格子数量非常大，在构建完全图时链路 总数也非常大，导致求线性规划最优解时计算量陡增。

针对上述问题，现有技术中有一种基于非均匀划分(Non-uniform Partitioning)的空间网络编码的网络传输方法，其基本内容包括对给定的终 端点进行非均匀划分，即从每个终端点画水平线和垂直线，各条水平线和 垂直线交点形成若干子矩形，再将每个子矩形划分为p×p个矩形格子，取 每个矩形格子中心作为候选的中继点，针对所有终端点和候选的中继点构 建完全图，然后构建基于信息流的线性规划数学模型并求线性规划最优解； 逐步增大p的数量，所求拓扑逼近最优拓扑，最后采用力学平衡的方法求 解中继点的最优位置。

该方法存在如下不足：当中继点和终端点之间存在非均匀密度分布时， 此时采用非均匀划分后矩形格子数量非常大，在构建完全图时链路总数也 非常大，导致求线性规划最优解时计算量陡增。

发明内容

针对现有技术的以上缺陷或改进需求，本发明提供了一种采用基于 Delaunay三角剖分的空间网络编码的网络传输方法，其目的在于解决现有 技术仅基于非均匀划分的空间网络编码方法中，中继点与终端点非均匀密 度分布时求线性规划最优解时计算量大的问题。

其中，Delaunay三角剖分(DelaunayTriangulation)是指将二维欧几里 得空间中由终端点所形成的凸包剖分为若干个Delaunay三角形，这些 Delaunay三角形满足如下主要性质：任一个Delaunay三角形顶点有且仅有 一个圆，且该圆内不含有任何其它终端点(即最大空圆性质)；任一个 Delaunay三角形一定是最小角最大(最小角最大化原则)，后者使得 Delaunay三角形更接近正三角形。

为实现上述目的，按照本发明的一个方面，提供了一种采用基于 Delaunay三角剖分的空间网络编码的网络传输方法，适用于包含N个终端 点的传输网络，N为正整数；该方法包括初始化步骤、Delaunay预处理步 骤、形成子矩形步骤、子矩形划分步骤、求平衡前线性规划最优解步骤、 调整中继点到平衡位置步骤、求平衡后线性规划最优解步骤和Delaunay后 处理步骤，具体如下：

(1)初始化步骤：计算N个终端点的凸包，得到包含各终端点的最小 凸多边形的各条边；其中，凸包是指二维空间中包含终端点集的最小凸多 边形；N为正整数；

(2)Delaunay预处理步骤：对于N个终端点，采用Delaunay三角剖 分的方法获得至多(2N-5)个Delaunay三角形；采用计算3个终端点的斯 坦纳点的方法，获取每个Delaunay三角形的斯坦纳点；将每两个相邻的 Delaunay三角形拼接成一个四边形，采用计算4个终端点的斯坦纳点的方 法，获取每个四边形的斯坦纳点；将所有斯坦纳点存入斯坦纳点集合S；

(3)形成子矩形步骤：获取N个终端点坐标的横坐标的最小值XI、 横坐标的最大值XA、纵坐标的最小值YI和纵坐标的最大值YA；连接坐标 为(XI，y_k)和(XA，y_k)的两点，形成横线段；连接坐标为(x_k，YI) 和(x_k，YA)的两点，形成纵线段；各横线段与纵线段形成子矩形；其中， (x_k，y_k)为终端点t_k的坐标，0≤k≤N-1；

(4)子矩形划分步骤：将各子矩形划分为p×p个矩形格子，获取各 矩形格子对角线交点的坐标；获取位于凸包上和凸包内的所有对角线交点， 将这些交点作为候选的中继点，存入中继点集合R；

对终端点集合、斯坦纳点集合、中继点集合、增补斯坦纳点集合和当 前最优中继点集合的并集构建完全图K＝(V，E，ω(uv))；

其中，平衡前节点集合V＝T∪S∪S’∪R∪R^*，包括N＝|T|个终端点与 M＝|S∪S’∪R∪R^*|个候选的中继点r_N-1+m，r_N-1+m的坐标为(x_N-1+m，y_N-1+m)， 1≤m≤M；节点集合V中任意两节点u和v之间用无向链路uv连接，uv∈E， E是指所有无向链路的集合；无向链路uv的权值ω(uv)为两节点u与v之间的 欧几里得距离；p取不小于2的正整数；T是指由N个终端点构成的终端点 集合；S是指斯坦纳点集合；S’是指增补斯坦纳点集合；R是指中继点集合； R^*是指当前最优中继点集合；

(5)求平衡前线性规划最优解步骤：基于上述完全图K，构建平衡前 基于信息流的线性规划数学模型，包括目标函数和约束条件；

目标函数为约束条件包括信息流守恒条件、信 息流上限条件和非负条件；利用线性规划方法获取平衡前基于信息流的线 性规划数学模型的最优解，输出平衡前基于信息流的线性规划数学模型的 目标函数值C_p；输出各有向链路的信息传输速率的值和总信息传输 速率的值，以及各无向链路uv的总信息传输速率f(uv)的值；

判断是否满足C_p＜CI；若是，则将目标函数值C_p作为平衡前最小代价 值CI；若否，则判断所有中继点的所有邻接无向链路的总信息传输速率是 否全为零；

若是，表明无中继点，则置当前最优中继点集合R^*为空集，并进入步 骤(7)；若否，则针对中继点的邻接无向链路的总信息传输速率不全为零 的中继点，判断是否其中2个以上中继点在一条线段上；若是，则删除处 于该线段上的其它中继点，仅保留处于该线段点位置的2个中继点，查找 满足“其所有邻接无向链路的总信息传输速率不全为零”的中继点，并将 满足该条件的所有中继点存入当前最优中继点集合R^*，进入步骤(6)；其 中，集合R^*的大小为M^*，记为M^*＝|R^*|；是指平衡前有向链路的权 值，为两节点u与v之间的欧几里得距离；A是指平衡前有向链路集合；表示从信源终端点t₀发送到信宿终端点t_i的信息流在有向链路上的信息 传输速率；i为信宿终端点计数器，1≤i≤N-1；

(6)调整中继点到平衡位置步骤：置回数计数器RD＝1；采用向量加 法获取当前最优中继点集合R^*中各中继点r_N-1+j的合力其中，为沿邻接有向链路方向的力，的大小若某个中继点合力不满足将该中继点r_N-1+j沿其 合力的方向移动到其合力在ε₁范围内的平衡位置，直至所有中继点合 力将当前最优中继节点集合R^*更新为所有调整到平衡位置的 中继点，进入步骤(7)；其中，为中继点r_N-1+j的合力的大 小，ε₁为合力误差；

(7)求平衡后线性规划最优解步骤：构建平衡后完全图K^*＝(V^*，E^*， ω^*(u′v′))；其中，平衡后节点集合V^*＝T∪R^*，由N个终端点和M^*个调整 到平衡位置后的中继点构成，平衡后节点集合V^*中任意两节点u′和v′之间用 无向链路u′v′连接，u′v′∈E^*，E^*是指所有无向链路的集合；无向链路u′v′的 权值ω^*(u′v′)为两节点u′和v′之间的欧几里得距离；

基于平衡后完全图K^*，构建平衡后基于信息流的线性规划数学模型， 其目标函数为其约束条件包括信息流守恒条件、 信息流上限条件和非负条件；利用线性规划方法获取平衡后线性规划最优 解，输出平衡后的目标函数值平衡后各有向链路的信息传输速率 和总信息传输速率的数值；

其中，是指有向链路的权值，为两节点u′和v′之间的欧几里 得距离；A^*是指平衡后有向链路集合；表示从信源终端点t₀发送到 信宿终端点t_i的信息流在有向链路上的信息传输速率，1≤i≤N-1；

判断是否满足若是，则将平衡后的目标函数值作为平衡后 最小代价值CI^*；

若否，则判断是否满足0≤CI－CI^*≤ε₂；若否，置p＝p+1，进入步骤(4)；

若是，则判断是否满足0≤CL^*－CI^*≤ε₃，若是，进入步骤(8)；若否， 则将上一轮平衡后获得的最小代价值CL^*作为平衡后最小代价值CI^*，并置 p＝p+1，进入步骤(4)；其中，ε₂是指第一代价误差，ε₃是指第二代价误差；

(8)Delaunay后处理步骤：查找以终端点t_k为公共顶点的任意两条链 路所形成的所有夹角；采用计算3个终端点的斯坦纳点的方法，获取形成 的夹角小于120°的三个顶点的斯坦纳点，存入增补斯坦纳点集合S’；

判断增补斯坦纳点集合S’是否为空集，若否，进入步骤(4)；若是， 表明找到具有最小代价的网络传输方式，则输出平衡后各有向链路的信 息传输速率和总信息传输速率的值、平衡后最小代价值CI^*， 以及当前最优中继点集合R^*中的中继点坐标；其中， k为终端点计数器，0≤k≤N-1。

优选的，上述步骤(2)的Delaunay预处理步骤，包括如下子步骤：

(2.1)对于N个终端点，采用Delaunay三角剖分的方法获得至多(2N-5) 个Delaunay三角形；

(2.2)采用计算3个终端点的斯坦纳点的方法，获取每个Delaunay三 角形的斯坦纳点，将取得的所有斯坦纳点存入斯坦纳点集合S中；

(2.3)将每两个相邻的Delaunay三角形拼接成一个四边形，采用计算 4个终端点的斯坦纳点的方法，获取每个四边形的斯坦纳点；将取得的所有 斯坦纳点也存入斯坦纳点集合S中。

优选的，上述步骤(3)形成子矩形步骤，包括如下子步骤：

(3.1)置终端点计数器k＝0；

(3.2)判断是否满足k≤N-1；若是，进入子步骤(3.3)，若否，则 进入子步骤(3.5)；

(3.3)获取N个终端点坐标的横坐标的最小值XI、横坐标的最大值 XA、纵坐标的最小值YI和纵坐标的最大值YA，包括下述过程：

(3.3.1)判断是否满足XI>x_k，是则置XI＝x_k，然后进入(3.3.2)；否则 直接进入(3.3.2)；

(3.3.2)判断是否满足YI>y_k，是则置YI＝y_k，然后进入(3.3.3)；否则 直接进入(3.3.3)；

(3.3.3)判断是否满足XA<x_k，是则置XA＝x_k，然后进入(3.3.4)；否 则直接进入(3.3.4)；

(3.3.4)判断是否满足YA<y_k，是则置YA＝y_k，然后进入子步骤(3.4)； 否则直接进入子步骤(3.4)；

(3.4)置k＝k+1，并返回至子步骤(3.2)；

(3.5)清空终端点计数器，置k＝0；

(3.6)判断是否满足k≤N-1；若是，则进入子步骤(3.7)；若否， 则进入子步骤(3.9)；

(3.7)连接坐标为(XI，y_k)和(XA，y_k)的两点，形成横线段；连 接坐标为(x_k，YI)和(x_k，YA)的两点，形成纵线段；

(3.8)置k＝k+1，进入子步骤(3.6)；

(3.9)各横线段与纵线段形成子矩形；其中，(x_k，y_k)为终端点t_k的 坐标，置初始值XI＝+∞，XA＝-∞，YI＝+∞，YA＝-∞。

优选的，上述(4)的子矩形划分步骤，包括如下子步骤：

(4.1)将步骤(3)获得的各子矩形划分为p×p个矩形格子，获取每 个矩形格子对角线交点的坐标；

(4.2)采用点的定位方法，找到位于所述凸包及其内的所有矩形格子 对角线交点，将上述交点作为候选的中继点，存入中继点集合R；

(4.3)构建完全图K＝(V，E，ω(uv))，节点集合V＝T∪S∪S’∪R ∪R^*，包括N＝|T|个终端点和M＝|S∪S’∪R∪R^*|个候选的中继点r_N-1+m，其 中r_N-1+m的坐标为(x_N-1+m，y_N-1+m)，m为平衡前中继点计数器；1≤m≤M；

其中，节点集合V中任意两节点u和v之间用无向链路uv连接，uv∈E， E是指所有无向链路的集合；无向链路uv的权值ω(uv)为两节点u与v之间的 欧几里得距离；T是指由N个终端点构成的终端点集合；S是指斯坦纳点集 合；S’是指增补斯坦纳点集合；R是指候选中继点集合；R^*是指当前最优中 继点集合；置初始值S’和R^*为空集。

优选的，步骤(5)的求平衡前线性规划最优解步骤，包括如下子步骤：

(5.1)基于步骤(4)获得的完全图K，构建平衡前基于信息流的线 性规划数学模型，包括目标函数与约束条件；

目标函数为目标函数为其中，有向链路集合 决策变量为完全图K中有向链路的总信 息传输速率决策变量的系数

约束条件包括信息流守恒条件、信息流上限条件和非负条件：

信息流守恒条件：

信息流上限条件：

非负条件：

(5.2)利用线性规划方法获取所述平衡前基于信息流的线性规划数学 模型的最优解，输出所述平衡前基于信息流的线性规划数学模型的目标函 数值C_p；输出各有向链路的信息传输速率和总信息传输速率的 值以及各无向链路uv的总信息传输速率f(uv)的值；其中，

(5.3)判断目标函数值是否满足C_p<CI；若是，则将目标函数值C_p作 为平衡前最小代价值CI，进入子步骤(5.4)；若否，则直接进入子步骤(5.4)；

(5.4)判断所有中继点的所有邻接无向链路的总信息传输速率是否全 为零；若是，则置当前最优中继点集合R^*为空集，进入步骤(7)；若否， 则进入子步骤(5.5)；

(5.5)针对中继点的邻接无向链路的总信息传输速率不全为零的中继 点，判断是否其中2个以上中继点在一条线段上；若是，则仅保留处于该 线段端点位置的2个中继点，进入子步骤(5.6)；若否，则直接进入子步 骤(5.6)；

(5.6)查找满足“其所有邻接无向链路的总信息传输速率不全为零” 的中继点，并将满足所述条件的所有中继点存入当前最优中继点集合R^*， 所述当前最优中继点集合的大小为M^*，记为M^*＝|R^*|；

其中，1≤i≤N-1；u,v,t₀,t_i∈V，V_←(u)表示始节点为u的 所有有向链路终节点的集合，V_→(u)表示终节点为u的所有有向链路始节点 的集合；表示从信源终端点t₀发送到信宿终端点t_i的信息流在有向链路 上的信息传输速率；为有向链路上的总信息传输速率，其等于有 向链路上所有的最大值；表示从信源终端点t₀发送到信宿终端 点t_i的信息流在有向链路上的信息传输速率；h为信源发出的总信息传输 速率，h>0；置初始值CI＝+∞。

优选的，步骤(6)的调整中继点到平衡位置步骤，包括如下子步骤：

(6.1)置回数计数器RD＝1；

(6.2)置中继点变量j＝1，置平衡计数器BL＝0；

(6.3)采用向量加法计算中继点r_N-1+j的合力其 中，为沿邻接有向链路方向的力，的大小

(6.4)判断是否满足若是，则置BL＝BL+1，进入子步骤 (6.5)；若否，则将中继点r_N-1+j沿其合力的方向移动距离 Δ＝1/(2×RD+3)，置再进入子步骤(6.5)；其中， 为中继点r_N-1+j的合力的大小，ε₁为合力误差；

(6.5)置j＝j+1，判断是否满足j≤M^*；若是，则进入子步骤(6.3)； 若否，则进入子步骤(6.6)；

(6.6)判断是否满足BL＝M^*，若是，则表明所有中继点调整到平衡位 置，将当前最优中继节点集合R^*更新为所有调整到平衡位置的中继点，进 入步骤(7)；若否，则置RD＝RD+1，进入子步骤(6.2)。

优选的，步骤(7)的求平衡后线性规划最优解步骤，包括如下子步骤：

(7.1)构建平衡后完全图K^*＝(V^*，E^*，ω^*(u′v′))，节点集合V^*＝T∪R^*， 包括N个终端点和M^*个调整到平衡位置后的中继点，节点集合V^*中任意 两节点u′和v′之间用无向链路u′v′连接，u′v′∈E^*；

(7.2)基于所述平衡后完全图K^*，构建平衡后基于信息流的线性规划 数学模型，该模型由目标函数和约束条件构成；

目标函数为其中，有向链路集合 决策变量为完全图K^*中有向链路的总信息传输速率决策变量的系数

约束条件包括信息流守恒条件、信息流上限条件和非负条件：

信息流守恒条件：

信息流上限条件：

非负条件：

(7.3)利用线性规划方法获取平衡后基于信息流的线性规划数学模型 的最优解，输出平衡后的目标函数值输出各有向链路的信息传输速 率和总信息传输速率的值；

(7.4)判断所述平衡后的目标函数值是否满足若是，则置 平衡后最小代价值进入子步骤(7.5)；若否，则直接进入子步骤 (7.5)；

(7.5)判断是否满足0≤CI－CI^*≤ε₂；若是，则进入子步骤(7.6)； 若否，则置p＝p+1，进入步骤(4)；

(7.6)判断是否满足0≤CL^*－CI^*≤ε₃；若是，则进入步骤(8)；若 否，则置上一轮平衡后最小代价值CL^*＝CI^*，置p＝p+1，进入步骤(4)；

其中，E^*是指所有无向链路的集合；无向链路u′v′的权值ω^*(u′v′)为节点 u′与v′之间的欧几里得距离；1≤i≤N-1；u′,v′,t₀,t_i∈V^*，指始节点为u′的所有有向链路终节点的集合，指终节点为u′的 所有有向链路始节点的集合；指从信源终端点t₀发送到信宿终端点t_i的信息流在有向链路上的信息传输速率；为有向链路上的总 信息传输速率，等于有向链路上所有的最大值；指从信 源终端点t₀发送到信宿终端点t_i的信息流在有向链路上的信息传输速率； h为信源发出的总信息传输速率，h>0；ε₂为第一代价误差，ε₃为第二代价 误差；置初始值CI^*＝+∞，CL^*＝+∞。

优选的，步骤(8)的Delaunay后处理步骤，包括如下子步骤：

(8.1)置终端点计数器k＝0；

(8.2)查找以终端点t_k为公共顶点的任意两条链路所形成的所有夹角；

(8.3)判断所述夹角是否小于120°；若是，则采用计算3个终端点 的斯坦纳点的方法，获取每组形成上述夹角的三个顶点的斯坦纳点；将获 得的所有斯坦纳点存入增补斯坦纳点集合S’中，进入子步骤(8.4)；若否， 则进入子步骤(8.4)；

(8.4)判断是否满足k＝N-1；若是，则进入子步骤(8.5)；若否， 则置k＝k+1，进入子步骤(8.2)；

(8.5)判断S’是否为空集；若是，表明找到具有最小代价的网络传输 方式，则输出CI^*、所有非零信息传输速率和非零总信息传输速率 的值，并输出当前最优中继点集合R^*中的中继点坐标；若否，则进 入步骤(4)；

优选的，上述合力误差ε₁满足0≤ε₁≤0.0001；ε₁越小，中继点的位置 越精确，但计算时间越长。

优选的，上述第一代价误差满足0≤ε₂≤0.0001，上述第二代价误差ε₃满 足0≤ε₃≤0.0001；ε₂和ε₃越小，和越精确，但计算时间越长。

通过上述的步骤(1)获取终端点的凸包；通过步骤(2)采用Delaunay 三角剖分得到Delaunay三角形，然后获取所有Delaunay三角形的斯坦纳点 和所有两个相邻Delaunay三角形所构成四边形的斯坦纳点；通过步骤(3) 和步骤(4)将凸包进行非均匀划分得到候选的中继点：步骤(3)获取终 端点的子矩形，步骤(4)对每个子矩形进一步划分为p×p个矩形格子， 取在凸包上和凸包内的矩形格子的对角线交点作为候选的中继点；对终端 点、斯坦纳点、候选中继点、增补斯坦纳点和当前最优中继点构建完全图； 通过步骤(5)构建平衡前基于信息流的线性规划数学模型，求平衡前线性 规划最优解，输出各有向链路的信息传输速率和总信息传输速率的数值，以及平衡前最小代价值CI；通过步骤(6)将所有当前最优中继点 的位置调整到合力为零的平衡位置，从而进一步降低代价；通过步骤(7) 构建平衡后基于信息流的线性规划数学模型，获取平衡后线性规划最优解， 输出各有向链路的信息传输速率和总信息传输速率的数值， 以及平衡后最小代价值CI^*，并将当前CI^*保存至上一轮平衡后最小代价值 CL^*；若不满足0≤CI-CI^*≤ε₂，则置p＝p+1后重新执行步骤(4)；若不 满足0≤CL^*-CI^*≤ε₃，则置p＝p+1后重新执行步骤(4)；直至满足前述 两个不等式之后进入步骤(8)；通过步骤(8)计算增补斯坦纳点作为候选 的中继点存入增补斯坦纳点集合S’中，若S’不为空集则重新执行步骤(4)； 若S’为空集则输出各有向链路的信息传输速率和总信息传输速率 的数值，以及平衡后最小代价值CI^*，并输出当前最优中继点集合R^*中的中继点坐标。

总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够 取得下列有益效果：

1、本发明提供的网络传输方法，采用步骤(2)Delaunay预处理方法 计算得到任意3个和4个终端点的所有可能斯坦纳点；采用步骤(8)Delaunay 后处理方法，并通过与步骤(5)线性规划方法和步骤(6)调整平衡方法 相结合，计算得到任意大于等于5个终端点的所有可能斯坦纳点，其中步 骤(6)中采用调整中继点到平衡位置的方法微调中继点的位置以进一步减 少代价。由于采用上述Delaunay预处理方法和Delaunay后处理方法，解决 现有技术中仅基于非均匀划分的空间网络编码方法中，当中继点与终端点 存在非均匀密度分布时求线性规划最优解时计算量变大的问题。

2、本发明提供的网络传输方法，将步骤(2)和(8)的Delaunay方法 与步骤(3)和(4)的非均匀划分相结合，不仅可以解决终端点与终端点 存在非均匀密度分布时造成的求线性规划最优解的计算量变大的问题，而 且可以解决中继点与终端点存在非均匀密度分布时造成的求线性规划最优 解的计算量变大的问题；在步骤(5)中求解当前一轮线性规划最优解时加 入上一轮求平衡后线性规划最优解所得的最优结果，可以进一步加快找到 最优解的迭代速度；综合前述所有步骤，本发明提供的基于Delaunay三角 剖分的空间网络编码的网络传输方案，其代价不高于采用空间路由的网络 传输方案，且复杂度低于采用空间路由的网络传输方案，从而有效提升网 络传输的总体性能。

附图说明

图1是本发明提供的网络传输方法的流程示意图；

图2是Delaunay预处理步骤的流程示意图；

图3是形成子矩形步骤的流程示意图；

图4是子矩形划分步骤的流程示意图；

图5是求平衡前线性规划最优解步骤的流程示意图；

图6是调整中继点到平衡位置步骤的流程示意图；

图7是求平衡后线性规划最优解步骤的流程示意图；

图8是Delaunay后处理步骤的流程示意图；

图9是本发明实施例采用本发明提供的网络传输方法获得的结果。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图 及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的 本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可 以相互组合。

本发明所提供的一种采用基于Delaunay三角剖分的空间网络编码的网 络传输方法，其流程如图1所示，包括初始化步骤、Delaunay预处理步骤、 形成子矩形步骤、子矩形划分步骤、求平衡前线性规划最优解步骤、调整 中继点到平衡位置步骤、求平衡后线性规划最优解步骤和Delaunay后处理 步骤；以下结合实施例具体阐述；

实施例用于包含N＝5个终端点的传输网络，终端点的坐标分别为 (0.5415756，0.4475305)、(0.1177682，0.4999264)、(0.2681085，0.3512345)、 (0.6861621，0.0972497)和(0.9908014，0.3454797)；其中(0.5415756， 0.4475305)为信源终端点的坐标，网络传输目标是信源终端点以最小代价 传输消息给其余4个信宿终端点；实施例提供的网络传输方法，具体如下：

(1)初始化步骤：计算N＝5个终端点t₀，t₁，t₂，t₃和t₄的凸包，得 到包含各终端点的最小凸多边形的各条边，分别为 t₀t₁，t₁t₂，t₂t₃，t₃t₄和t₄t₀；终端点t₀，t₁，t₂，t₃和t₄的横坐标和纵坐标 分别记为(x₀，y₀)＝(0.5415756，0.4475305)、(x₁，y₁)＝(0.1177682， 0.4999264)、(x₂，y₂)＝(0.2681085，0.3512345)、(x₃，y₃)＝(0.6861621， 0.0972497)和(x₄，y₄)＝(0.9908014，0.3454797)，其中(x₀，y₀)为信 源终端点t₀的坐标。

(2)Delaunay预处理步骤，包括如下子步骤：

(2.1)对于N＝5个终端点，采用Delaunay三角剖分的方法获得3个 Delaunay三角形，分别为Δt₀t₁t₂，Δt₀t₂t₃和Δt₀t₃t₄；

(2.2)采用计算3个终端点的斯坦纳点的方法，计算每个Delaunay三 角形的斯坦纳点，分别为(0.2702552840，0.3610615245)、(0.5029388856， 0.3680102729)和(0.7281646053，0.2689202192)，将计算出的所有斯坦纳 点存入斯坦纳点集合S中；

(2.3)将每两个相邻的Delaunay三角形拼接成一个四边形，分别为四 边形t₀t₁t₂t₃和t₀t₂t₃t₄；采用计算4个终端点的斯坦纳点的方法，获取每个 四边形的斯坦纳点，其中，四边形t₀t₁t₂t₃的斯坦纳点为(0.5029388856， 0.3680102729)，四边形t₀t₂t₃t₄的斯坦纳点为(0.5386773638，0.4348096122) 和(0.7239365626，0.2630487122)；将计算出的所有斯坦纳点，合并入斯 坦纳点集合S中，删除具有相同坐标的点(0.5029388856，0.3680102729)， 故合并之后集合S中的斯坦纳点为(0.2702552840，0.3610615245)、 (0.5029388856，0.3680102729)、(0.7281646053，0.2689202192)、 (0.5386773638，0.4348096122)和(0.7239365626，0.2630487122)；

(3)形成子矩形步骤，包括如下子步骤：

(3.1)置终端点计数器k＝0；更新XI、XA、YI和YA的值，分别为 XI＝0.5415756，XA＝0.5415756，YI＝0.4475305，YA＝0.4475305；

(3.2)置k＝k+1＝1，更新XI、XA、YI和YA的值，分别为XI＝0.1177682， XA＝0.5415756，YI＝0.4475305，YA＝0.4999264；

(3.3)置k＝k+1＝2，更新XI、XA、YI和YA的值，分别为XI＝0.1177682， XA＝0.5415756，YI＝0.3512345，YA＝0.4999264；

(3.4)置k＝k+1＝3，更新XI、XA、YI和YA值，分别为XI＝0.1177682， XA＝0.6861621，YI＝0.0972497，YA＝0.4999264；

(3.5)置k＝k+1＝4，更新XI、XA、YI和YA的值，分别为XI＝0.1177682， XA＝0.9908014，YI＝0.0972497，YA＝0.4999264；

(3.6)置k＝k+1＝5；由于不满足k≤4，则将终端点计数器清零，置k＝0； 并连接坐标为(XI，y₀)＝(0.1177682，0.4475305)和(XA，y₀)＝(0.9908014， 0.4475305)的两点，形成横线段；连接坐标为(x₀，YI)＝(0.5415756， 0.0972497)和(x₀，YA)＝(0.5415756，0.4999264)的两点，形成纵线段；

(3.7)置k＝k+1＝1，连接坐标为(XI，y₁)＝(0.1177682，0.4999264) 和(XA，y₁)＝(0.9908014，0.4999264)的两点，形成横线段；连接坐标 为(x₁，YI)＝(0.1177682，0.0972497)和(x₁，YA)＝(0.1177682，0.4999264) 的两点，形成纵线段；

(3.8)置k＝k+1＝2，连接坐标为(XI，y₂)＝(0.1177682，0.3512345) 和(XA，y₂)＝(0.9908014，0.3512345)的两点，形成横线段；连接坐标 为(x₂，YI)＝(0.2681085，0.0972497)和(x₂，YA)＝(0.2681085，0.4999264) 的两点，形成纵线段；

(3.9)置k＝k+1＝3，连接坐标为(XI，y₃)＝(0.1177682，0.0972497) 和(XA，y₃)＝(0.9908014，0.0972497)的两点，形成横线段；连接坐标 为(x₃，YI)＝(0.6861621，0.0972497)和(x₃，YA)＝(0.6861621，0.4999264) 的两点，形成纵线段；

(3.10)置k＝k+1＝4，连接坐标为(XI，y₄)＝(0.1177682，0.3454797) 和(XA，y₄)＝(0.9908014，0.3454797)的两点，形成横线段；连接坐标 为(x₄，YI)＝(0.9908014，0.0972497)和(x₄，YA)＝(0.9908014，0.4999264) 的两点，形成纵线段；

(3.11)各横线段与纵线段形成子矩形；

(4)子矩形划分步骤，包括如下子步骤：

(4.1)将各子矩形均划分为p×p＝2×2个矩形格子，获取每个矩形格 子对角线交点的坐标，分别为(0.1553533,0.1593072)、(0.1553533, 0.2834222)、(0.2305234,0.1593072)等64个点；

(4.2)采用点的定位方法，获取位于所述凸包及其内的所有矩形格子 对角线交点，分别为(0.2305234,0.4234565)、(0.1553533,0.4868274)、 (0.2305234,0.4606295)等31个点，将它们作为候选的中继点，存入中继 点集合R；

(4.3)构建完全图K＝(V，E，ω(uv))，节点集合V＝T∪S∪S’∪R ∪R^*，包括N＝|T|＝5个终端点和M＝|S∪S’∪R∪R^*|＝31+5＝36个候选的中继 点r_4+m，其中r_4+m的坐标为(x_4+m，y_4+m)，1≤m≤36；节点集合V中任意 两节点u和v之间用无向链路uv连接，uv∈E；E是所有无向链路的集合；无 向链路uv的权值ω(uv)为两节点u和v之间的欧几里得距离；

(5)求平衡前线性规划最优解步骤，包括如下子步骤：

(5.1)基于上述完全图K，构建平衡前基于信息流的线性规划数学模 型；包括目标函数与约束条件；

(5.1.1)目标函数为其中，有向链路集合 决策变量为完全图K中有向链路的总信 息传输速率决策变量的系数

(5.1.2)约束条件包括信息流守恒条件、信息流上限条件和非负条件：

信息流守恒条件：

信息流上限条件：

非负条件：

其中，1≤i≤4；u,v,t₀,t_i∈V，V_←(u)指始节点为u的所有 有向链路终节点的集合，V_→(u)表示终节点为u的所有有向链路始节点的集 合；表示从信源终端点t₀发送到信宿终端点t_i的信息流在有向链路上的信息传输速率；为有向链路上的总信息传输速率，其等于有向 链路上所有的最大值；表示从信源终端点t₀发送到信宿终端点 t_i的信息流在有向链路上的信息传输速率；h为信源发出的总信息传输速 率，置h归一化为1；

(5.2)利用线性规划方法求所述平衡前基于信息流的线性规划数学模 型的最优解，输出所述平衡前基于信息流的线性规划数学模型的目标函数 值C_p＝1.209665387；输出各有向链路的信息传输速率非零数值分 别为和 输出各有向链路的总信息传输速率非零数 值分别为和输 出各无向链路uv的总信息传输速率f(uv)，非零数值分别为 f(t₀r₃₆)＝f(r₃₆t₁)＝f(r₃₆t₂)＝1和f(t₀r₃₈)＝f(r₃₈t₃)＝f(r₃₈t₄)＝1；

(5.3)目标函数值C_p满足C_p<CI，置平衡前最小代价值 CI＝C_p＝1.209665387，进入子步骤(5.4)；

(5.4)由于所有中继点的所有邻接无向链路的总信息传输速率不全为 零，故针对中继点的邻接无向链路的总信息传输速率不全为零的中继点， 不满足2个以上中继点在一条线段上，进入子步骤(5.5)；

(5.5)查找其所有邻接无向链路的总信息传输速率不全为零的中继点， 并将这些中继点存入当前最优中继点集合R^*，包括(0.2702552840， 0.3610615245)和(0.7281646053，0.2689202192)，其大小为M^*，记为 M^*＝|R^*|＝2，进入步骤(6)；

(6)调整中继点到平衡位置步骤，对R^*的两个点进行微调；包括如下 子步骤：

(6.1)置回数计数器RD＝1；

(6.2)置中继点变量j＝1，置平衡计数器BL＝0；

(6.3)采用向量加法计算中继点r₅(其坐标为(0.2702552840， 0.3610615245))的合力其中，为沿邻接有向链路方 向的力，的大小

(6.4)满足置BL＝BL+1＝1，进入子步骤(6.5)；其中，为中 继点r₅的合力的大小，取合力误差ε₁＝0.0001；

(6.5)置j＝j+1＝2，满足j≤M*＝2，采用向量加法计算中继点r₆(其坐 标为(0.7281646053，0.2689202192))的合力其中，为 沿邻接有向链路方向的力，的大小

(6.6)满足置BL＝BL+1＝2，进入子步骤(6.7)；其中，为中 继点r₆的合力的大小；

(6.7)置j＝j+1＝3，不满足j≤M^*＝2，但满足BL＝M^*＝2，表明所有中 继点调整到平衡位置，将当前最优中继节点集合R^*更新为所有调整到平衡 位置的中继点，分别为(0.2702552840，0.3610615245)和(0.7281646053， 0.2689202192)，进入步骤(7)；

(7)求平衡后线性规划最优解步骤，包括如下子步骤：

(7.1)构建平衡后完全图K^*＝(V^*，E^*，ω^*(u′v′))；节点集合V^*＝T∪ R^*，包括N＝5个终端点和M^*＝2个调整到平衡位置后的中继点；

(7.2)基于上述平衡后完全图K^*，构建平衡后基于信息流的线性规划 数学模型：包括目标函数与约束条件；

(7.2.1)目标函数为其中，有向链路集 合决策变量为完全图K^*中有向链路的总信息传输速率决策变量的系数

(7.2.2)约束条件包括信息流守恒条件、信息流上限条件和非负条件：

信息流守恒条件：

信息流上限条件：

非负条件：

其中，1≤i≤4；u′,v′,t₀,t_i∈V^*，表示始节点为 u′的所有有向链路终节点的集合，表示终节点为u′的所有有向链路始 节点的集合；表示从信源终端点t₀发送到信宿终端点t_i的信息流在有 向链路上的信息传输速率；为有向链路上的总信息传输速率， 等于有向链路上所有的最大值；表示从信源终端点t₀发送 到信宿终端点t_i的信息流在有向链路上的信息传输速率；h为信源发出 的总信息传输速率，置h归一化为1；

(7.3)利用线性规划方法求所述平衡后基于信息流的线性规划数学模 型的最优解，输出所述平衡后基于信息流的线性规划数学模型的目标函数 值输出各有向链路的信息传输速率非零数值 分别为和 输出各有向链路的总信息传输速率非零数 值分别为和

(7.4)由于平衡后目标函数值满足置平衡后最小代价值 ${\mathrm{CI}}^{*}=C_p^{*}=1.209665387,$转子步骤(7.5)；

(7.5)由于满足0≤CI－CI^*≤ε₂，进入子步骤(7.6)；

(7.6)由于不满足0≤CL^*－CI^*≤ε₃，置上一轮平衡后最小代价值 CL*＝CI*＝1.209665387和置p＝p+1＝3，进入步骤(8)再次进行划分；其中， 第一代价误差ε₂取0.00001，第二代价误差ε₃取0.00001；

(8)再次进行划分，包括如下子步骤：

(8.1)将约束矩形中的每个子矩形划分为p×p＝3×3个矩形格子，计 算每个矩形格子对角线交点的坐标，为(0.1428249,0.1386214)、(0.1428249, 0.2213647)、(0.1428249,0.3041080)等144个点；

(8.2)采用点的定位方法，找到位于所述凸包及其内的所有矩形格子 对角线交点，为(0.1929383,0.4314812)、(0.2430518,0.3993825)、(0.2430518, 0.4314812)等73个点，将这些交点作为候选的中继点，存入中继点集合R；

(8.3)构建完全图K＝(V，E，ω(uv))，节点集合V＝T∪S∪S’∪R ∪R^*，包括N＝|T|＝5个终端点和M＝|S∪S’∪R∪R^*|＝73+5＝78个候选的中继 点r_4+m，其中r_4+m的坐标为(x_4+m，y_4+m)，1≤m≤78；

(9)再次求平衡前线性规划最优解，包括如下子步骤：

(9.1)基于步骤(8.3)获得的完全图K，构建平衡前基于信息流的线 性规划数学模型；

(9.2)利用线性规划方法求所述平衡前基于信息流的线性规划数学模 型的最优解，输出所述平衡前基于信息流的线性规划数学模型的目标函数 值C_p＝1.209665387；输出各有向链路的信息传输速率非零数值分 别为和 输出各有向链路的总信息传输速率非零数 值分别为和输 出各无向链路uv的总信息传输速率f(uv)，非零数值分别为 f(t₀r₇₈)＝f(r₇₈t₁)＝f(r₇₈t₂)＝1和f(t₀r₈₀)＝f(r₈₀t₃)＝f(r₈₀t₄)＝1；

(9.3)由于平衡前目标函数值C_p满足C_p<CI，置平衡前最小代价值 CI＝C_p＝1.209665387，由于不满足所有中继点的所有邻接无向链路的总信息 传输速率全为零，进入(9.4)；

(9.4)针对中继点的邻接无向链路的总信息传输速率不全为零的中继 点，由于不满足其中2个以上中继点在一条线段上，进入子步骤(9.5)；

(9.5)查找满足其所有邻接无向链路的总信息传输速率不全为零的中 继点，并将这些中继点存入当前最优中继点集合R^*，包括(0.2702552840， 0.3610615245)和(0.7281646053，0.2689202192)，其大小为M^*，记为 M^*＝|R^*|＝2，进入步骤(10)；

(10)再次调整中继点到平衡位置，包括如下子步骤：

(10.1)置回数计数器RD＝1；置中继点变量j＝1，置平衡计数器BL＝0；

(10.2)采用向量加法获取当前最优中继点集合R^*中的中继点r₅(其坐 标为(0.2702552840，0.3610615245))的合力其中，为 沿邻接有向链路方向的力，的大小

(10.3)由于满足置BL＝BL+1＝1，置j＝j+1＝2；由于满足j ≤M^*＝2，采用向量加法计算当前最优中继点集合R^*中的中继点r₆(其坐标 为(0.7281646053，0.2689202192))的合力其中，为沿 邻接有向链路方向的力，的大小其中，为中继点 r₅的合力的大小，取合力误差ε₁＝0.00001；

(10.4)由于满足置BL＝BL+1＝2，置j＝j+1＝3；由于不满足j ≤M^*＝2，进入子步骤(10.5)；其中，为中继点r₆的合力的大小；

(10.5)由于满足BL＝M^*＝2，表明所有中继点调整到平衡位置，将当 前最优中继节点集合R^*更新为所有调整到平衡位置的中继点，分别为 (0.2702552840，0.3610615245)和(0.7281646053，0.2689202192)，进入 步骤(11)；

(11)再次求平衡后线性规划最优解，包括如下子步骤：

(11.1)构建完全图K^*＝(V^*，E^*，ω^*(u′v′))，节点集合V^*＝T∪R^*， 包括N＝5个终端点和M^*＝2个调整到平衡位置后的中继点；

(11.2)基于(11.1)获得的完全图K^*，构建平衡后基于信息流的线性 规划数学模型：

(11.3)利用线性规划方法求所述平衡后基于信息流的线性规划数学模 型的最优解，输出所述平衡后基于信息流的线性规划数学模型的目标函数 值输出各有向链路的信息传输速率非零数值 分别为和 输出各有向链路的总信息传输速率非零数 值分别为和

(11.4)由于平衡后目标函数值满足置平衡后最小代价值 ${\mathrm{CI}}^{*}=C_p^{*}=1.209665387,$进入子步骤(11.5)；

(11.5)由于满足0≤CI－CI^*≤ε₂，进入子步骤(11.6)；

(11.6)由于满足0≤CL^*－CI^*≤ε₃，进入步骤(12)；其中，第一代价 误差ε₂＝0.00001；第二代价误差ε₃＝0.00001；

(12)再次进行Delaunay后处理，包括如下子步骤：

(12.1)置终端点计数器k＝0；查找以终端点t₀为公共顶点的任意两条 链路所形成的所有夹角，即∠r₅t₀r₆；

(12.2)由于满足夹角∠r₅t₀r₆小于120°，故采用计算3个终端点的 斯坦纳点的方法，获取形成上述夹角的三个顶点的斯坦纳点，即 (0.5407003445，0.4437396571)，均存入增补斯坦纳点集合S’中，进入子 步骤(12.4)；

(12.4)由于不满足k＝N-1＝4，置k＝k+1＝1；由于不存在以终端点t₁为公共顶点的任意两条链路所形成的所有夹角，不满足夹角小于120°的条 件，进入步骤(12.5)；

(12.5)由于不满足k＝N-1＝4，置k＝k+1＝2；由于不存在以终端点t₂为公共顶点的任意两条链路所形成的所有夹角，不满足夹角小于120°，进 入子步骤(12.6)；

(12.6)由于不满足k＝N-1＝4，置k＝k+1＝3；由于不存在以终端点t₃为公共顶点的任意两条链路所形成的所有夹角，不满足夹角小于120°，进 入子步骤(12.7)；

(12.7)由于不满足k＝N-1＝4，置k＝k+1＝4；由于不存在以终端点t₄为公共顶点的任意两条链路所形成的所有夹角，不满足夹角小于120°，进 入子步骤(12.8)；

(12.8)由于满足k＝N-1＝4，但不满足S’为空集，进入步骤(13)， 再次进行子矩形划分；

(13)再次进行子矩形划分，包括如下子步骤：

(13.1)将每个子矩形划分为p×p＝3×3个矩形格子，获取每个矩形格 子对角线交点的坐标，为(0.1428249,0.1386214)、(0.1428249,0.2213647)、 (0.1428249,0.3041080)等144个点；

(13.2)采用点的定位方法，获取位于所述凸包及其内的所有矩形格子 对角线交点，为(0.1929383,0.4314812)、(0.2430518,0.3993825)、(0.2430518, 0.4314812)等73个点，将这些作为候选的中继点，存入中继点集合R；

(13.3)构建完全图K＝(V，E，ω(uv))，节点集合V＝T∪S∪S’∪R ∪R^*，包括N＝|T|＝5个终端点和M＝|S∪S’∪R∪R^*|＝73+5+1＝79个候选的中 继点r_4+m，其中r_4+m的坐标为(x_4+m，y_4+m)，1≤m≤79；进入步骤(14)；

(14)再次求平衡前线性规划最优解，包括如下子步骤：

(14.1)基于完全图步骤(13.3)获得的完全图K，构建平衡前基于信 息流的线性规划数学模型；

(14.2)利用线性规划方法求所述平衡前基于信息流的线性规划数学模 型的最优解，输出所述平衡前基于信息流的线性规划数学模型的目标函数 值C_p＝1.209623475；输出各有向链路的信息传输速率非零数值分 别为和输出 各有向链路的总信息传输速率非零数值分别为 和输 出各无向链路uv的总信息传输速率f(uv)，非零数值分别为 f(t₀r₈₃)＝f(r₈₃r₇₈)＝f(r₇₈t₁)＝f(r₇₈t₂)＝1和f(r₈₃r₇₉)＝f(r₇₉t₃)＝f(r₇₉t₄)＝1；

(14.3)由于平衡前目标函数值C_p满足C_p<CI，置平衡前最小代价值 CI＝C_p＝1.209623475，进入子步骤(14.4)；

(14.4)由于不满足所有中继点的所有邻接无向链路的总信息传输速率 全为零；针对中继点的邻接无向链路的总信息传输速率不全为零的中继点， 由于不满足其中2个以上中继点在一条线段上，进入子步骤(14.5)；

(14.5)查找满足其所有邻接无向链路的总信息传输速率不全为零的中 继点，并将这些中继点存入当前最优中继点集合R^*，包括(0.2702552840， 0.3610615245)、(0.7281646053，0.2689202192)和(0.5407003445， 0.4437396571)，其大小为M^*＝|R^*|＝3，进入步骤(15)，进一步调整中继点；

(15)进一步调整中继点到平衡位置，包括如下子步骤：

(15.1)置回数计数器RD＝1；置中继点变量j＝1，置平衡计数器BL＝0； 采用向量加法计算当前最优中继点集合R^*中的中继点r₅(其坐标为 (0.2702552840，0.3610615245))的合力其中，为沿邻 接有向链路方向的力，的大小

(15.2)由于不满足将中继点r₅其合力的方向移动距离 Δ＝1/(2×RD+3)＝0.2，置再进入子步骤(15.3)；其中， 为中继点r₅的合力的大小，合力误差ε₁＝0.00001；

(15.3)置j＝j+1＝2，满足j≤M^*＝3，采用向量加法计算当前最优中继 点集合R^*中的中继点r₆(其坐标为(0.7281646053，0.2689202192))的合 力其中，为沿邻接有向链路方向的力，的大小

(15.4)由于不满足将中继点r₆其合力的方向移动距离 Δ＝1/(2×RD+3)＝0.2，置再进入子步骤(15.5)；其中， 为中继点r₆的合力的大小；

(15.5)置j＝j+1＝3，满足j≤M^*＝3，采用向量加法计算当前最优中继 点集合R^*中的中继点r₇(其坐标为(0.5407003445，0.4437396571))的合 力其中，为沿邻接有向链路方向的力，的大小

(15.6)由于不满足将中继点r₇其合力的方向移动距离 Δ＝1/(2×RD+3)＝0.2，置再进入子步骤(15.7)；其中， 为中继点r₇的合力的大小；

(15.7)置j＝j+1＝4，不满足j≤M^*＝3；且不满足BL＝M^*＝3；置RD＝RD+1， 进入子步骤(15.1)；多次执行子步骤(15.1)～(16.6)，中继点r₅、r₆和r₇分 别移动到新的位置，坐标分别更新为(0.2695887762，0.3575665531)、 (0.7254109975，0.2651414093)和(0.5396563548，0.4393207063)；进入 步骤(16)，进一步求平衡后线性规划最优解；

(16)求平衡后线性规划最优解，包括如下子步骤：

(16.1)构建平衡后完全图K^*＝(V^*，E^*，ω^*(u′v′))，节点集合V^*＝T ∪R^*，包括N＝5个终端点和M^*＝3个调整到平衡位置后的中继点构成；

(16.2)基于(16.2)获得的平衡后完全图K^*，构建平衡后基于信息流 的线性规划数学模型：

(16.3)利用线性规划方法求所述平衡后基于信息流的线性规划数学模 型的最优解，输出所述平衡后基于信息流的线性规划数学模型的目标函数 值输出各有向链路的信息传输速率非零数值 分别为和输出各有向链 路的总信息传输速率非零数值分别为 和

(16.4)由于平衡后目标函数值满足置平衡后最小代价值 ${\mathrm{CI}}^{*}=C_p^{*}=1.209574564,$进入子步骤(16.5)；

(16.5)由于不满足0≤CI－CI^*≤ε₂，置p＝p+1＝4，进入步骤(4)；

执行步骤(4)～步骤(7)，获得平衡前线性规划最优解CI＝1.209574564； 平衡后最小代价值CI^*＝1.209574564；

(16.6)由于满足0≤CL^*－CI^*≤ε₃，进入步骤(17)；

(17)进行Delaunay后处理，获得的S’为空集，表明找到具有最小代 价的网络传输方式，输出CI^*＝1.209574564；输出所有非零信息传输速率 的数值，分别为和 输出所有非零总信息传输速率的数值， 分别为和输出 当前最优中继点集合R^*中的中继点坐标，分别为(0.2695887762， 0.3575665531)、(0.7254109975，0.2651414093)和(0.5396563548， 0.4393207063)；采用实施例的网络传输方法获得的结果如图9所示。

在该实施例中存在中继点与终端点密度分布不均匀(中继点r₅离终端点 t₂很近、中继点r₇离终端点t₀很近)，若仅采用现有技术中基于非均匀划分 的空间网络编码方法，需要采用较大的划分参数p才能得到有效的候选的 中继点，但当p增大时，求线性规划最优解时的计算量将以p的四次方形 式的增加。由于本发明方法中采用Delaunay预处理和后处理的方法，使得 在划分p较小时即能快速找到最优解，由此可见，本发明有效降低了计算 量，加快了收敛速度，从而有效提升网络传输性能。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已， 并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等 同替换和改进等，均应包含在本发明的保护范围之内。