一种适用于凹陷型山地地形的无线传感器网络路由算法

张彦虎，鄢丽娟，孔淑梅

(广东松山职业技术学院计算机系，广东 韶关 512126)

0 引 言

随着科技的进步和无线网络技术的发展，无线传感器节点的应用范围越来越广[1-3]，有时因为监控环境或科研需要，需将无线传感器节点分布在各种复杂的山地地形去探测所需信息，如森林火灾、气温、降雨等自然状况的监测信息，这种状况下，无线传感器节点被分布在比较广阔的区域，其特点是分布面积较广、地形高低起伏不一、信号比较容易受障碍物的遮挡而减弱，因此无线传感器网络中各个节点的能量损耗相对平面无线网络而言有所增加，造成无限传感器节点能量容易消耗殆尽[4-5]。

本文着力于山地地形的特点，结合LEACH协议算法，对凹陷型山地地形进行研究与分析，探索一种能减缓无线传感器节点在高低起伏地形中各网络节点能量消耗速度的路由算法。

WSN路由协议分为平面、层次2种路由协议。平面路由协议一般适用于小规模网络；另外一种层次路由协议也称为分簇路由协议，其以簇头为核心，周边的普通传感器将信息传送至簇头节点，由簇头节点对其所收集的簇成员节点信息进行数据融合，通过一跳或者多跳的方式传送给基站[6]。分簇路由协议中最具代表性的一种协议是LEACH协议，许多学者在其基础上进行了多方面的优化及改进，如黄利晓等人[7]提出的LEACH-improved协议；叶继华等人[8]提出了LEACH改进协议——可变通信周期策略的能量均衡成簇协议ACPSEB-LEACH；鄢丽娟等人[9]提出了一种基于剩余能量进行簇头选举的算法；张文柱等人[10]提出了一种基于梯度的异构WSNs非均匀分簇路由协议(GUCRP)；余修武等人[11]提出了基于罚函数和水波优化的无线传感器网络(WSN)定位算法；吴意乐等人[12]提出了一种基于改进遗传模拟退火算法(SAGA)的WSN路径优化算法；彭蕾等人[13]提出了一种适用大规模网络的基于LEACH算法的混合无线传感网络节能路由算法；胡中栋等人[14]提出了一种基于最优分簇的能量异构无线传感器网络路由协议OCRP。文献[15-21]从各个不同方向提出了无线传感器的各类改进算法；本文在深入分析LEACH分簇算法基础上提出一种基于平均剩余能量产生簇头且优化节点信息传输方向的分簇路由协议。

1 相关模型

1.1 地形模型

椭圆抛物面数学模型方程定义为：

(1)

由椭圆抛物面来近似模拟山头地形，其中h代表山头高度，p、q分别是调整山头表面形状的因子。为方便研究，设p=q。则椭圆抛物面方程为：

x2+y2=p2(h-z)

(2)

图1所示为椭圆面模拟凹形山区地形。

图1 椭圆面模拟凹形山区地形

1.2 能量消耗模型

本文采用文献[22]所述的无线通信能量消耗模型，将节点能耗按照能量消耗的功能分为3个部分，分别为：发送信息、接收信息、数据融合等操作产生的能量消耗。该模型如图2所示。

图2 无线电通信模型

根据无线电通信模型的特点，当信号的传输距离d小于阈值dt，节点能量消耗与传输距离d的平方成线性相关；否则，能耗与间距d的四次方成正比关联。εfs、εmp为以上2种模型下功率放大器的能量参数[23]。阈值dt的计算过程为：

(3)

当传输距离为d，传感器发送kbit信息所需要消耗的能量为ET(k,d)，其计算公式为：

ET(k,d)=ET-elec(k)+ET-amp(k,d)

(4)

式(4)中，Etx为传感器发送1 bit信息所消耗的能耗，发送设备传送kbit信息的能量消耗ET-elec=kEtx，ET-amp(k,d)表示如果传输间距为d，功率放大器发送kbit数据的能量消耗。

接收设备接收kbit信息的能量消耗Erx(k)=kErx，对大小为kbit的数据进行融合所产生的能量消耗E(k)=kEda，其中Eda表示融合1 bit信息的能耗。节点接收kbit信息所需要的能耗为：

ER(k)=k×Eelec

(5)

式(5)中，Eelec表示发射电路的能耗，ER(k)为接收kbit信息消耗的能量。

2 改进算法

基于LEACH算法基础，结合凹陷型山区地形特点，本文提出一种在基站产生簇头且优化节点信息传送方向使其总是向距离基站更近的簇头发送信息的路由算法。基站在产生簇头时，基于已获取的全网络节点的平均剩余能量、位置坐标等信息，按照一定的规则产生簇头，并将新产生的簇头、各节点距离基站间距等信息向全网广播。网络节点接收到广播信息之后，更新自己到基站距离的参数，同时检查自己是否被设置为簇头节点，并按照相关设置进行工作模式切换；普通节点等待周围簇头节点发送的簇头广播信息，在收到的多个簇头广播中，选择一个距离基站更近的簇头节点入簇。

基站在产生簇头的过程中，基于已获取到的全网络节点剩余能量、节点位置坐标等信息，运行F(x)函数产生新一轮的簇头节点。

2.1 改进算法描述

本文算法中，最主要的部分是簇头的产生及无线网络节点的组网过程，其中基站在产生簇头时，将所有的规则设定在F(x)函数中并由其产生；节点的组网阶段是在新一轮簇头被确定，普通节点接收到周围簇头广播之后进行，下面对F(x)函数及网络节点的组网过程展开描述。

2.1.1F(x)函数相关参数

1)最小剩余能量阈值EOvall。

为了确保下一轮被选举簇头节点的剩余能量能大于全网络节点剩余能量，定义全网平均剩余能量的运算过程为：

(6)

式(6)中，ECi为节点Si的剩余能量，n为全网无线传感器节点的数量，EAVall为全网节点平均剩余能量。

2)最优簇头数量Kopt。

凹陷型山区地形的节点布置在山区平面之上，并不是完整的空间模型，为了研究方便，通过计算凹陷型山区地形表面积的方法获得节点需要覆盖的范围，然后通过凹陷型山区地形表面积除以一跳的距离而得到整个山区为了达到最优能量消耗所需的簇头数量。

凹陷型山区地形表面积的计算公式使用式(7)进行大概估算：

S=4πR2

(7)

其中，R为山区垂直投影所产生区域的半径。

Kopt=S/(πdt2)

(8)

其中，Kopt为最优簇头的数量，dt为式(3)所示的阈值。

3)簇头之间的最小间距d0。

为避免簇头扎堆出现在一个区域造成不必要的能量损耗，对簇头与簇头之间的间距做一定的限制，定义其最小间距不能小于d0，计算过程根据式(3)为：

(9)

4)节点到基站的距离df。

节点到基站间距计算公式为：

(10)

其中，基站的坐标为O(x0,y0,z0)，节点A的坐标为A(x1,y1,z1)，df为节点A到基站的空间距离。

2.1.2F(x)函数的计算过程

基站根据已获取的全网节点剩余能量、各簇平均剩余能量及各节点位置坐标等信息运行F(x)函数生成簇头集合C。

1)根据式(6)计算EAVall，根据式(7)、式(8)计算Kopt，根据式(9)计算d0；对全网络内所有节点进行遍历，凡是符合剩余能量大于等于EAVall的节点，都加入集合SO。

2)对集合SO的所有节点进行遍历，凡是节点到已选定的簇头集合C(初始值为null)的所有已选簇头的最小距离dmin小于d0，则将该节点加入到集合C。

3)当集合C中节点数量大于等于Kopt时，结束F(x)的运算，得到集合C，即为函数F(x)所选定的簇头节点集合。

4)根据所获悉的全网络节点的坐标，对节点到基站距离df为空的节点，计算该节点到基站的间距df，并将该值同簇头信息一同发送给全网络无线节点，并由各节点完成更新。

2.2 组网过程

1)普通节点接收到全网广播之后，检查自己是否被设置为下一轮的簇头节点，同时更新该节点到基站的距离。

2)如果节点被设置为下一轮的簇头节点，则将工作状态设置为簇头模式，同时向周围发送自己成为簇头的广播信息，随广播信息一同发送的还包括簇头节点距离基站的间距。

3)其它节点将工作状态设置为普通节点模式，并等待周围簇头发送的信息；当接收到簇头信息之后，普通节点优先选择距离基站更近的簇头加入。

4)当节点组网完成之后，进入信息采集与通信阶段。

3 仿真实验

3.1 模拟实验

为验证本文路由改进算法的效果，使用Matlab R2016模拟仿真软件分别对LEACH和本文算法在垂直投影面积为100×100 m2的凹陷型山区地形区域上进行了模拟实验。使用模拟软件在该区域内随机产生100个节点，基站位于凹陷山区地形的底端中心位置。对各对比算法分别进行100次的实验，每次运行3000轮，测试环境的参数设置如表1所示。

表1 测试环境的部分关键参数

3.2 结果分析

1)首个死亡节点对比。

通过分析得出：试验中，原LEACH协议首个死亡节点出现的平均轮数为34.25，即出现在第35轮左右，极大值为第54轮，极小值为第11轮；本文所述算法中，对100次的数据进行分析得出，首个死亡节点出现的轮数平均值为113.77，即出现在第113轮，极大值为183，极小值为48。本文所述算法中首个死亡节点出现的轮数较LEACH协议晚37轮，从图3可直观看出，本文所述算法的首个死亡节点的均值要优于LEACH协议。

(a) 首个死亡节点出现的轮数对比

(b) 实验过程中首个死亡节点的极值对比

2)成簇情况分析。

原LEACH协议簇头布局与本文所述算法簇头布局对比：

在原LEACH协议中，因为在簇头产生过程中，对未做过簇头的节点采用随机方式产生，会出现若干个簇头节点集中在一起扎堆的情况，如图4(a)所示。因为簇头节点要承担与基站的通信，其能量消耗相对而言要比普通节点高很多，在图4所示的情况下，该区域分布的3个簇头距离太近，而个别节点的通信距离又太远，造成全域节点能量消耗过快，有进一步提升改进的空间。

(a) LEACH协议产生的簇头结果

(b) 本文算法产生的簇头结果

在本文所述算法簇头产生的过程中，加入了一个限定条件，即符合做簇头条件且被系统选中拟产生的新簇头，需要跟已经确定为新一轮簇头的所有节点做数据分析，如果该节点与已确定的簇头列表中的任何一个簇头的距离小于设定值dic，则该节点不能做簇头。在这种条件下，系统中产生的所有簇头节点，一定不会有若干个节点扎堆出现的情况，在一定程度上避免了过多的能量消耗，降低了全域网络节点的能量耗损，增加了节点的存活时间。修正后簇头布局及信息传输方向如图4(b)所示。

3)剩余能量对比。

在对LEACH和本文所述算法所做的100次1000轮的测试中，将能被100整除轮次的剩余能量进行记录，然后求100次的平均值，进行对比发现，相比LEACH协议，本文所述算法全域平均剩余能量要大于LEACH，存在较明显的优势。

图5 剩余能量对比图

4 结束语

本文在经典LEACH协议的基础上，针对凹陷型山区地形的特点，对LEACH协议的簇头选举机制及节点对信息的传输方向进行改进，在簇头选举机制上，引入了全域网络节点平均剩余能量的概念；节点信息传输过程中优先向距离基站更近的簇头传输，使整个网络能量的耗散更均衡，避免了个别节点因能量消耗过多而过早死亡。通过使用Matlab对改进算法与经典LEACH协议进行对比，结果表明，本文所述改进算法在均衡全域节点能量消耗及延长网络生存周期等方面具有较明显的优势；本文存在的不足之处是未能更细致地为每个簇头指定具体的传感器节点，后期将以该方向为重点开展相关研究。