异构无线自组织网络中虚拟骨干网构建算法研究

1、异构无线自组织网络中虚拟骨干网构建算法研究近年来 , 无线自组织网络 (Wireless ad hoc network) 以其低本钱、分布式和 自组织的特点带来了信息感知与交互的一场变革 , 并在智能交通、环境监测、灾 难预警与救援、智慧医疗、战场监控、移动会议等领域有着广泛的应用前景。然 而,由于无线节点的电池能量有限 , 无线自组织网络中节点的计算能力与通信开 销仍然受到了较大的限制。为了解决这一问题 , 在无线自组织网络中通常需要构建虚拟骨干网来支持节 点之间的相互通信。简单来讲 , 虚拟骨干网 (Virtual backbone) 是无线自组织网 络中节点的一个子集 , 网络的路由功能

2、被限制在虚拟骨干网中的节点上 , 非虚拟 骨干网中的节点平时可以处于休眠状态。虚拟骨干网不仅可以节能 , 还能够降低网络的通信开销 ,防止通信过程中信 号干扰、信道竞争等问题。目前 , 连通支配集 (Connected dominating set) 是用 于构建无线自组织网络的虚拟骨干网的主要方法。由于较小的虚拟骨干网能够更好的增进网络的通信效率 , 因此,主流的虚拟 骨干网的构建算法都以较小的虚拟骨干网为目标 , 这可以抽象为计算图的最小连 通支配集 (Minimum connected dominating set) 的问题。由于最小连通支配集的 计算是一个NP难的问题,所以一般采用近似

3、算法来计算网络的最小连通支配集。现有的关于连通支配集工作大多关注于同构无线自组织网络 , 但现实中的很 多无线自组织网络具有异构性。因此 , 本文研究异构无线自组织网络中连通支配 集的构建问题。本文从以下三个方面的异构性对无线网络进行建模 , 并进行了相应的最小连 通支配集的近似算法设计 :(1) 通信延迟。除了虚拟骨干网的节点数量 , 通信延迟也是自组织网络中虚拟骨干网构建的重要因素, 这一问题在高延迟的无线自组织网络中更为关键。以水下自组织网络为例 ,由于电磁波在水下环境中衰减很快 , 因此水下自组 织网络通常采用声纳进行水声通信。 但是, 声波在水中的传输速度 (1.5*103 米/ 秒

4、)相比于电磁波 (3*108 米/ 秒)很慢,因此, 在水下自组织网络中 , 不能像基于 电磁波通信的陆上自组织网络一样以“跳数为标准来衡量节点间的延迟。为了解决这一问题 , 本文将具有较高点对点延迟的无线自组织网络抽象为边带权的图,并设计了三个近似算法(CDS-LO-1,CDS-LO-2,CDS-LO-3),在优化连通 支配集大小的同时 ,优化网络的通信延迟。通常使用两个参数来评价网络的通信 延迟：半径(Diameter,指网络中最长的最短路)和路由开销(Routing cost,指网 络中任意两点间的最短路 )。CDS-LO-1对连通支配集的半径具有2的近似度，但对连通支配集的大小不具 有

5、常数近似度;CDS-LO-2对连通支配集的大小具有140的近似度，对路由开销具 有6的近似度;CDS-LO-3对连通支配集的大小具有10.197的近似度,对连通支配 集的半径具有 12的近似度。 (2) 通信范围。在灾难营救等需要快速反响、通信根底设施可能受损的场景中 , 无线自组织 网络由于灵活部署、 易于组网的特性具有很大的优势。 然而,受到客观条件 (如反 应时间、设备本钱 ) 的限制 , 无线节点通信能力各异 , 直接表达在通信范围可能各 不相同。对于节点通信范围异构的无线自组织网络 ,现有工作未能得到较低近似度的 连通支配集构建算法。 本文基于经典数学问题 “圆包装 (Circle

6、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, 的具有常数

7、近似度的连通支配集 算法。 (3) 剩余能量。对于基于虚拟骨干网通信的自组织网络 , 非骨干节点在没有通信任务时可以 进入睡眠状态 , 从而节约能量。因此, 骨干节点作为中继节点要负担更多的通信任 务, 具有更高的能耗。骨干节点与非骨干节点能耗的不同导致网络中节点剩余能量的不同。 如果使 用一个固定的虚拟骨干网 ,那么骨干节点的能量就会较快耗尽而失效 ,从而导致 整个网络的失效。为了解决这一问题，本文提出了两个算法(CDS-LL和E-CDS-LL)来实现节点 的负载均衡，进而提高网络的生存时间。CDS-LL选择剩余能量较多的节点作为骨 干节点 , 从而增加网络的生存时间。实验说明CDS-LL可以提高约6倍的网络的生存时间。E-CDS-LL是 CDS-LL的扩展, 它通过在网络运行过程中动态构建连通支配集来进一步延长网络的生存 时间。相比于CDS-LL,E-CDS-LL可以提高约66%勺网络生存时间。综上所述，基于 具有不同的节点间通信延迟、 不同的节点通信范围以及不同的节点剩余能量等异 构无线自组织网络模型 , 本文对连通支配集的构建算法进行了研究。在理论价值上 ,