基于NC-MCDS算法的拓扑生成技术研究

魏恒舟，宋志群，邵国媛，陈大勇

(1.中国电子科技集团公司第五十四研究所，河北石家庄050081;2.第二炮兵驻石家庄地区军事代表室，河北石家庄050081)

0 引言

由于无线环境的复杂性、时变性以及授权网络的异构性和授权用户业务的多样性，认知无线电用户通信时使用的信道、信道的数量、使用的时间长短以及在信道上的发射功率等都是动态变化的。同时，认知无线电设备本身的移动性导致系统的拓扑动态变化，这不仅体现在拓扑结构的变化，而且体现在拓扑形式的变化。本文对认知无线电系统中拓扑可变的拓扑生成算法进行研究，采用基于图论的拓扑生成算法，包括核心树算法和最小连通支配集(MCDS)算法。

核心树算法是生成拓扑的典型算法，但在认知无线电系统中的应用还比较少见，该算法在认知无线电中的应用研究具有一定的探索意义。

MCDS 的求解是 NP 难问题［1，2］，因此，在实际应用中，通常采用近似算法求解。目前的研究也主要集中在近似算法上，算法的主要目标是在多项式时间内得到更好的近似解［3］，所以求MCDS的难点就是得出的近似连通支配集尽可能最小，尽量不含冗余支配点。网络图中的连通支配集(CDS)可以作为虚拟骨干的有效结构［4］，而较小的CDS意味着用更少的骨干节点参与消息转发，有利于降低能耗，延长网络寿命，这两点对于认知系统来说极其重要［4，5］。因此认知无线电系统中，对于 MCDS问题的研究有着重要意义。

1 核心树算法

核心树是所有节点通过相互间的父子关系所形成的树形逻辑拓扑。核心树算法全称是核心树组网路由算法(Kernel Tree Routing Algorithm，KTRA)，是一种新的Ad Hoc组网和路由算法，设计思想是在Ad Hoc网络自然拓扑结构中，利用节点间信息交互，设计树的构造算法和通信协议，重构形成一种逻辑上的树形拓扑结构［6］。本文通过核心树算法进行认知无线电系统中的拓扑生成。

核心树构造算法的基本思想是从树根开始向上生长，逐渐生成整棵树。所有节点按照到根的距离最短准则加入到树上，节点间所有通信，包括业务流量和拓扑结构维护等，都限制在这棵树上流动［6，7］。

为了避免因核心树级数过大而影响实际通信效果，限制核心树的级数最大为6级。核心树生成算法步骤如下:

①根节点启动，产生仅有一个节点的一级核心树。根节点级别固定为1。

②将能够与根节点直接通信的节点加入核心树，设置其级别为2。此时的核心树是一个2级核心树。

③未加入核心树的其他节点找出能与自身直接通信的已加入核心树节点，选择其中级别最小的节点作为父节点加入核心树，设置级别为父节点级别加1。

④未加入核心树的节点重复步骤③，直至所有的节点加入核心树。

2 NC-MCDS算法

2.1 基本概念

支配集［1，8］:设 D 是 V 的一个子集，如果集合D－V中的任何一个节点与D中的某个节点可直接通信，则称D是V的一个支配集，D中的节点称为V的支配节点。

连通图:如果2个节点之间存在一条直接或间接的(即通过其他节点中转的)通信路径，则称这2个节点是连通的，如果某图中任意2个节点是联通的，则称该图为连通图。

CDS［9］:给定一个图 G=(V，E)，图 G 的节点集D⊆V为满足如下条件的节点集合:由D导出的子图是连通图，且D是图G的一个支配集，则称D为连通支配集。若D为满足上述条件的最小节点集合，则称D为最小连通支配集。

相邻接节点:若p，q为图G=(V，E)中的任意2个节点，即p，q∈V，若存在E中的一条边连接节点p，q，则称节点p和节点q相邻。

一级邻接节点:节点x的直接邻接节点。

二级邻接节点:节点x的一级邻接节点的一级邻接节点(x除外)。

节点状态:每个节点有2种状态，分别用－1，0，1表示。节点x=－1为初始状态，节点x=0为被支配状态，节点x=1为支配状态。

节点连通度:可与某节点直接进行通信的节点的总数目称为该节点的节点连通度。选取具有最大节点连通度的节点充当支配点，可以获得更小的CDS，而且MCDS的建立时间也会加快。这样就可以减少非支配点之间冗余的无线通信链路，大大减少通信开销。

2.2 算法原理

参考 Ivan Stojmenovic等学者提出的 Ivan算法［10］、文献［11］中的集中式算法以及文献［12］中的EB-MCDS算法，将MCDS算法与基于连通度的思想相结合，提出NC-MCDS算法。算法基于若可与一个节点相连的节点数越多，则可认为这个节点越重要的思想，将其作为支配节点的优先级就应越高，进而使最终的支配集趋向于最小化。

采用最小连通支配集算法生成树状网，首先计算网络的最小连通支配集，如果最小连通支配集是树，并且满足系统的要求，则在其基础上添加分支，将剩余的节点接入;如果最小连通支配集不是树，则继续计算该网络的最小连通支配集，递归得出树状网。

2.3 算法步骤

下面介绍NC-MCDS算法的具体步骤。首先初始化所有节点，设从节点u开始，步骤如下:

①将节点u赋值为1;

②将u的一级邻接节点(处于初始状态的)赋值为0，暂时成为被支配点;

③比较u的二级节点(非支配节点)的可连接数值，选择值最大的二级节点v赋值为1，成为支配节点(若连通度相同，则可选择编号较小者，下同);

④在节点u与节点v之间的u的一级邻接节点(非支配节点)中，选连通度最大的节点的作为支配节点，赋值为1;

⑤相关节点重复步骤②～步骤④，直到网络中没有初始节点;

⑥排除终端节点被赋值为支配节点以及终端三角环路等情况，以尽量保证支配集最小;

⑦NC-MCDS算法构造结束。

至此，得出最小连通支配集，在其基础上添加叶节点，即可生成树状网。

3 仿真结果及分析

下面通过Matlab对核心树算法和NC-MCDS算法进行仿真分析。在100 m×100 m的区域中随机分布有16个认知设备节点。认知设备的通信半径为40 m，各节点可以探测到通信距离范围内的邻接节点，并可以通过预留的公共控制信道进行邻接节点间信息的交互。

同一分布情况下，最小连通支配集算法(NCMCDS)与核心树算法生成拓扑的对比情况如图1所示。为了便于区分，NC-MCDS算法没有添加终端节点，只显示最小支配集的节点，且用虚线标出了各节点的可达情况;核心树算法则完整的标出了各父子节点的连接情况。

图1 NC-MCDS算法与核心树算法生成拓扑对比

认知无线电设备在100 m×100 m范围内，分布情况变化50次过程中，NC-MCDS算法与核心树算法的核心节点数的对比情况如图2所示。NCMCDS核心节点数少于核心树的有22次，多于核心树的有14次，相等的有14次，即NC-MCDS算法占优的比例为44%，核心树算法仅为28%，二者比例超过3∶2。

图2 2种生成拓扑节点数对比(节点分布变化)

图3中，随着通信半径的增大，节点数总体呈现下降趋势。对于核心树算法与NC-MCDS算法核心节点数均有起伏变化。图3中50%的情况下，最小连通支配集算法NC-MCDS的节点数少于核心树算法的节点数;44%的情况下，最小连通支配集算法节点数等于核心树算法的节点数;6%的情况下，核心树节点数少于NC-MCDS的节点数，这是由于NCMCDS算法为最小连通支配集近似算法，可能不可避免地存在冗余节点。

图3 2种算法生成拓扑节点数对比(半径变化)

进行10次试验，每次试验进行50次随机拓扑生成，NC-MCDS的支配节点数不多于核心树的核心节点数的情况所占的比例如图4所示。从图中可以看出，NC-MCDS算法优于核心树算法的比例不小于64%，甚至可达到80%。单从图4看，NC-MCDS算法要优于核心树算法。

图4 NC-MCDS算法优于核心树算法的比例情况

4 结束语

将核心树算法、最小支配集算法与认知无线电的拓扑生成相结合，根据拓扑图的生成特性，可以为实际认知网络的组建提供理论依据。在很大的概率上(多次仿真，基本上不小于60%)，NC-MCDS算法所得的核心节点数比生成树算法计算出的核心节点数要少，从这一点来说，NC-MCDS算法要优于核心树算法;然而，MCDS的计算是 NP难问题，NCMCDS算法的复杂度也要高于核心树算法。针对认知无线电特定的应用环境及技术要求，权衡二者的其他技术指标，选择合适的算法则是一个关键问题，将针对此问题进行进一步的研究。

［1］路 纲，周明天，唐 勇，等.任意图支配集精确算法回顾［J］.计算机学报，2010，33(6):1 073 －1 087.

［2］LABRADOR M A，WIGHTMAN P M.Topology Control in WirelessSensorNetworks［M］.Berlin:Springer，2009:61－68.

［3］WU J.Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirection － nal Links［J］.IEEE Trans on Paralleland Distribu － ted Systems，2002，13(9):866－881.

［4］BLUM J，DING M，THAELER A，et al.Connected Dominating Set in Sensor Networks and MANETs［M］.Handbook of Combinatorial Optimization New York:Kluwer Academic Publishers，2004:329 －369.

［5］张 亮，赵林靖，胡 婧，等.基于认知无线电技术的802.22 标准［J］.无线电程，2007，37(1):9 －11.

［6］毛玉明，杨 宁，段景山.移动Ad Hoc网的一种新的自组织组网和路山算法［J］.电子学报，2004，32(12):161－164.

［7］万倩倩，白勇.基于邻居节点的拓扑控制算法研究与仿真［J］.无线电通信技术，2012，38(3):12 －13.

［8］路 纲，周明天，唐 勇，等.任意图支配集精确算法回顾［J］.计算学报，2010，33(6):1 073 －1 087.

［9］HAYNES T W，HEDETNIEMI S T，SLATER P J.Fundamentals of Domination in Graphs［M］.New York:Marcel Dekker Inc.，1998.

［10］STOJMENOVICL I，SEDDIGHET AL M.Internal Nodes Based Broadcasting in Wireless Network［C］∥34th Annual Hawaii International Conference on System Sciences.Hawaii，USA，2001:9 001 －9 005.

［11］GUHA S，KHULLER S.Approximation Algorithms for Connected Dominating Sets ［J］.Algorithmica，1998，20(4):374－387.

［12］凌 飞，吴振华.能量均衡的最小连通支配集分布式算法［J］.传感技术学报，2012，25(9):1 317－1 320.