基于分层自治域空间信息网络模型与拓扑控制算法

张威，张更新，边东明，苟亮，谢智东



基于分层自治域空间信息网络模型与拓扑控制算法

张威，张更新，边东明，苟亮，谢智东

（解放军理工大学通信工程学院，江苏南京 210007）

针对空间信息网络结构复杂、拓扑动态变化以及空间尺度大等特点，提出一种面向空间信息网的分层自治域模型。该模型根据节点属性、链路能力、任务特点、分布区域等不同，将整个网络划分为不同的自治域和子自治域，各域内可采用相对独立的控制策略，从而将子网间各动态因素解耦合。然后，基于该分层自治域模型，提出了一种最小化时延的拓扑控制算法。与现有的集中式和分布式拓扑控制方法不同，该算法采用混合式方法，将控制信息约束在相邻子自治域范围内，既保证了网络的连通性，又减少了控制信息的开销。理论分析表明，若网络的物理拓扑是连通的，则该算法得到的拓扑控制结果一定是连通的。仿真结果验证了理论分析和所提出算法的有效性。

空间信息网；网络模型；自治域；拓扑控制

1 引言

纵观世界范围内，各类卫星通信系统的建设仍然表现出各自为阵、独立建设的局面。各系统针对不同的任务需求和服务对象构建，系统缺乏一般性、通用性和相互协作的能力，形成重复建设、“烟囱式”发展的不利局面。譬如，仅40ºE~180ºE的亚太地区就有120多个GEO轨道位置用于卫星移动通信[1,2]，而各类宽带通信、数据中继、气象、导航卫星更占用了大量轨道资源，并且单个系统针对既定任务设计，系统完成任务后会出现较多空闲状态，无法对空间资源进行整体配置。此外，由于频谱和轨道等资源的限制，各系统的全域覆盖能力有限，不同的技术体制更导致网络扩展能力差。空间信息网的提出为解决上述问题提供了一种有效途径，已成为全球范围的研究热点[3~6]。

空间信息网络是以多种空间平台（如同步卫星、中/低轨道卫星、平流层气球和有人/无人驾驶飞机等）为载体，实时获取、传输和处理空间信息的网络系统。作为国家重要基础设施，空间信息网络在服务远洋航行、应急救援、导航定位、航空运输、航天测控等重大应用的同时，向下可支持对地观测的高动态、宽带实时传输，向上可支持深空探测的超远程、大时延可靠传输，从而将人类科学、文化、生产活动拓展至空间、远洋乃至深空[7,8]。相比传统卫星网络，空间信息网络具有组成结构复杂、拓扑动态变化、跨越空间尺度大和自组织程度高等明显特征。因此，如何提高整个空间信息网的管理效率，进行高效、可靠的拓扑控制具有一定的挑战性。

国内外学者已针对空间信息网的模型做出了一些探索。葛晓虎等[9,10]提出了一种基于三维MESH空间信息网络模型；吕本伟等[11]在将网络构架分为骨干网及非骨干网的基础上，提出主服务小区的概念；Pasquale等[12]提出了一种卫星与升空平台结合的架构，并研究了其路由策略。此外，TSAT系统、Iridium NEXT等计划中的系统已经具备了空间信息网的雏形。TSAT计划通过Teleport实现与美军其他卫星通信系统的互连互通，形成美国全球信息栅格(GIG)的空间部分[13,14]，为构建空间信息网架构提供了参考。Iridium NEXT融合了通信、导航增强、对地观测等多种业务[15]，为研究空间信息网的业务多样化提供了参考。同时，国内外大量关于多层卫星网（MLSN，multilayered satellite network）的文献也为研究空间信息网的模型提供参考[16~19]。然而，空间信息网是一个立体多层、异构动态的复杂网络，网络某一局部范围内组网应用方式、拓扑结构的变化都会影响到全网的状态。现有文献很好地解决这一特点下的空间信息网络拓扑控制问题，所涉及的拓扑控制一般是为了在全网范围内维持相对稀疏且可靠网络连接的同时，达到减少能量消耗[20~22]、减少端到端时延[23,24]、增加网络吞吐量[25,26]、确保网络顽健性[27,28]等目的。其方法一般可以分为集中式拓扑控制[29~31]和分布式拓扑控制[31~33]2种。集中式拓扑控制算法依赖于网内能够获取全网信息的中心节点单元，并依靠该单元对全网拓扑进行计算和控制，这种拓扑控制方法一般能够得到全区最优的拓扑控制结果。但由于空间信息网络各自治域中节点节点数量多、网络跨度大、网络具有一定动态性，如果采用集中式的拓扑控制方法，将使网络中控制信息开销过大，同时也加重了对中心节点性能的要求，网络抗毁能力弱。而分布式算法则通过各自节点获取周边节点信息，并相互协同完成全网拓扑控制，不需要核心单元。但由于各节点获取的均是局部信息，拓扑控制结果无法达到最优，甚至有时网络拓扑控制结果无法保证连通性。

针对上述问题，本文提出了一种分层自治域的空间信息网络模型。该模型将空间信息网划分为一系列自治域（AS，autonomous system），每个自治域内部可采用独立的控制策略，不同自治域之间通过边界节点实现路由和控制信息的交换，各自治域可根据需要再进行下一级子自治域的划分，从而构建分层自治域的组网结构。通过这种划分，将整体上是高动态变化的空间信息网划分为一个个局部具有弱动态性变化的子网络，从而解决子网间动态耦合性和整网可控性的问题。在该模型的基础上，提出了一种自治域内的最小化时延的拓扑控制算法。不同于传统的集中式控制算法[29~31]和分布式控制算法[31~33]，该算法采用混合式的方法，将集中式控制算法和分布式控制算法分别应用到子自治域内和子自治域间的拓扑控制中。算法的主要步骤如下：1）AS内的节点自主划分为sub-AS，并选取中心节点；2）利用从成员节点收集的信息，每个中心节点采用集中控制算法使节点间的时延最小化，并保持连通性；3）各中心节点利用边界节点获取的相邻sub-AS信息，采用分布式的拓扑控制算法计算相邻sub-AS间的最小时延链路，并保证连通性。最后对算法的连通性进行了证明，并分析了算法的消息复杂度。仿真结果验证了理论分析和所提出算法的有效性。

2 网络模型

如图1所示，空间信息网包含卫星、升空平台、传感器、用户等多种异构节点，其任务、功能、地位和分布空间具有明显的差异，同时，卫星的轨道运动、升空平台随气流的运动、多种用户终端的复杂运动、网络节点的增减等都会引起网络拓扑的动态变化，网络某一局部范围内组网应用方式、业务流量和流向、拓扑结构、信号传播环境等变化都会影响到全网的状态。如果对全网采用统一的网络管理与控制，将会使网络的运行效率极其低下，甚至因控制信息过多消耗带宽而难以正常运转。

因此，结合未来空间信息网中节点种类多、立体多层分布、异构特性明显、动态差异性大等特征，根据节点属性将空间信息网划分为一系列自治域，每个自治域内部采用独立的控制策略，不同自治域之间通过边界节点实现控制信息的交换，各自治域可根据需要再进行下一级子自治域的划分，从而构建分层自治域的组网结构。通过这种划分，将整体上是高动态变化的空间信息网解耦合为一个个局部具有弱动态性变化，由相似类型节点组成的准静态子网络，从而将整网控制的复杂问题简单化。如图2所示，将空间信息网划分为4个自治域，包括由各类卫星组成的AS-1、由高空平台站组成的AS-2、由低空飞机组成的AS-3以及地面各类节点组成的AS-4。AS-1中的节点动态性高，且运动具有规律性，其拓扑控制问题主要体现为卫星星座的设计，本文暂不讨论AS-1的拓扑控制。AS-2/3/4的特点类似，自治域中的节点移动速度较慢，并通过自组织组网。本文主要讨论AS-2/3/4的拓扑控制。

考虑到自治域内的节点属性类似，为了便于分析，这里不妨假设经过划分后的自治域内节点是同构的。它们具有相同的最大传输距离。用图表示一个自治域内的拓扑结构，其中，是节点（顶点）的集合，而是链路（边）的集合。是节点和之间的距离。每个节点根据其属性（例如MAC地址）被赋予一个唯一的ID。这里，是一般图，即如果，则和能够相互交换信息。此外，假设所有的链路是对称和不受遮挡的，节点能够通过一定途径获取自己的位置信息（如GPS）。在下述的定义中，为图，而和分别为子图。

3 算法描述

空间信息网络是一个大尺度网络，尽管对其进行了自治域划分，但自治域中相当比例的链路仍具有较高的时延。若保留这些高时延链路不仅会影响整网业务信息传输的时效性，而且会降低控制信息的传输效率。同时，高时延链路往往具有较长的传播距离，意味着更高的信号发射功率，而空间信息网中部分节点的能量资源是受限的，采用短时延链路也有助于整网的能量利用效率的提高。因此，在提出的算法中，采用Min-Max的准则，优化自治域内的时延，同时保持自治域内拓扑的连通性。Min-Max是将任意一对节点之间的端到端最大时延最小化准则。该算法不需要某个单元获取自治域拓扑的完整信息，相反，算法依靠的是AS内自组织生成的sub-AS。在sub-AS中采用集中控制算法，而在sub-AS之间采用分布式控制算法。算法的具体过程分为以下3个阶段。

3.1 阶段1：sub-AS的生成

阶段1的主要目的是在AS中生成最少数量的sub-AS，每个sub-AS有一个中心节点和若干成员节点，成员节点和中心节点之间一跳互连。各个中心节点是整个算法的主要执行者。

步骤1 广播hello信息。算法开始后，AS内的各节点在范围广播hello信息使相邻节点获取彼此信息。hello信息的格式为。具体为：1）：节点的唯一ID；2）：节点的位置信息；3）：该节点当前连接的中心节点的ID，若没有连接中心节点，则值为0，若本身是中心节点，则用自身ID；4）：节点的连接度（相连节点的个数）；5）：与相邻节点交换信息的时延。

步骤2 中心节点的选取。中心节点的选取在广播hello信息后等待一段时间进行，该等待时间应保证AS内每个节点从其相邻节点至少接收到一轮hello信息。在该步骤中，自治域内的每个节点选择成为中心节点或成员节点。各节点在接收到hello信息后根据当前状态计算值，用于判断自身角色。度量应与算法的优化目标一致，这里选取作为。这里采用是为了避免出现相同的值。的计算函数为，同时，为了平衡和，如式(2)所示。其中，是和之间的平衡因子。

(3)

因此，当某节点在其相邻节点中具有最大的值，则选择其作为中心节点，每个中心节点对应一个sub-AS。经过该步骤，AS中的第一批中心节点被选出，则相应的hello信息随之更新。

步骤4 优化和保持。考虑到节点的移动性，同时为了保证中心节点的数量最小，当中心节点检测到其范围内有其他中心节点（通过周期性的hello信息），判断自身是否具有最大的值。如果不是，则将不再作为中心节点，并成为对比过程中具有最大值节点的成员节点。其成员节点变为无父节点，并转到步骤3。最终，AS中只有2种节点，即中心节点和成员节点。该步骤将监测整个AS的状态。例如，当有新节点加入AS中，将其作为无父节点，并转向步骤3。

3.2 阶段2：sub-AS内拓扑控制

在sub-AS内部，本文采用集中控制算法。中心节点负责计算sub-AS内各成员之间的相互连接关系，从而达到优化目标（Min-Max时延准则并保证连通）。算法1给出了sub-AS内拓扑控制的具体过程。其中采用表示AS，而（sub-AS）是的分割。

算法1 sub-AS内拓扑控制

Output:

Begin:

end if

end for

3.3 阶段3：sub-AS间拓扑控制

为了使相邻sub-AS获取彼此信息，各节点继续周期性广播阶段1中的hello信息。当节点收到与其不同sub-AS的节点的信息（与具有不同的），将的信息添加到其边界列表中，并将该边界列表发送给其父节点。当中心节点收集到所有成员节点发送的边界列表后，执行算法2中的操作。其中，采用表示AS，而（sub-AS）是的分割。

在算法2中，假设相邻sub-AS为和，sub-AS的中心节点采用文献[34]中的算法（）检测和之间是否存在条独立链路，即利用双向图（bipartite graph）计算最大匹配，算法中的双向图顶点分别属于和。

如果小于最大匹配的数量，则中心节点从中选取条满足Min-Max时延准则的链路。当不存在条独立链路时（仅存在条独立链路），则中心节点从中选取条满足Min-Max时延准则的链路，保持连通性。需要说明的是，此时和之间只有连通，但当算法2结束后，由于其他相邻sub-AS之间连通性的保持，整个AS内是连通的。这点将在附录中进行证明。

当阶段3完成后，中心节点将链路列表分发给各成员节点，成员节点按照链路列表更新连接关系。同时，各节点以一定的周期广播hello信息以适应拓扑的动态性，维护拓扑的优化目标。

算法2 sub-AS间拓扑控制

Output:

Begin:

end for

else

end for

end if

end for

then

end if

end for

4 控制消息复杂度分析

这里通过计算拓扑控制过程中3个阶段的控制消息交换量对控制消息复杂度进行分析。令表示AS中的总节点数量，表示AS中划分的sub-AS数目，表示sub-AS中的平均节点数量，即。令表示sub-AS中节点成为边界节点的平均概率，。令表示sub-AS周围相邻sub-AS的平均个数，。

表1给出了在各sub-AS中算法各阶段为完成拓扑控制所需要消耗的平均消息数量。表1将各阶段划分为主要步骤，给出了消耗的消息数量。则从表1中可以得到，在整个AS中，所需要的控制消息数量为。进一步化简为，其最坏情况为。

表1 对于一个sub-AS算法各阶段的消息复杂度

5 仿真结果与性能分析

由于所提出的算法是混合了中心式和分布式的混合控制算法，这里将其与典型的中心控制算法[31]以及分布式算法[31]做对比。选择这2个算法进行对比的原因是，其优化准则和本文算法同是Min-Max准则。仿真结果利用NS2软件仿真得到。

对于每次AS拓扑控制仿真，考虑如下参数。

3) 1 000次重复统计。

本文提出的混合式算法，在其阶段1 sub-AS生成的过程中，中心节点和成员节点之间均是1跳连接。对应于AS区域中不同节点数目，阶段1算法生成的各sub-AS中平均节点数目分别为6.68、7.67、8.64、9.69和10.15（1 000次统计结果）。需注意的是，通过AS区域中取不同的节点数目，并保持其他参数（如区域大小、节点的最大信息收发距离等）不变，实际上调整了算法中的节点连接度。

图3给出了在一次仿真统计过程中，所提出算法的各阶段实际拓扑控制结果。

图4给出了相同仿真条件下，3种算法拓扑控制结果中节点间最大（max）和平均（avg）时延的统计结果。需指出，仿真过程中，仅考虑了链路传播时延（实际中还可能存在处理、传输时延）。仿真条件中，节点的最大信息收发距离是350 km，对应的信息传播时延为1.167 ms。当时，本文算法将节点数目为125时的最大时延降至0.864 ms，将节点数目为225时的最大时延降至0.577 ms。相比经典的分布式算法，最大时延低9.5%~18.1%，相比中心式算法高10.9%~ 18.9%。对于平均时延，当节点数为125时，本文算法结果中节点间平均时延为0.524 ms，当节点数为225时低至0.354 ms。相比算法，平均时延低9.0%~12.1%，相比平均时延高10.8%~ 13.2%。

可以看出，本文算法统计得到的链路时延优化性能在中心式算法和分布式算法中间。这种结果是能预期的，因为本文算法是一种混合了中心式和分布式的算法。尽管中心式控制算法具有更好的链路时延优化性能（约10.8%~20.8%），但中心式控制算法并不适合空间信息网这种大尺度网络。因为中心控制算法需要一个功能强大的中心实体获取并计算AS内所有节点的控制信息，同时控制消息需要经过多跳、长时延的收发，网络的控制效率低下。相反，本文算法中拓扑控制消息被约束在各sub-AS及其相邻周围，网络控制效率高，同时其链路时延优化效果优于纯分布式的算法。因此，对于空间信息网的拓扑控制，本文提出的算法具有更好的针对性和适用性。

图5给出了本文算法的平均节点度。相比无拓扑控制的情况，显然本文算法中节点的连接度不取决于网络的规模和节点的密度。图6给出了完成本文算法平均每节点的消息交互数量。根据消息复杂度的分析，本文算法的消息复杂度是。对于每个节点，平均要求消息数量为。图6中的仿真统计结果验证了分析，当AS中的节点数目从125增加到225，平均每节点的消息交互数量并未有明显增加。综上，本文算法具有较高的效率，可用性高。

6 结束语

本文提出了空间信息网的一种分层自治域网络模型，根据节点属性将网络划分为不同的自治域和子自治域，将网内各动态因素解耦合，从而简化了整网控制的复杂问题。在该模型的基础上，提出一种最小化时延的自治域拓扑控制算法。与现有的集中式和分布式拓扑控制方法不同，该算法采用混合式的方法，其控制信息被约束在相邻子自治域范围内，控制信息开销少，更适用于空间信息网这样的大尺度网络。此外，本文还对所提出算法的强连通性进行了证明，仿真结果验证了理论分析和所提出算法的效率。

附录 算法1和算法2的k连通性证明

为了对所提出的算法1和算法2的连通性进行证明，证明结果采用如下定理1和定理2表示。

1) 算法1的连通性证明

最后，对定理1的正确性进行证明。

2) 算法2的连通性

为了证明定理2的正确性，首先证明如下3条引理。

证明 由定理1，sub-AS内部的各节点之间是连通的。这里把sub-AS看做一个节点，也即是将图表示为，其中，，。实际上，边应该至少包含和之间的条独立路径。令表示将中的sub-AS看作节点后图，其中，。用表示中的sub-AS是因为这里不需要考虑sub-AS内的拓扑结构（无论和均是连通的）。由于假设sub-AS均为节点，那么认为和表示相同的边。算法2中，每个边均有一个值。

定理2证明 由定理1可知，算法1结束后，每个sub- AS均满足。将这些sub-AS划分为集合，其中各个集合包含的sub-AS之间在中是多跳连通的，也即是，，有。这里再定义集合，其中，。由引理5可知，对于各，，有。将看作的子图，，其中，，。由于仅包含多跳连通子图，由推论1可知，是连通的。又由推论2，可知是连通的。最终可得，定理2得证。

[1] 数字通信世界. 亚太地区卫星资源指南2014[EB/OL]. http://www. dcw.org.cn/images/cover /1-1.jpg.

Digital Communication World. Satellite resource guide of ASIA-pacific area in 2014[EB/OL].http://www.dcw.org.cn/ images/cover /1-1.jpg.

[2] Union of concerned scientists, UCS satellite database[EB/OL]. http://www.ucsusa.org/nuclear_weapons_and_global_security/solutions/space-weapons/ucs-satellite-database.html.

[3] MUKHERJEE J, RAMAMURTHY B. Communication technologies and architectures for space network and interplanetary internet[J]. IEEE Communication Surveys & Tutorials, 2012, 15(2): 881-897.

[4] BHASIN K B, HAYDEN J K. Architecting communication network of networks for space system of systems[C]//IEEE System of Systems Engineering Conference. c2008: 1-7.

[5] HU H F, LIU Y A. A feasible mesh-based architecture and protocol model of space information network[C]//IEEE Geoscience and Remote Sensing Conference. c2010: 529-531.

[6] REN F, FAN J L. An adaptive distributed certificate management scheme for space information network[J]. IET Information Security, 2013, 7(4): 318-326.

[7] ZHANG G X, ZHANG W, ZHANG H, et al. A novel proposal of architecture and network model for space communication networks[C]// IAF 65th International Astronautical Congress. c2014: 1-7.

[8] 国家自然科学基金委员会. 空间信息网络基础理论与关键技术重大研究计划2015 [R]. NSFC 2015年度项目指南. 2015.

National Natural Science Foundation of China. Major research program on the basic theory and key technology in space information network[R]. NSFC Annual Program Guidelines in 2015. 2015.

[9] 葛晓虎, 刘应状, 董燕, 等. 一种基于 MESH 结构的空天信息网络模型[J]. 微电子学与计算机, 2008, 25(5): 39-42.

GE X H, LIU Y Z, DONG Y, et al. A space-sky information network model based on MESH architecture[J]. Microelectronics and Computer, 2008, 25(5): 39-42.

[10] 张登银, 刘升升. 基于 Mesh 的空间信息网体系结构研究[J]. 计算机技术与发展, 2009, 19(8): 69-73.

ZHANG D Y, LIU S S. Research on mesh-based architecture for space information network[J]. Computer Technology and Development, 2009, 19(8): 69-73.

[11] 吕本伟, 刘元安, 胡鹤飞, 等. AIR: 基于QoS保障的空天信息网络路由算法[J]. 中国科技论文在线, 2010:1-6.

LV B W, LIU Y A, HU H F, et al. AIR: QoS routing algorithm for aerospace information network[J]. Science Paper Online, 2010: 1-6.

[12] PASQUALE P, et al. Routing and scalability issues for multi-layered satellite-HAPs networks[C]//ICASSC2010. c2010:64-69.

[13] PULLIAM J, ZAMBRZ Y, ARMARKER A, et al. TSAT network architecture[C]//MILCOM 2008 IEEE. c2008: 1-7.

[14] COOK K L B. Current wideband MILSATCOM infrastructure and the future of bandwidth availability[J]. IEEE Aerospace and Electronic System Magazine, 2010, 25(12):23-28.

[15] Discover the Iridium NEXT program[EB/OL]. http://www.iridium. com/About/Iiridum NEXT.aspx.

[16] NISHIYAMA H, TADA Y, KATO N, et al. Toward optimized traffic distribution for efficient network capacity utilization in two-layered satellite networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(3): 1303-1313.

[17] LI Y J, ZHAO S H, WU J L, et al. Designing of a novel optical two-layered satellite network[C]//IEEE Computer Science and Software Engineering Conference. c2008: 976-979.

[18] YIN Z Z, ZHANG L, ZHOU X W, et al. Qos-aware multicast routing protocol for triple-layered LEO/HEO/GEO satellite IP network[C]// IEEE Global Mobile Congress. c2010: 1-6.

[19] TALEB T, FADLULLAH Z M, TAKAHASHI T, et al. Tailoring ELB for multi-layered satellite network[C]//IEEE Communications Conference. c2009: 1-5.

[20] GUO B, GUAN Q, YU F, et al. Energy-efficient topology control with selective diversity in cooperative wireless ad hoc networks: a game-theoretic approach[J]. IEEE Transactions on Wireless Communications, 2014, 13(11): 6484-6495.

[21] SHANG D, ZHANG B, YAO Z, et al. An energy efficient localized topology control algorithm for wireless multihop networks[J]. IEEE Journal of Communication and Networks, 2014, 16(4): 371-377.

[22] SARDELLITTI S, BARBAROSSA S, SWAMI A. Optimal topology control and power allocation for minimum energy consumption in consensus networks[J]. IEEE Transactions on Signal Processing, 2012, 60(1): 383-399.

[23] ZHANG X, ZHANG Y, YAN F, et al. Interference-based topology control algorithm for delay-constrained mobile ad hoc networks[J]. IEEE Transactions on Mobile Computing, 2015, 14(4): 742-754.

[24] ESLAMLU G, SABAEI M, FEREYDOONI M. Delay-constraint load-aware topology control in wireless sensor networks[C]// Telecommunications and Signal Processing. c2012: 27-31.

[25] LI D, WANG B, JIA X. Topology control for throughput optimization in wireless mesh networks[C]//Mobile Ad-hoc and Sensor Networks. c2008: 161-168.

[26] TAO W, CHEN C, YANG B, et al. Adaptive topology control for throughput optimization in wireless sensor networks[C]//IEEE Communication Technology. c2010: 1299-1302.

[27] LI M, LI Z, VASILAKOS A. A survey on topology control in wireless sensor networks: taxonomy, comparative study[J]. Proceedings of the IEEE, 2013, 101(12): 2538-2557.

[28] LIU L, LIU Y, ZHANG N. A complex network approach to topology control problem in underwater acoustic sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(12): 3046-3055.

[29] RAMANATHAN R, ROSALES-HAIN R. Topology control of multihop wireless networks using transmit power adjustment[C]//IEEE INFOCOM. c2000: 404-413.

[30] YU J, ROH H, LEE W, et al. Topology control in cooperative wireless ad-hoc networks[J]. IEEE Journal on Selected Areas in Communications, 2012, 30(9): 1771-1779.

[31] LI N, HOU J C. Localized fault-tolerant topology control in wireless ad hoc networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2006, 17(4): 307-320.

[32] WATTENHOFER R, LI L, BAHL P, et al. Distributed topology control for power efficient operation in multihop wireless ad hoc networks[C]//IEEE INFOCOM. c2001: 1388-1397.

[33] CHIWEWE T M, HANCKE G P. A distributed topology control technique for low interference and energy efficiency in wireless sensor networks[J]. IEEE Transactions on Industrial Informatics, 2012, 8(1): 11-19.

[34] AZAD A, HALAPPANAVAR M, RAJAMANICKAM S, et al. Multithreaded algorithms for maximum matching in bipartite graphs[C]// IEEE Parallel and Distributed Processing Symposium. c2012: 860-872.

Network model and topology control algorithm based on hierarchical autonomous system in space information network

ZHANG Wei, ZHANG Geng-xin, BIAN Dong-ming, GOU Liang, XIE Zhi-dong

(College of Communication Engineering, PLA University of Science and Technology, Nanjing 210007, China)

Due to the distinguishing characteristics of space information network (SIN) such as large scale, high component complexity and dynamic, a novel network model based on hierarchical autonomous system (AS) was proposed. This model divided the complex SIN into simpler AS and sub-AS networks according to node properties, link capabilities, task features, distribution areas, etc. In these AS or sub-AS networks, different control strategies could be adopted. In this way, the dynamic network was decoupled into semi-static sub-networks, and the high dynamic coupling problem among sub-networks was solved. Then, an AS network topology control algorithm based on the hierarchical autonomous system model was proposed to minimize the time delay in the SIN. Compared with most existing approaches for SIN where either the purely centralized or the purely distributed control method was adopted, the proposed algorithm was a hybrid control method. In order to reduce the cost of control, the control message exchange was constrained among neighboring sub-AS networks. It is proved that the proposed algorithm achieve logical-connectivity on the condition that the original physical topology is-connectivity. Simulation results validate the theoretical analysis and effectiveness of the algorithm.

space information network, network model, autonomous system, topology control

TN927

A

10.11959/j.issn.1000-436x.2016120

2015-05-15；

2016-05-11

国家自然科学基金资助项目（No.91338201, No.91438109, No.61571464）

The National Natural Science Foundation of China (No.91338201, No.91438109, No.61571464)

张威（1987-），男，河南商丘人，解放军理工大学博士生，主要研究方向为卫星通信、空间信息网络等。

张更新（1967-），男，浙江平湖人，博士，解放军理工大学教授、博士生导师，主要研究方向为卫星通信、空间信息网络、深空通信等。

边东明（1975-），男，山东郓城人，博士，解放军理工大学副教授，主要研究方向为卫星通信、深空通信等。

苟亮（1981-），男，湖北枝江人，解放军理工大学博士生，主要研究方向为卫星通信、深空通信、网络编码等。

谢智东（1984-），男，甘肃通渭人，博士，解放军理工大学讲师，主要研究方向为卫星通信、空间信息网络、深空通信等。