一种无线自组网均匀分布簇结构路由

1、一种无线自组网均匀分布簇结构路由EquallydistributedclusteringroutinginwirelessselforganizednetworksHUFu-lin,XIAOHai-jun?!/、？CollegeofComputerScience&Technology,HuazhongUniversityofScience&Technology,Wuhan430074,China):Thispaperproposedanequallydistributedclusteringhierarchyroutingprotocol(EDCHR)whichbasingon

2、thelow-energyadaptiveclusteringhierarchyroutingprotocol(LEACH).EDCHRdividedtheroutingprotocolintothreesteps.Eachnodecoulddecideitsstatebyitself.Theclusterheaderwasselectedaccordingtoenergyuniformprinciple.ThesimulationresultshowsthatEDCHRhaslowerenergyassumptionandlongernetworklifetime.随着竞争的加剧，企业越来越

3、希望他的员工在离开办公室时，仍能通过基于一个号码上的综合通信服务，随时随地利用公司的语音与数据网络资源移动办公，提高办公效率，降低通信费用。企业这种移动办公的需求，对通信运营商、设备制造商提出了挑战需要使用移动自组织网络，满足企业用户高效、便捷、灵活、经济的个性化通信需求1,2。与传统的通信网络相比，移动自组织网络具有自组织、网络拓扑动态变化、多跳路由和节点能量受限等特点。其中，最大的限制因素是在移动办公的环境下，网络中各节点所在的工作环境可能在短时间内无法补充到能量，所以在移动自组织网络路由协议的设计过程中，必须充分地考虑节点的能量消耗问题3。为了达到高效使用能量和延长网络生命周期的目的，使

4、用簇结构来组织各个节点。簇成员节点(clustermember,CM)将收集到的信息发送到簇头节点(clusterheader,CH)，由簇头节点进行数据融合并将融合后的信息发送到基站(basestation,BS)。在自组织网络的簇结构形成过程中，如何选择簇头，各簇成员节点如何选择所在的簇是非常关键的问题。特别是在网络规模大时，簇结构对节能的作用将更加显著4,5。现阶段已经提出了一些路由协议。LEACHM由协议6是一种基于簇结构的分布式路由协议。其中每个节点都可能被选为簇头；剩余的节点将加入需要最小传输能量的簇中。基于LEACH加议，本文提出了一种均匀分布的簇结构层次路由协议(EDCHR。)

5、该协议按照能量均衡的原则选取簇头节点。仿真结果显示，整个网络拥有更长的生命周期。1 设计前提11能量模型使用文献7中相同的能量模型如图1所示。在该模型中，无线发送和接收的能量消耗为Eelec;£fs和£amp为信号放大的能量损失率。信道可使用最小能量消耗来发送数据或接收需要的数据，并且可以在不需要接收消息时关闭。ETx=kxEelec+kx£fsd2dvd0kXEelec+kx£ampd4(>d0(1)ERx=kxEelec式(1)和(2)用来计算传输和接收kbit报文的负载。其中d是传输距离。当dvd0时，信道遵循的是自由空间模型；否则，信道遵循

6、多路径衰退模型7。12设计目标本文的目标是在保证尽量小的能量消耗的情况下，保证自组织网络中每个节点的能量均匀消耗。主要是：a)更低的能量消耗。节点相互通信的过程中，每个节点尽量遵循自由空间模型。在本文中，节点的通信范围为r(也称为簇半径)。对于每个簇，其半径应小于d0/2。如此可以保证任意两个簇头之间的距离小于d0。b) 协议是完全分布式的。通过本地信息，每个节点可以决定自身的状态。如此可以保证协议的可扩展性。如果协议要求节点知道全局信息，那么协议扩展时负载是非常大的，而且很难保证全局的信息一致性。c)簇头节点在区域中均匀分布，以避免不必要的能量消耗。13假设1 )除了基站，在簇形成的过程中，

7、每个节点有相同的传输范围。2)对称通信。例如，如果节点A可以接收到B发送的报文,那么节点B也一定可以接收到A发送的报文。3）每个节点的位置信息是未知的。2 协议描述为了方便描述，本文符号定义如表1所示。表1符号定义表符号含义Ecur节点的当前能量能量ET节点能量门限值Pini节点可以成为后选簇头节点的概率Scan在节点传输半径r范围内，宣称为后选簇头节点的集合Send在节点传输半径r范围内，宣称为簇头节点的集合Sweight簇头集合，其中记录格式为ID,Wdrandom随机数distanceBS节点到基站之间的距离MAPK1示节点根据剩余能量，在竞标簇头节点时的标价W版值，与簇头节点和簇成员节

8、点距离成反比W版值，与簇头节点和基站之间的距离成反比，Wd=1/distanceBS本文将协议分为三个阶段：a）簇构造。在此阶段中，每个节点都有一定的几率成为簇头节点。簇头将在整个网络中均匀地选取，并且每个簇头会选择一个特定的CDMA马，用于簇之间的通信。当簇头节点选举出来后，每个簇成员节点选择合适的簇头。簇头为簇成员节点选择相应的TDMA寸隙。b)建立簇头树。为了节省簇头节点之间通信的能量损失，EDCHR、议按照与基站的距离大小将簇头组成簇头树。c) 传送数据。簇成员节点收集所需数据，并周期性地将数据发往簇头节点。簇头融合接收到的数据，并通过簇头树将数据发送到基站。21 簇构造在EDCHR、

9、议中，簇构造阶段有六步。从第一步到第四步是确定哪些节点为簇头，而第五步和第六步是簇成员节点选择簇头。然后每个簇头节点在簇间选择特定的CDMA马，为簇内各成员节点指定TDMA寸隙。在第一步中，各个节点产生一个随机数。如果随机数小于Pini,节点广播CANDIDAT报文。报文包含节点ID和MARK表明这些节点为后选簇头节点。在将该报文发送到其邻居节点的同时，记录ID和MAR倒Scan中。当邻居节点收到CANDIDATES文后，也记录ID和MAR倒其本身的Scan中。在一些特定的环境中，一些节点的Scan为空，也就是说该节点周围没有任何节点宣称为后选簇头节点。在第二步中，这些为空的节点将广播CAND

10、IDAT报文，宣称本节点为后选簇头节点。经过这两步以后，每个节点的Scan为非空。第三步，每个节点选择其Scan中MARK最大者为簇头节点。如果该节点就是簇头节点，它将广播HEAD报文。报文包含节点ID，表明该节点宣称为簇头节点。如此可能产生依赖链，如图2所示。节点A认为自己是最大的MARK?点，而节点B认为是C,那么节点C将会广播HEA讨艮文，并在Send中记录。而节点B接收到HEA讨艮文后，肯定不会再发送HEA讨艮文，则节点A不会收到HEA讨艮文。所以可能产生有些节点Send为空的情况。第四步，如果节点没有接收到任何HEADS文（包括自身发送的），那么它将广播HEAB艮文。集合Send的记

11、录中包含三个部分：发送者ID、能量和权值Wc。第一到第四步，选举出簇头。第五步，普通节点将会通过权值来判断，并向权值最大的簇头节点发送JOIN报文。簇头节点将创建簇成员列表，并在收到普通节点JOIN报文后，将该节点加入到成员列表。第六步，簇头选择簇间通信的CDMA马和簇内通信的簇成员TDMA寸隙。当节点的能量低于门限值时，EDCH刖议认为该节点死亡，从网络中退出。伪代码如下：22 创建簇头树簇构造完成之后将要创建簇头树。首先，基站向全网广播，各个簇头节点接收到广播以后，通过接收信号的强度获得权值Wd该权值反映了各簇头节点与基站之间的距离。然后，每个簇头以2r的通信半径广播WEIGHT艮文。如果

12、簇头接收到WEIGHT报文，将储存报文发送节点ID以及权值Wd当所有的簇头节点都广播完WEIGHT艮文后，各簇头将选择邻近范围内具有最大Wd的簇头节点作为其父节点。如果拥有两个权值相同的节点，选择ID较大的作为父节点。最后，距离基站最近的簇头将成为簇头树的根节点，并直接与基站通信。当存活的簇头越来越少时，簇头之间将无法组成簇头数。在这种情况下，所有的簇头直接向基站发送数据报文。23 发送数据在无线自组织网络中，每个节点收集数据并在分配的时隙内将数据发送给簇头。为了使得能量消耗最小化，每个簇成员只是在所分配的时隙才激活通信信道，而其他时间信道处于睡眠状态。簇头将每轮簇成员发送的消息收集起来，进行

13、数据融合后，再转发至基站。而EDCHR勺设计中保证了2rvd0,几乎所有的通信都是遵循自由空间模型的，因此节省了大量的能量。24 仿真本文中将LEACHLEACH-CF口EDCHRJ行了仿真与比较。实验平台为Pentium41.8GHz,512MBRAM使用的操作系统是Windows2000下的Cygwin平台，网络仿真平台是NS227(networksimulatorversion2.27)。第一个仿真场景，100个节点随机分布在面积大小为500mx500m的区域，其中基站位置(50m,100m)o第二个仿真场景，100个节点随机分布在面积大小为1000mx1000m的区域，其中基站位置(5

14、0m,175m)。每个节点初始能量为20J。一旦节点死亡，将退出网络。MAC1使用的802.11协议，模拟时间为200s，每10s一轮。在LEACHF口LEACH-8，节点的传输半径是随着簇头与基站的距离而变化的。EDCHR、议中，各个节点使用相同的传输半径150m,该距离与前两种协议中节点的平均距离是比较接近的。图3和4分别显示了在500mx500m和1000mX1000m的环境下，存活节点数量的变化。由于EDCH时前两种协议节点间距离比较接近，开始的时候三种协议的性能比较接近。170s以后，EDCHR勺性能开始明显优于LEAC悌口LEACH-C可以看出EDCHR有着更长的生命周期，如图3所

15、示。在1000mx1000m区域中，显然，EDCHR勺性能要优于前两者。因为随着网络区域的增加，相同数量的节点在网络中的分布将越来越稀疏。LEACHF口LEACH-C协议中，通信的能量是随着节点之间的距离增大而增加的。而EDCHR、议中，通信能量基本上是保持不变的，所以随着网络区域变大，EDCHR勺网络有着更大的生命周期，如图4所示。图5和6中显示的是500mx500m和1000mx1000m两种场景中的节点总能量消耗情况。图5中可以看到，LEACH勺总能量消耗增长速度远远高于EDCHR但是LEACH-Cfc3090s的总能量消耗是低于EDCHR勺。这是因为EDCHR勺簇构造以及簇头树的形成需

16、要消耗一定的能量，但90s以后，EDCHR勺总能量消耗是最小的。图6中，在170s以后，EDCHR勺总能量消耗高于LEAC年口LEACH-C这是因为仿真中，当剩余节点无法构成网络的情况下，将终止仿真。EDCHR总够保证节点均匀地消耗能量，所以仿真终止时的节点数更少。这意味着有更多的节点能量耗尽，所以EDCHR勺总能量消耗较氤图7显示簇构造和组成簇头树的能量消耗。在此阶段，EDCHR在场景500mx500m和1000mx1000m中分别消耗了总能量的0.8%和3%而LEACHF口LEACH-C在相应的场景中大概只需要消耗总能量的0.5两口2%这说明EDCHRE簇构成阶段和组成簇头树阶段的多次广播消息还是需要消耗一定能量的。不过基于轮的簇协议每轮中间隔的时间比较长，所以这样的大能量消耗并不是非常频繁。从前面的结果中也可以看到，总的能量消耗，EDCHR还是优于LEACHF口LEACH-C。由以上的分析可以得出如下结论