近年来,无线自组织网络(Wireless ad hoc network)以其低成本、分布式和自组织的特点带来了信息感知与交互的一场变革,并在智能交通、环境监测、灾难预警与救援、智慧医疗、战场监控、移动会议等领域有着广泛的应用前景。然而,由于无线节点的电池能量有限,无线自组织网络中节点的计算能力与通信开销仍然受到了较大的限制。为了解决这一问题,在无线自组织网络中通常需要构建虚拟骨干网来支持节点之间的相互通信。简单来讲,虚拟骨干网(Virtual backbone)是无线自组织网络中节点的一个子集,网络的路由功能被限制在虚拟骨干网中的节点上,非虚拟骨干网中的节点平时可以处于休眠状态。虚拟骨干网不仅可以节能,还能够降低网络的通信开销,避免通信过程中信号干扰、信道竞争等问题。目前,连通支配集(Connected dominating set)是用于构建无线自组织网络的虚拟骨干网的主要方法。由于较小的虚拟骨干网能够更好的增进网络的通信效率,因此,主流的虚拟骨干网的构建算法都以较小的虚拟骨干网为目标,这可以抽象为计算图的最小连通支配集(Minimum connected dominating set)的问题。由于最小连通支配集的计算是一个NP难的问题,所以一般采用近似算法来计算网络的最小连通支配集。现有的关于连通支配集工作大多关注于同构无线自组织网络,但现实中的很多无线自组织网络具有异构性。因此,本文研究异构无线自组织网络中连通支配集的构建问题。本文从以下三个方面的异构性对无线网络进行建模,并进行了相应的最小连通支配集的近似算法设计:(1)通信延迟。除了虚拟骨干网的节点数量,通信延迟也是自组织网络中虚拟骨干网构建的重要因素,这一问题在高延迟的无线自组织网络中更为关键。以水下自组织网络为例,由于电磁波在水下环境中衰减很快,因此水下自组织网络通常采用声纳进行水声通信。但是,声波在水中的传输速度(1.5*10~3米/秒)相比于电磁波(3*10~8米/秒)很慢,因此,在水下自组织网络中,不能像基于电磁波通信的陆上自组织网络一样以“跳数”为标准来衡量节点间的延迟。为了解决这一问题,本文将具有较高点对点延迟的无线自组织网络抽象为边带权的图,并设计了三个近似算法(CDS-LO-1,CDS-LO-2,CDS-LO-3),在优化连通支配集大小的同时,优化网络的通信延迟。通常使用两个参数来评价网络的通信延迟:半径(Diameter,指网络中最长的最短路)和路由开销(Routing cost,指网络中任意两点间的最短路)。CDS-LO-1对连通支配集的半径具有2的近似度,但对连通支配集的大小不具有常数近似度;CDS-LO-2对连通支配集的大小具有140的近似度,对路由开销具有6的近似度;CDS-LO-3对连通支配集的大小具有10.197的近似度,对连通支配集的半径具有12的近似度。(2)通信范围。在灾难营救等需要快速反应、通信基础设施可能受损的场景中,无线自组织网络由于灵活部署、易于组网的特性具有很大的优势。然而,受到客观条件(如反应时间、设备成本)的限制,无线节点通信能力各异,直接体现在通信范围可能各不相同。对于节点通信范围异构的无线自组织网络,现有工作未能得到较低近似度的连通支配集构建算法。本文基于经典数学问题“圆包装”(Circle packing)、“球包装”(Sphere packing)、和“球编码”(Spherical code),给出了对于节点通信范围异构的无线自组织网络常数近似度的最小连通支配集算法。基于本文的结果,在二维无线网络中,当通信范围比(网络中最大节点通信范围与最小节点通信范围之比)为(1,1.152],(1.152,1.307],…时,本文给出近似度为9.9459,11.0794,…的连通支配集算法,这一结果大幅改进了现有算法中19.708的近似度;在三维网络中,当通信范围比为(1,1.023],(1.023,1.055],…时,本文首次给出了近似度为16.02,17.02,…的具有常数近似度的连通支配集算法。(3)剩余能量。对于基于虚拟骨干网通信的自组织网络,非骨干节点在没有通信任务时可以进入睡眠状态,从而节约能量。因此,骨干节点作为中继节点要负担更多的通信任务,具有更高的能耗。骨干节点与非骨干节点能耗的不同导致网络中节点剩余能量的不同。如果使用一个固定的虚拟骨干网,那么骨干节点的能量就会较快耗尽而失效,从而导致整个网络的失效。为了解决这一问题,本文提出了两个算法(CDS-LL和E-CDS-LL)来实现节点的负载均衡,进而提高网络的生存时间。CDS-LL选择剩余能量较多的节点作为骨干节点,从而增加网络的生存时间。实验表明CDS-LL可以提高约6倍的网络的生存时间。E-CDS-LL是CDS-LL的扩展,它通过在网络运行过程中动态构建连通支配集来进一步延长网络的生存时间。相比于CDS-LL,E-CDS-LL可以提高约66%的网络生存时间。综上所述,基于具有不同的节点间通信延迟、不同的节点通信范围以及不同的节点剩余能量等异构无线自组织网络模型,本文对连通支配集的构建算法进行了研究。在理论价值上,本文在边带权图、非单位圆盘图、非单位球体图上推动了对于图论中最小连通支配集近似算法这一基本数学问题的研究;在实用价值上,除了连通支配集的大小,本文还对网络的通信延迟、生存时间等进行了优化,并通过实验证明了本文算法的有效性。