文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 基于拥塞控制的无线传感器网络数据汇集树生成算法
侵权投诉

基于拥塞控制的无线传感器网络数据汇集树生成算法

以通广播算法[11 12]进行层次发现得到,t(x)初始化为1,在数据汇集的过程中通过统计上行数据流的源节点地址个数得到,并通过ACK稍带的方式,告知邻居节点.

对于一棵数据汇集树,假设其深度为N,给定层次i,i<N,从i+1到N层的所有节点,设总共M个节点,则这M个节点产生的数据流,必然全部通过第i层.假设第i层上有n个节点,其t值分别为t1,t2,···,tn,且t1+t2+···+tn=M.为了均衡数据流,应该让t1,根据乘法原理,当 tn

2,···,tn之间的差值最小化.

i=1ti最大时,t1,t2,···,tn之间的差值最小.

定义1.由图G=(V,E)生成的一棵最短路径树T=(V,E ),E E,深度为N,第i层的节点个数为ni,则树T的第i层的拥塞权值定义为

W1

L(i)=i

(1)

tij

j=1

其中,tij表示第i层节点j的t值.

树T的拥塞权值定义为

W1T=

N ni(2)

tij

i=1j=1

定义2.由图G=(V,E)生成的一棵最短路径

树T=(V,E ),E E,如果树T的拥塞权值达到最小,则称T为最短路径最小拥塞数据汇集树.

在数据汇集应用中,传感器节点周期性的产生数据,注入网络,经过多跳流向Sink节点,数据流的大小和方向相对稳定,其拥塞往往发生在热节点和瓶颈节点处.因此从直觉上理解,认为度数越大的节点热度较高.

定义3.对图G=(V,E)的任意节点x∈V,y∈V,定义运算符 ,可以对x,y排序,其排序规则为

x y=d(x)<d(y),d(x)=d(y)

id(x)<id(y),d(x)=d(y)

,x,y∈V

(3)

定理1.通过运算符 ,对G=(V,E)中的任意节点u的父节点可以构造一个全序集(F(u), ).

证明.由于每个节点具有唯一标号,并且可以排序,所以定理1显然成立,证明从略.

为了构造最短路径最小拥塞树,本算法定义以下三种消息:

Request(x,y)表示节点x请求加入y作为其子节点.

Con rmMsg(x)表示节点y确认了节点x的请求消息或更改消息,并稍带更改后自己的t值.

Change(x,y,z)表示节点x请求加入y作为其子节点,并脱离父节点z,消息包含节点x的t值.

NotifyMsg(x)表示通知父节点x,其t值的变化量.当发送队列数据有要发送时,可以取消该消息,t值可以通过稍带方式发送.

节点随时偷听邻居节点网络的消息,实时更新邻居节点和自己的t值.2.2DGT-CC算法描述

步骤0.节点初始化,d(x)=0,h(x)=0,N(x)=Φ,F(x)=Φ,t(x)=1;

步骤1.由Sink节点开始,采用广播算法进行层次发现,使每个节点得到h(x),以及所有的hx(y).

步骤2.节点发送hello消息进行邻居发现,构造相对邻居图,使每个节点得到N(x),d(x)和所有的dx(y).

步骤3.如果节点x,h(x)=1,则为Sink邻居节点,则直接建立与Sink的父子关系.否则,节点使用运算符 ,构造一个全序集(F(x), ),并选择全序集(F(x), )的第一个节点y为父节点.并发送Requestx,y)消息通告,收到Request的节点y,发送Con rmx)进行确认.节点x收到确认后建立与y的父子关系.到此可以生成一棵最短路径汇集树.

步骤4.在数据汇集的过程中,统计上行数据流的源节点地址个数得到每个节点的t值,并通过ACK稍带的方式,告知邻居节点.经过一个数据采集周期T可以得到稳定的t(x)和所有tx(y).

步骤5.采用流量均衡算法,进一步规避局部热节点,具体操作如下:

1)对于节点x,其父节点为u,如果v满足{u,v∈F(x)}∩{t(x)+tx(u)<tx(v)},则发送ChangeMsg(x,u,v)消息,并将父节点置为v,否则执行步骤6.

2)收到ChangeMsg(x,u,v)消息的节点u和v,分别改变自己的t值,并使用Notify消息或者数据稍带方式通知上层节点.

3)收到NotifyMsg消息或者数据稍带的t值变化的节点,继续通知上层,直到与Sink连接的顶层节点.

4)执行步骤5的子步骤1).步骤6.结束.

2.3DGT-CC算法举例

节点随机部署在检测区域中,通过DGT-CC算法的步骤1和步骤2就可以建立如图1所示的相对

上一页第3页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email