无线传感器网络拓扑控制算法（精品）.docx

《无线传感器网络拓扑控制算法（精品）.docx》由会员分享，可在线阅读，更多相关《无线传感器网络拓扑控制算法（精品）.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、无线传感器网络拓扑控制算法1概述无线传感器网络(WirelessSensorNetwork，WSN)近年来的快速发展离不开传感器技术、网络无线通信技术、嵌入式技术、分布式信息技术以及微电子制造技术等相关关键技术的日益成熟。它是一种无中心节点的全分布系统，是有针对性对某个监控区域内进行随机投放的若干个传感器节点自组织通过无线电信通信构成网络系统。传感器节点可根据其内置的不同功能的传感器，感悟所在的周遭环境中人们的感兴趣的数据，如温度、红外线、湿度、压力、土壤成分、移动物体的属性等。正由于无线传感器网络的无处不在的感悟技术优势，它有着非常广泛的应用前景。在军事领域、环境应用、医疗事业、工业应用以及

2、商用等多个领域都占有意义非凡的一席之地。显然，无线传感器网络是当前多学科高度穿插、前沿的热门研究之一。无线传感器网络中传感器节点一般由数据采集模块、数据处理和控制模块、无线通信模块和供电模块组成。而正由于它本身的物理特性因素，其电量供应有限成为无线传感器网络生命期主要的瓶颈问题之一。早期的经典拓扑控制算法思想主要是借助控制节点传输功率或稀疏化网络拓扑图，到达降低节点信道之间干扰的目的。近阶段有一些研究者，指出机械性减少边的数量、长度及邻节点度不一定就能保证节点之间的干扰现象也降低，并就干扰模型的定义和度量方法进行了研究。其中，定义的干扰模型有基于发送节点的干扰模型、基于接收节点的干扰模型。基于

3、不同的干扰模型，文献8指出二维及二维以上的网络模型的拓扑控制干扰优化问题已被证实属于NP问题。在上述拓扑控制算法的研究中，很少有以降低全局网络节点中的最大干扰值作为首要目的，干扰的存在不仅会影响通信质量，而且造成数据不断重传损耗电量缩短网络生命周期9，大部分算法针对的都是节点分布比拟均匀的网络情况，而对于节点间非均匀分布的网络情况，如指数链模型无线传感器网络下的干扰优化效果甚微。本文将采用基于接收节点干扰模型，以干扰阈值作为重要考虑因素，以最小化最大干扰值、网络连通性为算法首要目的，对一维指数链模型的无线传感器网络节点的邻居节点、节点传输半径和网络节点数、节点所受的干扰进行研究，设计一种启发式

4、算法，并将其算法思想沿用至二维网络模型中，保证其网络连通性的同时到达优化最大干扰值的目的。2相关工作功率控制是研究无线传感器网络拓扑控制重要方向之一，功率控制指的是合理地设置或动态调整节点的传输半径功率，在保证整个网络的连通的同时，弱化节点间的互相干扰，并到达高效节能、延长网络生命期的目的。文献7指出包含近期邻居的节点算法(下文简称为近期邻算法)在指数链模型上的干扰优化效果不甚理想。在一维指数链上若有n个节点以2的指数倍的距离相隔进行排布，由于近期邻算法的算法特性，会将构成网络中的最短途径的链路保留下来，以减少链路开销。而一维指数链的特性会使得新参加每一条的连接增大原先最右边的节点的发射半径，

5、这也加剧了网络中节点的最大干扰值扩大。如图1所示，由文献7指出近期邻算法产生的拓扑构造节点中遭到的最大的干扰到达n2n。显然，一个节点在有n个节点的网络中，在最坏的情况下，遭到除已的其他节点干扰，即干扰值为n1，可见，近期邻算法在一维指数链上干扰优化的改良效果不如人意。3干扰模型要素根据无线传感器网络的特性，本文延续文献7-8模型化方法利用单位圆盘图(UnitDiskGraph，UDG)理论进行无线传感器网络抽象建模。便于讨论后文提出的干扰优化拓扑控制算法，本文采用无向图中的顶点来模拟在监测区域投放的传感器节点，图中任意2点存在的边作为任意2个传感器节点直接通信即一跳距离的根据。31单位圆盘图

6、在UDG图G=(V，E)中，V为图G中顶点的集合，E为图G的任意顶点存在边的集合。V中的每个顶点都有以该顶点为中心的等半径的圆逐一对应，假设所有节点具有一样的通信半径上限rmax，当且仅当u顶点和v顶点之间的欧氏距离小于等于rmax时，则e(u，v)E。根据上述UDG图的定义，假定UDG图G=(u，v)为无线传感器网络的抽象模型，并设定无线传感器网络中的传感器节点的传输功率是可调节的，其有效值区间是0，MaxPower，其中，MaxPower代表了节点传输功率的上限值。32模型字符为更简洁明了描绘本文要点，将使用下面模型字符进行定义:(1)Nu表示结果拓扑图T中u节点的邻居节点集合，即在结果拓

7、扑图T中与u只要一跳距离的顶点的集合。(2)ru表示结果拓扑图T中u节点的通信半径，ru=maxvNuu，v，其中，u，v指的是u节点与v节点之间的欧氏距离。(3)D(u，ru)表示以u为圆盘中心ru为通信半径所覆盖的节点的集合，为方便算法展开分析，这里不考虑节点本身覆盖的情况。(4)本文采用基于接收者的干扰模型，RI(u)表示u节点对于根据拓扑控制得到最终的拓扑图T=(V，E)，节点遭到干扰是这样定义。(5)衡量结果拓扑图的干扰值是由众节点所受的干扰度最大的那个节点的干扰值所决定。根据31节中指出通信功率的上限MaxPower，则同样的，传感器节点都受限于同一个最大通信半径值MaxRadiu

8、，而节点的通信半径取值随着拓扑控制调节控制在0，MaxRadiu区间，也就是讲，无线传感器网络中的传感器节点初始条件都是统一的，当中的最早消耗完电量的节点则是遭到干扰最多的那个节点，这也决定了当前无线传感器网络的生命期的长度。4本文算法设计思想根据上述采用的基于接收者的网络拓扑干扰模型，本文提出了一种基于干扰阈值调节的拓扑控制(ThresholdAdaptiveTopologyControl，TATC)算法。TATC算法思想主要如下:(1)建立模型:每个节点需要与其他节点进行消息交互，收集搭建链路的距离即通信半径的数据。考虑在理想状态下，假如网络中任意u，v节点能通过一跳距离能收到消息响应成功

9、，则根据式(1)，它们之间的通信链路距离是不超过设定的单位通信半径上限单位1，则图G中u，v点中存在直接链路，即e(u，v)E。(2)初始化构造拓扑图T，T=(V，ETATC)，ETATC=NULL。由于当前T中边为空集，当前RI(T)=0;设定一个干扰阈值RI-threshold初始值为1。(3)随机遍历E集合中的链路，对链路进行预处理选择，尝试每一条链路逐步参加ETATC集合中，并计算出当前图T中各个节点RI值，进而得到RI(T)值。(4)对当前假设的图T中ETATC集合中利用深度搜索算法进行能否存在边回路检测，如若存在回路，则ETATC集合中将不会包含该链路，与此同时，E集合中也将剔除该

10、链路，之后返回步骤(3)，将继续遍历下一条链路。否则，执行步骤(5)。(5)假如参加链路能使RI(T)不超过当前的RI-threshold，则该链路将参加ETATC集合中，与此同时，E集合中也将剔除该链路。(6)遍历完毕，延续深度搜索算法检测图T连通性，假如不连通，则将当前最大干扰阈值进行向上调整，执行步骤(3)，否则执行步骤(7)。(7)算法执行完毕，得到结果拓扑控制图T=(V，ETATC)，此时的最大干扰阈值RI-threshold则为当前结果拓扑控制图T中的RI(T)值。5拓扑构造性质分析TATC是一个贪心算法。在进行拓扑控制时，在结果拓扑图T中的链路还未到达所需时，此时，算法中设定的R

11、I-threshold阈值参数相当于当前的目的函数。把所有符合当前的全局最大干扰阈值条件下的链路都会包含在ETATC集合中，前提是该链路的参加不造成T中有环，假如造成环，直接在初始G中丢弃该链路，假如符合当前添加情况，也需在G中剔除该链路。继续检测拓扑图T能否为连通图为该算法的出口的关键，假如不为连通图，需增大RI-threshold阈值参数，继续上述的步骤(3)。显而易见，G图中有m条链路，n个节点，每次遍历的是当前G中链路集合。RI-threshold阈值参数在算法中逐步增加，直到图T构成了一个连通图。因而，步骤(3)中需要至多遍历RI-thresholdm次。其中，RI-threshol

12、d的取值范围的上限是n1，步骤(4)、步骤(5)中会剔除一些冗余的链路，步骤(3)再次遍历时其链路集合工作负荷逐步减轻。同理，步骤(6)对图T的连通性需检测RI-threshold次。其中，算法从e(u，v)=E(u，v)V，ETATC=开场，重复执行下面的操作:在所有e(u，v)=E找到符合一条符合当前RI-threshold阈值参数的边参加集合ETATC，同时在原集合E中删除该边，直至ETATC中有n1条边，即图T为极小连通图。算法的时间复杂度为O(n2)。如图3所示，16个节点的一维指数链，使用TATC算法所得的构造拓扑图中产生的最大干扰RI(T)=5，而根据本文第2节中指出的近期邻算法

13、则在该链路上产生的RI(T)=14。6性能仿真与分析为评估TATC算法的有效性，根据文献8所介绍的指数链特征采用UDG模型分别构建一维指数链以及二维指数链的初始拓扑构造。如图4、图5所示，横坐标表示当前一维指数链网络中的节点数，纵坐标分别表示当前网络中节点的最大的干扰值、网络节点的平均干扰值。图中比拟了近期邻算法以及本文算法在一维指数链产生的拓扑图中节点中的最大干扰值以及平均干扰值。与近期邻算法相比，TATC算法显著减小了网络中节点的最大干扰值、平均干扰值，而且随着节点数的增加，拓扑控制后的拓扑图的最大干扰、平均干扰增长幅度较慢。图6、图7仿真的是在区域1000m1000m的区域中，据二维指数

14、链特性7排布50个400个节点，上述的2种算法在该网络环境产生的拓扑构造图中的节点的最大干扰值以及平均干扰值。能够明显看到，采用TATC算法的网络中的最大干扰值、平均干扰值的数值优于近期邻算法。7结束语本文设计一种基于最大干扰值阈值调节的拓扑控制算法。该算法以网络连通性、拓扑构造干扰弱化性为目的函数，对干扰阈值不断自适应调节，直到构造成所需的网络拓扑构造。实验结果表明，在指数链模型上，该算法能控制节点的最大干扰值在构建拓扑构造中趋于缓慢增长，比近期邻算法获得了更好的干扰优化效果。但该算法还需进一步改善并推广至其他网络模型。今后将从网络容错性能和适用性方面上继续改良该算法，以提升网络的抗毁性，降低算法的局限性。