基于节点位置的无线传感器网络分簇路由协议

刘睿琼，齐小刚，孙正海

(1.西安电子科技大学研究生院，陕西西安 710071;2.西安电子科技大学理学院，陕西西安 710071;3.西安理工大学高等技术学院，陕西西安 710082;4.空间电子信息技术研究院，陕西西安 710000)

作为一种新的信息获取方式和处理模式，无线传感器网络(Wireless Sensor Network，WSN)目前已成为国内外备受关注的研究热点。由于工作环境和自身构造所限，WSN网络传感器节点的计算、通信能力及能量都较为有限，对于节点的更换和充电也较难实现。因此，尽量减少节点能耗、延长网络生存时间，已成为WSN网络协议及传输机制研究的一个主要目标。网络中的数据传输靠路由协议控制管理，无线传感器网络具有与传统网络不同的特点，传统路由协议不能有效地用于无线传感器网络。人们研究了众多的路由协议，其中 LEACH(Low—Energy Adaptive Clustering Hierarchy)［1］协议是由美国麻省理工学院的J.Heinzelman等人提出的一种低功耗自适应分层算法，对该算法的分析研究以及改进有着重要的应用价值。

l LEACH协议

LEACH是一种分布式自组织的分簇协议，LEACH协议按轮(Round)运行，每轮分为初始化(Setup)和稳定(Steady)两个阶段。在初始化阶段，首先以自组织的方式随机选出部分传感器节点作为簇头。每个节点产生一个0～1之间的随机数，若随机数小于设定的阈值T(n)，则该节点发布自己是簇头的消息。T(n)的计算公式为

其中，p是簇头占所有节点的百分比，即节点当选簇头的概率;r表示目前进行的轮数;G代表前轮中还没有当选过簇头的节点集合。在簇头选举过程中，若节点已经当选过簇头，则将T(n)值设置为0，在下一轮选举中不再参与簇头节点选举，这样保证网络中每个节点都有当选簇头的机会。当只剩下一个节点未当选簇头时，T(n)值为1，表明其一定当选为簇头节点。簇头节点选定后，选出的簇头进行广播，非簇头节点根据接收信号的强弱来选择加入最近的簇，并通知相应簇头。当簇头节点接收完所有节点的加入信息后，就会形成一个TDMA时隙列表，并向簇内所有节点通知。

在稳定阶段，簇内节点通过TDMA方式与簇头进行通信，簇内其他节点将采集的数据传输给簇头节点，簇头节点对簇中所有节点采集的数据进行进行聚合再发送给Sink节点。

LEACH协议中分层的簇型结构降低了节点能量消耗，但LEACH协议存在以下缺点:(1)簇头的选择完全依赖于簇形成阶段节点产生的随机数，从而导致簇头的产生具有较大的随机性;作为簇头的节点不一定是最优节点。(2)传感器节点分布不均匀，可能会出现个别簇头相距Sink节点太远或部分簇内成员离簇头太远的情况，大幅增加了节点的传输能耗，反而不能有效延长网络生存时间。(3)协议没有考虑节点的剩余能量和节点之间的距离。

2 LEACH－C协议

LEACH—C协议［2］是在LEACH基础上加以改进的一种集中式路由协议。协议仍然引用“轮”的概念，每轮还是簇建立和数据传输两阶段。但在第一阶段与LEACH有较大不同。LEACH－C中，每个传感器要先将自己的位置和能量信息传输给基站，基站根据模拟退火算法和簇平衡原理决定簇头。LEACH是传感器器节点和簇首之间根据广播信号的强度来确定节点归属于哪个簇，而LEACH－C中节点的位置已确定，基站在确定簇头后将簇头的信息广播给各个节点，每个节点根据距离公式算出到各个簇头的距离来确定该节点加入哪个簇。在数据稳定传输阶段，如果簇头没有收到该簇传感器的数据，那么要对节点的能量进行判断，如果小于阈值那么就认为节点已经死亡，如果大于阈值就认为节点已经移动，重新判断节点应该属于哪一簇。

LEACH－C协议由基站选择簇头好处是均衡整个传感器网络的能量，并合理安排簇头的地理位置，使簇头之间不过于集中，从而延长了网络寿命。正是由于整个网络过分依赖基站，若节点由于某种原因不能向基站正确传送自身信息时，基站就无法根据网络情况选出较好的簇头节点。另外，增加了成簇的开销、时间延迟、信号干扰以及网络流量。文中提出一种基于节点的地理位置信息和能量的分簇算法(New Geography and Energy Cluster Algorithm，NGECA)。

3 NGECA算法描述

3.1 网络模型

文中N和传感器节点均匀分布在一个正方形区域内，并且该传感器网络具有如下特点:(1)所有节点部署后不再移动，基站部署在区域以外的一个固定位置。(2)所有节点初始能量相同并可以根据距离调整无线发射功率的大小。(3)若已知对方发射功率，节点可以根据接收信号的强度计算出发射者到自己的近似距离。

3.2 簇头选择

LEACH协议簇首节点分布不均，可能出现节点密集的地方簇首多，节点稀疏的地方簇首节点少，甚至部分节点可能没有在任何簇内，造成网络的不完全连通。另外节点密集处如果产生了多个簇首，收集到的数据也会产生冗余，造成能量的不合理消耗。因此，算法首先寻找最优簇头的个数。

采用的能量模型是一种简单的一阶无线电能量模型通信模型，与文献［3］相同，节点收发数据的能耗通过式(2)和式(3)计算

(1)发送阶段能量消耗为

(2)接收阶段能量消耗

则整个簇在一轮中所需能量Ecluster为簇头和簇成员所需能量因此整个网络一轮中所需能量为K个簇所需能量值之和，即

式(8)中参数具体值均可在网络设置是给定，这样就直接得到最优簇头数。

随后根据网络节点分布，网络规模确定簇首间的最短距离，再结合式(9)中改进阈值T(n)［4］来选择簇头

其中，Ecur表示节点当前能量;E0表示节点初始能量;rs表示节点连续未当选簇头的轮数，若节点成为簇头;rs重置为0。此改进阈值公式不仅考虑能量因素，而且阈值可动态调整，使在连续轮中未当过簇头的节点成为簇头概率变大，平衡网络能量。

3.3 分簇过程

在网络初始化阶段，基站利用较大的发射功率向所有节点发送广播消息(ADV)，每个节点收到后根据接收信号计算自己到基站的距离dtoBS，当第i个节点当选为簇头时，其簇内节点成员数目n［5］可按式(10)确定

其中，λ为加权因子，取0.5;dmax和dmin为节点到基站的最远和最近距离。这样保证了靠近基站的簇规模小、数量多，远离基站的簇规模大、数量少，保持簇间负载均衡。可以得出簇成员的最大数目为

簇头选好后，向周围非簇头节点发出簇头特有信号，非簇头节点根据接收信号强弱判断加入信号最强的簇，簇头必须控制加入簇的节点数量和簇的大小。如果簇头同意节点加入簇，会向节点发送允许加入信息，否则发送拒绝信息。当普通节点收到簇头的拒绝信息时，再尝试向另一个距离较近的簇首发出申请，直至接收到允许加入的信息和簇内传输数据的TDMA，此时分簇成功。这样建簇使得每个簇节点数会比整个网络节点数少得多，传输数据的距离也相对较小，数据传输延迟不会过于明显［6］。

3.4 簇间路由

簇内发送数据采用单跳传输，而簇头将信息融合后以多跳方式传到基站。将Dijkstra算法应用到簇头间路由，其主要思想是用最短路径算法的选路方法，这样做可以使各簇头节点以最快的速度找到距离 Sink的最短路径。当簇头准备将数据传输到Sink时，簇头先对簇成员的数据进行聚合，消除数据冗余，减小数据包的传输量，提高网络的能量利用率。文中假设数据可以进行完全聚合，然后各簇头用 Dijkstra算法找到距离Sink的最短路径将数据以多跳通信的方式发送至Sink。这样，有效降低了距离Sink较远的簇头给Sink传送数据的能耗。

4 算法仿真

借助Matlab仿真工具，通过编写VC++及Matlab程序，实现对LEACH，LEACH－C，NGECA仿真比较。仿真流程如下:(1)按LEACH算法和本文算法的原理编写VC++程序(leach.cpp、leach－c.cpp和 ngeca.cpp)，在此实现变量初始化、簇头选择、分簇、簇内数据收发以及簇头向Sink数据发送。(2)将以上两个VC++程序运行后的数据保存保存为两个文件表(outputl.txt、outputlc.txt和outputn.txt)，保存每轮运行结束后所有节点总能量和簇内剩余节点数目。(3)用MatlabR 2007a编写绘图程序，将输出在txt文件中的数据绘图并进行比较。

网络在100 m×100 m的区域内，随机部署100个传感器节点，基站坐标(50，175)。设定节点初始能量E0为 2 J，为 50 nJ/bit，εfs为 10 pJ/bit·m－2，εmp为0.001 3 pJ/bit·m－4，EDA为 5 nJ/bit signal，数据包长度为4 800 bit，广播包长度为200 bit，节点能量低于Eth=0.000 1 J时，认为其死亡，假设数据融合率为100%，且在转发过程中无数据包丢失情况，没有误码率。

从图1和图2可以看出，GECA算法在网络存活节点数以及网络运行过程中的剩余总能量都明显优于LEACH和LEACH－C算法，有效延长网络的生命周期，解决了LEACH算法簇头个数不确定，簇头位置最优化不完全等问题。与LEACH－C相比，NGECA算法有效解决了LEACH－C中对基站过高的依赖性。

5 结束语

对无线传感器网络分簇算法LEACH协议和LEACH协议进行重点分析，针对LEACH协议簇头数目不选取的随机性导致分均匀分簇造成的能量损耗问题，以及LEACH－C协议过分依赖簇头所造成的分簇开销、时间延迟和信号干扰的增大，设计了一种基于节点的地理位置和能量的分簇算法NGECA。通过仿真实验比较，说明NGECA算法在节点存活个数和网络剩余总能量上都明显优于LEACH和LEACH－C协议，有效延长了网络的生存周期。但延迟方面还需进一步改进，并且也没有考虑安全因素，下一步将对能量高效的路由协议安全性作进一步讨论。

［1］WENDI R H，ANANTHA C，HARI B.Energy—efficient communication protocol for wireless microsensor network ［C］.Washington:IEEE Proceedings of the Hawaii International Conference on System Science，2000:3005 －3014.

［2］何延杰，李腊元，邢明彦.WSN中一种能量均衡的分簇路由协议的设计［J］.传感技术学报，2009，22(10):1510－1514.

［3］HEINZELMAN WB，CHANDRAKASAN A P，BALAKRISHNAN H.An application specific protocol architecture for wireless microsensor networks ［J］.IEEE Transaction on Wireless Communications，2002，1(4):660 －670.

［4］沈波，张世永，钟亦平.无线传感器网络分簇路由协议［J］.软件学报，2006，17(7):1588－1600.

［5］韩万强，刘云.WSN中基于分簇的改进路由协议［J］.计算机工程，2012，38(5):105 －107.

［6］潘雪峰，李腊元，何延杰.低能耗无线传感器网络路由协议研究［J］.计算机工程与设计，2012，33(4):1347－1351.