一种抗干扰半静态分簇路由算法*

祝　敏，李敬兆，葛　斌

(1.安徽理工大学 计算机科学与工程学院，安徽 淮南 232001；2.安徽理工大学 电气与信息工程学院，安徽 淮南 232001)



一种抗干扰半静态分簇路由算法*

祝敏1，李敬兆2，葛斌1

(1.安徽理工大学 计算机科学与工程学院，安徽 淮南 232001；2.安徽理工大学 电气与信息工程学院，安徽 淮南 232001)

摘要:针对无线传感器网络(WSNs)分簇路由算法中的能量洞、热点和抗干扰问题，设计一种抗干扰半静态分簇(AISSC)路由算法，给无线传感器网络提供能量多、距离短、链路质量好的路径来传输数据。该算法利用节点定位获取节点地理位置，综合考虑传感器节点剩余能量和干扰信噪比，通过节点距离度量、节点聚簇、簇间融合、簇头选举和簇头轮换五个步骤进行无线传感器网络节点的分簇。仿真结果表明:这种路由算法可以提高无线传感器网络通信链路质量，均衡网络能量消耗。

关键词：无线传感器网络； 抗干扰半静态分簇(AISSC)路由算法； 信噪比

0引言

无线传感器网络[1](wireless sensor networks，WSNs)具有组网快速、方便且不受有线网络约束的特点，广泛应用于军事安全、环境监测和智能交通等领域。但传感器节点一般分布在人无法接近的特殊环境中，无法补充能量，导致网络能源受限；规模大、密度高的传感器节点，导致网络节点间通信干扰问题。传感器节点能量主要消耗在采集数据、处理数据、接收和发送数据上。其中，接收和发送数据消耗的能量最多。因此，路由算法在无线传感器网络能量方面起着重要作用，优化路径和抗干扰是路由算法两个重点研究的问题。

本文在传统分簇路由算法[2]的基础上，创新地将传感器节点干扰信噪比(SNR)和节点剩余能量加入节点距离度量的计算，综合考虑网络开销和网络抗干扰性能，设计一种抗干扰半静态分簇(anti-interference semi static clustering，AISSC)路由算法，可以有效均衡网络能量消耗。

1无线传感器网络分簇路由算法现状分析

现有分簇路由算法主要为了解决三类问题：一是能量洞问题，二是热点问题，三是链路质量问题。

1)关于能量洞问题

2000年,Heizelman W提出第一种分簇路由算法LEACH[3]，算法主要思想是：在无线传感器网络中随机选择几个簇头，向非簇头节点发布邀请信息，节点根据邀请信号强度决定加入哪个簇。在LEACH基础上，Heizelman W又提出一种算法LEACH—C，节点把自身地理位置、能量和邻接关系等信息直接发送给Sink节点，Sink节点择优选择簇头。所有节点直接与Sink节点通信，导致离Sink节点较远,节点能耗过大。HEED算法簇头选举主要参考节点的剩余能量信息，但是，每次选举簇头需要簇内节点通过大量通信来反馈结果，节点能耗较大。TEEN算法按照LEACH算法进行节点的聚簇和簇头选择，在簇头节点设置软硬两个阈值以减少发送数据次数，降低网络能耗，但是阈值的设置缺少理论依据。

2)关于热点问题

针对热点问题，文献[4]提出很多分簇路由算法,主要思想都是采用非均匀半径聚簇方法进行传感器节点分簇。距离Sink节点较近的簇头，不仅要接收簇内节点的信息，还要转发外层簇的信息。因此，需要形成较多簇，分担转发信息的任务；距离Sink节点较远的簇头，主要负责收集簇内信息，转发消息的任务较少，可以形成较少簇。但是，聚簇半径大小的设置缺少理论依据，而且这种算法比较复杂，能耗过大。

3)关于链路质量问题

一些算法是在泛洪算法的基础上，利用链路空间相关性或者构造最优链路树，优化转发路径。文献[5]提出一种考虑链路质量的路由选择机制算法EXT，把期望传输次数作为路由选择参考。文献[6]在EXT算法基础上进行改进，选择路径时考虑累计链路质量，进一步优化路径，但是，算法未考虑传感器节点能量问题，导致节点成为传输热点。文献[7]提出一种较为全面且考虑链路质量的分簇路由算法，算法采用多路径转发机制，但是传感器节点需要经常计算和保存不同路径的权重，能耗较大。

2AISSC路由算法

2.1干扰信噪比的计算

衡量一个无线传感器网络链路质量的参数评估可以分为两类：基于软件的参数评估和基于硬件的参数评估，如图1所示。

图1　链路质量评估的参数分类Fig 1　Parameters classification of link quality assessment

基于软件的评估参数有：包接收率(packet reception rate,PRR),需要的包数(required number of packet,RNP),基于分数(score-based)。基于软件的链路质量评估参数需要通过网络长期发送和接收探测包来进行估值，导致较大网络通信量。

本文采用基于硬件的评估参数SNR来衡量网络链路质量，它的值可以直接通过读取接收信号强度指标寄存器的值计算出来。SNR表示接收到有用信号的强度与干扰信号的强度比值。SNR计算公式为

(1)

其中，Power为接收到有用数据帧的信号强度，Noise包括坏境噪声和其他节点形成的干扰信号噪声。实验中，传播模型采用双径地面反射模型，接收端Powerr为

(2)

式中d为接收端到发送端的实际距离，Powert为发送端数据帧的信号强度，Gt和Gr分别为发送端和接收端的天线收益，ht和hr为发送端和接收端天线的高度，L为系统损耗。在本文实验中，Powert可以进行设置，Gt,Gr和L均设为1，ht和hr设为1.5m。

因此，当节点正接收数据帧，其他数据帧也到来时，接收端对应的SNR为

(3)

式中Power为根据式(2)计算的接收到有用数据帧信号强度，Poweri为其他数据帧的信号强度。

2.2AISSC路由策略

AISSC主要思想是：利用节点定位算法获取节点地理位置信息为基础，在传感器节点分簇时，综合考虑节点剩余能量、干扰信噪比和节点间实际地理距离，在每个簇头节点增加一个簇内节点链表存储节点实时信息，包括地理位置信息、剩余能量和SNR值。根据各个节点的“簇内节点距离和(SEPC)”的值，在簇头链表中节点按照倒序排列。当簇头能量低于一定阈值，按照SEPC值顺序，自动进行簇头轮换。具体步骤如下：

1)节点间距离的度量

在二维欧氏距离公式基础上，加入节点剩余能量和干扰信噪比。改进后传感器节点间距离计算如式(4)所示

(4)

式中E为传感器节点初始能量，Ea和Eb为任意两节点当前能量值，SNRa和SNRb为节点当前信噪比。

2)初始节点聚簇

聚簇时，每个节点把自己看作簇头，向其他节点发送簇融合的信息包，收到信息包的节点计算与信息来源簇之间的距离，计算如式(5)所示

(5)

式中DPGMA为簇间的平均距离，m，n为任意两个簇的节点数，D(i,j)为式(4)中节点i和j之间的距离。

聚簇的同时由簇头创建并维护一个簇内节点链接表，动态更新簇内节点剩余能量、SNR信息和地理位置信息，表内节点的顺序按照SEPC的值倒序排列，SEPC计算方式如式(6)所示

(6)

式中m为簇内节点数，i和j为簇内任意两节点。

3)簇间融合、簇头选举和簇头轮换

根据步骤(2)，距离最近的两个簇进行融合，合并簇内节点链接表。按式(6)计算簇内每个节点SEPC值，更新链接表，SEPC值最小的节点当选为簇头。如果网络中所有簇都满足簇的规模阈值限定，则停止聚簇；否则，簇头发送含有新的簇内节点信息的融合数据包，重新计算与其他簇的距离，进行簇间融合，按照式(6)推选出新的簇头。

当前簇头的能量低于一定的阈值后，链接表传递给下一个将要担任簇头的节点，簇内自动执行簇头轮换操作。

4)重新聚簇

一段时间后，簇内所有节点都不满足担任簇头的要求时，当前簇头向Sink节点发送重新聚簇的信号，所有节点重新聚簇。步骤同样可以分为节点距离度量、初始聚簇、簇间融合、簇头选举和簇头轮换。

3仿真结果分析

实验采用NS2仿真软件，在相同场景参数下分别对LEACH算法、LEACH—C算法和AISSC算法的性能进行比较，验证AISSC算法的有效性和可行性。网络性能分析指标采用网络丢包率和网络中剩余节点数。仿真场景参数设置如表1所示。选用802.11MAC层协议，无线传播模型采用双径地面反射模型。

表1　场景参数

1)网络丢包率比较

图2显示了LEACH,LEACH—C,AISSC算法在相同场景下网络丢包率的比较，未考虑节点干扰SNR的分簇路由算法LEACH和LEACH—C算法网络丢包率近似。仿真进行1 800 s时，LEACH算法丢包率是4.6 %，LEACH—C算法丢包率是4.2 %，综合考虑节点剩余能量、干扰SNR和地理位置的AISSC算法丢包率是2.5 %，相比LEACH—C算法降低了2.1 %。实验结果表明:AISSC算法降低了网络丢包率。

图2　不同算法的网络丢包率比较Fig 2　Comparison of network packet loss rate ofdifferent algorithms

2)网络剩余节点数比较

图3显示了不同算法在相同场景下网络剩余节点数的比较，实验进行到1 800 s时，LEACH算法中剩余节点数为80个，改进算法LEACH—C中剩余节点数为99个，AISSC算法中节点剩余数为112个。AISSC算法相比LEACH—C算法，剩余节点数增加13个，相比LEACH算法，增加32个。图中每个算法消亡速率曲线变化也不同， AISSC算法曲线斜率最大，说明节点能量均衡性较好。因此，表明 AISSC算法有效均衡网络能量消耗。

图3　不同算法的网络剩余节点数比较Fig 3　Comparison of network alive nodes number ofdifferent algorithms

4结束语

本文分析了现有分簇路由算法，针对这些算法的优势和缺陷，设计一种能量有效的AISSC路由算法。首先，算法通过在计算节点距离时加入节点剩余能量和干扰SNR，有效减缓网络中能量洞问题和干扰问题；其次，算法制定特殊的簇内节点管理机制，使无线传感器网络在聚簇的同时进行簇内节点的排序，自动进行簇头的轮换；最后，设计再次聚簇的机制，将能耗小的节点置于簇的中心，增加其充当簇头的概率，有效改善了网络热点问题。因此，AISSC算法综合考虑干扰问题、能量洞问题和热点问题，能有效降低网络能耗，延长网络生命周期。

参考文献:

[1]任丰原,黄海宁,林闯.无线传感器网络[J].软件学报,2003,14(7):1282-1291.

[2]沈波,张世永,钟亦平.无线传感器网络分簇路由协议[J].软件学报,2006,17(7):1588-1600.

[3]HeinzelmanW,ChandrakasanA,BalakrishnanH.Energy-efficientcommunicationprotocolforwirelesssensornetworks[C]∥2000IEEEProceedingsoftheHawaiiInternationalConferenceonSystemSciences,Hawaii,2000:3005-3014.

[4]申志远,刘方爱,侯冰俏,等.节能高效的无线传感器网络非均匀分簇路由协议[J].传感器与微系统,2013,32(12):67-70,77.

[5]CoutoD,AguayoD,BicketJ,et,al.Ahigh-throughputpathmetricformulti-hopwirelessrouting[J].WirelessNetworks,2005,11(4):419-434.

[6]袁正午,梁均军.累积链路质量无线传感器网络路由协议研究[J].计算机工程与应用,2011,47(14):66-69.

[7]DialloC,MarotM,BeckerM.Linkqualityandlocalloadbalancingroutingmechanismsinwirelesssensornetworks[C]∥2010TheSixthAdvancedInternationalConferenceonTelecommunications(AICT),2010:306-315.

An anti-interference semi static clustering routing algorithm*

ZHU Min1， LI Jing-zhao2， GE Bin1

(1.School of Computer Science and Engineering,Anhui University of Science and Technology,Huainan 232001,China; 2.College of Electrical and Information Engineering,Anhui University of Science and Technology,Huainan 232001,China)

Abstract:To solve energy hole,hot issue and anti-interference problem in clustering routing algorithm for wireless sensor networks(WSNs),an anti-interference semi static clustering(AISSC) routing algorithm is proposed.A path of more energy,short distance and good link quality is provided to transmit datas.The algorithm obtains geographical position of nodes by node localization,the residual energy of sensor node and signal noise ratio are synthetically considered,clustering of WSNs node is carried out through five steps,which are distance measurement,nodes clustering,clusters fusion,the cluster head election and cluster head rotation.Simulation result indicates that the algorithm can improve the link quality of WSNs communication,balance the network energy consumption.

Key words:wireless sensor networks(WSNs); anti-interference semi static clustering(AISSC) routing algorithm; signal noise ratio(SNR)

DOI:10.13873/J.1000—9787(2016)02—0147—03

收稿日期：2015—05—15

*基金项目：国家自然科学基金资助项目(6117060)；安徽省自然科学基金资助项目(1408085ME110)

中图分类号：TP 393

文献标识码：A

文章编号：1000—9787(2016)02—0147—03

作者简介:

祝敏(1989- )，女，安徽安庆人，硕士研究生，主要研究方向为无线传感器网络。