本发明公开了一种基于链路生存时间的卫星自组织网络路由抗毁方法，其包括根据卫星节点和其邻居节点的Hello分组消息生成邻居表，之后预测卫星自组织网络中每个卫星节点与其邻居节点间的链路生存时间；选取每个卫星节点的MPR节点，并通过卫星节点的MPR节点全网广播TC消息建立卫星自组织网络拓扑图；采用基于跳数和链路生存时间的Dijkstra算法，计算卫星自组织网络拓扑图/临时网络拓扑图A中源节点到目的节点的主路由和备选路由；临时网络拓扑图A为卫星自组织网络拓扑删除主路由中非源节点和目的节点的所有卫星节点得到。本方案的路由抗毁方法解决了传统OLSR路由协议在卫星自组织网络的应用中容易出现链路失效的问题。
1.基于链路生存时间的卫星自组织网络路由抗毁方法，其特征在于，包括：S1、卫星节点周期性向外广播Hello分组消息和接收来自于邻居节点周期性向外广播的Hello分组消息；Hello分组消息包括卫星节点的邻居节点、链路状态信息及发送消息时的位置坐标和时间戳；
S2、根据卫星节点和其邻居节点的Hello分组消息生成邻居表，之后预测卫星自组织网络中每个卫星节点与其邻居节点间的链路生存时间；
S3、选取每个卫星节点的MPR节点，并通过卫星节点的MPR节点全网广播TC消息建立卫星自组织网络拓扑图；
S4、采用基于跳数和链路生存时间的Dijkstra算法，计算卫星自组织网络拓扑图中源节点s到目的节点d的主路由，并将主路由加入主路由表；
S5、在初始状态与卫星自组织网络拓扑图相同的临时网络拓扑图A中删除主路由中非源节点s和目的节点d的所有卫星节点；
S6、采用基于跳数和链路生存时间的Dijkstra算法，计算临时网络拓扑图A中源节点s到目的节点d的备份路由，并将备份路由加入备份路由表；
选取每个卫星节点的MPR节点的方法包括：A1、在初始状态与卫星自组织网络拓扑图相同的临时网络拓扑图B中获取卫星节点的所有1跳邻居节点的深度；
A2、判断临时网络拓扑图B中卫星节点与其2跳邻居节点间是否具有唯一通路的1跳邻居节点；若有进入步骤A3，否则进入步骤A5；
A3、将卫星节点与其2跳邻居节点间具有唯一通路的1跳邻居节点作为MPR节点加入MPR集中，并删除临时网络拓扑图B中MPR节点及其覆盖的所有2跳邻居节点；
A4、判断临时网络拓扑图B中卫星节点的所有2跳邻居节点是否都被删除，若是，则完成MPR节点选择，否则进入步骤A5；
A5、获取临时网络拓扑图B中卫星节点的所有1跳邻居节点的到达性，并判断到达性最高的1跳邻居节点的数量是否大于1，若是，进入步骤A6，否则进入步骤A7；
A6、选择可靠度最大的1跳邻居节点作为MPR节点加入MPR集中，之后进入步骤A8；
A7、将到达性最高的1跳邻居节点作为MPR节点加入MPR集中，并进入步骤A8；
A8、删除临时网络拓扑图B中MPR节点及其覆盖的所有2跳邻居节点，并判断临时网络拓扑图B中卫星节点的所有2跳邻居节点是否都被删除，若是，则完成MPR节点选择，否则返回步骤A2；
其中，LI为可靠度；t1为卫星节点与1跳邻居节点的链路生存时间；t′i为1跳邻居节点与其所覆盖的第i个2跳邻居节点的链路生存时间；n为1跳邻居节点的到达性。
2.根据权利要求1所述的基于链路生存时间的卫星自组织网络路由抗毁方法，其特征在于，预测每个卫星节点与邻居节点间的链路生存时间的方法包括：S21、邻居节点b记录其连续两次接收到卫星节点广播的Hello分组消息的时间t1、时间t2及卫星节点连续两次广播Hello分组消息时的位置坐标；
S22、邻居节点b根据接收到的卫星节点位置坐标及时间t1、时间t2，计算卫星节点瞬时运动速度
S23、邻居节点b通过提取自身轨道信息得到自身t1、t2两个时刻的位置信息，根据位置信息和时间差计算邻居节点b的瞬时运动速度S24、根据瞬时运动速度 和瞬时运动速度 计算卫星节点相对于邻居节点b的相对运动速度
S25、根据相对运动速度 及卫星节点和邻居节点b的位置坐标，计算卫星节点与邻居节点b的链路生存时间。
3.根据权利要求2所述的基于链路生存时间的卫星自组织网络路由抗毁方法，其特征在于，所述链路生存时间的计算公式为：其中，tab为卫星节点与邻居节点b链路生存时间；R为卫星节点的最大通信距离； 为邻居节点b第二次接收到Hello分组消息时与卫星节点间的相对距离；a点为卫星节点在t2时的位置，b点为邻居节点在t2时的位置；c点为邻居节点b向卫星节点相对运动轨迹作垂线的垂足， 分别为ab点及ac点对应的向量；α为邻居节点b第二次接收到卫星节点的Hello分组消息时与卫星节点的连线和卫星节点相对运动方向形成的夹角。
4.根据权利要求1‑3任一所述的基于链路生存时间的卫星自组织网络路由抗毁方法，其特征在于，采用基于跳数和链路生存时间的Dijkstra算法，计算卫星自组织网络拓扑图/临时网络拓扑图A中源节点s到目的节点d的主路由/备份路由进一步包括：B1、将卫星自组织网络拓扑图/临时网络拓扑图A中的每条边的权值设置为1；
B2、采用Dijkstra算法求解源节点到目的节点的最短路径；
B3、判断是否存在多条相同跳数的最短路径，若存在，进入步骤B4，否则采用最短路径作为主路由/备份路由，并进入步骤B5；
B4、对每条最短路径所经过的每段链路的预测生存时间进行判断，记录最小生存时间，选取最小生存时间最长的最短路径作为主路由/备份路由；
基于链路生存时间的卫星自组织网络路由抗毁方法
技术领域
[0001] 本发明涉及网络中的路由生成技术，具体涉及一种卫星自组织网络中OLSR路由协议的路由抗毁方法。
背景技术
[0002] 在卫星自组织网络中，每个卫星节点都扮演了两种角色。一种是收发数据的终端节点，另一种是转发数据的路由节点。经研究，大量的卫星自组织网络路由协议方案相继被
提出，依据不同的标准，卫星自组织网络路由协议有不同的分类方式。针对卫星自组织网络
路由问题，按照路由建立的方式不同，可分为后应式路由协议、先应式路由协议。
[0003] 后应式路由协议又称为按需路由协议，不需要维护网络拓扑和当前路由信息，当源节点需要发送分组时，被动地搜索从源节点到目的节点的路由。后应式路由协议虽然能
够减小控制报文的开销，但存在不确定性，包括目的节点是否可达的不确定性以及路由建
立延时的不确定性。现有的研究表明，后应式路由协议的时延远远大于先应式路由建立的
时延。
[0004] 先应式路由协议又称为表驱动路由协议，在网络运行过程中必须实时跟踪网络拓扑的变化，更新路由表信息。优化链路状态路由协议(OLSR,Optimized Link State
Routing)是一种典型的表驱动先应式路由协议。OLSR路由协议要求卫星节点周期性地交换
Hello分组和Topology Control(TC)分组在内的各种控制分组，进行分布式计算来建立网
络拓扑。
[0005] 在卫星自组织网络中，卫星节点的快速运动和网络拓扑的频繁变化会带来路由信息的快速更新，传统的OLSR协议所计算的路由存在不稳定性，快速变化的拓扑可能会造成
链路断裂的问题。同时，传统OLSR协议只计算一条通往目的节点的路径，在链路失效等问题
发生后，只能等待重新收敛，造成了无线带宽资源和卫星节点能量的浪费，也降低了整个路
由协议的运行效率。
发明内容
[0006] 针对现有技术中的上述不足，本发明提供的基于链路生存时间的卫星自组织网络路由抗毁方法解决了传统OLSR路由协议在卫星自组织网络的应用中容易出现链路失效的
问题。
[0007] 为了达到上述发明目的，本发明采用的技术方案为：
[0008] 提供一种基于链路生存时间的卫星自组织网络路由抗毁方法，其包括：
[0009] S1、卫星节点周期性向外广播Hello分组消息和接收来自于邻居节点周期性向外广播的Hello分组消息；Hello分组消息包括卫星节点的邻居节点、链路状态信息及发送消
息时的位置坐标和时间戳；
[0010] S2、根据卫星节点和其邻居节点的Hello分组消息生成邻居表，之后预测卫星自组织网络中每个卫星节点与其邻居节点间的链路生存时间；
[0011] S3、选取每个卫星节点的MPR节点，并通过卫星节点的MPR节点全网广播TC消息建立卫星自组织网络拓扑图；
[0012] S4、采用基于跳数和链路生存时间的Dijkstra算法，计算卫星自组织网络拓扑图中源节点s到目的节点d的主路由，并将主路由加入主路由表；
[0013] S5、在初始状态与卫星自组织网络拓扑图相同的临时网络拓扑图A中删除主路由中非源节点s和目的节点d的所有卫星节点；
[0014] S6、采用基于跳数和链路生存时间的Dijkstra算法，计算临时网络拓扑图A中源节点s到目的节点d的备份路由，并将备份路由加入备份路由表；
[0015] S7、输出主路由表和备份路由表。
[0016] 本发明的有益效果为：本方案能够更加适应拓扑频繁变化的卫星自组织网络实际应用，降低资源浪费，提高了路由的抗毁能力和运行效率，主要表现为：
[0017] (1)利用卫星轨道数据提供的坐标信息对邻居链路的生存时间进行预测，将其作为路由计算的参数考量，提出基于跳数和链路生存时间的Dijkstra算法，充分考虑了卫星
自组织网络拓扑频繁变化的特点，大大提高了路由的可靠性和抗毁能力。
[0018] (2)采用备份路由的思想，并且保证主路由和备份路由充分独立，当链路失效问题发生后，直接选用备份路由进行数据转发，无需等待重新收敛，快速进行路由修复，提高了
资源利用率和运行效率。
附图说明
[0019] 图1为基于链路生存时间的卫星自组织网络路由抗毁方法的流程图。
[0020] 图2为卫星节点与邻居节点b相对运动的示意图。
[0021] 图3为卫星自组织网络的拓扑图一。
[0022] 图4为卫星自组织网络的拓扑图二。
具体实施方式
[0023] 下面对本发明的具体实施方式进行描述，以便于本技术领域的技术人员理解本发明，但应该清楚，本发明不限于具体实施方式的范围，对本技术领域的普通技术人员来讲，
只要各种变化在所附的权利要求限定和确定的本发明的精神和范围内，这些变化是显而易
见的，一切利用本发明构思的发明创造均在保护之列。
[0024] 为了避免在描述中引起歧义，此处对1跳邻居节点和2跳邻居节点进行说明：本方案中出现的所有1跳邻居节点和2跳邻居节点均指代卫星节点的1跳邻居节点和2跳邻居节
点。
[0025] 参考图1，图1示出了基于链路生存时间的卫星自组织网络路由抗毁方法的流程图，如图1所示，该方法S包括步骤S1至步骤S7。
[0026] 在步骤S1中，卫星节点周期性向外广播Hello分组消息和接收来自于邻居节点周期性向外广播的Hello分组消息；Hello分组消息包括卫星节点的邻居节点、链路状态信息
及发送消息时的位置坐标和时间戳。
[0027] 卫星节点通过Hello消息周期性地交互，各个节点建立起自己的邻居信息，然后通过邻居节点的Hello消息，还能知道两跳邻居。
[0028] 在步骤S2中，根据卫星节点和其邻居节点的Hello分组消息生成邻居表，之后预测卫星自组织网络中每个卫星节点与其邻居节点间的链路生存时间。
[0029] 当卫星节点选好MPR节点后，每个MPR节点均会建立起一个MPR Selectors表，MPR Selector是指将本节点选为MPR节点的邻居节点(如选择a节点作为b节点的MPR节点，b节点
就是a节点的MPR Selector)。
[0030] MPR Selectors表规定了在建立拓扑时，MPR节点要转发来自哪些节点的TC分组信息，如a节点就转发来自b节点的TC消息，TC消息包含节点的MPR Selectors信息(意味着可
以通过该节点到达这些节点)。
[0031] 网络中每一个节点都维护一张拓扑表，表中记录了从TC消息获得的网络拓扑信息，节点将网络中其他节点的MPR Selectors的信息记录在拓扑表中，每个节点维护一张拓
扑表。
[0032] 参考图2，其示出了卫星节点连续两次向外广播Hello分组消息过程中，卫星节点与邻居节点相对运动的示意图，其中坐标点a、b分别表示卫星节点和邻居节点b，R为卫星节
点的最大通信距离。
[0033] 参考图2对本方案预测每个卫星节点与邻居节点间的链路生存时间的方法进行说明：
[0034] S21、邻居节点b记录其连续两次接收到卫星节点广播的Hello分组消息的时间t1、时间t2及卫星节点连续两次广播Hello分组消息时的位置坐标；
[0035] S22、邻居节点b根据接收到的卫星节点位置坐标及时间t1、时间t2，计算卫星节点瞬时运动速度
[0036] S23、邻居节点b通过提取自身轨道信息得到自身t1、t2两个时刻的位置信息，根据位置信息和时间差计算邻居节点b的瞬时运动速度
[0037] S24、根据瞬时运动速度 和瞬时运动速度 计算卫星节点相对于邻居节点b的相对运动速度
[0038] S25、根据相对运动速度 及卫星节点和邻居节点b的位置坐标，计算卫星节点与邻居节点b的链路生存时间：
[0039]
[0040] 其中，tab为卫星节点与邻居节点b链路生存时间；R为卫星节点的最大通信距离；为邻居节点b第二次接收到Hello分组消息时与卫星节点间的相对距离；a点为卫星节
点在t2时的位置，b点为邻居节点在t2时的位置；c点为邻居节点b向卫星节点相对运动轨迹
作垂线的垂足， 分别为ab点及ac点对应的向量；α为邻居节点b第二次接收到卫星
节点的Hello分组消息时与卫星节点的连线和卫星节点相对运动方向形成的夹角。
[0041] 在步骤S3中，选取每个卫星节点的MPR节点，并通过卫星节点的MPR节点全网广播TC消息建立卫星自组织网络拓扑图。
[0042] 在本发明的一个实施例中，选取每个卫星节点的MPR节点的方法包括步骤A1至步骤A8：
[0043] 在步骤A1中，在初始状态与卫星自组织网络拓扑图相同的临时网络拓扑图B中获取卫星节点的所有1跳邻居节点的深度；结合图3对深度进行说明：
[0044] 参考图3，其示出了以卫星节点a为源节点的网络拓扑图，其中节点b和节点c为源节点a的1跳邻居节点，节点d、e、f为源节点a的2跳邻居节点；其中1跳邻居节点的除源节点
之外的对称邻居节点数量即为源节点a的1跳邻居节点的深度，节点b的深度为2，节点c的深
度为3。
[0045] 在步骤A2中，判断临时网络拓扑图B中卫星节点与其2跳邻居节点间是否具有唯一通路的1跳邻居节点；若有进入步骤A3，否则进入步骤A5；
[0046] 以图4示出的网络拓扑为例对卫星节点与其2跳邻居节点间是否具有唯一通路的1跳邻居节点进行说明，在图4中节点e满足存在与源节点a具有唯一通路的1跳邻居节点b，因
此节点b为卫星节点与其2跳邻居节点间具有唯一通路的1跳邻居节点，节点b覆盖的2跳邻
居节点为节点e、f。
[0047] 在步骤A3中，将卫星节点与其2跳邻居节点间具有唯一通路的1跳邻居节点作为MPR节点加入MPR集中，并删除临时网络拓扑图B中MPR节点及其覆盖的所有2跳邻居节点。
[0048] 在图4中，当节点b被选为MPR节点后，其覆盖的2跳邻居节点e、f将被删除，在继续选择MPR节点时，节点b、e、f将不再被考虑。
[0049] 在步骤A4中，判断临时网络拓扑图B中卫星节点的所有2跳邻居节点是否都被删除，若是，则完成MPR节点选择，否则进入步骤A5；
[0050] 可以继续参考图4对步骤A4进行说明，当节点b、e、f被删除后，源节点a还存在2跳邻居节点g，于是就进入步骤A5继续进行MPR节点选取。
[0051] 在步骤A5中，获取临时网络拓扑图B中卫星节点的所有1跳邻居节点的到达性，并判断到达性最高的1跳邻居节点的数量是否大于1，若是，进入步骤A6，否则进入步骤A7；
[0052] 其中的到达性是指与节点连接的下一跳邻居节点的数量，比如图4中的节点b、c的到达性均为2，节点d的到达性为1。
[0053] 可以继续参考图4对步骤A5进行说明，在节点b、e、f被删除后，源节点a的1跳邻居节点就只剩下节点c、d，从图4可以看出，节点c、d的到达性均为1。
[0054] 在步骤A6中，选择深度最大或者可靠度最大的1跳邻居节点作为MPR节点加入MPR集中，之后进入步骤A8；
[0055] 实施时，本方案优选所述可靠度的计算公式为：
[0056]
[0057] 其中，LI为可靠度；t1为卫星节点与1跳邻居节点的链路生存时间；t′i为1跳邻居节点与其所覆盖的第i个2跳邻居节点的链路生存时间；n为1跳邻居节点的到达性。
[0058] 在步骤A7中，将到达性最高的1跳邻居节点作为MPR节点加入MPR集中，并进入步骤A8；
[0059] 在步骤A8中，删除临时网络拓扑图B中MPR节点及其覆盖的所有2跳邻居节点，并判断临时网络拓扑图B中卫星节点的所有2跳邻居节点是否都被删除，若是，则完成MPR节点选
择，否则返回步骤A2。
[0060] 在步骤S4中，采用基于跳数和链路生存时间的Dijkstra算法，计算卫星自组织网络拓扑图中源节点s到目的节点d的主路由，并将主路由加入主路由表；
[0061] 在本发明的一个实施例中，采用基于跳数和链路生存时间的Dijkstra算法，计算卫星自组织网络拓扑图/临时网络拓扑图A中源节点s到目的节点d的主路由/备份路由进一
步包括：
[0062] B1、将卫星自组织网络拓扑图/临时网络拓扑图A中的每条边的权值设置为1；
[0063] B2、采用Dijkstra算法求解源节点到目的节点的最短路径；
[0064] B3、判断是否存在多条相同跳数的最短路径，若存在，进入步骤B4，否则采用最短路径作为主路由/备份路由，并进入步骤B5；
[0065] B4、对每条最短路径所经过的每段链路的预测生存时间进行判断，记录最小生存时间，选取最小生存时间最长的最短路径作为主路由/备份路由。
[0066] 参考图4，假设最短路径是acg和adg，其中链路ac、cg、ad、dg的预测生存时间分别为0.11、0.13，0.09、0.10，那么在步骤B4中最短路径acg和adg分别记录的最小生存时间为
0.11，0.09，由于0.11＞0.09，则最终选取的acg作为主路由/备份路由。
[0067] B5、输出主路由/备份路由。
[0068] 本方案采用上述方式获取主路由和备份路由后，由于主要基于跳数和链路生存时间进行选取的，充分考虑了链路的失效问题，从而使得最终得出的主路由和备份路由更加
稳定。
[0069] 在步骤S5中，在初始状态与卫星自组织网络拓扑图相同的临时网络拓扑图A中删除主路由中非源节点s和目的节点d的所有卫星节点；
[0070] 在步骤S6中，采用基于跳数和链路生存时间的Dijkstra算法，计算临时网络拓扑图A中源节点s到目的节点d的备份路由，并将备份路由加入备份路由表；
[0071] 在步骤S7中，输出主路由表和备份路由表。
[0072] 本方案提供的路由抗毁方法解决了传统OLSR路由协议在卫星自组织网络的应用中存在的路由不稳定，容易出现链路失效问题及出现链路失效问题后，只能等待重新收敛，
造成资源浪费和运行效率下降问题。
[0073] 综上所述，本方案的路由抗毁方法利用卫星轨道对链路生存时间进行预测，并将其加入路由计算的参数限制，以此得到更加稳定的路由。同时采用备份路径的思想，当链路
失效问题发生后，直接选用备份路由进行数据转发，无需等待重新收敛，减少资源的浪费，
快速进行路由修复。
