基于分环多跳的无线传感网分簇路由算法.doc

第3期刘志等：基于分环多跳的无线传感网分簇路由算法113基于分环多跳的无线传感网分簇路由算法刘志, 裘正定(北京交通大学 信息科学研究所, 北京 100044)摘 要：为了提高无线传感网在大区域情形下的能量效率，提出了一种分环多跳分簇路由算法RBMC（ring based multi-hop clustering routing algorithm）。RBMC算法采用分环的方式实现簇头间的多跳通信，通过在不同环内构建大小不同的簇解决传感器网络中存在的“热点”问题，在不同的簇头选举策略下，能够同时满足节点能量同构及异构两种情形。仿真结果表明，在大区域环境下，分环多跳分簇路由算法能在很大程度上均衡节点能量消耗，延长网络的生命周期。关键词：传感器网络；分簇路由；分环模型；能耗均衡中图分类号：TP393 文献标识码：B 文章编号：1000-436X(2008)03-0104-10Ring based multi-hop clustering routing algorithm for wireless sensor networksLIU Zhi, QIU Zheng-ding(Institute of Information Science, Beijing Jiaotong University, Beijing 100044, China)Abstract: A ring based multi-hop clustering routing algorithm(RBMC) for wireless sensor networks(WSN) was proposed. The main task of RBMC was to prolong the lifetime of the network, balance energy consumption between nodes. The main idea of RBMC was to divide the WSN field into concentric rings and build unequal size of clusters in different rings. From the objective of minimum energy consumption in first ring and balance of it between first ring and other rings, the optimal choice of cluster numbers for each ring was deduced. Via adoption of different algorithms for cluster head election, RBMC could be applied to homogeneous and heterogeneous energy settings. The simulation results prove the good performance of RBMC in large area WSN scenarios. Key words: wireless sensor networks; clustering routing; ring based model; balance energy consumption1 引言收稿日期：2006-06-28；修回日期：2007-12-28能量受限是传感器网络最显著的特点之一。实验表明，传输一个比特所消耗的能量比运算处理一个比特消耗的能量大1。采用高效的路由算法，可以大大提高无线传感网（WSN, wireless sensor networks）的能量效率，分簇路由算法被认为是比较符合传感器网络的特性的高效算法。有关分簇的问题很早便有论述，如文献29，这些算法基本都是启发式的，其目标是生成具有最小数量的簇，同时使得任意一个簇中的任意节点到簇头的跳数至多为d跳，算法的复杂度在O(N)量级（N为网络中的传感器节点总数）。针对传感器网络的特性，Heinzelman提出了LEACH（low-energy adaptive clustering hierarchy，低能耗自适应分簇层次算法）算法10。其核心思想是让每个节点轮流担当簇头，从而使得网络中的能量消耗尽可能均匀，减少网络失效时刻的能量浪费。LEACH算法只考虑了单跳模型，因此只适合于小型WSN网络。文献11提出了M-LEACH（multi-hop variant of LEACH，多跳LEACH）算法，簇内的节点不是以单跳的方式传输数据到簇头，而是通过簇内其他节点转发。文献12提出了一个多跳簇头模型，采用从下到上的策略，逐层生成每一层的簇头，最终得到一个多层结构的WSN网络。文献13采用基于代价的目标函数对传感器网络设计进行了分析，推导出单跳和多跳的适用范围，最后提出一种单跳多跳混合的路由算法,以克服网络中的“热点”问题。为进一步延长网络的生命周期，网络的异构性研究受到重视11,1418。文献15讨论了当类型0节点服从Possion过程，类型1节点采用确定性的格点分布，在确保连通性和覆盖性的前提下，要保证最少T轮数据采集，两类节点应满足的最优分布强度和能量配置。文献18提出了一种更为完善的能量异构算法：SEP（stable election protocol for clustered heterogeneous wireless sensor networks，异构分簇无线传感网的稳定选举协议）算法。SEP算法采用类似LEACH的簇头随机选择方案，具有较好顽健性；不同之处在于，根据节点初始能量的不同，SEP算法为节点设置不同的簇头选举概率，从而均匀能耗。SEP算法从本质上说仍然是一个单跳路由算法。文献16提出UCS（unequal clustering size, 不均等分簇）算法，将节点按距离Sink的远近分成大小不同的簇，从而较好的克服了“热点”问题。UCS假定里层的簇头在圆形区域中的分布是事先设计好的，这个假设不适合于随机部署的WSN网络。文献17也提出了和UCS类似的异构网络算法：EEUC（energy-efficient unequal clustering, 能量高效的非均等分簇）算法。EEUC算法中，每个节点先根据一个预先确定的门限，随机确定自己是否成为伪簇头,成为伪簇头的节点根据接收到的Sink信号的能量，计算自己与Sink的距离，形成不同半径的竞争区域，竞争区域内的伪簇头通过竞争，能量最大的成为簇头；簇头再根据周围簇头的剩余能量与转发代价，从转发代价最小的2个簇头中选择剩余能量最大的簇头作为自己的下一跳节点。文中的仿真表明，EEUC算法的簇头数比LEACH算法和HEED（hybrid energy-efficient distributed clustering，混合式的能量高效分布式分簇）算法更稳定，能量消耗更均匀，网络的生命周期更长。EEUC算法中用到了4个参数，文中没有给出参数的选取策略，需要进行人工选取，实际操作起来比较困难，算法性能难以达到最优。针对前述论文的问题，本文提出基于分环多跳的分簇路由算法RBMC（ring based multi-hop clustering routing）。首先将监控区域分成多个同心圆环，外环的簇头通过里环的簇头转发数据，使多跳路由的生成算法变得简单、清晰；再在第一环以能耗最小化为目标，推导最优的第一环簇头数；接着利用能耗均匀的原则，推导出其余各环的最优簇头个数，最终形成一个能耗均匀、簇大小异构的多跳WSN网络，克服网络中的“热点”问题。本算法完全避免了文献10,13,18中对单跳模式的依赖，可以真正应用于大区域环境中；簇头随机选取又克服了文献1416中簇头确定性分布带来的缺点；另外，本文运用与文献17不同的簇异构思路，给出了关键参数的求解方法，避免了文献17所面临的参数选择难题。本文的内容组织如下，第1节分析目前的分簇路由算法的原理及性能，第2节详述作者提出的分环多跳分簇路由算法RBMC，第3节是算法的计算机仿真，第4节是结束语。2 算法描述假设有N个节点，分布在半径为的圆形区域，节点位置已知，节点能量可以相同，也可以不同，Sink节点位于区域的中央。2.1 同心均匀间隔圆环的多跳网络模型由于节点在半径为的圆形区域里均匀分布，在此基础上均匀随机生成的簇头也一定在区域中均匀分布。为了便于多跳路径的建立与相关参数分析，同时不失一般性，本文在逻辑上将整个区域划分成S个均匀间隔的同心圆环区域，圆环的中心为Sink，圆环间的间距为（单位为m，下同），如图1所示。图1 分环多跳网络模型从Sink节点向外将圆环分别编号为第1环，第2环，第S环（其中的第1环实际上是以Sink为圆心的一个圆，为了统一，这里也将其称为一个环）。由于节点在区域中的部署是随机的（比如通过人工随机撒播），部署之前无法确定每个节点将会落入分环模型中的哪个环。为了便于节点的配置与部署，本算法只在Sink节点中配置关于区域的总体信息集合，定义为(1)当节点被部署后，Sink首先通过总体信息，计算出各环的最优初始簇头选举概率，再将和以及Sink节点的位置打包为SINK_ADV_SYS_MSG消息，向区域中广播。当区域很大时，SINK_ADV_SYS_MSG将以泛洪的方式进行广播，每个初次接收到该包的节点都将广播一次该消息，以使消息能到达区域中的每个节点。区域中的任一节点接收到广播包后，通过总体信息和自身的位置，即可以确定自己所在的环，其方法是(2)其中，为距离运算，取欧氏距离。由此，节点可以从集合中找到自己所在环的簇头选举概率。每个环内的节点根据所在环的簇头选举概率，进行独立的簇头自选。当选的簇头将向外通告CH_ADV_MSG消息，消息中包含簇头的位置。周围的簇头和普通节点都将接收到这个消息。簇头消息通告结束后，普通节点从接收到的多个簇头的CH_ADV_MSG消息中选择离自己最近的簇头，向其发送NODE_JOIN_MSG消息；而第k+1环的簇头节点则从接收到的所有第k环簇头的CH_ADV_MSG消息中，选择距离自己最近的簇头，作为下一跳，向其发送RELAY_REQ_MSG，从而形成了相应的簇及簇间的多跳路由。考虑到簇头通告是采用广播的方式发送的，由于访问冲突及干扰等因素，可能会有极少量的节点（簇头）没有收到任何CH_ADV_MSG消息。LEACH算法中让这类节点直接发送数据到Sink节点，这在区域比较大的情况下是低效率的或者不可能的；另外，对于没有收到簇头通告信息的簇头，则会造成多跳通信无法建立的严重问题。为此，在簇头通告结束后，没有接收到任何CH_ADV_MSG消息的节点（簇头）将主动向外广播CH_REQ_MSG消息，消息中包含自己的ID。收到该消息的相应簇头向其单播发送CH_ACK_MSG消息。通过这一过程，保证了簇和多跳路由的可靠建立。在一个数据采集周期里，簇内节点将采集的数据发送给簇头，簇头对数据进行聚合处理。第k+1环区域内的簇头把聚合后的数据发送自己的下一跳簇头（即距离自己最近的第k环区域内的簇头，在前面的过程中已经选择好），第环内的簇头再将其转发给第k1环内的簇头，以此类推，数据最终到达Sink节点。由于来自不同簇的数据相关性很小17，聚合效率不高，因此簇头不对来自上一跳簇头的转发数据包作聚合处理，只是转发给自己的下一跳。在这样的分簇多跳网络中，离Sink节点近的环里的簇头转发负荷大，易提前耗尽能量而死亡，此即无线传感网中的“热点”问题。为了克服这个问题，本文通过控制不同环中的簇头选举概率，在不同的环里构建大小不同的簇，以均衡不同环的簇头间的能耗。概括来说，是让距离Sink越近的环，形成的簇的规模越小，使其簇头消耗在簇内通信和数据聚合上的能量越少，以补偿其因为转发外环簇头的数据包而造成的能量消耗；而距离Sink越远的环，形成的簇的规模越大，使其在簇内通信和数据聚合上的能耗增大，以抵消其因转发的数据包较少而节省的能量。一个环中的平均簇大小是由该环的簇头数来控制的；求得了一个环的最优簇头数，也就求得了该环的最优簇头选举概率。因此，本算法的关键是求解各环的最优簇头数。RBMC的多跳模型与文献13类似，但文献13中没有使用簇大小异构的思想，也没有对分环的参数给出分析。2.2 各环最优簇个数在一个簇头周期里，普通节点（无论处于哪一环）仅和自己的簇头通信，不同环的节点能耗相差不大；而簇头除了和所有簇内节点通信外，还要进行数据聚合，转发簇间数据包，其能耗远大于普通节点，且越靠近Sink的环里的簇头能耗越大。因此，均衡能量消耗，主要目标是均衡不同环的簇头间的能耗。一个簇头周期分为簇（及多跳路由）建立阶段和数据采集阶段。在第一个阶段，各环的簇头仅和自己周围的节点进行控制包的收发，由于节点均匀分布，控制包很小且仅有极少量的若干次收发，因此可以认为此时所有簇头的能耗也是相差不大的。在第二个阶段，簇头收发和处理的数据包的尺寸非常大（一般至少比控制包大一个数量级），且是以一定的频率周期性的进行的，不同环的簇头需要转发的数据包的数量相差很大，此阶段消耗了簇头的绝大部分能量，极易造成不同环簇头间能耗的不均衡。下面，将从分析数据采集阶段的一个数据采集周期里簇头的能耗出发，推导出不同环的最优簇个数。这里分析将圆形区域划分成S个环的情形，即，假设第环的簇个数为,第环内的节点总数为。从而(3)假设传感器节点在区域中均匀分布，则选举出的簇头应该也是在区域中均匀分布的，当节点的数量非常大时，可以求出第环中簇头到Sink节点的距离平方的期望和距离的期望：(4)(5)第环中的簇头到第环中簇头的距离平方的期望:(6)这里采用和文献10相同的能耗模型，有关参数的定义参见文献10。由于采用多跳模式，单跳通信距离比较短，因此假设所有的节点间的通信距离均小于临界距离18。由此，第环中一个簇头的平均能耗可表示为(7)从能量消耗均匀的角度出发，第环中簇头的平均能耗应该等于第环中簇头的平均能耗：即要满足。选取，可以推导出第一环中的簇头数和其它各环中的簇头数之间的关系，由此可以得到个关于的方程式，尚不足以求解方程组。下面，再从最小化第一环内节点的总能耗出发，推导最优的。位于第一环的节点数为，第一环（实际上是以Sink为圆心的一个圆，故这里称为半径）的半径为，则第一环中一个簇头节点的平均能耗为(8)一个非簇头节点的能耗为，其中，(9)一个簇的总能耗(10)故而第一环中所有节点总的能耗为(11)为使第一环的总能耗最小，即(12)利用式（12）可以求出第一环的最优簇头数。结论：在分环模型下，第一环的最优簇个数不受外面各环的簇头个数的影响。可以从本文的分环模型去理解上面的结论。因为第一环外面各环的簇头向第一环转发的数据包是均匀分布在第一环的所有簇头上的，因此对第一环的各簇头来说，其负荷是同时增大的，因此最优的簇个数不会受到外面各环簇头个数的影响。根据前面导出的能耗均衡的条件，有(13)由式（3）、式（6）、式（12）和式（13）联立组成多元二次方程组，可以求得各环的最优簇头数。作为示例，这里给出S2，3，4的情形下的最佳簇个数。在2个环的情形下，=1 000,=60m时,求得m116，m2 =37。容易计算得知，第2环中每个簇比第1环中每个簇大30%左右。在3个环的情形下，=1 000,=60m时，求得m1=11, m2=20, m3=28，即第2环中每个簇比第1环中每个簇大65%，第3环中每个簇比第1环中每个簇大97，第3环中每个簇比第2环中每个簇大20。在4个环的情形下，=1 000,=60m时，求得m1=8, m2=13, m3=17，m421，第2环中每个簇比第1环中每个簇大84%，第3环中每个簇比第1环中每个簇大133%，第4环中每个簇比第1环中每个簇大164%。从这几种情形可以分析出，通过控制每个环中的簇个数，使得不同环中的簇大小不同：距离Sink近的环里的簇小，距离Sink远的环里的簇大，即产生了簇异构现象。随着分环数的增多，里环的簇和外环的簇之间的这种差别会进一步增大。这是因为，随着环数增多，里环的簇头需要转发的数据包会更多，用于转发的耗能会更大，缩小簇的大小可以减小簇内耗能，最终达到能耗均匀化的目标。2.3 簇头选举概率RBMC算法中的簇头选举过程可以使用2种方法。若节点是能量同构的，使用LEACH算法10提出的簇头选举模型，每一环中的节点以各自的概率单独进行簇头选举。各环节点簇头选举的门限为(14)下标表示区域中的第环，下标表示第环的第个节点。为第环节点进行簇头选举的当前总轮数。Nk为第环的节点总数，mk为第环中期望的簇头个数。表示在该簇头周期的前面所有轮中还没有充当过簇头的节点的集合。若节点是能量异构的，使用SEP算法18来选举簇头。假设网络节点中，高级节点的比例为，其所携带能量是普通节点的倍，因此整个网络的能量是原来的倍。从均匀能量的角度出发，高级节点将有更多的机会成为簇头。假设同样空间分布下，LEACH算法的最优簇头选举概率为，每个簇头周期为，则在SEP算法下，每个簇头周期将变为：18。在一个簇头周期中，普通节点将充当一次簇头，而一个高级节点则充当次簇头。设每一轮中，普通节点选举作为簇头的概率为，高级节点选举作为簇头的概率为，有(15)可以得到能量异构情形下，普通节点和高级节点成为簇头的门限：(16)其中，表示当前的轮数，表示在该簇头周期的前面所有轮中还没有充当过簇头的普通节点（高级节点）的集合。表示普通节点、高级节点成为簇头的门限。2.4 算法执行过程简述RBMC算法的执行步骤如下：1) Sink节点根据配置的区域总体信息集合I，计算出各环的最优簇头选举概率T，将I和T以及Sink节点的位置打包为SINK_ADV_ SYS_MSG消息，向网络中以泛洪的方式广播；2) 网络中的所有节点根据收到的SINK_ ADV_SYS_MSG包，利用式（2），确定自己所在的环，从SINK_ADV_SYS_MSG包中找到所在环的簇头选举概率；3) 簇头自选：每个节点以均匀分布生成一个随机数，将其与所在环的簇头选举概率进行比较判决，确定是否在本轮中充当簇头；4) 当选簇头以为半径向外通告CH_ADV_MSG消息，消息中包含簇头的ID及位置；5) 非簇头节点根据接收到CH_ADV_MSG消息，选择离自己最近的簇头加入，向簇头发送加入请求消息NODE_JION_MSG，消息的内容为节点的ID；第环簇头根据收到的第环簇头的通告消息，选择距离自己最近的簇头作为下一跳，向其发送转发请求消息RELAY_REQ_MSG，消息的内容为自己的ID及所在环的编号；6) 没有收到任何通告消息的节点及簇头主动向外广播CH_REQ_MSG消息，消息中包含自己的ID；收到该消息的簇头向其单播发送CH_ACK_MSG消息，消息中包含簇头的ID。由此每个普通节点均找到了所属的簇，每个簇头均找到自己的下一跳，簇及多跳路由建立阶段结束，进入数据采集阶段；7) 各环节点每t s进行一次簇头轮换，循环从3)到7)的过程。3 仿真验证仿真的算法包括LEACH、SEP、EEUC、和本文提出的RBMC(使用LEACH和SEP作为各环的簇头选择算法，分别称为RBMC_LEACH，RBMC_SEP)。仿真环境采用NS2（NS-2.31）和Matlab，其中LEACH算法的仿真代码是由MIT在uAmps项目中所开发的代码19移植修改而成。仿真的重点为不同算法的生命周期和能量效率。论文对节点总数N=400，N=1 000，N=1 600，N=8 000，区域半径从40m到720m的场景均进行了仿真。为了保证大区域下的节点能进行较长时间的通信，在NS2中，每个普通节点的初始能量为10J，每个高级节点的初始能量为普通节点的2倍，高级节点所占比例为10%(b0.1)或者没有(b=0)，普通节点和高级节点在区域中随机均匀分布。由于本论文中分析比较的各种算法均是参照LEACH算法所作的改进或扩充，为了便于比较，本文的仿真环境中所用的各种公用参数均采用LEACH算法中的参数。表1为仿真中所用的主要参数。表1NS2仿真环境主要参数参数名称参数值接收门限(CSThresh)1 nW成功接收门限(RXThresh)6 nW宽带1106 Mbit/sEelec5010-9 J/bitfs10pJ/bit/m2Emp0.0013pJ/bit/m4EDA5 nJ/bit/signaldo87m队列算法Queue/DropTail队列长度100 packets链路延迟25us包头开销25 byte数据包尺寸500 byte3.1 生命周期的定义根据网络的规模大小及应用场景的要求不同，对传感器网络生命周期的定义差异很大，这里仅从存活节点数量的角度给出本文对生命周期的定义。设TH为网络正常工作的门限值，运算符表示求集合元素个数，设t时刻的失效节点集(17)则定义网络的生命周期为(18)由于仿真中的传感器节点数量比较大，少量节点失效对网络的正常运行几乎没有影响，因此将其中的门限取值为0.1。下面分析中的所有数据均为10组实验数据的统计平均。3.2 生命周期与能量分布1) 节点数=1000，分环数3，区域半径240m，环间间距80m的场景。以下数据为NS2的仿真结果，仿真效果如图2图4所示。仿真表明，在节点能量同构（0）的情况下，LEACH 算法的平均生命周期为161s，SEP算法的平均生命周期为158s，两者的生命周期相当。这是由于此时节点能量相同，SEP算法实际上等同于LEACH算法。EEUC算法有4个可调参数，这里使用该文作者在文献17中采用的参数：T=0.4，R0comp=90m，c=0.5，TD_MAX=150m，由此得到的平均生命周期为301s。RBMC_LEACH的平均生命周期为541s，RBMC_SEP的平均生命周期为546s。可见RBMC算法的平均生命周期均比SEP、LEACH和EEUC长，RBMC_LEACH比LEACH的生命周期长236%，RBMC_SEP比SEP 的生命周期长245，RBMC_LEACH的生命周期比EEUC长79%。说明当节点密集、网络的区域比较大时，LEACH和SEP算法以单跳方式传输数据的能量消耗大，缩短了网络的生命周期；而RBMC由于信号发送半径小、节点的冲突范围小、能耗相对均匀而大大提高了能量利用效率，生命周期得以大大延长。EEUC作为多跳算法，其本身的能量效率相比单跳算法也有很大的提高，但因其参数的最优选择比较困难，影响了其性能的发挥。当节点能量异构（0.1）时，LEACH算法的平均生命周期为165s，SEP算法的平均生命周期为179s，相比之下，SEP算法的网络生命周期增加了8左右。RBMC_SEP的生命周期为602s，RBMC_LEACH的生命周期为545s。EEUC的平均生命周期为381s。RBMC_LEACH的生命周期比LEACH长230，RBMC_SEP的生命周期比SEP长236，RBMC_LEACH的生命周期比EEUC长40%。可见在能量异构的情形下，RBMC算法的性能大大领先于其他算法。另外还能发现，尽管区域中的高级节点只占10%，但RBMC_SEP和RBMC_LEACH相比延长了网络将近10%的生命周期，说明RBMC_SEP能够充分利用异构的能量提升网络的性能。因此，通过适当控制区域中高级节点的比例，可以大大延长网络的生命周期。从另外一个角度说，如果周期性的向一个剩余能量不多的WSN网络中随机均匀补充一部分节点，同时配置Sink发布新的SINK_ADV_SYS_MSG消息，可以延长网络的生命周期，限于篇幅，这里不对此种情形进行详细分析。 (a) 能量同构 (b) 能量异构图2 生命周期曲线（1 000个节点，区域半径240m，分环数为3）图3为生命期结束时的剩余能量分布（这里仅列出EEUC，SEP，RBMC_SEP的能量曲线），可以发现，此时SEP算法剩余能量比较大的节点很多，而剩余能量比较小的节点数却只占很小的比重，说明在区域比较大的情况下，SEP算法已经不能保证能量的均匀消耗。RBMC算法中剩余能量在1.5左右的节点数占了最大的比例，比SEP算法更靠近零点，而且曲线拖尾也更短，说明它的能量利用效率比SEP要高很多。图中也可以看出，EEUC算法的剩余能量也比较靠近零点，这是因为EEUC的多跳算法中把节点的剩余能量作为簇头下一跳选择的一个重要指标，促进了能耗的均衡化。(a)能量同构 (b) 能量异构图3 生命周期结束时的剩余能量分布（1 000个节点， 240m半径，分环数3）图4显示了RBMC_SEP仿真中3个环的簇大小曲线。第1个环每个簇的节点个数的均值约为10，第2个环每个簇的均值约为16，第3个环每个簇的均值约为20。理论上计算，第1个环的簇大小均值应为10，第2个环应为17，第3个环应为21，可见仿真和理论计算上比较吻合。但是，从图中也可以看出，每个环中都有些簇偏大或者偏小，这是由于本地随机簇头选择算法造成的，要解决这个问题，需要给每个节点更多的全局信息，或者使用Sink作集中式的簇头选择及分簇，但这在大区域下的代价是比较大的。2) 其他场景在MATLAB仿真环境下，也有类似的结论。以下数据为MATLAB环境下的仿真结果，其中的生命周期以数据采集轮数为单位，普通节点的初始能量为0.5J，其他参数与表1相同。因篇幅有限，这里没有给出仿真的曲线，只将仿真所得的生命周期在表2中列表显示。 (a) 能量同构 (b) 能量异构图4 RBMC算法的簇异构曲线（1 000节点，240m半径，分环数为3）表2 各种仿真场景下的生命周期（以数据采集轮数为单位）仿真场景EEUCLEACHSEPRBMC-LEACHRBMC-SEP节点数400,区域半径200m, RBMC分环数2同构513460458782790异构552463501834871节点数1 000,区域半径240m, RBMC分环数4同构478287285727729异构517287306758775节点数8 000,区域半径720m, RBMC分环数4同构36944513520异构42645530567表2中可见，当区域比较小（区域半径200m）时，RBMC相对LEACH、SEP的优势比3.2节的仿真结论有所减小，其原因是，此时区域比较小，单跳通信距离较短，LEACH、SEP能够体现一定的性能；另外，此时节点总数比较少，在分环模式下，每个环的节点数比较少，RBMC的簇头选择效率会有所下降。当区域很大的情况下（区域半径720m），LEACH、SEP的性能完全不能接受。EEUC因为采用了多跳机制，其性能表现也比较稳定。相比之下，RBMC算法一直都保持了最长的生命周期。3.3 分环与不分环的选择文中直接给出的是采用分环时的有关分析，但是没有给出分环与不分环的界限，这里给出仿真的结论。区域半径从20m到220m变化，用不分环LEACH算法和分环数为2的RBMC_LEACH算法仿真各种区域下网络的生命周期，所得曲线如图5所示。可以看出，当区域的半径比较小时，LEACH算法的生命周期比RBMC-LEACH算法长；随着区域半径的增大，LEACH算法的能量效率逐渐降低；当区域半径超过70m左右时，LEACH的生命周期比RBMC-LEACH短，并且随着区域的增大，两者间的差别越来越大；之后由于区域过大，节点分布变稀，RBMC-LEACH的生命周期也迅速缩短。图5 不分环与2分环的生命周期比较(400节点，能量同构)3.4 生命周期和分环数的关系最后讨论当区域半径比较大时，最佳的分环数。给定区域为半径160m，240m，720m，节点总数分别为1 000个、1 600个和8 000个。仅仿真当分环个数从2环到8环时，网络的生命周期。图6中可见，当区域半径为160m时，分环数为2的生命周期最长，随后逐渐变短；当区域半径在240m时，分环数为3的网络生命周期最长，继而逐渐变短；当区域半径为720m时，分环数为4的网络生命周期最长。该仿真表明，区域面积越大，分环数应该越多；但并不是越多越好，当环数到达某一最优值后，继续增大环数反而会降低网络的性能。其原因，一方面是由于分环数比较多时，簇头接收、聚合、转发的耗能增量抵消了多跳带来的能效增量；同时，分环数越多，单个环内的节点数越少，不利于簇头的最优选择；跳数过多也会使得网络的延迟大大增加，使传感网络难以实时响应某些事件。另外，从图6中也可以看出，在同样的区域下，节点数越多生命周期越长，这也是符合直观想象的。图6 生命周期与分环数的关系（能量同构）4 结束语本文在分析已有分簇路由算法的基础上，提出了RBMC算法，采用分环模式实现传感器网络中的多跳路由；对第一环内节点采用能耗最小为目标，寻求第一环的最优簇头个数；从能耗均匀的角度出发，给出求解其余各环最优簇头个数的方法，从而构造了距离Sink近的簇小、距离Sink远的簇大的异构型传感器网络，较好的克服了网络中的“热点”问题。网络中的节点只需知道自己的位置和Sink的位置，不需要知道全局网络信息，这为实际应用带来方便。RBMC能够适应能量同构和能量异构的情形，具有比较广泛的适用性。仿真表明，在大区域的情形下，该算法的网络生命周期比单跳算法LEACH、SEP以及多跳算法EEUC更长，能量消耗更均匀。参考文献：1POTTIE G J, KAISER W J. Wireless integrated network sensorsJ. Communications of the ACM, 2000,43(5):51-58.2BAKER D J, EPHREMIDES A. The architectural organization of a mobile radio network via a distributed algorithmJ. IEEE Transactions on Communications, 1981, 29(11): 1694-1701.3DAS B, BHARGHAVAN V. Routing in ad-hoc networks using minimum connected dominating setsA. Proceedings of IEEE International Conference on Communications(ICC)C. 1997.376-380.4LIN C R, GERLA M. Adaptive clustering for mobile wireless networksJ. Journal on Selected Areas in Communication, 1997, 15(7): 1265-1275.5AMIS A D, PRAKASH R, VUONG T H P, et al. Max-min d-cluster formation in wireless ad hoc networksA. Proceedings of IEEE INFOCOMC. 2000.32-41.6HEINZELMAN W R, CHANDRAKASAN A, BALAKRISHNAN H. Energy-efficient communication protocol for wireless microsensor networksA. Proceedings of IEEE HICSSC. Hawaii, USA, 2000.7CHIASSERINI C F, CHLAMTAC I, MONTI P, et al. Energy efficient design of wireless ad hoc networksA. Proceedings of European WirelessC. Florence, Italy, 2002.8EPHREMIDES A, WIESELTHIER J E, BAKER D J. A design concept for reliable mobile radio networks with frequency hopping signalingJ. Proceeding of IEEE,1987, 75(1): 56-73.9PAREKH A K. Selecting routers in ad-hoc wireless networksA. Proceedings of ITSC. 1994. 420-424.10HEINZELMAN W R, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networksJ. IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.11BANDYOPADHYAY S, COYLE E J. An energy efficient hierarchical clustering algorithm for wireless sensor networksA. Proceedings of INFOCOM 2003C. 2003.1713-1723.12MHATRE V, ROSENBERG C. Homogeneous vs. heterogen