基于改进广度优先搜索的无线传感网树状拓扑生成方法

摘要

本发明提供了一种基于改进广度优先搜索的无线传感网树状拓扑生成方法，用于无线传感网拓扑管理。本发明在传统广度优先搜索策略的基础上综合考虑传感器节点剩余能量、节点负载估计模型、传感器节点子节点数目，在拓扑生成过程中，限制网络中各个传感器节点最大子节点数目，引入节点负载估计模型以及随机化的父节点选择模型，新加入节点依概率优先选择负载估计值低的节点作为父节点。本发明能有效均衡网络中传感器节点的负载，延长网络生存时间。

说明书

技术领域

本发明涉及无线传感网拓扑管理技术领域，具体涉及一种基于改进广度优先搜索的无线 传感网树状拓扑生成方法。

背景技术

近年来，无线传感网(Wireless Sensor Networks,WSN)被广泛地应用在各个领域以提供 大规模的数据感知与收集，比如环境监测，火情监控等。无线传感网是一种由部署在监测区 域的低能耗、低成本、微型传感器节点，以自组织、自配置的方式构成的多跳大规模无线通 信网络，用来为各类上层应用提供基本的信息感知、传输与汇聚。在网络中，传感器节点能 对自身感知数据与来自子节点感知数据进行融合，减少数据冗余。由于无线传感网络的巨大 潜力以及现代无线通信技术、微型传感器技术的发展，无线传感网在军事、医疗、环境、交 通等领域中都具有广阔的应用前景。

在很多应用中，无线传感网采用典型的多对一、汇聚的通信模式，即随机部署在监测区 域的传感器节点通过树状网络拓扑将感知信息传递给汇聚节点。如图1所示，在无线传感网 中，传感器节点通过多跳无线通信的方式将感知信息传递给汇聚节点，是一种典型的多对一、 汇聚的通信模式。不可避免地，在一个传感网中，各传感器节点的子节点数目可能分布不均 匀，因此，部分节点可能因承担过大的数据转发任务而过早耗尽能量，而另一方面，无线传 感网一般是一次性部署、不可充电、不可替换的，网络节点能耗的不均衡可能导致整个网络 因少部分节点的连通中断而过早瘫痪。

为了方便网络的管理，无线传感网通常采用树状的网络拓扑结构，如图2所示，网络的 汇聚节点相当于树的根，各传感器节点相当于树的子节点，各传感器节点又有自己的子节点； 各节点间的链路表示传感器节点间的通信链路；每个传感器节点都将自身的感知数据及子节 点的感知数据加以汇聚、融合然后传递给父节点，经过各节点层层传递，所有的感知数据最 终汇聚到汇聚节点。

传统的无线传感网树状拓扑生成方法一般都是基于广度优先搜索(Breadth-first Search，BFS) 策略的，通过生成的树状拓扑的叶子节点迭代地向周围节点发现新节点的方式拓展生成树， 最终将所有的传感器节点加入到生成树中。文献1：Cormen T H,Leiserson C E,Rivest R L,et al. Introduction to algorithms[M].Cambridge:MIT press,2009,pp.531-539，公开了一种能有效地生 成连通的网络拓扑结构的方法，但该方法容易造成传感器节点负载分布不均匀，影响网络生 存时间。

发明内容

针对现有问题，本发明提供一种基于改进广度优先搜索的无线传感网树状拓扑生成方法， 通过限制传感器节点的最大子节点数，并引入动态的节点负载估计及随机化的拓扑生成控制， 从而能有效均衡网络中传感器节点的负载，延长网络生存时间。

本发明的基于改进广度优先搜索的无线传感网树状拓扑生成方法，定义三种颜色标记示 传感器节点状态：WHITE表示节点尚未连接到网络，GRAY表示节点已连接到网络但其子节 点集合还未确定，BLACK表示节点已经连接到网络并且该节点的子节点集合已经确定。首先， 设置节点负载估计参数q和最大子节点数目c，在当前网络拓扑T下，定义l_i(T)为节点i的负 载估计值，L_i(T)为节点i的估计生存时间，如公式(1)所示：

其中，设节点i的父节点为p_i，表示节点i与父节点p_i的距离，E_i表示节点i的初始 能量，表示节点数据传输能耗，表示数据接收能耗；

表示节点i的估计传输数据量，如式(2)所示：

$D_i^{Tx}\left(T\right)=B·w_0+D_i^{Rx}\left(T\right)---\left(2\right)$

表示节点i的估计接收数据量，如式(3)所示：

$D_i^{Rx}\left(T\right)=B·(w_1·N_i^1(T)+w_2·N_i^2(T)+...w_q·N_i^q(T\left)\right)---\left(3\right)$

其中，B表示传感器节点单位时间感知数据量，表示节点i的m跳距离的子节点 个数，w_m表示节点i的m跳距离的子节点的权重，m＝1,2,…q；权重w₀,w₁,…,w_q的取值范围 均为[0,1)且w₀≥w₁≥…w_q。汇聚节点的负载估计值设为0。

然后对网络中的任意一个传感器节点v，进行下面步骤1～步骤16。

步骤1，对节点v进行初始化设置，具体是：设置节点v的父节点P[v]为空，节点v的颜 色标记C[v]为WHITE，节点v的子节点数量CN为0，节点v的子节点更新完成标记为F， 子节点更新完成标记包含两个取值F和T，F表示未完成，T表示完成；

步骤2，判断节点v是否为网络的汇聚节点，如果是，将颜色标记C[v]设置为GRAY， 父节点P[v]设置为v，然后执行步骤3；如果否，直接执行步骤3；

步骤3，判断节点v的颜色标记C[v]是否为GRAY，如果否，执行步骤4；如果是，跳转 到步骤10执行；

步骤4，判断节点v的颜色标记C[v]是否为WHITE，如果是，执行步骤5；如果否，结 束对节点v的执行过程；

步骤5，等待t秒，监听相邻节点的加入请求消息，将发出加入请求消息的节点加入到自 己的候选父节点集合CP[v]；设CP[v]中包含n个候选父节点P₁,P₂,…,P_n，n为正整数；

步骤6，获得节点P₁,P₂,…,P_n的负载估计值，得到对应的估计生存时间L₁，L₂…L_n，划分 n个取值区间S₁,S₂,…S_n；其中，$S_1=[0,L_1),S_j=[\underset{x=1}{\overset{j-1}{\Sigma }}{L}_x,\underset{x=1}{\overset{j}{\Sigma }}{L}_x),j=2,3...n;$

步骤7，按照均匀分布生成[0,L₁+L₂…L_n)之间的随机数R；

步骤8，确定R所在取值区间S_y，将节点v的父节点P[v]更新为节点P_y，并向P_y发送父 节点请求消息；确认后，将颜色标记C[v]更新为GRAY；

步骤9，跳转到步骤3执行；

步骤10，找到节点v的所有相邻节点，并加入节点集N[v]；

步骤11，判断N[v]是否为空集及CN是否小于c，若N[v]为空集或CN不小于c，转步骤 12执行；否则，转步骤14执行；

步骤12，判断节点v的子节点更新完成标记是否为T，若是，则将C[v]更新为BLACK， 然后结束对节点v的执行过程；若否，执行步骤13；

步骤13，更新节点v的子节点信息以及负载估计值，再跳转到步骤12执行；处理相邻 节点的父节点请求消息，更新节点v的子节点数量CN、负载估计值和子节点更新完成标记；

步骤14，从N[v]中取出一节点u；

步骤15，判断节点u的颜色标记C[u]是否为WHITE，若是，转步骤16执行，若否，转 步骤11执行；

步骤16，请求节点u将C[u]设置为GRAY，将P[u]设置为v，然后跳转到步骤11执行。

本发明从无线传感网树状拓扑生成问题出发，在传统的基于广度优先搜索策略的树状网 络拓扑生成方法基础上，提出了一种基于改进广度优先搜索策略并结合节点负载动态估计与 随机化父节点选择机制的树状网络拓扑生成方法，相较于传统方法，具有如下优点：

(1)本发明方法更好地均衡了网络节点的负载，均衡了各节点能耗，有效延长了网络的 生存时间。

(2)与其他树状拓扑生成算法相比，本发明既考虑了均衡网络中各节点的子节点数目， 又考虑了节点传输效率，并提出随机化父节点选择机制有效地保证了无线传感网树状拓扑生 成的稳定性，最终生成能量有效的树状网络拓扑。

(3)本发明的无线传感网树状拓扑生成方法充分考虑了当前普通无线传感网的网络结构 与传感器节点功能特性，并提出了分布式的实现方式，具有较高的可行性和较广的适用性。

附图说明

图1是无线传感网的应用场景图；

图2是树状的无线传感网拓扑结构图；

图3是传统无线传感网树状拓扑生成的流程示意图；

图4是本发明的基于改进广度优先搜索的无线传感网树状拓扑生成方法整理流程图；

图5是本发明更新子节点信息以及负载估计值的方法流程图；

图6是本发明仿真实验的仿真结果示意图。

具体实施方式

下面将结合附图和实施例对本发明作进一步的详细说明。

传统基于广度优先搜索的无线传感网树状拓扑生成方法中，搜索从根节点，即传感网的 汇聚节点出发，每当一个节点新加入到树状网络后，搜索节点的其他相邻节点尚未加入到网 络中，一旦发现还有相邻节点没有加入到网络中，该搜索节点通知该相邻节点加入到网络， 并且搜索节点自己作为新加入节点的父节点；通过新加入到网络中的节点迭代地搜索新的相 邻节点最终生成以汇聚节点为根的树状拓扑结构。

定义三种颜色作为传感器节点状态标记(WHITE，GRAY，BLACK)，WHITE表示节点 尚未连接到网络，GRAY表示节点已连接到网络并且可能存在相邻传感器节点尚未连接到传 感网，BLACK表示节点已经连接到网络并且所有的相邻节点都已经连接到网络。

如图3所示，传统无线传感网树状拓扑生成的流程如下：

对于任意传感器节点v，执行下面(1)～(8)；

(1)初始化，将父节点P[v]设置为空(EMPTY)，将颜色标记C[v]设置为WHITE；

(2)判断自己是否为网络的汇聚节点，如果是汇聚节点，则将父节点P[v]设置为 EMPTY，并且将颜色标记C[v]设置为GRAY；

(3)判断自己的颜色标记C[v]是否为GRAY，如果C[v]不是GRAY，则跳转到步骤(4)； 如果C[v]为GRAY，则跳转到步骤(5)；

(4)判断自己的颜色标记C[v]是否为WHITE，如果C[v]为WHITE，则v保持监听状 态，监听邻居节点发来的消息，并根据消息包的要求更新自己的父节点P[v]以及颜色标记C[v]， 完成更新后，跳转到步骤(3)；如果C[v]不为WHITE，则跳转到步骤(8)；

(5)广播消息包给相邻节点，获得邻居节点信息，将所有邻居节点ID加入到相邻节 点集合N[v]；

(6)判断N[v]是否为空集，如果N[v]是空集，则将自己的颜色标记更新为BLACK， 再跳转到步骤(8)；如果N[v]不是空集，则从v的相邻节点集合中取出一个节点，记作u；

(7)判断u的颜色标记C[u]是否为WHITE，如果C[u]为WHITE，则通知节点u将其 颜色标记C[u]以及父节点P[u]分别更新为GRAY以及v。下一步，跳转到步骤(6)；

(8)结束。

如上述所示，在步骤(5)中，对于网络中任意一个传感器节点v，只要其颜色标记为 GRAY，便广播消息给处于监听状态的其他相邻节点，周围颜色标记为WHITE的其他节点收 到v的广播消息之后便以v为父节点连接到传感网，不可避免地，当v相邻节点数目过大时， 以v为父节点的传感器节点数目也就相应地比较大，从而使v承担过重的数据转发任务，导 致v过早耗尽能量，影响网络的生存时间。另外，传统基于广度优先搜索的无线传感网树状 拓扑生成方法并未考虑传感器节点的剩余能量。对于剩余能量少的传感器节点，其所拥有的 子节点数目应该也相应的减少。

针对上述问题，本发明在传统广度优先搜索策略的基础上综合考虑传感器节点剩余能量、 节点负载估计模型、传感器节点子节点数目，提供了一种基于改进广度优先搜索的无线传感 网树状拓扑生成方法。

具体地，本发明方法中进行了下面方面的改进。

(1)首先，限制网络中各个传感器节点最大子节点数目。

(2)其次，引入节点负载估计模型。

本发明采用自由空间电磁波传播模型，传感器节点数据传输/接收能耗分别表示如下。

数据传输能耗E_Tx(d,k)表示为：

E_Tx(d,k)＝E_elec×k+ε_amp×k×d²  (1)

数据接收能耗E_Rx(d,k)表示为：

E_Rx(d,k)＝E_elec×k  (2)

其中，E_elec表示传感器节点的电路能耗，k表示数据量的大小，ε_amp表示功放能耗，d表示 节点间距离。

对于网络中的任意传感器节点i，定义l_i(T)为在当前网络拓扑T中节点i的负载估计值， L_i(T)为节点i的估计生存时间，如公式(3)所示，L_i为l_i的倒数。在计算负载过程中，可将 下面公式(2)～(5)中的网络拓扑T省略，例如l_i(T)简写为l_i，L_i(T)简写为L_i。

其中，E_i表示节点i的初始能量，设节点i的父节点为p_i，表示节点i与父节点p_i的距 离，及分别指节点i的估计传输数据量与估计接收数据量，二者分别为：

$D_i^{Rx}\left(T\right)=B·(w_1·N_i^1(T)+w_2·N_i^2(T)+...w_q·N_i^q(T\left)\right)---\left(4\right)$

$D_i^{Tx}\left(T\right)=B·w_0+D_i^{Rx}\left(T\right)---\left(5\right)$

其中，及w_m(m＝1,2,…q)分别表示节点i的m跳距离的子节点个数及其相应的权 重，B表示传感器节点单位时间感知数据量，q指节点负载估计参数，可以根据实际情况设置， 本发明通过大量实验，确定在不同q值情况下节点负载估计值的表现，一般设置为3～5时节 点负载估计模型表现比较好。针对不同的数据融合模型取不同w_m分布，一般权重w₀,w₁,…,w_q的取值范围均为[0,1)，且w₀≥w₁≥…w_q，若各级节点能对接收数据进行线性数据压缩，压缩 率r∈(0,1),则w_i＝rⁱ。

本发明在生成传感网树状拓扑过程中，各个传感器节点动态地更新其m(m＝1,2,3…q) 跳子节点数量信息通过联立公式(1)～(5)可动态地估计节点的负载情况。

对于汇聚节点，因为传感网中，一般能对汇聚节点供电，可将其估计生存时间视为无穷 大，所以它的负载估计值记作常数0。

(3)引入随机化的父节点选择模型。本发明的网络拓扑生长过程中，新加入到网络的传 感器节点可能有多个候选父节点，新加入节点依概率优先选择负载估计值低的节点作为父节 点，以此均衡节点能耗延长网络生存时间。

同样，本发明方法中定义三种颜色(WHITE，GRAY，BLACK)表示传感器节点状态， WHITE表示节点尚未连接到网络，GRAY表示节点已连接到网络但其子节点集合还未确定， BLACK表示节点已经连接到网络并且其子节点集合已经确定。下面结合图4来说明本发明基 于改进广度优先搜索的无线传感网树状拓扑生成方法的具体实现步骤。首先，设置节点负载 估计参数q和最大子节点数目c，然后对网络中的任意一个传感器节点v，进行下面步骤1～ 步骤16。

步骤1，初始化。将节点v的父节点P[v]设置为空(EMPTY)，节点v的颜色标记C[v] 设置为WHITE，子节点更新完成标记FINISHED设置为F，子节点数量CN设置为0。子节 点更新完成标记包含两个取值F和T，F表示未完成，T表示完成。

步骤2，判断节点v是否为网络的汇聚节点，如果是汇聚节点，则将父节点P[v]设置为其 自身v，并且将颜色标记C[v]设置为GRAY，然后执行步骤3；如果否，直接执行步骤3。

步骤3，判断节点v的颜色标记C[v]是否为GRAY，如果C[v]不是GRAY，则执行步骤4； 如果C[v]是GRAY，则跳转到步骤10执行。

步骤4，判断C[v]是否为WHITE，如果C[v]是WHITE，执行步骤5；如果C[v]不是WHITE， 那么此时节点v的颜色标记应为BLACK，此时结束对节点v的执行过程。

步骤5，等待t秒，监听相邻节点的加入请求消息，将这些发出加入请求消息的节点加入 到自己的候选父节点集合CP[v]中。设CP[v]中包含n个候选父节点，n为正整数。t表示时间， 为正数。此处的加入请求消息是指相邻节点请求节点v作为子节点的消息。

步骤6，获得候选父节点P₁，P₂…P_n的负载估计值和估计生存时间，设P₁，P₂…P_n的估 计生存时间分别为L₁，L₂…L_n；划分n个取值区间S₁,S₂,…S_n。

对于CP[v]中的节点P_i(i＝1,2,…,n)，利用公式(1)～(5)来计算节点P_i的负载估计值 和估计生存时间。首先根据公式(4)和(5)确定该节点P_i的估计接收数据量与估计 传输数据量然后根据公式(1)和(2)确定该节点P_i的数据传输能耗和数据接收能 耗，最后根据公式(3)来确定节点P_i的负载估计值和估计生存时间。设节点P₁，P₂…P_n的 负载估计值分别为l₁，l₂…l_n，P₁，P₂…P_n的估计生存时间L₁，L₂…L_n。

$S_1=[0,L1),S_2=[L_1,L_1+L_2),...,S_j=[\underset{x=1}{\overset{j-1}{\Sigma }}{L}_x,\underset{x=1}{\overset{j}{\Sigma }}{L}_x),...,S_n=[L_1+L_2...L_{n-1},L_1+L_2...L_{j-1}+L_n);j=2,3...n.$

步骤7，按照均匀分布生成[0,L₁+L₂…L_n)之间的随机数，记作R。

步骤8，确定R所在取值区间S_y，y的取值范围为[1,2,…,n]，将节点v的父节点P[v]更新 为节点P_y，并向P_y发送父节点请求消息；确认后，将颜色标记C[v]更新为GRAY。

步骤9，跳转到步骤3执行。

步骤10，找到节点v的所有相邻节点，将其加入节点集N[v]。

步骤11，判断N[v]是否为空集及CN是否小于c，若N[v]为空集或CN不小于c，则跳转 到步骤12；否则，跳转到步骤14执行。

步骤12，判断节点v的子节点更新完成标记FINISHED是否为T，若FINISHED为T， 则将C[v]更新为BLACK，然后结束对节点v的执行过程；如果FINISHED为F，则执行步骤 13。

步骤13，更新节点v的子节点信息以及负载估计值，再跳转到步骤12执行。

步骤14，从N[v]中取出一节点，标记为节点u。

步骤15，判断节点u的颜色标记C[u]是否为WHITE，如果C[u]是WHITE，则跳转到步 骤16执行；如果C[u]不为WHITE，则跳转到步骤11执行。所有的节点初始化时，节点的颜 色标记都为WHITE。

步骤16，请求节点u将C[u]和P[u]分别设置为GRAY和v，然后跳转到步骤11执行。

对于任意传感器节点v，如图5所示，步骤13中更新节点v的子节点信息以及负载估计 值，通过如下步骤实现：

步骤13.1，等待s秒，监听相邻节点的父节点请求消息，并将所有的父节点请求消息置 入消息队列；此处的父节点请求消息是指相邻节点请求节点v作为父节点的消息。s表示时间， 为正数。

步骤13.2，判断消息队列是否为空，如果消息队列为空，则跳转到步骤13.5；如果消息 队列不为空，则取出队首的父节点请求消息M[u]，u表示发送该父节点请求消息的节点；

步骤13.3，将节点u加入到v的子节点集合，并更新节点v的子节点数量CN＝CN+1；

步骤13.4，通知v的祖先节点，更新其各跳子节点信息以及负载估计值；跳转到步骤13.2。

对于汇聚节点，无祖先节点，更新自身子节点信息即可。对于非汇聚节点，至多经过最 大跳数q到达汇聚节点，祖先节点的负载更新只须进行到汇聚节点。

步骤13.5，根据公式(1)～(5)，更新节点v的负载估计值l_v。

对于汇聚节点，因为传感网中，一般能对汇聚节点供电，可将其能量视为无穷大，所以 它的负载记作常数0，汇聚节点也无须更新父节点。

对于非汇聚节点，根据公式(1)～(5)来计算节点的负载估计值和估计生存时间。

步骤13.6，将节点v的子节点更新完成标记FINISHED更新为T；

步骤13.7，节点v更新子节点信息以及负载估计值的过程结束。

下面通过仿真实验来证明本发明方法优于现有的传感网树状拓扑生成方法。仿真参数设 置如下表1。

表1 仿真参数

参数 值 传感网范围 400m*400m 传输半径 55m 每一时隙节点感知数据 16Bytes 节点初始能量 随机数(10,15)J E_elec,ε_amp50nJ/bit,100pJ/m²/bit 数据压缩率 0.15

将本发明方法与现有的四种传感网树状拓扑生成方法进行比较。四个现有方法分别是：

1)节点度受限的BFS；

2)alpha-SPT方法；该方法在文献2中记载，文献2：W.Bechkit,Y.Challal,A.Bouabdallah, M.Koudil,B.Souici,and K.Benatchba,"A new weighted shortest path tree for convergecast traffic  routing in WSN,"in Proc.of IEEE ISCC,Cappadocia,Turkey,Jul.2012,pp.187-192.

3)E-SPAN方法；该方法在文献3中记载，文献3：M.Lee and V.Wong,“An energy-aware  spanning tree algorithm for data aggregation in wireless sensor networks,”in IEEE PACRIM, Victoria,BC,Canada,Aug.2005,pp.300-303.

4)随机树状拓扑方法。

仿真结果如图6所示，从图中可明显看出，采用本发明方法延长了网络的生存时间，明 显优于其他四种方法。

本发明方法基于广度优先搜索策略，引入传感器节点最大子节点数目限制因子以及随机 化的拓扑树生成控制机制，通过动态的节点负载估计以及随机化的拓扑生成，控制生成一种 能量有效的无线传感网树状拓扑结构，能有效地均衡网络节点能耗，延长网络生存时间。