无线光通信网络拓扑形成问题研究∗

程 朴 覃慧玲

（1.华中光电技术研究所-武汉光电国家实验室 武汉 430223）（2.中国船舶重工集团公司第七二二研究所 武汉 430223）

1 引言

无线光通信［1］是以激光为载体来传递信息的一种通信方式。无线光通信网络是无线光通信与移动自组织网络相结合的产物。无线光通信网络具有无中心、自组织、可快速展开、可移动和多跳等特点，它通过多跳数据的传递能够绕开各种障碍物，实现远距离的跨节点通信，拓展了无线光通信的作用距离和覆盖范围；它通过无中心分布式对等网络［2］的组成，实现了各通信节点的自组织功能，有效降低了局部链路失效带来的全局瘫痪风险，提高了网络的健壮性和灵活性。

无线光通信网络初始化过程中，一个通信节点面临着多个候选通信对象，而节点内通信收发机的数量又是有限的（即节点的度），因此，需要获得一种拓扑形成（拓扑控制）算法来实现通信链路的优化选择，以期形成连通的最优网络拓扑结构。目前，国内外已有一些针对无线光通信网络拓扑结构方面的研究［3］。拓扑控制主要是利用Heuristic方法［4］计算一种最优的拓扑，使得物理层的误码率与网络层的拥塞率都达到最小；文献［5］中，主要是针对无线光通信网络中环形拓扑的控制进行研究。文献［6］研究FSO的重点是通过控制网络拥塞最小的拓扑结构来实现动态重构。文献［7］中提出了一种新的分组无线网络拓扑控制（NTC）的算法，以实现高吞吐量的连接。本文主要以无线光通信网络树形结构为对象，将网络的拓扑形成问题转换为度约束最小生成树（DCMST）问题，并引入了一种快速近似算法来加以求解。

2 问题描述

无线光通信网络的拓扑形成的目的是优化选择网络中各节点的通信对象，建立节点间的通信传输路径，实现网络各节点的互连互通。结合图论理论，可以将无线光通信网络用图论的方式加以表达。由于无线光通信网络点对点间的通信链路往往是双向的传输的，因此无线光通信网络的连通图可以当作无向图［8］

G=(V,E,W)，其中，V={1,2,…,n}为顶点集，代表无线光通信网络中节点的集合；E为边集，代表各通信节点间潜在链路的集合；W=(wij)n×n为权矩阵，且wij=wji，wii=+∞，代表通信传输代价，可用通信距离、延时、误码率等参数来衡量；各顶点的度约束设为bi{i=1,2,…,n}，代表节点i内通信收发机的数目。

图论中，无圈的连通图称为树。如果存在子图T包含G中所有顶点和一部分边，且不形成回路，则称T为图G的生成树。代价最小的生成树则称为最小生成树（MST）。当节点度受限时，这种带有顶点度约束的最小生成树问题被称之为度约束最小生成树（DCMST）问题。因此，无线光通信网络节点通信收发机数量受限的情况下，其最优拓扑的形成问题就转化为图G度约束最小生成树的问题，其数学模型可表述如下：

这里，变量集合S中所含图G的顶点个数，约束（2）、（3）保证了所求得的为棵生成树，约束（4）为度约束。

3 算法的实现

就一般情形而言，度约束最小生成树的问题是一个NP完备的难解问题，曾经出现过的一些精确算法（如分支定界法等［9］）都是指数时间的，无法求解中型以上规模的实际问题［10］。本文这里引入了一种快速近似算法，经证明其计算时间复杂度为O(n2log2n2)，可对一般意义下的DCMST问题进行求解［11］。

针对模型，该快速近似算法的其核心是，在不违反度约束和不形成圈的前提下，每次加入权最小的边，直至加入n-1条边为止。该算法的具体步骤如下：

1）G的边权矩阵（第i列表示图G的第i条边，的第i列的前两行储存第i条边关联的顶点编号，第3行储存第i条边的权），对边权矩阵按照边的权进行从小到大排序，设排序后的矩阵为BW。

2）由各顶点的度约束bi(i=1,2…,n)，生成各顶点的初始度检查值di=bi(i=1,2…,n)。

3）将BW中具有最小权的边（为BW的第一列）及该边所关联的顶点（不妨设该边所关联的顶点为i1和j1）加入到图T中，修改这两个顶点度的检查值：将和对应的度检查值减去1（即：，并从BW中删除该边更新BW。

4）检查BW的第1列对应的边是否可以用：如果该边所关联的顶点的度检查值都大于0，而且将该边加入到图T后，图不会形成圈，则BW的第1列对应的边可以用，否则该边不可以用，从BW中删除该边，更新BW，直到BW的第1列对应的边可以用为止。转入步骤5）。

5）检查图中边的数目是否小于n-1，如果图中边的数目不小于n-1，则已经找到一棵近似度约束最小生成树，转步骤6）；否则将BW中具有最小权的边（为BW的第一列）及该边所关联的顶点加入到图中，并将该边所关联的顶点（不妨设该边所关联的顶点为ik和jk），所对应的度检查值减去1（即：，并从BW中删除该边更新BW，转步骤4）。

计算图的总权重，输出图及总权重。

图1 无线光通信网络示意图

4 计算机仿真

假设存在如下图所示的无线光通信网络，网络中通信节点分别为1、2、3…、9，图中画出了各节点之间的潜在链路，各通信节点的收发机数量统一限制为3，即各节点度约束为3。

若以节点间的距离作为权，则给定上述网络图G的权矩阵为W，矩阵各元素的大小设定如下：

若考虑无线光通信节点间通信的最大作用距离为18，则上述矩阵亦可表达为如下权矩阵：

对于上述实例，无线光通信网络其度约束最小生成树的最优解为{(1,3)(1,2)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}和{(1,3)(2,3)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}生成树的最小权值为35；利用第3节给出的求取度约束最小生成树的算法步骤，可以得到度约束最小生成树的最优解为{(1,3)(1,2)(6,8)(7,9)(1,4)(5,7)(2,8)(4,5)}，其最小权值为35。

5 结语

通过对无线光通信网络拓扑形成实例的计算表明，将无线光通信网络的拓扑形成转换为图论的DCMST问题［12］，可以获得网络近似最优的树形拓扑结构，为网络链路的选择和建立提供了参考。由于该算法并不保证每个通信节点达到其度的上限，导致获得的网络仅仅是连通，因此还需进一步研究利用其节点度的空余来增加冗余链路的问题，使其网络更加健壮。此外，该算法还只适用于集中处理，因此还有必要进一步研究相关分布式算法。

参考文献

［1］张斯珩.我国光纤通信技术的发展研究［J］.民营科技，2015（11）：85.

［2］Hirya Richard Edymond.Using a Directional Antenna to Achieve Quality Transmission on a Wireless Ad Hoc Net⁃work under Jamming Attacks［D］.长沙：湖南大学，2013.

［3］Zhuang J F，Casey M J. Multi-objective optimization techniques in topology control of free space optical net⁃works.IEEE Mi ICOM，Maryland University，MD.USA，2004：430-435.

［4］刘锋，何东武，袁学海.模糊时间预测系统的Heuristic模型的改进［J］.辽宁师范大学学报（自然科学版），2002，25（2）：116-119.

［5］Desai A，Topology control and routing over wireless optical backbone networks［M］.Technical Report，Department of Electrical Engineering，University of Maryland，2003.

［6］ A.Desai and S.Milner，Autonomous reconguration in free-space optical sensor networks［J］.IEEE J.Sel.Areas Commun.2005（23）：1556-1563.

［7］L.Hu，Topology control for multihop packet radio networks［J］.IEEE Trans Commun，1993（41）：1474-1481.

［8］冷明.基于多水平方法的无向图剖分及其在VLSI设计中的应用研究［D］.上海：上海大学，2008.

［9］顾立尧.带有度约束的最小耗费生成树的分支限界算法［J］.计算机应用与软件 ，1989，6（6）：49-54.

［10］马良，蒋馥.度约束最小生成树的快速算法［J］.运筹与管理，1998，7（1）：1-5.

［11］宋海洲.求解度约束最小生成树的快速近似算法［J］.系统工程学报，2006，21（3）：232-236.

［12］黄敏，李尔达，袁媛，郑健.基于路网拓扑的聚类分析算法研究与实现［J］.中山大学学报（自然科学版），2015 ，54（6）：99-103.