图6-4给出了3种仿真场景下算法得到的最重拓扑，图，，表示3种仿真场景中运行DMST算法得到的近似最优的最小生成树，图，，表示对应的CG算法的结果。在仿真中，仅考虑RC中的可行解来与CG算法比较。图6-7给出了两种算法在3种仿真场景中的运算结果。......
2023-07-02
空间信息网络中节点连通度保证算法的描述
【摘要】：在空间信息网络中，由于星群节点的异构性，不同的节点可能需要不同的连通度来满足不同任务的需要。然而，在一个生成树中，节点的连通度几乎肯定是无法保证的。因此在本节中，将基于一棵最小生成树，通过提出的连通度保证算法，在网络中增加某些额外的边来满足节点连通度的需求，同时算法还需要保持网络中的平均链路权重尽量地小。表6-4节点连通度保证算法伪代码（续表）
节点的连通度指的是节点上建立的星间链路的数量。在空间信息网络中，由于星群节点的异构性，不同的节点可能需要不同的连通度来满足不同任务的需要。比如导航卫星和移动通信卫星所需要的路由数量是不同的，因此需要建立的链路数量也是不同的。然而，在一个生成树中（尤其是最小生成树），节点的连通度几乎肯定是无法保证的。因此在本节中，将基于一棵最小生成树，通过提出的连通度保证（CG）算法，在网络中增加某些额外的边来满足节点连通度的需求，同时算法还需要保持网络中的平均链路权重尽量地小。
考虑一个给定的树型图G=（V，E）和一个节点连通度需求向量C∈R N×1，C中的元素表示为c i，i=1，2，…，N，而c i表示节点i的连通度需求。希望增加某些边到图G中形成一个新的图ψ=（V，ε），而ψ能够在满足节点连通度需求的前提下最小化链路平均权重。
将优化问题构建如下：
式中，B表示新图ψ对应的邻接矩阵，而bij为B中的元素。第一个约束条件保证节点连通度的需求；第二个约束条件表示新的拓扑是在最小生成树的基础上通过增加额外的边形成的，但是不能超出邻居矩阵的限制。就像式（6-2）一样，该问题也是一个MINLP问题，同样可以采用贪婪启发算法来近似地求解。
连通度保证算法的实现过程为：若当前拓扑中节点i未满足节点连通度需求，即∑jbij＜c i。显然，节点i需要建立更多的链路来满足需求，与DMST算法的第一阶段类似，节点i将按邻居队列的顺序逐个尝试连接它的邻居节点，直至其节点连通度需求得到满足或邻居队列为空。算法同样包括listening和requesting两个线程。对于节点i，算法的伪代码如表6-4所示。
表6-4 节点连通度保证算法伪代码
（续表）
有关空间激光微波混合信息网络技术的文章
- 详细阅读
-
空间信息网络下的节点逐边调整算法详细阅读
图的拉普拉斯矩阵及特征值在数学领域有着广泛的研究，尤其是在采用图论和数学规划方法解决网络拓扑构型问题方面。图5-2位于不同轨道的3颗卫星组成的星间组网系统轨道分布情况；星间距离和可视性关系变化规律本章主要考虑空间信息网络中节点分布高动态和节点运算能力有限等星上系统的特点，针对网络初始化和网络重构两种典型场景，通过对拉普拉斯矩阵特征值在矩阵摄动条件下演化规律的分析，得出一种新的逐边调整的启发式算法。......
2023-07-02
-
基于节点自由度约束下的最大代数连通度生成树算详细阅读
目前有大量文献针对最小生成树的构造问题进行研究。Zhou等人基于BUA算法，提出了节点自由度约束下的具有最大代数连通度的生成树算法。近年来，除了在网络中寻找具有最小开销的连通链路之外，最小生成树也在其他领域发挥了重要的作用。......
2023-07-02
-
满足节点连通度需求的最小链路平均权重算法比随详细阅读
提出的满足节点连通度需求的链路平均权重最小化算法与随机连接算法相比，当取节点自由度分别为3，4，5时，在低轨道卫星网络中，提出的算法分别降低了约9.57%，16.27%，18.94%的链路平均权重；在同步轨道星群网络中分别降低了约78.42%，87.16%，92.37%；而在多层空间信息网络中分别降低了约68.15%，78.06%，80.93%。......
2023-07-02
-
算法评价：正确性、时间复杂度、空间复杂度《信详细阅读
评价算法的前提条件是这些算法都应该是正确的，在此基础上再通过时间复杂度和空间复杂度进一步评价算法的优劣。空间复杂度是指在算法执行过程中需要耗费的内存空间资源。现在，我们通过一个例子来说明算法的设计过程以及如何评价一个算法的优劣。所以这种算法最少称1次，最多要称7次。算法分析的目的在于选择合适的算法并改进算法。......
2023-10-22
-
解决MINLP问题的高效策略在空间信息网络中详细阅读
由于λ2的非线性和a ij的整数限制，因此原始问题可以认为是一个混合整型非线性规划问题，这是一个NP-hard问题。MINLP问题也可以通过将凸优化和分支定界法相结合来得到最优解，但在部署时通常需要采用中心式的策略耗费大量的计算资源，在空间信息网络中是不适用的。......
2023-07-02
-
空间信息网络的组网方式详细阅读
表1-1不同业务应用对应的空间网络层次化设计参数按照组网方式不同，可以将天地一体化网络的网络架构归为3大类：天星地网、天基网络、天网地网，不同网络架构的比较如表1-2所示。表1-2美军天基信息系统现状1）天星地网天星地网是目前普遍采用的一种网络结构，包括Inmarsat、Intelsat、宽带全球卫星等系统，其特点是天上卫星之间不组网，而是通过全球分布的地面站实现整个系统的全球服务能力。......
2023-07-02
-
加权代数连通度的定义与计算详细阅读
图5-1给出的例子中包括了5个节点组成的不同拓扑的网络结构及其对应的代数连通度。图5-1代数连通度概念示例λ2=0；λ2=0.382 0；λ2=1.382 0；λ2=5代数连通度的最大化问题是图论中一个经典的数学规划问题。在星间组网系统中，考虑到星上资源受限，本章在代数连通度的概念基础上增加了链路权重的因素，将代数连通度扩展为加权代数连通度加以分析。以权重矩阵来计算加权代数连通度的方法与以邻接矩阵来计算非加权代数连通度的方法相同。......
2023-07-02
相关推荐