与有线网络相比,无线网络具有灵活性、易扩展性和抗毁性强等特点,被广泛应用于搜索、救援、军事、农业以及工业等诸多领域。然而,由于无线网络无基础设施,固有的扁平结构等特点,使得网络管理以及广播等问题凸显,为提高资源利用率,优化网络性能,构造一个虚拟骨干网(Virtual Backbone Network,VBN)以担当网络中的基础设施是有必要的。VBN构造在图论中等同于求解图的最小连通支配集(Minimum Connected Dominating Set,MCDS)。MCDS的求解在图论中已被证明是NP-hard问题,因此,大量的MCDS近似算法已经被提出。但是在已有的文献中所采用的通信模型一般假设节点具有足够的网络知识,强大的通信能力并且忽略节点之间发送消息产生的碰撞问题。这对于设计一个简单有效的CDS算法是相对容易的,但难以在实际中应用。另外,在无线电网络(Cognitive Radio Networks,CRNs)中,由于主要用户(Primary Users,PUs)随机活动,使得认知用户(Cognitive Users,CUs)机会地使用授权给主要用户的频谱(信道),造成链路使用的不连续性。因此,在CRNs中,具有最大寿命的CDS明显比具有更小规模CDS更受欢迎,而在传统的算法中目的为构造具有较小规模的CDS。针对上述问题,本文在匿名无线网络以及CRNs中分别提出关于MCDS的求解方案。工作内容与贡献如下:在匿名无线网络中,将网络模型化为单位圆盘图,分别提出一个分布式最小DS和局部式MCDS算法。与现存算法不同的是在构造DS和CDS的过程中本文考虑了节点之间的冲突问题。通过设置jitter,使得节点的发送时刻尽可能不同,借助节点的载波侦听能力达到减少冲突发生的目的。对于算法的设计,本文首先提出计算节点一跳邻居算法,其时间复杂度为O(log N),其中N表示网络规模的上界。随后将节点的度转化为?log N???位的二进制串,从高到低逐位传输。寻找局部具有最大度的节点作为leader,得到最小DS。对于CDS的构造,本文提出一个基于分层的L-MCDS算法。首先,选取一个源节点(一般为簇头或sink节点)作为第0层,以此层为基础,逐层迭代,将网络划分为不同的层。然后,分别在各层上选择leader,各层leader的并集即为所求CDS。在CRNs中,本文基于删除策略提出具有最大寿命的CDS构造算法。算法分为四个阶段:首先,删除网络中寿命较小的链路;然后,通过设置标志变量计算网络中连通分量的数目;接着,选取网络中具有最大寿命的链路加入到网络中,使得网络是连通的;最后,通过设置规则,在保证CDS有效的前提下,删除网络中冗余节点,以得到规模尽可能小的CDS。仿真结果表明,本文提出算法得到CDS确实比传统CDS算法(WanPJCDS,GuhaCDS,WuLiCDS以及StojmenovicCDS)得到CDS具有更好的寿命。