无线传感器网络的拓扑控制研究

无线传感器网络的拓扑控制研究

网络交叉检测和网络分布对自组织无线传感器网络非常重要。通过拓扑控制自动生成合适的网络拓扑结构能够提高路由协议和MAC协议的效率,为数据融合、时间同步、目标定位等多方面奠定基础,有利于节省节点的能量来延长网络的寿命。传感器网络拓扑控制目前主要的研究问题是在满足网络覆盖度和连通度的前提下通过功率控制和骨干节点选择,剔除节点之间不必要的无线通信链路,生成一个高效的数据转发网络拓扑结构。拓扑控制可以分为集中式和分布式两种方案。无线传感器网络一般节点数量巨大,分布范围广泛,节点的位置随机分布,且受能量耗尽、环境等因素影响造成节点的失效等问题也会导致网络中节点数量的动态的变化和链路的变化,网络拓扑也会随之动态地变化,收集全局信息在实际中难以实现。因此目前的研究主要集中于分布式方案。1基于邻近图的lmst算法目前分布式方案拓扑控制的研究主要集中在节点功率控制和层次型拓扑控制两个方面。节点功率控制是节点发送功率的控制。每个节点动态地调整自身的发送功率(节点发送半径),在保证网络拓扑结构连通的前提下,减少节点的平均能量消耗,从而延长整个网络的生存时间。目前主要的算法有LMA/LMN,LINT/LILT等。层次型拓扑控制协议中比较典型的是文献提出的一种低功耗自适应分簇算法(lowenergyadaptiveclusteringhierarchy,LEACH)。LEACH算法对节点分簇,通过一定的算法选举簇头节点,相邻节点动态地组成簇。簇内节点将数据发送给簇头节点,簇头节点进行数据融合等处理后发送给基站。LEACH算法可以让网络中的节点等概率的担任簇头,节省节点的能量,延长了网络的寿命。文献中提出一种基于邻近图(MST模型)的LMST算法。在LMST算法中,任意一个节点u在发送半径范围R内探测确定自身的邻居节点集合NRuuR,节点u及其邻居节点集合NRnnR之间的连线构成邻居子图GRuuR。图GRuuR中边的权值是以边的长度,即边的两个端点之间的欧式距离来确定的。因为无线通信中,能量消耗E和距离d的关系是:E=kdn.2≤n≤4n的取值按照具体情况而定。Eg严格随d增大而增大,因此可以使用d作为边的权值。对节点(u1,v1),(u2,v2),确定唯一权值d′的方法见文献。这样节点之间以d′作为权值,在GRuuR范围内进行最小生成树算法得到本地最小生成树Tu。GRuuR中各节点将Tu上与自身距离为一跳的节点设为邻居节点,并调整发送功率为达到最远邻居节点的功率,减少网络中不必要的链路,从而形成网络拓扑。LMST算法有效地降低了节点的发送功率,减少了节点之间的竞争通信干扰。本文的主要想法是将分簇控制和局部MST算法的思想结合起来,综合两者的优点,研究如何在无线传感器网络中实现高效的拓扑控制。2algorithm算法性能分析本文提出了一种基于分簇的分布式无线传感器网络拓扑控制算法(Acluster-baseddistributedWSNtopologycontrolalgorithm,CDTC),研究此算法在拓扑控制中的性能表现。2.1分簇算法仿真实验在无线传感器网络中存在节点分布不均匀的情况。在某些局部区域内,节点数量多、密度大。若节点都以最大发送功率通信,将导致局部通信竞争激烈,导致网络吞吐量急剧下降。因此需要减少邻居节点之间发生冲突的几率,提高节点能量利用率。利用分簇的思想,将节点按一定的规则划分为不同的簇;在簇内运用局部拓扑控制思想,通过某种MST算法(如Prim算法),确定邻居节点关系并调整节点发送功率;在簇间通过关联节点连接簇,形成合适的网络拓扑,以降低节点发送功率,减少不必要的链路,减少节点间干扰,达到减少网络能量消耗,延长网络寿命的目的。本文中所有的场景都假设是在二维平面内。假设网络中所有的节点都有一个唯一的,所有节点都知道自身地理位置坐标,网络中时间同步。假设信道对称,无线传播无障碍,节点之间无线通信的能量衰减模型采用自由空间(Free-space)模型,即发送方发送数据的能量损耗与距离的平方成正比。假设在发送者和接收者之间只有一跳无障碍的直线路径,通信范围是在以发送方为中心,发送范围为半径的一个圆,若接收者在这个圆内则双方可以通信。所有节点都具有相似的通信和处理能力,所有节点都可以调整自身的无线发送功率大小。算法中有如下的定义:定义1簇头(CLUSTERHEAD,CH)节点CH由一定的簇头选择算法选出,负责运行局部MST算法,通知其簇内的节点确定邻居节点关系。CH之间互不相邻。CH的作用在于监控和调整簇内节点的拓扑关系。定义2TEST消息TEST消息发送成功则节点发送HELLO消息,表示自身成为簇头。节点若已经是簇头,或者已经属于某一个簇,则不发送TEST消息。定义3HELLO消息由CH发出,都包含节点自身的ID、节点坐标的信息。定义4簇内(CLUSTERMEMBER,CM)节点节点通过侦听到的HELLO消息得知哪个节点成为簇头,并将自身设置为CM节点。CM节点接受CH的指挥,确定自身邻居节点关系,并调整自身发送功率。定义5CLUSTERu消息由CH节点u发送,告知CM节点CH节点的ID(u),及该簇内部所有节点之间的邻居节点关系。收到该消息的CM节点记录自身处于哪一个簇,并确定邻居节点,调整发送功率。定义6ACK消息非CH节点在收到CH的HELLO消息后,周期性地向CH回复。包含节点自身的ID、节点坐标的信息,通知CH自己加入该簇。定义7关联节点一个CM节点可以同时属于不同的多个簇,这种节点称为关联节点,是连接不同的多个簇的关键。一个节点一旦成为关联节点,就要周期性地向自身所处的各个簇头节点发送CONNECTNODE消息报告,报告自身的关联的簇的信息。定义8成为簇头的概率pp与节点n的剩余能量成正比,p=kEnEmaxp=kEnEmax。En是节点n当前剩余能量,Emax是节点n初始最大能量。分簇算法参考文献中提出的随机簇头选择算法,这种簇头选举方式十分简单,仅仅通过随机竞争的方式完成,实验证明单个节点发送探测消息的平均次数接近e次,这在实际网络成簇中是可以接受的。在网络中选举剩余能量多的节点作为簇头也有利于延长传感器节点的生存时间。本文的仿真实验采用的系统模型参考了文献。网络范围设为1000m×1000m,节点最大发送范围设为250m。节点随机部署在网络中,一旦部署就不再移动。节点ID唯一。所有节点都具备同样的通信和计算模块。所有节点都能够调整自身的发送功率大小。使用Matlab软件考察在网络中随机部署一定数量的节点时的成簇情况。图1是节点数为60时的分簇情况。图中圆圈标出的是簇头。可以看到簇头之间不相邻,由关联节点连接簇。在不同节点数量的条件下各随机生成三次拓扑,记录簇头数量,如表1所示。从表1中可以看到,在节点数变化的情况下,簇头数量基本稳定在11左右。图2是节点数为60时,一次随机簇头选举后的簇分布图。可以看到网络未连通,有孤立的簇,即与其他簇之间没有关联节点,此时就要重新选举簇头或者结合路由方面的协议来关联簇。实验发现节点密度较大的网络中存在孤立簇的可能性较小。稀疏网络中,孤立簇出现的可能性较大。孤立簇的情况有两种:①物理上的孤立簇某个孤立的节点在其发送范围内,或某个局部范围内的所有节点在各自发送范围内都没有与其他簇关联的节点。这种情况下孤立簇就被丢弃。②逻辑上孤立的节点某个孤立簇头节点在其他簇的簇头的发送范围内,或某个局部范围内的部分节点在其发送范围内有与其他簇关联的节点,但是由于簇头选举的原因(簇头与簇头之间不相邻),导致没有关联节点。对于逻辑孤立簇,可以采用两种解决方案:①结合路由算法,由sink节点统计从未收到节点的ID,达到一定的阈值后要求网络重新成簇;②簇形成后,若簇头没有收到簇内节点的CONNECTNODE报告,说明簇内没有关联节点。簇头节点发送消息要求所有簇内节点探测各自可达邻居节点,若发现邻居节点中有不在同一个簇的,则通知簇头将可自身设为关联节点,或者要求在簇内原簇头不参与选举的情况下重新选举簇头。本文中为了方便起见,以下的使用中没有物理孤立簇的场景。簇内控制采用LMST算法的思想在簇内由CH收集CM节点信息,选取各节点之间的距离作为权值,运行局部MST算法,调整节点之间的相互邻接关系。簇之间由关联节点连接,保证网络的连通性。2.2节点n从其nrnnr-tn的信号生成树基于以上的讨论,算法的基本过程可分为以下4个阶段。STEP1分簇①节点部署以后,在初始时刻T0,任意一个节点n首先以概率p发送TEST消息。若发送TEST消息不成功,则进入侦听状态;若发送成功,就将自身设置为簇头(CH),并使用最大发送功率R向周围发送HELLO消息。若在一个时槽Tm内没有节点成功发送TEST消息,则重新选举。其他节点若接收到这个HELLO消息,就向节点n周期性地回复ACK消息,表明自己加入该簇。如图3所示(图3中r1,r5分别为node1,node5的最大发送半径)。②节点n接收到其他节点回复的ACK消息,统计自身的邻居节点集NRnnR,形成一个簇CLUSTERn,再发送CLUSTERn消息,如图4中的node1,node5。所有收到CLUSTERn消息的节点记录自身处于的簇的簇头ID(即n),表示自己已成为CLUSTERn的簇内(CM)节点,如图4中的node2,node3,node4。任意一个节点只要收到HELLO消息就必须要回复ACK消息。若节点m收到多个CLUSTERu(u=1,2,…)消息,表示节点m处于多个簇头的发送范围内,节点m就要将不同的簇的信息记录下来,这样的节点就是关联节点。如图4中的node4。STEP2簇内拓扑控制簇形成后,簇头n在其NRnnR内生成最小生成树Tn。CH节点n按达到最远邻居节点的发送功率向所有邻居节点发送CLUSTERn消息,通知簇内各节点相互之间邻接关系。收到CLUSTERn消息后CM将Tn上与自己距离一跳的节点设为自身邻居节点,确定彼此之间邻居关系,调整各自发送功率为到达最远邻居节点所需的功率。最小生成树关系如图5所示。STEP3簇间通信簇间的通信依靠关联节点来实现。对于孤立簇的情况,若CH未收到CM节点的CONNECTNODE,则要求所有CM探测自身的邻居节点,寻找关联节点。STEP4拓扑维护阶段若簇内CM节点失效数量达到一定的阈值,CH就重新运行MST算法,调整CM关系;若CH失效,则重新进入簇头选举。在系统运行到一定的周期Tr后,网络进入全局重新选举状态,重新成簇,以均衡网络能量。3模拟与性能分析3.1运行lmst算法为了对比不同算法的性能,在网络中随机部署160个节点,按照此场景分别运行不同的拓扑控制算法。图6是运行随机簇头选举后划分簇的情况。图中红色圆圈标出的是簇头节点,簇与簇之间有重叠,即关联节点存在,簇头之间互不相邻。图7、图8、图9分别是同样的场景下在无拓扑控制(nocontrol,NOC),运行LMST算法,运行CDTC算法的情况下,记录网络由初始状态开始所建立的第一个连通的网络拓扑的示意图。图7是无拓扑控制的情况,即所有节点都以最大发送功率通信时的拓扑状态,网络中链路数量很多且相互关系复杂,节点间通信干扰很大。图8表明网络运行LMST算法形成网络的连通性得到保证,链路数量明显优化。图9中显示运行CDTC算法后的网络拓扑。圆圈标出的是簇头,网络的连通性较好,减少了不必要的链路,优化了节点之间的连接,且节点之间干扰较小。3.2算法性能比较仿真使用的性能比较指标:①平均总链路数对于某个节点平均总链路数量少,通信所消耗的能量就少,有利于减少整个网络的能量消耗。②平均节点度节点度是一个节点的所有距离该节点一跳范围的邻居节点数目。节点度小有利于空间的重利用,提高网络容量,减少竞争,减少分组传播碰撞的概率。③簇头数簇头数量较少且稳定,整个系统拓扑建立所需的计算和通信开销就少。④节点平均发送半径平均发送半径是决定能耗的主要方面。平均发送半径越小,发送数据所需的能量就越少。在仿真实验中,节点数分别取40、60、80、100、120、160,每次分别随机生成3个场景,记录各项数据,按照上述的性能比较指标计算并取平均值。图10、图11、图12、图13是各项性能指标的比较图。图10、图11表明,运行CDTC算法后,网络中平均节点度基本稳定在2左右;簇头数量稳定;这样节点相互之间的干扰也会减少,有利于提高网络容量,减少分组碰撞概率。图12表明,网络中的总链路数变化比较稳定,与NOC相比,一直保持在一个相对较低的水平,说明减少了网络中的部分链路,这样有利于减少通信冲突。图13表明随着节点数的增加,节点的平均发送半径明显下降,而且比NOC的情况相比更小;网络的平均链路长度也大幅减少。CDTC算法选用的分簇算法十分简单,无需全局式的集中控制。各节点随机选举簇头且选举开始时无需预先收集邻居节点信息,在通信和计算开销上都较小,是一种分布式算法。簇内通信借鉴性能较好的LMST算法,减少网络中不必要链路,使用关联节点连接簇,生成合适的网络拓扑。实验表明C