WSN中簇首角色自适应能量树链算法

关 昕，王 杰，陶志勇

1.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105

2.辽宁工程技术大学 研究生学院，辽宁 葫芦岛 125105

WSN中簇首角色自适应能量树链算法

关 昕1，王 杰2，陶志勇1

1.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105

2.辽宁工程技术大学 研究生学院，辽宁 葫芦岛 125105

无线传感器网络（Wireless Sensor Network，WSN）中无线通信单元是消耗能量主要单元[1]。传感器节点能量有限且无法补充。网络拓扑结构的合理性影响高层通信协议的执行和网络运行能耗，且传输比运算处理一个比特的能耗大很多倍[1]。从节点参与通信的拓扑和方式，可以将WSN路由协议分为平面路由协议和分簇路由协议。典型的平面路由协议有SPIN[2]、Directed Diffusion[3]、Rumor[4]等。分簇更符合传感器网络的特性，经典的有LEACH[5]、HEED[6]、PEGASIS[7]、TEEN[8]、DWEHC[9]、ACE[10]、FLOC[11]等。

1 相关路由协议

文献[12]提出分层链树的路由协议，根据节点与sink的距离为圆心划分环状层次区域，并形成多跳并行的有向链连接到主链上。但忽视了不同层的节点能量的差异，链路具有不稳定性。文献[13]提出了一种簇头成链算法LEACH-P。能有效地延长网络生存周期，但是簇内仍然是一跳通信，而且簇首的分布不受控制，没有避免簇内和簇首间长链的消耗。文献[14]基于最小生成树多跳通信，将节点的度作为竞争因子，引入非均匀分簇，簇的大小取决于簇头节点到sink节点的距离。但最小生成树没有考虑节点的剩余能量。文献[15]在PEGASIS的基础上引入距离门限避免相邻节点间产生长链。但固定的距离门限使成链丧失了自适应性。且每个节点成链延迟较大。文献[16-19]也提出了各自针对LEACH或PEGASIS的改进。

2 约束簇位置的能量树成链算法

本文针对以上协议提出了簇首角色自适应能量树成链算法（Energy-tree Chain algorithm of Role-adaptive Cluster head，ECRC）。该算法通过设置参考点控制前期簇头的分布，节点根据到最近簇首距离的自适应探测范围汇聚于“大能量节点”，形成能量从根到叶依次降低的“能量树”，能量树根节点成单链由链首向sink节点发送数据，并为低能量的能量树根节点设置选举阈值和替换方案。

本文算法分成四个阶段：簇头选举阶段，能量树建立阶段，能量树根节点成链阶段，数据传输阶段。所有的节点根据接收的信号强度指示（Received Signal Strength Indication，RSSI）可以获知自己的位置信息，并具有一定数目的可调功率，根据接收者的距离远近，自动地调节其发送功率。

2.1 算法中的变量参数设定

（1）pi(n)为每个节点自身产生的随机数。节点每轮产生的0～1之间的随机数，用来和T1(n)或T2(n)比较，确定是否符合选簇首的条件。

（2）T1(n)为前T轮选簇首的阈值。

（3）Q为成簇的间隔轮数。是轮数r的函数，在仿真环节具体设置。

（4）T为对簇首的位置和个数的轮数限制。开始时簇首个数为5且受到参考节点的限制。T轮后簇首的个数可以小于5，并且由选簇首的阈值T2(n)判断随机选出的节点是否担任簇首。基于实验观测首个死亡节点出现的轮数的期望来进行设置。

（5）T2(n)为T轮后选簇首的参数。

LEACH一大轮后G置零忽略了本轮中能量消耗的差异，这里不再设置“G置零”，而是改为用能量阈值M来判断是否让其担任簇首。

（6）M为能量阈值。能量阈值为能量树根节点完成一轮通信所需的最小能量。能量树根节点（簇首或大能量节点）完成本轮通信所需的能量值阈值M为：广播自身剩余能量的能耗+接受广播信息的能耗+接收普通节点数据的能耗+数据融合的能耗+转发单链上和自身融合后的数据给其他能量树根节点的能耗。

该值在每次实验阶段的前T轮通过对每个能量树根节点的以上列出部分的能耗求平均值得出。在T轮之后的选簇公式和能量阈值中应用。属于反馈值，具有对每次实验的参数和场景变化的自适应性。

（7）S为能距因子。能距因子的计算公式S=Eleft/ dtosink，其中dtosink为能量树根节点到sink节点的距离，Eleft为能量树根节点剩余的能量。

（8）Ci为前T轮共用的簇首标记位。

2.2 参考点设置

本文首次提出了设置参考点来约束簇首位置。而且算法中节点到最近的簇首的距离决定了其加入能量树的探测范围，100个节点的最优簇首数目在5个左右[16]，故前期簇首数目设置为5。前期单个能量树结构分布的区域较小。后期节点死亡增多则对应的簇首数目应该减少，簇首位置也不再限制，簇首和能量树根节点分布就变灵活，实现对节点普遍低剩余能量情况下的路由的合理构建。

在100×100的分布区域内，前期先设置5个参考点（图1～3中的菱形），坐标分别为（25，25），（25，75），（50，50），（75，25），（75，75）。在前T轮中簇首在距离参考点L1～L5范围内的节点中选取。

如图1和图2，参考节点1～4的 L1～L4设置为25。为了避免长距离传输设置中间参考节点：L5为25。中间区域与周围有4个重叠区域，为不让中间区域节点能量因选簇过早耗尽，扩大共有区域使中间区域的可选节点变多并通过对节点设置公共的簇首标记位Ci避免重复选簇。

如图3，实际选择簇首的区域完全由每个小正方形区域（50×50）的内接圆决定，避开了簇首在边缘地区的不利情况。

图1 L1～L4

图2 L5

图3 100×100

增设参考点可以将多个（100×100）区域拼接在一起（如200×100）。根据实际监测区域面积对参考点个数进行设置。

2.3 簇头选举阶段

（1）第一轮先基于参考点选出5个簇首，簇首成单链将信息汇聚到sink节点。第一轮结束后，节点能量将产生差异。

（2）从第二轮开始计数，每隔Q轮成簇。设置一个标记Q_round，值随着轮数r的增加而减小。

（3）用成簇算法（此时参数T1(n)）产生在离参考点L1～L5距离内的5个簇首。

算法流程图如图4所示。

图4 算法流程图

与文献[13-14]相比，本文算法设置了前期簇头的个数和选举范围以均衡能耗。而且sink节点没有辅助选择簇首分布，是分布式计算，更好地适应WSN分布式的特性。

2.4 能量树建立阶段

本文首次提出使节点探测和发送的距离为每个节点到最近簇首的距离以适应最近的转发点形成合理的多跳路由树。该阶段的目标是在全网中建立各自独立且均匀分布的能量树结构。

（1）簇首在全网广播自己当选簇首的信号（Advertisement Message，ADV）。

（2）全网内所有节点收到广播后分别计算到最近的簇首的距离设为D(r，i)（即是第r轮第i个节点到最近簇首的距离），所有节点（包括簇首）分别以自己的D(r，i)为半径向附近广播自己的当前剩余能量Eleft，并附带自己的ID号。

（3）所有节点将收到的附近节点ID和簇首的能量信息以能量从大到小的有序表方式保存。

（4）节点比较有序表后将会把信息转发给在其D(r，i)距离内，能量最大的节点（可以是大能量节点或是簇首节点），形成一些各自分离的能量树。如果节点周围的D(r，i)距离的节点中剩余能量最大的非簇首节点和最近簇首的节点能量相同，则优先发送给非簇首节点。

（5）簇首也对周围的节点能量进行比较，并转发收到的信息给周围的大能量节点。除非自身的能量在附近节点中最大，此时簇首自身将作为能量树的根节点。

（6）能量树根节点（可以是大能量的普通节点或大能量的簇首节点）将收到的信息数据融合后准备进行转发。

与文献[12-13]相比，本文算法能量树的建立没有以节点到sink的距离为判断依据，而是以自身的检测范围内的节点能量排序来建立。在每个区域内实现能量地理位置分布的适应性，并且避免了长链。

本文首次让簇首同时具有被约束的位置特性和随机选取的概率特性。并由这两种特性将簇首担任收集簇内信息和连接划分区域以传递能量树根节点信息的双重角色。并且此处的“簇内”已不再是单独依据最近距离来判断，而是在与大能量节点包括距离和能量的竞争中来获取归属自己的节点。此时连接簇首的节点的情况是：离簇首较近，且范围内无比簇首能量更大。因为在离簇首远距离的范围中大能量节点很可能出现。从而避免了到簇首的长距离传输，分担了簇首转发远距离节点信息的任务，同时簇首因为其位置人为设定的均匀性也能承担起转发能量树根节点信息的功能（参考点的均匀性保障了簇首的均匀性，而簇首作为探测距离的端节点的均匀性又保障了能量树分布的均匀性）。同时簇首具有角色自适应性：当簇首能量偏低时其自身吸引普通节点的竞争力就下降，甚至会不接收其他节点的信息而成为实际上的普通节点，这样就及时保护了节点和路由的有效性，而且不用任何的提前设定，都是节点根据探测与节点竞争的动态判断。这更加符合WSN的动态的分布式计算的特点，同时低能量节点仍然可以通过树状拓扑的层次转移，用多跳和子节点的方式转发信息将能耗转移给附近的大能量节点，实现基于节点互助动态能耗平衡。

2.5 能量树根节点成链阶段

本文首次将簇，树，链三种结构有效地结合在一起，提出能量树成链的方法，与簇首或簇内最小生成树成链有很大不同，主要体现在能量和距离的适应性上。该阶段的目标是把全网中已经建立好的各自独立能量树结构的根节点用单链串联起来。

（2）由最远的节点开始，每个能量树根节点根据贪婪算法找到离自己最近的向sink节点靠拢的下一个能量树根节点。

（3）由离sink最远到最后一个节点，用贪婪算法一跳跳地连接起来。

（4）单链形成后，由sink节点在能量树根节点（大能量节点和簇首节点）中选出一个到sink节点能距因子S(r，i)最大的节点，作为链首节点。S(r，i)表示第r轮ID号为i的节点的能距因子。

由于单链承担了较多的数据收集与转发的任务，在数据传输阶段可能会能量耗尽，为了网络链路的完整，需要对链进行维护。后文中提出替换方案对链进行维护。将链上低能量根节点的汇聚转发工作转交给附近探测范围内能量最大的节点同时该根节点变成普通节点以节省能量。

文献[13]提出簇首成链，本文优化为带有距离和能量自适应性的能量树根节点成链，使节点链路连接的方式多元化，并减少了完成一轮通信的最大传输距离。与文献[16]的所有节点成单个最小生成树和文献[17]的距离门限相比，更具有能量适应性，而且探测范围为到最近簇首，相当于对长链的一个距离门限，而偏远节点的探测范围相对更大，能获得更大区域中更多节点链路转发的支持，故是一个动态的距离门限，更具对节点地理位置的适应性。

2.6 数据传输阶段

能量树内普通成员根据TDMA时隙表并调节到父节点能接受到的最小发射功率发送信息，父节点收到数据后与自己采集的数据进行融合后再发往其自身父节点。同时过程受令牌控制，防止数据重复提交。单链再由链首节点产生Token，并将Token发往单链的任意一端，然后链首节点再将Token发往主链另外一端，最后链首节点将两端传来的数据经过融合后，传输到Sink节点。

所谓线上线下“双师课堂”，即由一位名师通过视频在线上直播自己的讲课，而在线下的实体课堂里还有一位辅导老师负责在现场为学生答疑解惑。[2]这种课堂并不完全都是两个教师的“1+1”模式，多数情况下是“1+N”模式的，即一个名师线上上课，同时有N个线下实体课堂在学习该课程，N个线下课堂里配备N个辅导老师进行现场辅助教学。

2.7 低能量的树根节点替换方案

当簇首或大能量节点在转发信息的过程中，能量低于阈值M时，先向全网广播自己放弃担任簇首和告知顶替自己任务的节点的消息，再将自己的一个标志位CantbeCH_flag设置为1，将信息转发至其探测范围内剩余能量最大的节点（非簇首节点优先），由其担任自身的角色。

3 能耗分析

根据如前所述的无线传感网络特点，对ECRC算法能量模型作如下假设：网络能量耗费主要在数据发送、数据接收和数据融合三个方面。成链阶段的能量耗费相对整个数据传送阶段是很小的，忽略不计。而在实际中，因接收机不收数据时可关闭接收机，所以接收机接收不是发给自己的数据的能量耗费可不计。在本文中采用目前比较常用的传感器节点工作能耗模型，将一个k-bit的信息传送距离d，无线通信模块的发送能耗和接收能耗分别为：

式中，Eelec表示传感器无线发射电路(TE)或无接收电路(RE)发送或接收每bit数据的能耗，Efs表示发射放大器将每bit数据传送单位平方米所耗的能量，ETx-elec(k)、ETx-amp(k，d)、ERx-elec(k)分别表示发射电路、发射电路放大器和接收电路的能耗，r为传播衰减指数，其取值由周围环境决定，在仿真中与实际距离阈值d0相比较，取2或4。并且比较结果也导致发射电路放大器能耗一项取不同的系数。

其中Efs为自由空间信号放大倍数。Emp为多径衰减信道信号放大倍数。

n个能量树根节点的无线传感器网络沿着单链传输k-bit的数据到链首节点所消耗的能量为：

式子中的d(i，j)表示链上两个节点ni到nj的通信距离。

能量树根节点所成的单链上从末梢节点到链首节点数据融合消耗的能量为：

不同节点承担的角色分为：单簇首（也是能量树根节点之一）；能量树中非根节点的父节点；能量树根节点；作为能量树根的子节点的簇首；链首（也是能量树根节点之一）节点；普通叶子节点。簇首和普通节点一样，在选出后可以根据节点环境在这些角色中自适应地选择，这是本文算法的核心之一。

4 仿真分析

使用MATLAB进行仿真，导入相同的随机节点分布场景，并在相同参数设置下与PEGASIS协议、HCTRP协议和LEACH-P协议的仿真结果进行比较。

4.1 仿真参数设置

预先设定的MATLAB仿真环境主要参数如表1。

表1MATLAB仿真环境主要参数

并且为了实现对成簇间隔Q的控制，通过以下的公式完成对于其数值的渐变：

通过反复实验，800轮左右网络中出现死亡节点，为了均衡对节点能量的消耗，并将死亡节点出现的轮数延后和低能量状态下的能耗均匀分布，设定800轮之后为每轮分簇。

开始时Q值为5，之后每隔200轮Q的值减去1，到800轮以后通过程序设定为1的固定值。

4.2 实验结果和分析

如图5所示，本文算法中的簇首选择性地将数据转发给到附近的最大能量节点（当附近没有比其簇首自身能量大的节点时，选择自身担任能量树的根节点，如图中间的簇首）。簇首和能量树根节点分布均匀，没有长链，确保近簇区域内的节点的数据收集的同时，也保证节点不会跨越到簇头距离的半径去发送数据给大能量节点。

图5 新算法的链路图（簇首用长方形标示出）

如图6所示，与PEGASIS、HCTRP和LEACH-P算法相比，ECRC算法在节点总能量消耗上更均衡。

图6 网络节点能量图

如图7所示，与PEGASIS、HCTRP算法相比，ECRC算法在存活节点个数上的开始死亡的时间延后了300轮左右，延长了37%。在节点全部死亡，网络失效时间上比PEGASIS和HCTRP推迟了600轮的时间，提高了50%。比LEACH-P推迟了400轮的时间，提高了29%，对网络所有节点的利用率更高。能量树根节点相连成链，回避了长链传输，每跳传输能耗都趋于平均值。由于节点将信息向能量树根节点汇聚，将融合和长距离发送数据的负担转移到了在多个探测距离的迭代范围内具有大能量的节点上，起到了延长网络生命周期的作用。

图7 节点存活数目图

5 结语

本文提出了一种簇首角色自适应能量树成链算法。该算法将在不同的区域均匀分布的能量树结构连接成单链。算法不是簇，树，链三种结构的简单叠加，而是通过簇首的多角色自适应选择将每种结构的特色和优点发挥。簇更适用于簇间短距离通信，树适用于对能耗的层次转移，用多跳和子节点的方式协助低能量节点转发信息而避免长距离发送而能量耗尽失效。链连接所有根节点能减少多簇首的消耗，但太多跳会有延迟，长链会有较大能耗。本文算法避免了多簇首与sink通信，而且单链路径上没有长链和交叉。实验表明，新算法在生存时间、能耗均衡等方面较PEGASIS、HCTRP和LEACH-P算法有明显改进。

[1]Estrin D.Wireless Sensor Networks tutorial part IV：sensor network protocols[R].Westin Peachtree Plaza，Atlanta，Georgia，USA，2002：23-28.

[2]Heinzelman，Rabiner W，Kulik J，et al.Adaptive protocols for information dissemination in wireless sensor networks[C]//The 5th Annual ACM/IEEE International Conference on Mobile Computing and Networking，1999：174-185.

[3]Intanagonwiwat C，Govindan R，Estrin D.Directed diffusion：a scalable and robust communication paradigm for sensor networks[C]//Proc of Mobicom，Boston，2000.

[4]Braginsky，David，Estrin D.Rumor routing algorithm for sensor networks[C]//Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications，2002.

[5]Heinzelman W R，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless micro sensor networks[J].IEEE Transactions on Wireless Communications，2002，1（4）：660-670.

[6]Lindsey S，Raghavendra C S.Power efficient gathering in sensor information systems[J].IEEE Aerospace Conference Proceedings，2002，3（3）：1125-1130.

[7]Manjeshwar，Arati，Agrawal D P.A routing protocol for enhanced efficiency in wireless sensor networks[C]//IEEE Parallel and Distributed Processing Symposium，2001：2009-2015.

[8]Baker D J，Ephremides A.The architectural organization of a mobile radio network via a distributed algorithm[J]. IEEE Transactions on Communications，1981，29（11）：1694-1701.

[9]Ding P，Holliday J，Celik A.Distributed energy efficient hierarchical clustering for wireless sensor networks[C]// Proceedings of the IEEE International Conference on Distributed Computing in Sensor Systems，Marina Del Rey，CA，2005.

[10]Chan H，Perring A.An emergent algorithm for highly uniform cluster formation[C]//Proceedings of the 1st European Workshop on Sensor Networks（EWSN），Berlin，Germany，2004.

[11]Demirbas M，Arora A，Mittal V.A fast local clustering service for wireless sensor networks[C]//Proceedings of Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks，Palazzo dei Congressi，Florence，Italy，2004.

[12]王波，蒋卫，孙燚.改进PEGASIS的分层链树路由协议[J].计算机系统应用，2009（12）.

[13]张震，闫连山，潘炜.基于LEACH和PEGASIS的簇头成链可靠路由协议研究[J].传感器技术学报，2010，23（8）.

[14]霍建营.无线传感器网络分簇路由协议的研究[D].南京：南京邮电大学，2013.

[15]余勇昌，韦岗.无线传感器网络中基于PEGASIS协议的改进算法[J].电子学报，2008，36（7）.

[16]周洁，石志东，张震.WSN中一种基于LEACH协议的改进算法[J].上海大学学报，2013，19（2）.

[17]廖倩.基于能量均衡的无线传感器网络LEACH协议的研究[D].郑州：郑州大学，2013.

[18]古晓辉.无线传感器网络中基于梯度的有网关分簇拓扑控制研究[D].郑州：郑州大学，2013.

[19]宁林.无线传感器网络中基于TLEACH协议的研究[D].长沙：长沙理工大学，2013.

GUAN Xin1,WANG Jie2,TAO Zhiyong1

1.School of Electronics and Information Engineering,Liaoning Technical University,Huludao,Liaoning 125105,China
2.Institute of Graduate,Liaoning Technical University,Huludao,Liaoning 125105,China

In previous routing protocol,the topologies of cluster,tree and chain are simple,and the distribution of cluster heads is irrational.The problem of long chain and crosses also troubles single-chain protocol.In response to this phenomenon, this paper proposes an Energy-tree Chain algorithm of Role-adaptive Cluster head（ECRC）.It liberates the cluster heads from fixed role and constructs secondary topology adaptively.Nodes form energy trees adaptively,the roots of which form into a single chain and combine the advantages of chain,tree and cluster.Simulation results show that this algorithm achieves better results in balancing energy consumption between nodes,and prolonging the network lifetime.

routing protocol;reference points;cluster head;energy tree;single chain;role-adaptive

以往的路由协议中，分簇，成树，成链算法的拓扑结构单一，簇首分布不合理，单链存在长链和交叉的问题，且簇首无法自适应地转换角色融入节点环境。由此，提出簇首角色自适应能量树链算法（ECRC），将簇首从固定角色中解脱，能自适应地进行拓扑的二次构建。节点自适应形成能量树结构，而能量树根节点成单链将簇、树、链优势结合。仿真结果对比表明，该算法能有效地均衡节点间能耗、延长网络生命周期。

路由协议；参考点；簇首；能量树；单链；角色自适应

A

TP393

10.3778/j.issn.1002-8331.1404-0273

GUAN Xin,WANG Jie,TAO Zhiyong.Energy-tree chain algorithm of role-adaptive cluster head in WSN.Computer Engineering and Applications,2014,50（24）：70-75.

关昕（1967—），男，副教授，硕士生导师，主要研究方向：网络安全；王杰（1990—），通讯作者，男，硕士研究生，主要研究方向：无线传感器网络；陶志勇（1978—），男，博士研究生，副教授，主要研究方向：多媒体通信。E-mail：705892335@qq.com

2014-04-17

2014-06-03

1002-8331（2014）24-0070-06

CNKI网络优先出版：2014-07-16，http∶//www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1404-0273.html

book=75,ebook=80