双向度有界的三维无线传感器网络拓扑控制方法

摘要

本发明涉及一种双向度有界的三维无线传感器网络拓扑控制方法，包含如下步骤：一、对任意节点u，计算其邻居节点集N

说明书

技术领域

本发明涉及一种三维无线传感器网络拓扑控制方法，具体涉及一种对三维 无线传感器网络提出的双向度有界、高效节能、分布式的拓扑控制方法，属于 三维无线网络拓扑控制领域，适合用于大规模、自组织、随机部署、环境复杂 以及节点能量有限的无线传感器网络。

背景技术

无线传感器网络是由大量具有数据采集、处理和无线通信能力的微型低功 耗传感器节点通过多跳的方式构成的自组织网络系统，其目的是协作地感知、 采集和处理网络覆盖的地理区域中感知对象的信息。无线传感器网络一般具有 大规模、自组织、随机部署、环境复杂、传感器节点资源有限、网络拓扑经常 发生变化的特点。传感器、感知器和观察者构成了无线传感器网络的三个要素。 早期对传感器网络研究，几乎完全集中于理想的二维平面，它的一项基本假设 是节点在二维平面分布。然而这种二维假设并不适用于水下网络，因为大多数 水下传感器网络系统要求节点分布在不同深度的水域中执行感知任务。

三维无线传感器网络是由部署在三维物理空间中、具有一定感知任务的传 感器节点组成的无线网络系统。现在已经有大量三维无线网络的应用，如水下 静态传感器网络、移动水下设备网络、空间环境监测、森林火灾预测、部署在 建筑物各层的无线网络等。尤其是近年来水下传感器网络研究的兴起，推动了 三维传感器网络系统的发展。

构成三维无线传感器网络的节点体积微小，计算能力和通信能力相当有限， 节点的能量依靠电池提供且不能得到后续补充。所以，传感器节点在工作过程 中的能量消耗高低直接关系到整个网络的生存时间。如果每个节点都以最大功 率进行通讯，不仅节点能量消耗非常迅速，而且必然会加剧节点之间信号的干 扰，降低通讯效率。

拓扑控制方法是一种设置每个节点发射功率即传输范围的方法，其目标是 通过控制节点的传输范围，在减少系统能量消耗的前提下，保证整个网络拓扑 的连通性和覆盖性。拓扑控制在无线传感器网络研究中具有重要意义：首先， 拓扑控制是一种重要的节能技术；其次，拓扑控制保证覆盖质量和连通质量； 再次，拓扑控制能够降低通信干扰提高MAC协议和路由协议的效率，为数据融 合提供拓扑基础；此外，拓扑控制能够提高网络的可靠性、可扩展性等其他性 能。

拓扑控制在二维平面上有大量的研究结果，但国内外目前对三维空间的拓 扑控制研究甚少。与二维无线传感器网络相比，三维无线传感器网络提出了许 多新的问题和挑战，如他的问题难度增加；计算复杂度成倍上升；现实物理结 构复杂。而且目前三维无线传感器网络的研究主要集中在其覆盖质量、连通质 量和路由等问题上。经过对现有技术的文献检索发现，目前适用于三维无线传 感器网络的拓扑控制方法有以下几个协议：

1)LMST(Local Minimum Spanning Tree)协议。文献《Applications of k-local  MST for topology control and broadcasting in wireless ad hoc networks》所提的 LMST协议能够扩展到三维网络，能够保证所处理后的网络是连通的，但是它有 可能会有很大的能量消耗，即它的能量扩展因子没有界。

2)CBTC(Cone-Based Distributed Topology Control)协议。CBTC是一个 能够保证网络连通性的基于方向的分布式算法，原来是一个用于二维无线传感 器网络的协议。麻省理工大学的Bahramgiri等人在文献《Fault-tolerant and  3-dimensional distributed topology control algorithms in wireless multi-hop  networks》中将其推广到三维空间，提出了容错的CBTC协议。其核心是检查以 u为中心的角度为α的每个三维圆锥中是否都存在一个可通信的邻居节点。他们 证明了当α≤2π/(3k)时，三维CBTC保持网络图的k-连通性。但是这种方法没 有提供能量有界和度有界的证明，而且基于方向的算法需要可靠的方向信息， 节点需要配备多个有向天线，因而对传感器节点提出了较高的要求。

3)XTC协议。Wattenhofer等人在文献《XTC：A practical topology control  algorithm for ad-hoc networks》中提出一个基于邻居的拓扑控制算法——XTC协 议。协议的计算只依赖于局部信息，每个节点只需要和邻居节点交换两次信息。 但是他们没有对XTC在三维中的拓扑结构做任何理论和实验分析。

4)3DRNG、3DGG和3DYAO。RNG、GG、YAO是三种二维无线传感器 网络的拓扑控制算法。Yu Wang等人在文献《Energy-efficient topology control for  three-dimensional sensor networks》将其推广到三维空间，并且证明了3DRNG、 3DGG和3DYAO的拓扑特性。如3DRNG具有连通性，但不具有能量支撑性； 3DGG具有连通性，其能量t-Spanner系数是1；3DYAO具有连通性、能量支撑 性和外向度有界性。

综上所述，目前所有提出的针对三维无线传感器网络的拓扑结构均没有双 向(内向和外向)度有界的性质。节点度数有界是指在生成的拓扑结构中节点 的邻居个数小于一个常数k，降低节点的度数可以减少节点转发消息的数量和路 由计算的复杂度，这对于节约能量和降低网络干扰具有重要意义。

发明内容

本发明的目的是针对现有技术的缺陷，提供一种三维无线传感器网络的拓 扑控制方法，保证其生成的拓扑结构具有双向度有界和高效节能的特性。

本发明的目的是通过以下技术方案实现的：

一种双向度有界的三维无线传感器网络拓扑控制方法，包含如下步骤：

一、针对给定三维无线传感器网络中的任意节点u，计算其邻居节点集 N_UBG(u)，即u的最大通信距离能覆盖的节点集；

二、以节点u的邻居节点集N_UBG(u)为输入，使用3DYAO算法对其进行处理， 得到u节点处理后的3DYAO邻居节点集N_YG(u)；

三、把3DYAO邻居节点集N_YG(u)向u的邻居节点集N_UBG(u)广播；

四、计算节点u的内向邻居集如果u∈N_YG(v)，那么把v加入节点u 的内向邻居集中，即

五、以节点u的内向邻居集为输入，使用与步骤二中相同的3DYAO 算法对其进行处理，得到u节点处理后的邻居节点集

六、把节点集向u的邻居节点集N_UBG(u)中所有邻居广播；

七、对于N_YG(u)中所有节点v，假如u也在中，那么就把v加入N_YYG(u) 中；

八、输出节点u的双向度有界的三维无线传感器网络拓扑N_YYG(u)，调整发 射功率为可达到N_YYG(u)中最远的邻居位置。

有益效果

本发明提出的方法是基于3DYAO的三维拓扑控制方法，具有双向度有界和 高效节能的特性，能够在本地分布式实现，达到延长网络生命周期，降低网络 干扰，提高网络吞吐率的目的。

目前国内外对三维空间的拓扑控制研究甚少，并且没有一种拓扑结构能够 具有双向度有界的性质。降低节点的度数可以减少节点转发消息的数量和路由 计算的复杂度，以达到降低网络干扰和节约能量的目的。

本发明提出的方法还具有能量支撑因子有界的特性。它集中了度数有界和 能量控制两种目前拓扑控制解决方案的优点，更大程度延长了网络的生命周期。

本发明提出的方法考虑到传感器节点有限的计算能力和通讯能力，方法复 杂度和通讯次数都比较少，并且是分布式控制，网络中的节点仅仅依靠自己常 数跳邻居的信息，不需要全局信息就能够本地构造自己的拓扑结构。

附图说明

图1是双向度有界的三维无线传感器网络拓扑控制方法的具体实现流程。

图2是使用固定划分法的3DYAO结构。

图3是使用灵活划分法的3DYAO结构。

具体实施方式

下面结合附图对本发明的实施例做详细说明：本实施例在以本发明技术方 案为前提下进行实施，给出了详细的实施方式和具体的操作过程，但本发明的 保护范围不限于下属的实施例。

图1给出了本发明所述的基于3DYAO的双向度有界的三维传感器网络拓扑 控制方法详细的流程，具体的技术实施方案如下：

步骤一：对于给定无线传感器网络中的任意节点u，计算其邻居节点集 N_UBG(u)。具体的计算方法如下：

以节点u为球心，以无线传感器节点发射功率能达到的最大通信距离R 为半径，形成一个球体。在给定的三维无线传感器网络中，如果节点v落在球 体内，那么v就是u的邻居节点。所有的节点v构成u的邻居节点集N_UBG(u)。

步骤二：使用3DYAO算法对节点u的邻居节点集N_UBG(u)进行处理，得到u 节点处理后的邻居节点集N_YG(u)。

作为本发明的优选实施方式，3DYAO算法采用固定划分法或者灵活划分法。 下面具体描述这两种划分法的3DYAO拓扑结构。

1)固定划分法：

在固定划分法中，对于任意节点，圆锥体的划分方法都相同，并且划分的 圆锥体彼此不相交。具体可以有两种划分方法：

第一种：对任意节点u，首先使用三个正交平面(xy平面、yz平面和xz平 面)把u的传输范围UBG划分成8个区域，每一个区域是1/8个球体；其次， 再使用三个平面把每一个区域划分成4个锥体，如图2(a)所示，图中所示的c1、 c2和c3分别是所在圆弧的中点。如此则把u的传输范围划分成了32个彼此不 相交的锥体。最后，在任意椎体内，对于u的邻居节点集N_UBG(u)，节点u只选 择锥体内长度最短的边uv保留，这些有向边uv形成了3DYAO拓扑结构N_YG(u)。 这种划分法形成的3DYAO结构的度数最大为32。

第二种：对任意节点u，首先使用三个正交平面(xy平面、yz平面和xz平 面)把u的传输范围UBG划分成8个区域，每一个区域是1/8个球体；其次， 使用6个平面把每一个区域划分成7个锥体，如图2(b)所示，其中，ci和ci’(i＝1，2，3) 分别是所在圆弧的三等分点。如此则把u的传输范围划分成了56个锥体。最后， 在任意椎体内，对于u的邻居节点集N_UBG(u)，节点u只选择锥体内长度最短的 边uv保留，这些有向边uv形成了3DYAO拓扑结构N_YG(u)。这种划分法形成的 3DYAO结构的度数最大为56。

2)灵活划分法：

在这种划分法中，对于不同节点来说，锥体的划分方法不同，划分的圆锥 体可以彼此相交。具体有两种划分方法：

第一种：

1a)对任意节点u，首先计算其邻居节点集；

1b)对节点u的邻居节点集中的任一邻居节点v，设PROCESSED(v)＝0；

1c)对任一邻居节点v，且有PROCESSED(v)＝0，执行以下步骤：

①以uv为轴，以一个小于π/3的角度θ为顶角，构建一个锥体；

②节点u选择锥体内最短的边uw保留，且对锥体内所有邻居节点x， 设PROCESSED(x)＝1；

1d)这些有向边uw形成了3DYAO拓扑结构N_YG(u)。

如图3(a)所示。

第二种：

2a)对任意节点u，首先计算其邻居节点集；

2b)根据节点u到邻居节点v_i的长度由小到大对u v_i进行排序，即||u v_i||≤||u v_i+1||(i由1到m，m为邻居节点个数))；

2c)对所有邻居节点v_i(i由1到m)，设PROCESSED(v_i)＝0；

2d)对邻居节点v_i(i由1到m)，假如PROCESSED(v_i)＝0，执行以下步骤：

①以u v_i为轴，以一个小于2π/3的角度θ为顶角，构建一个锥体；

②节点u选择边u v_i保留，且对锥体内所有邻居节点w，设 PROCESSED(w)＝1；

2e)这些有向边u v_i形成了3DYAO拓扑结构N_YG(u)。

如图3(b)所示。

步骤二处理之后，能够保证处理后的网络外向度数为一个常数。

步骤三：把3DYAO邻居节点集N_YG(u)向u的邻居节点集N_UBG(u)中所有邻居 广播。

步骤四：计算节点u的内向邻居集如果u∈N_YG(v)，那么把v加入节 点u的内向邻居集中，即

步骤五：以节点u的内向邻居集为输入，选取和步骤二中相同的 3DYAO算法对其进行处理，得到u节点处理后的邻居节点集

步骤五处理之后，能够保证处理后的网络内向度数为一个常数。

步骤六：把节点集向u的邻居节点集N_UBG(u)中所有邻居广播。

步骤七：对于N_YG(u)中所有节点v，假如u也在中，那么就把v加入 N_YYG(u)中。

步骤八：输出节点u的双向度有界的三维无线传感器网络拓扑N_YYG(u)，调 整发射功率为可达到N_YYG(u)中最远的邻居位置。

本发明对于邻居节点集和内向邻居集分别采用3DYAO算法进行处理。由于 3DYAO算法具有连通性、能量支撑性和外向度有界性，因此本发明构造的三维 无线传感器网络拓扑结构具有双向度有界的特性。降低节点的度数可以减少节 点转发消息的数量和路由计算的复杂度，以达到降低网络干扰和节约能量的目 的。

以上所述仅是本发明的优选实施方式，应当指出，本发明提出这种双向度 有界的三维无线传感器网络拓扑控制方法能够通过对任意满足3DYAO结构的 不同算法进行两次操作达到节约能量，双向度有界，延长网络的生存时间，降 低网络干扰的目的。对于本技术领域的普通技术人员来说，在不脱离本发明原 理的前提下，还可以做出若干改进，或者对其中部分技术特征进行等同替换， 这些改进和替换也应视为本发明的保护范围。