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

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

0 引言

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

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

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

1 核心树算法

核心树是所有节点通过相互间的父子关系所形成的树形逻辑拓扑。……