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

摘要

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

主权项

一种基于改进广度优先搜索的无线传感网树状拓扑生成方法，定义三种颜色标记示传感器节点状态：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\left(T\right)+\mathrm{...}{w}_q·N_i^q\left(T\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，对节点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,\mathrm{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监听并处理相邻节点的父节点请求消息，更新节点v的子节点数量CN、负载估计值和子节点更新完成标记；步骤14，从N[v]中取出一节点u；步骤15，判断节点u的颜色标记C[u]是否为WHITE，若是，转步骤16执行，若否，转步骤11执行；步骤16，请求节点u将C[u]设置为GRAY，将P[u]设置为v，然后跳转到步骤11执行。