| 主权项 |
1.一种采用空间网络编码的网络传输方法，适用于包含N+1个终端点的传输网络，N为正整数，包括初始化步骤、形成约束矩形步骤、划分步骤、求平衡前线性规划最优解步骤、调整中继点到平衡位置步骤和求平衡后线性规划最优解步骤，其特征在于：(1)初始化步骤：计算N+1个终端点t<sub>n</sub>的凸包，得到包含各终端点的最小凸多边形的各条边；(2)形成约束矩形步骤：计算N+1个终端点t<sub>n</sub>的最小横坐标值XI、最小纵坐标值YI、最大横坐标值XA和最大纵坐标值YA；对于N+1个终端点的每个坐标(x<sub>k</sub>，y<sub>k</sub>)，0≤k≤N，连接坐标分别为(x<sub>k</sub>，YI)和(x<sub>k</sub>，YA)的两点，形成纵线段；连接坐标分别为(XI，y<sub>k</sub>)和(XA，y<sub>k</sub>)的两点，形成横线段；各条纵线段和横线段所形成的最大矩形为约束矩形，约束矩形中包含若干子矩形，转步骤(3)；(3)划分步骤：将约束矩形中的每个子矩形划分为p×p个矩形格子，找到位于所述凸包及其内的所有矩形格子对角线交点，将它们作为中继点r<sub>N+j</sub>，1≤j≤M，M为中继点的个数；构建完全图K<sub>N+1+M</sub>＝(V，E，ω(uv))，节点集合V由N+1个终端点和M个中继点构成，节点集合V中任意两节点u和v之间用无向链路uv连接，uv∈E，E表示所有无向链路的集合；无向链路uv的权值ω(uv)为两节点u和v之间的欧几里得距离；(4)求平衡前线性规划最优解步骤：基于完全图K<sub>N+1+M</sub>，构建平衡前基于信息流的线性规划数学模型，由目标函数和约束条件构成：目标函数<img file="FDA00003472564400011.GIF" wi="591" he="72" />约束条件包括信息流守恒条件、信息流上限条件和非负条件；利用线性规划方法求所述平衡前基于信息流的线性规划数学模型的最优解，输出所述平衡前基于信息流的线性规划数学模型的目标函数值C<sub>p</sub>及各有向链路<img file="FDA00003472564400012.GIF" wi="66" he="52" />的信息传输速率<img file="FDA00003472564400013.GIF" wi="140" he="63" />和总信息传输速率<img file="FDA00003472564400014.GIF" wi="124" he="64" />的数值；将目标函数值C<sub>p</sub>的最小值置于平衡前最小代价值CI；若所有中继点r<sub>N+j</sub>的所有邻接无向链路r<sub>N+j</sub>v(v∈V)的总信息传输速率<img file="FDA00003472564400021.GIF" wi="737" he="78" />全为零，置中继点计数变量Z＝Z+1，且若Z＞ZA，表明无中继点，输出CI、PI以及其相应的非零信息传输速率<img file="FDA00003472564400022.GIF" wi="140" he="63" />和非零总信息传输速率<img file="FDA00003472564400023.GIF" wi="124" he="64" />的数值，结束；若Z≤ZA，表明存在中继点，置p＝p+1，转步骤(3)；若所有中继点r<sub>N+j</sub>的所有邻接无向链路r<sub>N+j</sub>v(v∈V)的总信息传输速率<img file="FDA00003472564400024.GIF" wi="736" he="78" />不全为零，转步骤(5)；(5)调整中继点到平衡位置步骤：置回数计数器RD＝1；采用向量加法计算每个中继点r<sub>N+j</sub>的合力<img file="FDA00003472564400025.GIF" wi="489" he="90" />其中<img file="FDA00003472564400026.GIF" wi="145" he="90" />为沿邻接有向链路<img file="FDA00003472564400027.GIF" wi="135" he="72" />方向的力，<img file="FDA00003472564400028.GIF" wi="146" he="90" />的大小<img file="FDA00003472564400029.GIF" wi="468" he="90" />若存在某中继点r<sub>N+j</sub>的合力<img file="FDA000034725644000210.GIF" wi="116" he="89" />的大小<img file="FDA000034725644000211.GIF" wi="278" he="89" />将该中继点r<sub>N+j</sub>沿其合力<img file="FDA000034725644000212.GIF" wi="116" he="89" />的方向移动距离Δ＝1/(2×RD+3)，置<img file="FDA000034725644000213.GIF" wi="488" he="89" />若经过一轮位置调整后，仍不满足所有中继点<img file="FDA000034725644000214.GIF" wi="279" he="89" />置RD＝RD+1，进行下一轮调整，直至满足所有中继点<img file="FDA000034725644000215.GIF" wi="279" he="89" />再转步骤(6)；其中，0≤合力误差ε<sub>1</sub>≤0.0001；ε<sub>1</sub>越小，中继点的位置越精确，但计算时间越长；(6)求平衡后线性规划最优解步骤：构建完全图<img file="FDA000034725644000216.GIF" wi="655" he="72" />节点集合V<sup>*</sup>由N+1个终端点和M个调整到平衡位置后的中继点构成，节点集合V<sup>*</sup>中任意两节点u′和v′之间用无向链路u′v′连接，u′v′∈E<sup>*</sup>，E<sup>*</sup>表示所有无向链路的集合；无向链路u′v′的权值ω<sup>*</sup>(u′v′)为两节点u′和v′之间的欧几里得距离；基于完全图<img file="FDA000034725644000217.GIF" wi="213" he="62" />构建平衡后基于信息流的线性规划数学模型，由目标函数和约束条件构成：目标函数<img file="FDA000034725644000218.GIF" wi="743" he="87" />约束条件包括信息流守恒条件、信息流上限条件和非负条件；利用线性规划方法求所述平衡后基于信息流的线性规划数学模型的最优解，输出所述平衡后基于信息流的线性规划数学模型的目标函数值<img file="FDA000034725644000219.GIF" wi="59" he="67" />及各有向链路<img file="FDA000034725644000220.GIF" wi="104" he="63" />的信息传输速率<img file="FDA000034725644000221.GIF" wi="182" he="82" />和总信息传输速率<img file="FDA000034725644000222.GIF" wi="163" he="76" />的数值；将目标函数值<img file="FDA000034725644000223.GIF" wi="58" he="68" />的最小值置于平衡后最小代价值CI<sup>*</sup>；针对中继点的邻接无向链路的总信息传输速率不全为零的中继点，若其中2个以上中继点在一条线段上，则仅保留处于该线段两个端点位置的2个中继点，删除处于该线段上的其它中继点；若0≤CI-CI<sup>*</sup>≤ε<sub>2</sub>，则表明找到具有最小代价的网络传输方式，输出CI<sup>*</sup>和PI及其所有非零信息传输速率<img file="FDA00003472564400031.GIF" wi="182" he="81" />和非零总信息传输速率<img file="FDA00003472564400032.GIF" wi="163" he="75" />的数值；输出满足下述条件的中继点坐标：这些中继点的邻接无向链路的总信息传输速率不全为零，结束；否则置p＝p+1，转步骤(3)；其中，0≤合力误差ε<sub>1</sub>≤0.0001；ε<sub>1</sub>越小，中继点的位置越精确，但计算时间越长。 |
