基于跳数限制的高能效分簇路由算法

蔡 钊，马林华，黄绍城，孙康宁，田 雨

(1.空军工程大学 航空航天工程学院，陕西 西安710038;2.95876 部队，甘肃 张掖734100)

0 引 言

分簇算法通过构建层次化的拓扑结构，依靠簇头融合作用减少数据包发送量和路由维护信息量，很大程度上提升了网络的能量效率，其中，最具代表性的算法有LEACH［1］，DEEC［2］等。但这些算法要求簇头与基站之间采用直接通信的方式传输数据，极大地增加了簇外通信能耗。基于此，很多采用簇外多跳方式传输数据的分簇算法［3～6］被提出，但也随之产生了“热区”问题［7～9］。此外，在实时性较强的传感器网络中，要求部分数据需在指定跳数内到达基站。目前，虽有一些基于最小跳数的分簇路由算法［10，11］被提出，但此类算法并不能保证所有紧急数据包的传输实时性。

针对上述问题，本文提出一种基于跳数限制的高能 效 分 簇 路 由(hop－constrained energy－efficient clustering routing，HCECR)算法，其相较于传统算法有三个创新点:1)根据网络规定的跳数限制、簇成员数量及簇内平均通信开销，构建兼顾能量效率并满足跳数要求的簇结构;2)针对普通数据，在簇间通信中引入了普通节点的中继机制，提高簇头与普通节点之间的负载均衡度，同时减弱基站附近的“热区”效应;3)在数据包传输阶段，簇头根据接收数据包剩余跳数区分紧急和普通数据包，并针对性采取不同的转发机制。

1 系统模型假设

在场景设置上，仅考虑一个基站、n 个同构节点的情况，全部节点随机布撒且不具有移动性。基站无功率限制，传输区域能够覆盖整个区域。网络内每个数据包均设置有最大跳数，根据取值不同分为紧急数据和普通数据。其中，紧急数据具有极强的时效性，需要在指定跳数(跳数属于固定区间)内到达基站。

传感器节点广播信息时使用全向天线，通信区域为圆形，并可以利用非对称链路进行通信。节点具有感知自身位置的能力，且发射功率可以调整，共有n 个离散的发射功率，即p1，p2，…，pn，其中，pn=pmax。为保证数据包的时效性需求，假定所有簇头均能与基站直接通信。

2 HCECR 算法

算法由很多轮次组成，每个轮次分为分簇阶段和数据传输阶段。其中，分簇阶段又可被划分为三个步骤:1)分簇信息泛洪;2)簇头选举;3)簇成员划分。

2.1 分簇信息泛洪

分簇信息泛洪阶段，各节点要广播自身分簇(CL)信息，并依据收到的分簇信息构建邻居队列。其中，分簇信息由六部分组成:源节点地址S_Add、坐标S_Pos(x，y)、上一跳转发节点地址L_Add、坐标L_Pos(x，y)、数据包剩余跳数R_hop、源节点至当前节点的累计最小可达能耗TMRC。当节点i 要发送初始分簇信息时，各参数应按照式(1)进行设置

节点收到邻居CL 信息后，忽略源节点地址相同且TMRC取值更大的信息和剩余跳数为0 的信息，利用剩余信息更新邻居表。首先计算自身到上一跳节点的距离，并利用式(2)得出最小可达能耗。假设当前节点为i，上一跳节点为last(i)，则传输长度为l 数据包的最小可达能耗为

节点将数据包剩余跳数减一，并将最小可达能耗与原数据包中的TMRC 进行累加，得出从源节点到自身的TMRC

计算出TMRC(i)和数据包剩余跳数后，节点要利用处理后的CL 信息更新邻居队列，并将L_Add 和L_Pos(x，y)分别替换为自身地址和坐标，再次转发此CL 信息。

2.2 簇首选举

经过t0时间后将进入簇头选举阶段，簇首的选取需综合考虑节点剩余能量、簇内平均通信开销和成员数量，簇头权值表达式见式(4)。每个节点计算出自身的簇头权值后将进行广播，同时接收邻居的簇头权值。若节点的簇头权值高于所有邻居的取值，则向基站推举自己为潜在簇头;否则，作为普通节点。基站根据各潜在簇头的簇头权值和邻居队列确定正式簇头，并广播正式簇头信息

式中 wCH(k)为k 的簇头权值，Qs为邻居队列的元素个数，ER(k)和E0(K)分别为节点k 的剩余能量和初始能量。

2.3 簇成员划分

每个正式簇头需向自身邻居队列中的所有成员发送簇头声明(CHS)信息，CHS 信息包含五项内容:簇头地址、目的节点地址、上一跳节点地址、上一跳节点坐标和TMRC。其中，目的节点即为簇成员，上一跳节点为最近转发CHS信息的节点，TMRC 则代表从簇头至簇成员的累计最小可达能耗，此项可由簇头查找邻居队列得到。普通节点根据收到的CHS 信息，判断自身是否属于某个簇头的成员，若不属于任何簇，则声明自身为正式簇头;若仅属于一个簇头，则成为该簇的成员;若同时属于多个簇头，则加入TMRC 取值最小的簇，并将自身属于多个簇的情况告知这些簇头。特别地，满足第三种情况的节点可以承担簇外的中继任务，减小簇头的转发能耗。

假设节点p，q 分别为簇头i，j 的成员，k 为两个簇的共有成员，即j∈B(i，j)。此时，若节点i 向j 传输的是普通数据包，则应当采用簇间的多跳中继，如图1 虚线所示。若为紧急数据包，则要采用簇间的直接通信(图1 中直线)或基站的直接通信。

图1 簇外通信示意图Fig 1 Diagram of outer-cluster communication

在簇划分结束后，普通节点根据CHS 信息中的上一跳坐标和自身坐标，计算两点间距离并调整自身传输半径。当两点间距离满足:rm－1＜d(i，next(i))＜rm时，将传输半径调整为rm。虽然节点调整发射功率造成了部分非对称链路，但这并不影响簇内数据的汇聚。因为数据包向簇头汇聚的路径是单向的，而当簇头需要向成员传输数据时，由于已知其坐标可采用直接通信。

2.4 节点类型与数据包类型

在数据传输阶段，网络内的数据包共分为三类，即感知、融合和中继数据包。传感器节点探测环境产生感知数据包，将其发送给对应簇头，簇头接收成员感知数据包后进行数据融合得到融合数据包。而中继数据包是针对普通融合数据包进行簇外多跳通信而设立的，旨在降低转发能耗。

簇头向基站传输融合数据包分为快速模式和正常模式。快速模式针对紧急的融合数据包，即满足R_hop∈［hmin，hup］的数据包。当簇头节点收到数据包的剩余跳数满足下式时:1 ＜R_hop≤hup，采用簇外多跳路由，将数据传输给相邻簇头中距离基站最近的一个簇头。而当数据包剩余跳数为1 时，簇头将直接把数据传输到基站。

相比之下，正常模式是能量效率更高的传输模式，在传输普通融合数据包时使用。在簇外多跳通信中，融合数据包先由簇头直接发送给多簇头交叉集内的边缘节点，边缘节点将数据包类型改为中继包，并通过簇内多跳的方式传给下一跳簇头。

图2 描述了不同节点类型可以发送、接收、转发数据包的类型。簇头可以发送、转发融合数据包，而普通传感器节点将忽略融合数据包，只发送、转发感知数据包或中继数据包。特殊地，处于两个簇头交叉集内的边缘节点可以转发融合数据包。当簇头产生一个融合数据包后，其可以将数据包传给边缘节点，再由边缘节点通过簇内多跳的方式传给下一个簇头，也可以直接传给下一跳簇头或基站。需要注意的是，若边缘节点需要通过普通节点进行中继，需先将融合数据包转换为中继数据包。

图2 节点类型与数据包类型对应图Fig 2 Node type corresponding to data packet type

2.5 能耗模型

根据簇头邻居队列中存储的累计最小可达能耗和剩余跳数等信息，可知单次簇内通信的平均开销

在仅考虑簇内数据汇聚能耗、忽略中继其他簇数据的情况下，普通节点在一个采样周期内的能量消耗为

式中 DDN为网络的平均节点度。由于簇内数据融合采用的是树状结构，故需要其协助汇聚数据的邻居数量是DDN－1。结合式(5)和规定的最小跳数，可以计算出簇间通信的平均距离

忽略转发其他簇头数据的情况下，簇头接收、融合簇内成员数据，并向基站传输自身融合数据包的总能耗为

式中 αin，αout和αBS分别为簇头产生融合数据后，选择簇间多跳传输、簇间直接传输和基站传输的概率，αin+αout+αBS=1。结合这三个概率能得到当前簇(包括簇头和簇成员)转发邻簇融合数据的能量开销

式中 DDCH为下游相邻簇头节点数量。根据式(5)～式(9)可知，单个簇在单个采样周期内的总能耗为

3 仿真分析

本文选用NS2 和Matlab 作为仿真平台，将HCECR 算法与HEED［12］和ECDS［13］算法在过期数据包比例、节点死亡时间等方面进行比较。在数据流设置上，感知、融合和中继数据包的长度均为500 bits，CL 信息和CHS 信息的长度分别为120，96 bits。在节点配置方面，初始能量设为0.5 J，并假定节点在能量耗尽前不会失效。此外，规定紧急数据包跳数的取值区间为5～15，普通数据的初始跳数为255。

首先衡量不同算法的能量使用效率，比较最短节点寿命和最长节点寿命。将场景大小设为400 m×400 m，基站坐标定为(200，200)m，分别仿真节点数为200，300，400 的三种情况。最短与最长节点寿命比较如图3，图4。

图3 最短节点寿命的比较Fig 3 Comparision of the shortest node lifetime

图4 最长节点寿命的比较Fig 4 Comparision of the longest node lifetime

网络内的节点死亡将极大地影响数据的传输路径，增加传输能耗，缩短节点和簇的生存周期，故网络内首个节点死亡时间代表整簇性能下降的起始时刻，最后一个节点的死亡时间表明网络完全失效的时刻。两个时间的整体水平可以反映算法的能量效率，而它们的差值能够体现节点间能量均衡程度。由图3、图4 可知，在不同的节点数量的情况下，HCECR 算法的最短节点寿命和最长节点寿命均长于HEED 和ECDS 算法，且两者之差也是三种算法中最小的，故此算法的能量效率和能量均衡性在三只算法中都是最好的。考虑到HCECR 算法中数据包有严格的跳数限制，在转发过程更多地采用簇头与基站的直接通信，降低了能量效率，故在不同节点数量情况下，比较数据包存在跳数限制和无跳数限制(跳数设为255，算法记为HCECR—W)时节点最短、最长寿命的变化情况，比较结果如图5、图6。

图5 跳数限制对节点最短寿命的影响Fig 5 Impact of hop limit on the shortest node lifetime

图6 跳数限制对节点最长寿命的影响Fig 6 Impact of hop limit on the longest node lifetime

结合图5、图6 可知，无跳数限制的HCECR—W 算法相比HCECR 算法，具有更长的节点寿命。因为HCECR—W 算法在簇外通信中，更多地采用了簇间多跳通信，减少了簇间直接通信和簇头与基站直接通信的次数，降低了簇外的转发总能耗。

最后衡量新算法在数据包实时性方面的提升效果，将三种算法在网络运行期间内失效数据包占总数的比例作为判断标准。设场景大小为200 m×200 m，数据包跳数限制设为2，仿真节点数量为50，75，100 的三种情况，如图7。

图7 过期数据包比例的比较Fig 7 Comparison of ratio of overdue data packets

由图7 可知，在网络运行期间，有跳数限制的HCECR算法无过期数据包。而无跳数限制的HCECR—W 算法则有一定比例的数据包过期，且与HEED 和ECDS 两种算法相比，其随着节点数量的增多，过期数据包比例的增长速度最快。这主要是因为HCECR 算法引入了簇间多跳中继的通信方式，一定程度上增加了转发总跳数，导致满足跳数要求的数据包比例下降。

4 结束语

本文提出一种基于跳数限制的分簇路由算法，构建了兼顾数据实时性和能量使用效率的簇结构和路由转发机制。此外，在簇间利用普通节点中继数据，降低簇头的簇外转发能耗和链路总能耗，均衡簇头与普通节点之间的能量水平。仿真结果表明:HCECR 算法在保证数据包时效性的同时，减小了网络总体通信能耗，提高了节点间能量均衡度。

［1］ Afsar M M，Tayarani M H.Clustering in sensor networks:A literature survey［J］.Journal of Network and Computer Applications，2014，46:198－226.

［2］ Qing L，Zhu Q X，Wang M W.Design of a distributed energy－efficient clustering algorithm for heterogeneous wireless sensor networks［J］.Computer Communications，2006，29:2230－2237.

［3］ Tanwar S，Kumar N，Niu Jainwei.EEMHR:Energy－efficient multilevel hetrogeneous routing protocol for wireless sensor networks［J］.International Journal of Communication Systems，2014，27(9):1289－1318.

［4］ Akkari W，Bouhdid B，Belghith A.LEATCH:Low energy adaptive tier clustering hierarchy［J］.Procedia Computer Science，2015，52:365－372.

［5］ Tiwari T，Roy N R.Heirarchical clustering in heterogeneous wireless sensor networks:A survey［C］∥International Conference on Computing，Communication＆Automation，ICCCA 2015，Noida，Piscataway，NJ，USA:IEEE，2015:1385－1390.

［6］ 曾华圣，熊庆宇，杜 敏，等.一种分布式能量高效的WSNs非均匀分簇路由协议［J］.传感器与微系统，2014，33(3):146－149.

［7］ Hari U，Ramachandran B，Johnson Chris.An unequally clustered multihop routing protocol for wireless sensor networks［C］∥International Conference on Advances in Computing，Communications and Informatics，ICACCI 2013，2015:1007－1011.

［8］ 蒋畅江，石为人，唐贤伦，等.能量均衡的无线传感器网络非均匀分簇路由协议［J］.软件学报，2012，23(5):1222－1232.

［9］ Malathi L，Gnanamurthy R K，Chandrasekaran K.Energy efficient data collection through hybrid unequal clustering for wireless sensor networks［C］∥Computers and Electrical Engineering，2015:1－13.

［10］范书平，马宝英，高晨光，等.一种分簇WSNs 最小跳数路由算法研究［J］.小型微型计算机系统，2014，35(8):1775－1779.

［11］王潇娴.基于最小跳数的WSNs 分簇路由协议研究与设计［D］.南京:南京邮电大学，2011.

［12］Younis O，Sonia F.HEED:A hybrid，energy－efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Trans on Mobile Comput，2004，3(4):366－379.

［13］Albath J，Mayur T，Sanjay M.Energy constraint clustering algorithms for wireless sensor networks［J］.Ad Hoc Netw，2013，11(8):2512－2525.