无线传感器网络中基于位置信息的低能耗路由算法

胡君

摘 要：许多研究表明，优秀的分簇路由算法能够有效的延长传感器网络的使用时间。在分析典型的分簇路由算法LEACH存在问题的基础上，提出了基于位置信息的低能耗路由算法，该算法在LEACH算法的簇头选取机制上进行了改进，综合考虑了位置和能量等信息，仿真实验表明，新算法较LEACH算法能更好的降低能耗，均衡网络能量，延长网络使用时间。

关键词：传感器网络；簇头；位置信息；节能

1 引言

无线传感器网络可以灵活方便的部署于高危或不适于人类生存的地区收集、处理和发送监测数据。因此在军事、民用等领域有着十分广泛的应用。传感器节点携带的电子设备都需要通过其电池来进行供电。由于传感器网络部署的特殊环境及网络中节点的数量极大，因此电池能源往往得不到及时有效的补充，导致部分节点因能量耗尽无法工作，造成监测黑洞或者通讯盲点。上述原因使得在能量受限的条件下延长传感器网络工作时间成为研究人员关注的热点[1][2]。传感器网络在得不到能量补充时只 能通过降低网络能耗来有效延长使用时间。而优秀的传感器网络路由算法往往可以通过缩短节点通信距离，减少通信数据量等方式降低节点的工作能耗，从而延长传感器网络的工作时间。

本文提出了一种基于位置信息的低能耗路由算法，在LEACH算法选取簇头的基础上，综合考虑传感器节点与其它节点的相对位置，剩余能量及承担与基站通信的工作量等相关要素，使得簇的拓扑结构更加合理，簇头节点能耗更低，网络能耗更加均衡，有效的延长了传感器网络的工作时长。

2 相关工作

目前，已有许多分簇路由算法[3][4]被提出，其中Heinzelman等人提出的LEACH算法[5]是最具代表性和里程碑意义的。

2.1 LEACH算法描述

LEACH算法主要通过随机选择聚类首领，平均分担中继通信业务来实现。同时LEACH定义了“轮”（Round）的概念，针对每个节点n设定了一个阀值T（n），每轮开始时，节点自动产生一个0到 1之间的随机数，如果随机数小于阈值，节点就当选簇头，并向周围广播其簇头消息，其余节点根据接收到的簇头广播信息选择距离自己最近的簇加入。

2.2 存在问题

⑴LEACH算法选取簇头时没有考虑成簇后，该簇头在簇中的位置。如果选取的簇头位于簇结构的边缘位置，则簇头较位于簇结构中心位置的簇头要耗费更多的能量。

⑵由于簇头能量消耗远比一般节点大。因此在选取簇头时，应该尽可能选取剩余能量较多的节点。而LEACH算法没有考虑节点能量问题。

⑶LEACH算法没有考虑到部署区域中靠近基站的簇头将承担比一般簇头更多的数据汇聚和转发工作，能量消耗也更加快的问题。应该在这类区域中选取更多的簇头，这样有利于控制每个簇的规模，减少簇头簇内能量消耗，均衡能耗。

3 LEACH算法改进

3.1 无线传感器网络体系设定

为了算法描述的清晰，做以下假设：

⑴所有节点经部署在边长为L的正方形区域；

⑵传感器节点部署后节点位置保持不变；

⑶传感器节点能量受限，且具有GPS定位系统，能确定自己的位置坐标；

⑷每个节点都是同构的，具有相同的初始能量、通信及感知半径，并能监测自身的剩余能量；

⑸传感器节点可以通过多跳的方式与基站BS进行通讯，基站可以对所有传感器节点进行广播。

本文使用以下关于通讯距离和通讯数据量的传感器节点发送、接收能耗模型：

Esend（k，d）=Eunit*k+Eamp*k*d2 （1）

其中Esend（k，d）表示节点发送k字节大小的数据包到距离为d的目标节点所需耗费的能量，Eunit为发送单位自己的能耗，Eamp为电气特性参数。

Erec（k）= Eunit*k （2）

Erec（k）表示节点接收数据的能耗关于数据量K的函数。

3.2 簇头选取阀值的优化

在传感器节点部署后第一轮成簇的时候，基站对所有节点广播自己的位置坐标（xBS，yBS）及传感器部署区域的坐标。

以后每轮节点簇头阀值计算步骤为：

Step1：各节点根据基站的坐标计算出自己距离靠近基站一侧的部署边界的距离DNi（第1轮计算）；

Step2：所有节点Ni{i∈I|1≤i≤n，n∈N}以通讯半径r向周边节点广播Msg_location，其中包括自己的坐标，节点编号；

Step3：节点Ni根据收到的其它节点信息计算出它的候选簇头聚合性指标G。

假设节点Ni收到M个其它节点发出的广播。其中，Nj∈M，dist（Ni，Nj）表示节点Ni到另一个节点Nj的直线距离。

W值越大，则表示Ni节点如果成为簇头，其越靠近簇结构的中心位置，应该优先成为簇头。

Step4：每个节点计算出自己的候选簇头能量指标H，

其中，Ecur表示节点当前能量，Einit表示节点初始能量，H值越大表示节点能量越多，成为簇头的几率应该较高。

Step5：每个节点计算出候选簇头中转通信能耗指标，

F值越大，则表示节点越靠近距离基站一侧边界，其承担的转发通信工作也越多，应该具有更高的成为簇头的几率，其中XA，XD，为部署区域靠近基站一侧边界的两个顶点的横坐标。

Step6：根据式（4）、（5）、（6）可以得到阀值公式综合改进指标，

Q=α*w+β*H+γ*F （6）

其中，α、β、γ均为权值调节参数，并可以保证P∈[0，1]。

Step7：改进的LEACH簇头阀值计算公式如下：

4 仿真实验及结论

为了验证基于位置信息的低能耗路由算法（EELIRG）性能，使用matlab對LEACH算法和EELIRG算法进行了仿真。传感器节点部署在范围为200CM*200CM的矩形区域，节点初始能量为1J。部署区域靠近基站的一侧两定点坐标为（300，300），（300，100），基站坐标为（500，200），Eunit=50nJ/bit，Eamp=100pJ/bit/m2， α、β、γ分别取0.4，0.3，0.3。

若随机生成100，150，200……个传感器节点，仿真实验结果如下：

横坐标为部署的节点个数，纵坐标为采用LEACH算法或EELIRG算法时成簇的轮数（即网络的使用时间），可以看出，传感器网络采用EELIRG算法比采用LEACH算法的使用时间延长了50%左右。仿真实验表明，EELIRG算法能比LEACH算法更有效地降低与均衡网络的能量消耗，从而可以使传感器网络的生命周期在LEACH算法的基础上有较大提高。

[参考文献]

[1]赵昕，张新.基于博弈论的无线传感器网络簇间路由选择算法[J].计算机应用，2013，33（7）：1813–1815.

[2]戴菲菲，等.改进K-ACO无线传感器网络的分簇路由算法[J].传感器与微系统，2013，32（8）：135–138.

[3]田炜，杨震.新的位置感知分簇算法[J].通信学报，2010，31（3）：25–30.

[4]王刚，等.无线传感器网络中簇首选择算法研究[J].通信技术，2010，43（8）：35–40.

[5]HEINZELMAN W，CHANDRAKASAN A，BALAKRISHNAN H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C].In：Proc.of the 33rd Annual Hawaii Intl Conf.on System Sciences.Maui：IEEE Computer Society，2000.3005-3014.