基于二叉树的无线传感器网络分簇能量均衡路由确定方法

摘要

本发明涉及一种基于二叉树的无线传感器网络分簇能量均衡路由确定方法。该方法采用了数据结构中的二叉树结构和它的后序遍历，结合传感网节点的能量均衡机制，提出了该路由确定方法。在无线传感网的分簇组网过程中，有效地减少和均衡整个无线传感器网络中节点的能量消耗，延长整个网络的生存周期。在路由建立阶段，根据能量均衡机制和节点过去的情况，使剩余能量较大并且当选次数较少的节点成为簇头的概率大大提高，在簇内进行多跳通信时的TDMA时隙分配中，成员节点根据信号强弱先后加入簇头，簇头根据到达时间的先后建立二叉树，并根据对二叉树的后序遍历分配每个节点工作的时隙，实现了通信距离上的最小化，有效地降低了一部分相对离簇头较远的节点的能量消耗。本发明的方法较为简单，易于实现，适用于各种以数据为中心的无线传感器网络的应用场合。

主权项

1.一种基于二叉树的无线传感器网络分簇能量均衡路由确定方法，其特征在于操作步骤如下：a.在其中某一轮的形成簇的阶段时，每一个节点都先处于等待状态，并生成一个随机变量R＝rand(0，1)；根据网络中每个节点此时自身的剩余能量Enow，每个节点初始时的最大能量Einitial，在过去的所有轮数中该节点当选过簇头的次数Times_Head，网络中簇头节点所占总节点数目的百分比P和当前的轮数r，以及整个传感器网络到本轮为止所经历的循环次数$r/\left(\frac{1}{P}\right)+1,$生成每个节点在本轮的阈值T′(n)，$T^{\prime }\left(n\right)=\frac{P}{1-P\left(r\mathrm{mod}\frac{1}{P}\right)}\times (\frac{E_{\mathrm{now}}}{E_{\mathrm{initial}}}\times \frac{r/\left(\frac{1}{P}\right)+1}{\mathrm{Times}\_\mathrm{Head}}).$如果某个节点产生的R小于该节点的T′(n)，则当选为本轮的簇头；如果某个节点产生的R大于该节点的T′(n)，则成为本轮的簇头的成员节点；b.当选的簇头节点向网络中其它节点广播各自簇头广告包，在广告包中有一个cost域是用来保存簇头的Enow，供非簇头选择自己的簇所用；在整个广告的过程中，其它非簇头节点全部处于接受状态，用来接收来自簇头的数据；非簇头节点有可能会收到来自不同簇头节点的广告包，根据簇头节点的剩余能量cost，非簇头节点收到簇头信号的强弱S_intensity，得到不同簇头节点的COST，$\mathrm{COST}=\frac{\cos t}{S\_\mathrm{intensity}},$选择COST最大的簇头节点作为自己的簇头节点；c.成员节点选定自己的簇头后，设定一个加权的随机退避定时器，权值的设定依赖于节点所收到的簇头信号的强弱也就是与成员节点与簇头之间的距离dCommunication与每个节点的通信半径DMax，求出定时时间Delay，$\mathrm{Delay}=\exp (-\frac{d_{\mathrm{Communication}}}{D_{\mathrm{Max}}});$定时时间到，每个成员节点向选定的簇头发出应答包，数据包的帧格式中要包含成员节点的ID；d.簇头节点根据时间先后，会收到来自不同成员节点的应答包，基于成员节点数目，会产生一个TDMA时隙表；时隙表的建立与应答包到达的先后顺序有关；建立一棵二叉树的数据结构，来安排成员节点的标示ID放入二叉树的每个结点；越先到达的应答包所对应的成员节点在整个二叉树内就要越靠近根结点也就是簇头节点，即最先到达的2个应答包对应的成员节点作为簇头的2个子节点也就是根结点的2个子结点，随后到达的4个应答包对应的成员节点作为刚才2个子结点的子结点，以此类推，直到将所有的应答包对应的成员节点全部分配完毕；生成的二叉树对应簇内多跳通信时，数据发送的方向，数据总是由子结点向父节点发送；e.二叉树建立完毕之后，对其进行后序遍历，将遍历的结果作为依次放入TDMA时隙表，并将TDMA时隙表和二叉树的结构广播给簇内所有成员节点；f.每个成员节点收到TDMA时隙表后，在时隙表内查找自己的标示ID；在属于自己的时隙范围内，根据收到的二叉树的结构将数据发送给二叉树数据结构中的父结点；在不属于自己的时隙范围时，关闭射频模块以减少能量消耗；g.二叉树后序遍历序列的最后一个结点必定是根结点也就是簇头，所以当TDMA时隙运行到最后一个时隙时，簇头将前面若干时隙中收到的数据发送给汇聚节点，本轮结束，进入下一轮。