创建单核共享组播树的方法

摘要

本发明涉及一种创建单核共享组播树的方法，包括：计算虚拟卫星星座拓扑中一个组播组的所有卫星成员节点的虚拟卫星位置的平均值，通过该平均值计算出与所述平均值最接近的虚拟卫星位置，即核位置；进行数据初始化，即以所述核位置作为初始位置点，计算初始位置点与各个目的地成员节点之间的最短路径及所述最短路径的跳数，选择其中跳数最少的路径作为第一组播路径，将所述组播路径上的卫星节点作为第一节点集即第一核心群。本发明解决了低轨卫星网络中典型方法的信道资源严重浪费问题，使用本发明生成的组播树链路重用率高，所用信道资源少，且选核方法简单、高效，适用于星上资源稀缺的低轨卫星网络。

说明书

技术领域

本发明涉及一种组播通信的方法，特别是一种适于低轨卫星网络的创建单核共享组播树的方法。

背景技术

近年来多媒体通信和分布式环境中协同工作等应用的出现促使了一种新的通信模式——组播(multicast)的发展。例如视频会议、文件发布、CSCW、分布交互式仿真等，都需要组播来有效支持。

组播不同于广播和单播。通过广播机制发送的信息会被通信范围内的所有节点接收到，尽管其中某些节点可能并不需要这些信息；广播本身没有筛选和过滤机制，相对没有安全保障，安全级别高的信息不适合通过广播发送。单播即点到点的通信，若一个节点需要向N个目的节点发送信息，它必须分别依次发送这些信息到每个目的节点，共需要发送N次。组播是介于广播和单播之间的一种信息传输机制，分组从源(发送者)发送给一组确定的接收者，这些分组只在分支节点(branch node)处被复制，在每条链路上只转发一次，从而最大程度地利用了网络传输带宽资源，不需要向每个目的地分别单独发送，也避免了广播的资源浪费和安全性差的问题，适合一对多(one-to-many)和多对多(many-to-many)的通信。

组播路由(multicast routing)即如何确定源节点和目的节点之间具体的转发路径，是组播技术中的一个重要问题。组播组成员之间信息转发的所有连接路径通常称为组播分发树，简称组播树。组播算法的基本问题是找到一棵代价低的组播树，即如何尽量共享传输路径，称为组播树或组播路径的创建问题。组播树一般分为两类：一类是基于源(source-based)的组播树，每个源节点以自己为根生成一棵源组播树，如果一个组有N个源节点，那么这个组需要生成N棵源树，即源树的数目会随着组播组内源的数目成比例增长，它的时延性能较好，但可扩展性(scalability)较差；另一类是基于核的共享树(core-based shared tree)，简称核共享树，以组播组中某个或某几个成员节点为根(称为核)，生成一棵由组内所有成员节点共享的组播树，具有良好的代价性能和可扩展性，可以节约系统资源。核节点为一个的共享树称为单核共享树，核节点为多个的称为多核共享树。

随着视频会议、远程教育等各种多媒体业务的推广和应用，覆盖范围广、具有无线广播特性的卫星通信系统也日益得到重视，因为它们非常适合传输组播业务。与高轨(GEO)和中轨(MEO)卫星网络相比，低轨(LEO)卫星网络的信息传输时延很小，更适合对时延性能要求较为严格的多媒体组播业务，然而星上资源稀缺(如带宽、存储空间、处理能力和能量等)的特点给它们的应用带来了一定的局限性，因此需要一种高效资源利用的星上一对多/多对多通信的信息分发机制。

传统的地面网络组播树创建方法中，基于源的方法如距离向量组播路由协议(DVMRP)、开放式组播最短路径优先(MOSPF)等需要依赖点对点通信的单播路由协议，并且只适用于固定或者拓扑缓慢变化的网络中；而共享树方法如核基树(CBT)、稀疏模式的协议无关组播(PIM-SM)等在拓扑动态变化的网络中因为移动导致频繁的信息交换，从而产生很大的开销。鉴于卫星网络的高速移动性以及星上资源极其稀少的特点，这些方法不适合应用于卫星网络，所以需要为卫星网络设计专用、简单、高效的组播树创建方法。

目前，已提出的专用于低轨卫星网络的组播树创建方案主要有组播路由算法(Multicast Routing Algorithm，MRA)、矩形边Steiner树(Rectilinear Steiner Tree，RST)等。其中RST方法使用整数线性规划方法求解最小RST树，使组播路由的带宽使用最少，但计算过程比较复杂；MRA方法仅利用当前树上节点(on-tree nodes)到目的节点的单跳(one-hop)局部信息计算组播路径，尽管得到的端到端传播时延较小，但极其浪费带宽资源，链路重用效率很低。对于星上资源极其宝贵的卫星网络，RST和MRA两种方法都有一定的局限性。所以需要设计高效资源利用的、简单的组播树创建方法以提高网络带宽利用率和组播传输效率，有效增加系统容量。

相比基于源的方法，共享树方法可以节约系统资源，比较适用于卫星网络。在传统的地面移动网络中，选核方法通常会因网络拓扑动态变化频繁进行核移植操作，而这通常对于星上资源稀缺的卫星网络是一笔很大的开销；另外，星上资源稀缺的特性也决定了它们不适合执行复杂的星上计算，所以需要专门为卫星网络设计开销小而又简单的选核方法。

发明内容

本发明所要解决的技术问题在于针对现有组播树创建方法严重浪费信道资源的问题以及低轨卫星网络的拓扑结构高动态变化和星上资源稀缺的特点，提供一种适于低轨卫星网络的构建单核共享组播/多播树的方法，所用信道资源少，大大提高了网络的带宽利用率和组播传输效率。

为此，本发明提供了一种创建单核共享组播树的方法，其特征在于，包括如下步骤：

步骤1、计算虚拟卫星星座拓扑中一个组播组的所有卫星成员节点的虚拟卫星位置的平均值，记为(p_a，s_a)，公式如下：

$>>>p>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>p>i>>)>>>s>$

$>>>s>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>s>i>>)>>>s>$

其中，i＝0，1，...，N-1，N为所述卫星星座中所述组播组的卫星成员节点的数量；

p_i为所述组播组内的成员节点的虚拟卫星位置的轨道编号，0≤p_i≤P-1，s_i为所述组播组内的成员节点的虚拟卫星位置的卫星编号，0≤s_i≤S-1；

步骤2、计算从所述平均值位置到所述组播组中各卫星成员节点的距离最小值，记为d_min，公式如下：

$>>min>\{>>d>i>>|>>d>i>>=>>>>(>>p>i>>->>p>a>>)>>2>>+>>>(>>s>i>>->>s>a>>)>>2>\; >\}>>s>$

其中，i＝0，1，...，N-1，N为所述卫星星座中所述组播组的卫星成员节点的数量；

p_i为所述组播组内的成员节点的虚拟卫星位置的轨道编号，0≤p_i≤P-1，s_i为所述组播组内的成员节点的虚拟卫星位置的卫星编号，0≤s_i≤S-1；

步骤3、依照如下公式求解，得到距离所述平均值位置最近的第一卫星成员节点的位置，即核位置，记为(p_c，s_c)：

$>>>d>c>>=>>d>min>>=>>>>(>>p>c>>->>p>a>>)>>2>>+>>>(>>s>c>>->>s>a>>)>>2>\; >>s>$

步骤4、进行数据初始化，即以所述核位置作为初始位置点，计算所述初始位置点与所述组播组中各个目的地卫星成员节点之间的最短路径，并比较所述最短路径的跳数，选择其中跳数最少路径作为第一组播路径，同时将所述第一组播路径上的所有卫星成员节点作为第一节点集即第一核心群，用于构建与其余各目的地卫星成员节点进行信息转发的共享组播树。

上述技术方案中，所述步骤4之后还包括：计算得出组播组中第二目的地卫星成员节点以及所述目的地卫星成员节点到第一核心群的最短路径，以该路径为第二组播路径，该路径上的所有卫星节点加入第一核心群用于构成第二核心群；并且以此类推，计算得出组播组中第三个至最后一个目的地卫星成员节点以及所述目的地卫星成员节点到上一个核心群的最短路径，以该路径作为第三至最后一个组播路径，该路径上的所有卫星节点加入上一个核心群用于构成下一个核心群。

所述步骤3和步骤4之间还包括：如果得到的所述解为唯一解，则以该解作为核位置；如果得到的所述解为多个解，则随机选取该多解其中之一作为核位置。

所述步骤4及之后步骤还包括：如果有多个跳数最少路径，则比较该多个跳数最少路径的链路长度，选取其中距离最短的路径作为组播路径；然后继续进行后续步骤。

本发明提出了节约网络信道资源的核心群合并单核共享树(core-cluster combination-based shared tree，CCST)组播树构建方法，以解决原有组播树创建方法严重浪费信道资源的问题。CCST方法包括动态近似中心(dynamic approximate center，DAC)选核方法和核心群合并(core-cluster combination)组播路径构建方法。DAC是专门为动态、规律变化的卫星网络提出的一种简单、节约资源并且不需频繁更新和移植核的选核方案。在核心群合并方法中，以核节点作为初始核心群，通过核心群和剩余组成员的最短路径方法逐步扩展直至整棵组播树构建完成，从而使得组播树的树代价最小，大大提高了网络的带宽利用率和组播传输效率。

本发明基于虚拟卫星位置构成的虚拟静态、规则的网络拓扑结构，首先为组播组提供了选择核位置的方法，该方法简单、高效，适合星上资源稀缺的低轨卫星网络，所选的核位置不会因为拓扑快速变化而频繁进行核移植；然后提供了高效资源利用的核心群合并组播路径创建方法，解决了低轨卫星网络中典型算法的信道资源严重浪费问题，所生成的组播树链路重用率高，所用信道资源少。

下面通过附图和实施例，对本发明的技术方案做进一步的详细描述。

附图说明

图1为本发明实施例1的流程图；

图2为本发明实施例2的流程图；

图3为本发明实施例3的流程图。

具体实施方式

实施例1

图1为本发明的实施例1的流程示意图。如图1所示，本发明包括如下步骤：

步骤101、计算虚拟卫星星座拓扑中一个组播组的所有卫星成员节点的平均值位置，记为(p_a，s_a)，公式如下：

$>>>p>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>p>i>>)>>>s>$

$>>>s>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>s>i>>)>>>s>$

其中，i＝0，1，...，N-1，N为所述卫星星座中所述组播组的卫星成员节点的数量；

p_i为所述组播组内的成员节点的虚拟卫星位置的轨道编号，0≤p_i≤P-1，s_i为所述组播组内的成员节点的虚拟卫星位置的卫星编号，0≤s_i≤S-1；

步骤102、计算从所述平均值位置到所述组播组中各卫星成员节点的距离最小值，记为d_min，公式如下：

$>>min>\{>>d>i>>|>>d>i>>=>>>>(>>p>i>>->>p>a>>)>>2>>+>>>(>>s>i>>->>s>a>>)>>2>\; >\}>>s>$

其中，i＝0，1，...，N-1，N为所述卫星星座中所述组播组的卫星成员节点的数量；

p_i为所述组播组内的成员节点的虚拟卫星位置的轨道编号，0≤p_i≤P-1，s_i为所述组播组内的成员节点的虚拟卫星位置的卫星编号，0≤s_i≤S-1；

步骤103、依照如下公式求解，得到距离所述平均值位置最近的第一卫星成员节点的位置，即核位置，记为(p_c，s_c)：

$>>>d>c>>=>>d>min>>=>>>>(>>p>c>>->>p>a>>)>>2>>+>>>(>>s>c>>->>s>a>>)>>2>\; >>s>$

步骤104、进行数据初始化，即以所述核位置作为初始位置点，计算所述初始位置点与所述组播组中各个目的地卫星成员节点之间的最短路径，并比较所述最短路径的跳数，选择其中跳数最少路径作为第一组播路径，同时将所述第一组播路径上的所有卫星成员节点作为第一节点集即第一核心群，用于创建与其余各目的地卫星成员节点进行信息转发的共享组播树。

本实施例1通过对虚拟卫星星座中某个组播组中的成员位置进行设定，计算出该组所有成员位置的平均值，从而确定各成员位置相对于平均值的相对位置，以及各成员到平均值位置的最短路径，比较所述最短路径和跳数，得到核位置和第一组播路径，然后通过最短路径方法不断扩展，得到后续的组播路径，生成一个较优的组播树，也就是本发明所说的单核共享组播树。采用此组播树可以节约系统的资源，适合星上资源稀缺的低轨卫星网络，所构造的组播树链路重用率高，所用信道资源少。

实施例2

图2为本发明实施例2的流程图。本实施例是基于实施例1，在实施例1的步骤104之后，增加了步骤，具体如下：

步骤105、计算得出组播组中第二目的地卫星成员节点以及所述目的地卫星成员节点到第一核心群的最短路径，以该路径为第二组播路径，该路径上的所有卫星节点加入第一核心群用于构成第二核心群；

步骤106、计算得出组播组中第三个至最后一个目的地卫星成员节点以及所述目的地卫星成员节点到上一个核心群的最短路径，以该路径作为第三至最后一个组播路径，该路径上的所有卫星节点加入上一个核心群用于构成下一个核心群。

实施例3

图3为本发明实施例3的流程图。

步骤101、计算虚拟卫星星座拓扑中一个组播组的所有卫星成员节点的平均值位置，记为(p_a，s_a)，公式如下：

$>>>p>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>p>i>>)>>>s>$

$>>>s>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>s>i>>)>>>s>$

其中，i＝0，1，...，N-1，N为所述卫星星座中所述组播组的卫星成员节点的数量；

p_i为所述组播组内的成员节点的虚拟卫星位置的轨道编号，0≤p_i≤P-1，s_i为所述组播组内的成员节点的虚拟卫星位置的卫星编号，0≤s_i≤S-1；

步骤102、计算从所述平均值位置到所述组播组中各卫星成员节点的距离最小值，记为d_min，公式如下：

$>>min>\{>>d>i>>|>>d>i>>=>>>>(>>p>i>>->>p>a>>)>>2>>+>>>(>>s>i>>->>s>a>>)>>2>\; >\}>>s>$

其中，i＝0，1，...，N-1，N为所述卫星星座中所述组播组的卫星成员节点的数量；

p_i为所述组播组内的成员节点的虚拟卫星位置的轨道编号，0≤p_i≤P-1，s_i为所述组播组内的成员节点的虚拟卫星位置的卫星编号，0≤s_i≤S-1；

步骤103、依照如下公式求解，得到距离所述平均值位置最近的第一卫星成员节点的位置，即核位置，记为(p_c，s_c)：

$>>>d>c>>=>>d>min>>=>>>>(>>p>c>>->>p>a>>)>>2>>+>>>(>>s>c>>->>s>a>>)>>2>\; >>s>$

步骤1031、如果得到的所述解为唯一解，则以该解作为核位置；如果得到的所述解为多个解，则随机选取该多解其中之一作为核位置；

步骤1041、进行数据初始化，即以所述核位置作为初始位置点，计算所述初始位置点与所述组播组中各个卫星成员节点之间的最短路径；

步骤1042、并比较所述初始位置点与所述各目的地卫星成员节点的跳数，选择其中跳数最少路径作为第一组播路径；

步骤1043、如果有多个跳数最少路径，则比较该多个跳数最少路径的链路长度，选取其中距离最短的路径作为组播路径；

步骤1044、同时将所述第一组播路径上的所有卫星节点构成第一节点集即第一核心群，用于创建与其余各目的地卫星成员节点进行信息转发的共享组播树；

步骤1051、计算所述组播组中第二目的地卫星成员节点与所述第一核心群内所述各卫星节点的最短路径并比较它们的跳数；

步骤1052、如果有多个跳数最少路径，则比较该多个跳数最少路径的链路长度，选取其中距离最短的路径作为组播路径；

步骤1053、得出所述组播组中第二个目的地卫星成员节点到第一核心群的跳数最少路径；

步骤1054、以所述跳数最少路径作为到达第二个组播路径；

步骤1055、将所述第二组播路径上的所有卫星节点加入第一节点集构成第二核心群；

步骤1061、计算得出组播组中第三个乃至最后一个目的地卫星成员节点以及它们到上一个核心群的最短路径，以该路径作为第三乃至最后一个组播路径；

步骤1062、所述第三乃至最后一个组播路径上的所有节点加入上一个核心群构成下一个核心群。

实施例3

本实施例3是在上述实施例的基础上，更为细化的一个实施方案。本发明为低轨卫星网络中创建单核共享组播树的方法，需要首先为组播组选择核位置，然后以核位置为根，创建从核节点到其它成员节点的组播路径。假设低轨卫星网络中的某组播组G共有N个成员节点，低轨卫星网络包括P个轨道，每个轨道内均匀分布有S颗卫星。本发明的功能流程图见图2。具体为如下步骤：

步骤1011、在某个初始时刻将星座内的轨道按照一定次序编号，并使用p标识轨道编号(0≤p≤P-1)；然后将轨道内的卫星依次编号，使用s标识卫星编号(0≤s≤S-1)，则(p，s)可以表示此时网络内的一个卫星节点。将整个星座覆盖区依据此时每颗卫星的覆盖范围划分为与卫星个数相等的虚拟卫星位置，且每个虚拟卫星位置以此刻卫星所在位置在地面的映射点为中心，则一个虚拟卫星位置对应着一颗实际的卫星，符号(p，s)完全可以标记虚拟卫星位置。规定每个虚拟卫星位置由当前距离最近的卫星管理。若将静态的虚拟卫星位置作为一个虚拟节点，则卫星网络的拓扑结构具有虚拟稳定、规则的特点。见图1所示初始时刻低轨星座网络的模型。将G记为G＝{g₀，g₁，g₂，...，g_N-1}，其中g_i(i＝0，...，N-1)代表成员节点的虚拟卫星位置，g_i＝(p_i，s_i)；

步骤1012、首先计算组G中成员节点的虚拟卫星位置的平均值，记为g_a，g_a＝(p_a，s_a)，其中p_a、s_a可由下式求得：

$>>>p>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>p>i>>)>>->->->>(>1>)>>>s>$

$>>>s>a>>=>>1>N>>>(>>\Sigma >>i>=>0>>>N>->1>\; >>s>i>>)>>->->->>(>2>)>>>s>$

步骤1013、定义d_min为g_a到组G中每个成员节点虚拟卫星位置距离的最小值，由下式可得：

$>>>min>\{>>d>i>>|>>d>i>>=>>>>(>>p>i>>->>p>a>>)>>2>>+>>>(>>s>i>>->>s>a>>)>>2>\; >\}>>,>i>=>0>,>.>.>.>,>N>->1>->->->>(>3>)>>;>>s>$

步骤1014、将与g_a距离最近的虚拟卫星位置记为g_u＝(p_u，s_u)，其中p_u、s_u满足下式：

$>>>d>c>>=>>d>min>>=>>>>(>>p>c>>->>p>a>>)>>2>>+>>>(>>s>c>>->>s>a>>)>>2>\; >->->->>(>4>)>>;>>s>$

步骤1015、若(4)式有唯一解，则以它作为核位置，即g_c＝g_u；若有多个解，则随机选取其中之一作为核位置。将核位置记为g_c，g_c＝(p_c，s_c)；

步骤1016、进行数据初始化，即以核位置g_c作为初始核心群C₀，即C₀＝{g_c}，设核位置g_c是g₀，令i＝0，G₀＝{g₁，g₂，...，g_N-1}；

步骤1017、使用最短路径方法计算C₀与G₀中每个成员节点之间的最短路径并比较它们的跳数，得到C₀与G₀之间的跳数最少路径；

步骤1018、如果有多个跳数最少路径，则比较它们的链路长度，选取其中距离最短的路径作为组播路径；并得到此路径上同时属于G₀的相应端节点g₁’，将g₁’和相应中间节点(记为g_1a’，g_1b’，...)与C₀合并为一个新的核心群C₁，则C₁＝{g_c，g₁’，g_1a’，g_1b’，...}；

步骤1019、令i＝i+1，G_i＝G_i-1-{g_i’}，即将G_i-1中与核心群C_i合并后剩余的成员节点组成集合G_i，计算核心群C_i中的每个节点与G_i中每个成员节点之间的最短路径并比较它们的跳数，得到G_i与C_i之间的跳数最少路径；

步骤1020、如果有多条跳数最少路径，则比较它们的链路长度，选取其中距离最短的路径作为组播路径；并得到此路径上作为一个端节点的G_i中的成员节点g_i+1’；

步骤1021、将g_i+1’和路径上相应的中间节点与核心群C_i合并得到新的核心群C_i+1＝{g_c，g₁’，g₂’，...，g_i+1’，...，g_1a’，g_1b’，...g_2a’，g_2b’，...g_(i+1)a’，g_(i+1)b’，...}，其中g_i+1’(i＝0，1，...)是属于集合G_i的某个非核成员节点，g_(i+1)j’(j＝a，b，...)是组播路径上的中间节点；

步骤1022、判断是否i＝N-2，即核心群G_i是否为空，否转到3)；是则程序结束。

另外，需要补充的是，当卫星移出当前某个虚拟卫星位置同时移进轨道内下一个虚拟卫星位置时，需要进行路由表的移交。移出的卫星发送它的路由表到轨道内移进的后续卫星，并从轨道内前序卫星接收新的路由表。

最后所应说明的是，以上实施例仅用以说明本发明的技术方案而非限制，尽管参照较佳实施例对本发明进行了详细说明，本领域的技术人员应当理解，可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明技术方案的精神和范围。