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

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

邻居图,虚线表示邻居关系,并发现各自距Sink节点的层次.每个节点的id(h,d)如图1所示

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

.

图1

无向层次图

Fig.1

Undirectedgraphwithlevel

由算法的步骤3可以生成如图2所示的最短

路径数据汇集树,实线表示父子关系,每个节点的id(h,d,t)如图所示.例如:节点16使用运算符,构造一个全序集(F(16), )={2,14},则选择节点2为其父节点,并建立父子关系

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

.

图2最短路径树

Fig.2

Shortestpathtree

图2中节点8的转发任务量明显比节点14大,节点6的转发任务量比节点17大,因此对于节点17和10需要调整其父节点.经过步骤4和步骤5,节点17和10改变自己的父子关系,从而减少了节点8和6的转发任务量,降低了其拥塞程度,生成了如图3所示的最短路径最小拥塞权值树.

3DGT-CC算法正确性证明

定理2.DGT-CC算法收敛.

证明.显然,DGT-CC算法的步骤0~步骤3收敛,而步骤4经过一个数据采集周期后收敛.步骤5采用反正法证明:假设步骤5不收敛,存在节点x,

x∈V,且存在u∈F(x)和v∈F(x),节点x不能准确判定tx(u)与tx(v)的大小关系.而DGT-CC算法通过Notify、ACK稍带、数据稍带和偷听机制保证了节点x可以准确知道tx(u)与tx(v)的大小关系,因此矛盾,所以步骤5收敛.DGT-CC算法所有步骤收敛,DGT-CC算法收敛得证.

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

图3最短路径最小拥塞权值树

Fig.3Shortestpathtreewithminimum

congestionweight

定理3.DGT-CC算法构造的路由汇集树是一棵最短路径树.

证明.使用反证法.假设由G=(V,E),通过DGT-CC算法构造了树T=(V,E ),E E,树T不是最短路径树,则存在节点u∈V,u到Sink节点的距离不是最短路径,对于v∈F(u),边uv∈E .但是由算法的步骤3知,必然存在一个v∈F(u),其边uv∈E ,因此矛盾,故定理3得证.

定理4.DGT-CC算法构造的路由汇集树使得每一层的拥塞取值最小.

证明.使用反证法.假设由G=(V,E),通过DGT-CC算法构造了树T=(V,E ),E E,存在树T的第i层,i<N,其拥塞权值不是最小,则在第i层存在节点x,y,在第i+1层中存在u,x∈F(u),y∈F(u),满足t(u)+tu(x)<tu(y).由算法步骤5知,节点u的父节点必然发生调整,因此树T没有通过DGT-CC算法完成构造,这与树T=(V,E )是通过DGT-CC算法构造的矛盾,定理4得证.

定理5.DGT-CC算法构造的路由汇集树是一棵最短路径最小拥塞树.

证明.使用反证法.假设由G=(V,E),通过DGT-CC算法构造了树T=(V,E ),E E,树T不是最小拥塞树,则由定义1和定义2知,至少存在第i层,i<N,其拥塞权值不是最小,但这与定理4矛盾,定理5得证.

上一页第4页

你可能喜欢

热门文档

相关文档

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