一种基于节点密度的无线传感器网络路由协议*

路成杰， 蒋海峰

(南京理工大学 自动化学院，江苏 南京 210094)

0 引 言

无线传感器网络(WSNs)由许多无线传感器节点组成，应用于大面积的监控应用中,这些应用主要包括数据收集和事件驱动两类。传感器节点多为一次性节点，电源更换困难，所以，能量问题成为了制约无线传感器网络发展的瓶颈。为此，提出了许多能量有效利用技术来延长了网络的寿命[1]。

因为网络中的能量主要消耗在无线通信过程中，所以，选择有效的路由协议能够很好地降低通信过程中的能耗。路由协议通过选择最优信息传递路径来降低能耗。在已提出的各类路由协议中，基于簇的路由协议对降低通信能耗，延长网络寿命具有良好的效果。

在已有的基于簇的路由协议中，簇头需要承担收集簇内数据、与基站通信的任务。许多基于能量有效利用的路由协议均采用与簇相关的网络构架[2]。簇头的选择与成簇对于均衡整个网络能量，延长网络寿命，降低网内延迟与增强网络可扩展性起到了重要的作用。而成簇算法一般需要解决以下3个问题：应用需求、网络模型与其参数设置、选取适于评价算法的参数。

常见的分簇路由算法可以分为以下几类：阶层式成簇算法主要包括LEACH[3]协议，采用了分布式算法，这类算法很好地处理了簇内信息收集，但缺点在于其网络结构不利于簇间的数据传递。分割式成簇算法也如典型的k-means method[4]以网络参数与应用需求为参照，以分割法求重心以获得簇头位置。

本文是在原有LEACH协议上提出的改进算法SDD-LEACH(sensors density depended-LEACH)。与文献[4]不同的是，该种算法不需要预知网内状况与运用需求，具有较好的可移植性。在整个协议的运行过程中，着重考虑候选簇头区域的选择降低簇间通信的能耗，平衡全网能耗。

1 模型建立

1.1 能量模型

本文选用了文献[3]的无线通信能量消耗模型。在这里，一个无线传感器节点发送lbit的数据到一个到其距离为d的传感器节点的能耗为

(1)

1.2 网络模型

假设在一面积为S的特定区域内，一共分布了N个无线传感器节点：1)所有网内节点都是同构节点；2)节点之间的链路是对称的；3)节点具有发送/接收与数据融合的能力；4)基站位于传感器网外部。

2 路由协议的改进

2.1 簇头个数的确定

在网内，普通节点数远大于簇头节点数，且普通节点只承担接收监测数据与发送数据至簇头节点，所以，考虑网内能耗时，只需单独考虑功能较多的簇头节点。对于一个簇头节点来说，它的能耗主要源自3个方面：簇头节点接收簇内节点数据消耗的能量Ech-rec，簇头节点进行数据融合消耗的能量Ech-df，簇头节点将融合完毕的数据发送给基站时消耗的能量Ech-bs[5]，即

E∑=Ech-rec+Ech-df+Ech-bs.

(2)

在簇的建立阶段，可以保证每个簇群内普通节点到簇头节点的距离，使其通信模型符合自由空间信道模型。假设网内簇头节点的个数为n，则每个簇群内传感器节点的个数为N/n，普通节点发送数据大小为lbit。由公式(1)得

(3)

(4)

其中，εdf为簇头节点每进行1 bit数据融合而消耗的能量。

假设在该区域内，传感器节点的概率密度为ρ(x,y)，每个簇群覆盖的面积为一半径为r的正圆，S/n=πr2，则

(5)

令ρ(r,θ)为常数C， 将其带入公式(3)得

(6)

设融合后每个簇头节点需发送的数据大小为kbit。簇头节点与基站的通信模型符合多径衰落信道模型，即

(7)

(8)

可以得到一轮中单个簇头的能耗为

(9)

(10)

(11)

因为在大型多跳簇间通信协议中，多跳路由协议能耗一定少于单跳路由协议[6]，所以，nsingle和nproper可以作为簇头个数选择的参考。

2.2 簇头的选择与生成

簇头的选择对于分簇路由协议至关重要，因为无论是簇内通信还是簇间通信距离，都受簇头分布的位置影响。

在LEACH协议中，所有节点都能参与簇头节点的选举，这是十分不合理的。在均匀分簇算法中，若是簇头节点所在的区域节点过于稀疏，可能会造成整个簇群通信范围变大，或是有普通节点加入簇头失败，如图1中节点2的区域；相反，周围节点比较密集的节点1就更适合成为簇头。

图1 簇头的选择区域示意图

参数p的选取至关重要，如果p选取过高，会导致参与选举的簇头局限在某些区域内，从而在网络工作过程中，该区域能量急遽下降，不利于延长网络寿命。

3 算法仿真与分析

为了研究改进算法与原有的算法的区别，本文在NS2网络仿真软件的环境下进行仿真。环境参数设置为：仿真区域大小为100 m×100 m；节点个数为100；参数p为0.8；基站位置为(50,65)m；数据包长度为4 000 bit。

图2为在选择不同的参数p情况下网络节点生存的情况(p分别取1，0.5，0.8)。从图中可以看出：当参数p选择为0.5时，曲线与原LEACH协议比较接近，说明参数p选择较小，对改善网内能耗分布基本没有作用。当参数p选择为1时，虽然第一次出现死亡节点的轮数有所推迟，但是一段时间后节点迅速死亡，在符合条件的候选簇头节点全部死亡的情况下，网络通信失败。最终选择p=0.8为较合适参数。

图2 不同参数p对网络的影响

图3从每轮存活节点个数这个方面，对LEACH,LEACH-C以及改进后的SDD-LEACH协议进行比较。从仿真中可以得出:SDD-LEACH的出现第一个死亡节点的时间有了一定的延后，且整个网内节点死亡速率较前2种算法减慢，在相同的轮数下，改进算法具有更多的存活节点数。

表1为各协议下首次出现死亡节点的轮数。

表1 各协议死亡节点首次出现轮数

图3 不同协议下节点存活数目对比

图4为每轮节点能耗对比。由图4知，改进协议的能耗曲线更为缓和，说明改进协议可以较好完成平衡网内能量。

图4 不同协议下每轮能耗对比

4 结 论

本文在总结已有的各类成簇算法的基础上，总结了基于成簇的无线传感器路由协议的主要思想，提出了一种改进的成簇算法。将节点密度作为约束条件，减少了簇内与簇间通信的距离，从而减少了通信能耗，延长了网络寿命,并且该改进法对分布式成簇算法具有良好的可移植性和实用性。本算法改进所考虑的约束条件比较少，在参数p的选取上，只给出几个参考数据,后期将扩大研究范围。

参考文献:

[1] Marin-Perianu R S,Scholten J,Havinga P J M,et al.Cluster-based service discovery for heterogeneous wireless sensor networks[J].International Journal of Parallel,Emergent and Distributed Systems,2008,23(4):325-346.

[2] Dimokas N,Katsaros D,Manolopoulos Y.Energy-efficient distri-buted clustering in wireless sensor networks[J].Journal of Parallel and Distributed Computing,2010,70(4):371-383.

[3] Heinzelman W R,Chandrakasan A,Balakrishnan H.Energy-efficient communication protocol for wireless microsensor network-s[C]∥2000 Proceedings of the 33rd Annual Hawaii International Conference on System Sciences,IEEE,2000:10.

[4] Cleuziou G.An extended version of the k-means method for overlapping clustering[C]∥2008 19th International Conference on Pattern Recognition,ICPR 2008，IEEE,2008：1-4.

[5] 尚凤军,任东海.无线传感器网络中分布式多跳路由算法研究[J].传感技术学报,2012,25(4):529-535．

[6] 周新莲,吴 敏,徐建波.BPEC:无线传感器网络中一种能量感知的分布式分簇算法[J].计算机研究与发展,2009(5):723-730.