基于梯度的分簇式路由协议

程敏敏，宋家友，张 汉

(郑州大学信息工程学院，河南郑州450001)

随着传感器技术、现代网络技术、嵌入式技术以及无线通信技术的发展与进步，推动着具有重要意义的无线传感器网络的诞生与发展，无线传感器网络被誉为是21世纪最具发展潜力的一项研究，应用于军事、医疗、社会公共服务、农业生产和食品检测等各个领域。整个网络通常是由大量微型的传感器节点组成，这些节点被抛洒在需要监测的区域，由于被抛洒区域是一些无人监管区域，而无线传感器节点的能量无法更换，这使得设计出能够有效节约能源、延长整个网络生命周期的路由协议，成为无线传感器网络研究的一个重点。

本文在EAMCT-G［1］分簇路由协议的基础上进行改进，用以提高整个网络的能效性。EAMCT-G算法是一种基于能量的有网关的多级簇数算法。该算法利用图论中基于极大独立集和极小支配集的思想，在整个网络中选取能够覆盖全网的几个节点，并且这些节点的能量较为充足，构成网络中的簇头。这样整个网络就形成了覆盖全网的几个簇，网络分好簇后，簇头节点通过一些网关节点，建立有网关的多级簇树结构，将采集数据发送到基站。

该算法在选择簇头的过程中仅考虑以剩余能量作为权值，而忽略了距离和周围节点的各种因素的影响。路径的选择是由BS发起建立从簇头经过网关节点到基站的路由。

本文中以节点的剩余能量、周围一跳邻居节点的个数以及到其周围节点的平均距离作为节点的权值，采用文献［1］中的分簇策略，从主动式路由考虑，节点将采集信息传送到基站以牺牲较少的能量、能够较及时地传送信息为目标，建立从基站到节点之间的一个梯度。这样，数据在传送的过程中就不会盲目地进行传送，而是具有一个方向性，使得数据都朝着BS的方向传送。

1 改进后的路由协议算法

1.1 路由协议算法分析

1.1.1 相关约定和数学模型

G=(G(v)，G(e)，G(w))是连通的无向加权图，式中表达式的含义为：G(v)={v1，v2，…，vn}表示的是传感器节点的集合;G(e)={evivj}表示的是每一条边的集合，即为节点vi和vj都在各自的通信半径范围之内;G(w)={w(v1)，…，w(vi)，…，w(vn)} 表示节点的权值，其中

式中：En为节点的剩余能量;number为邻居节点个数;AMRP为节点到邻居节点之间距离的平均值，且AMRP=为节点到邻居节点i的距离。

1.1.2 传感器节点收发器能耗模型

本文中采用传感器节点收发器能量模型［3］，每个节点若传送一个k bit的分组数据包能量消耗分为2个部分：

1)传感器节点发射信号消耗的能量

2)传感器节点接收信号消耗的能量

式中：ETX-elec(k)和ERX-elec(k)分别表示发送电路和接收电路接收k bit的能量消耗，接收电路能量消耗和发送电路能量消耗均为Eelec×k，设Eelec=50n J/bit，n的取值由选择的无线信道距离决定;ETX-amp表示放大器发送k bit数据到达距离为d的另外一端，所消耗的能量，d是信号传输距离，εamp是信号放大器的放大倍数。在自由空间中信道衰减模型n取2，εamp=100 pJ/(bit·m2);在多径衰减信道模型中n=4，εamp=0.013 pJ/(bit·m4)。本文中取 k=20，di=87.7 m。

1.1.3 过程分析

假设在无线传感器网络中有N个节点，BS在网络边缘的位置，则：

1)通过基站发射不同强度的信号，在某个信号强度范围内，节点根据收到信号强度的范围，来确定自己的梯度L;

2)从无线传感器网络中的N个节点中寻找一组权值较大，并能够覆盖整个网络的Q个节点作为簇头节点［4］;

3)通过簇成员节点和簇头节点，使得信息都传向基站，最终使得节点都能够通过多跳的方式把数据发送给BS。

1.2 基于梯度的分簇式路由算法分析

主动式路由：节点通过寻找d/W一跳代价较小、跳数较少的路径传送给基站。

无线传感器网络中的传感器节点都具有唯一的节点ID标号，且在抛洒后节点的相对位置保持不变。并且节点都具有相同的初始能量、信号发射功率以及节点数据融合能力等，节点的通信半径要能够保证整个网络的通信连通性。

改进后的协议算法包括梯度划分阶段、分簇阶段和路由选择3个阶段：

1)梯度划分

BS节点通过改变发射信号的强度，无线节点根据接收到的信号的强度来划分所在的梯度。

2)分簇阶段

网络中的节点在起初交互时，需要保存的信息(neighbor(N)，level(n)，neighbor(AMRP)，E(n))，按照文献中的根据极大独立集的性质，进行全网的分簇过程，选择出能够覆盖全网的簇头节点。权值按照式(1)进行计算。

3)路由阶段

当簇分好后，需要建立一条到BS的路由，按照主动路由方式，寻找代价较小、跳数较少的路由进行选择。首先，处于最高level的簇头c节点寻找邻居节点中处于较小梯度、d/W较小的节点，如果梯度相同，则选择d/W较小的，把该节点f作为自己的父亲节点，发送child(c，f)，接收到该消息的节点继续寻找邻居节点中梯度较小、尽量为簇头节点且d/W较小的节点，进行路由选择。最后建立一条从簇头节点经过簇成员节点到达BS的一条路由。

2 特例分析

2.1 实验仿真参数的设定

在NS2［5-6］平台上设置仿真环境。在1 200×1 200的正方形区域内，随机抛洒50个节点，模拟脚本的MAC层采用IEEE 802.11协议，默认载波侦听(CSThresh_)距离为550 m(1.559×10-11W)，即监测接收信号强度，如果信号强度小于这个门限值，则在NS2的PHY层直接丢掉，MAC层就无法接收到该信号;无线节点的覆盖范围(RXThresh_)为250 m(3.652×10-10W)，在仿真中，载波侦听的距离要大于2倍的无线节点覆盖范围;带宽为2 Mbit/s;其传输功率为Pt_(0.281 8381 5 W);载波频率freq_为9.14 GHz;节点的初始能量为1 J，接收功率(rx-Power)为0.1 W，发射功率(txPower)为0.2 W;应用层再用数据流(cbr)来模拟节点的数据采集，节点每秒发送一个数据包cbr，数据包的大小为210 byte。参数设置详见表1。

表1 仿真参数的设置

节点随机分布图如图1所示。

图1 节点网络分布图

2.2 实验仿真结果分析与比较

下面对改进后的协议算法进行仿真，并将仿真结果与已有的EAMCT-G协议进行比较。

2.2.1 网络传输时延

用计算公式［5］：

式中：D(i)表示传输时延;RT(i)表示接收时间;ST(i)表示发送时间;i表示第i个分组。

平均时延

通过对原有EAMCT-G协议以及改进后的路由协议进行仿真，仿真时间分别为10 s，20 s，30 s，40 s，50 s，60 s，70 s，80 s，90 s，100 s。通过实验结果比较分析得出改进后的协议在传输时延上有很大的改善。如图2所示。

图2 网络的平均时延

2.2.2 网络丢包率

分析Trace文件时，可以用丢失数据包总数与发送的数据包总量的比值来表示丢包率的大小［5］

式中：NSP表示节点发送数据包数目;NRP表示节点接收到数据包数目。

设置整个网络仿真时间为400 s，簇头的轮换的时间为110 s，仿真结果如下图3所示。

图3 丢包率

从图3中可以看出，随着仿真时间的延长，由于节点能量的降低，丢包率逐渐呈上升趋势，尤其在簇头轮换的时间点110 s，220 s等附近，有较大的丢包率。经过改进后的协议虽然也呈现这种趋势，但整体上在网络数据传输的丢包率上有所下降。

2.2.3 网络吞吐量

在分析Trace文件时，使用如下的计算公式计算吞吐量［5］

式中：TB(i)表示第i个数据包被目的节点接收的时侯已经传输的数据总量;RT(i)表示第i个数据包的接收时间。i＞m，表示计算从第m个分组到第i个分组的吞吐量，若m=1计算的则是平均吞吐量。

整个仿真过程改变数据发送的速率进行多次模拟，数据发送以步长为50 kbyte递增，在Tcl文件中实现数据传输速率的改变“MYMcbr_(MYMi)set rate_ 0kb(50kb，100kb，150kb，200kb，250kb，300kb)”。整个仿真时间设置为 100 s，MYMns_at 100.00000001“finish”。仿真结果如图4所示。

图4 网络吞吐量随数据传输速率的变化

图4显示在数据传输速率不同的情况下网络的吞吐量，当数据传输速率达到250 kbit/s时，网络的吞吐量达到最大。改进后的路由协议在网络吞吐量上与EAMCT-G协议比较有些提高，从而对网络情况的改善有很大的提高作用。

2.2.4 网络生存周期

由于无线传感器网络节点是由电池供电，其能量的有限性，限制了网络的工作效率。网络的生存期有2方面定义：1)网络中第一个节点的死亡时间，即为该网络的生存周期;2)该网络无法完成既定任务，即定为网络的死亡时间。在本文中，以第一种方式记为网络的生存周期。在进行仿真时，通过改变节点的通信半径来进行比较。这就需要设置无线节点的通信范围，NS的物理层定义了与无线节点相关的参数：

由于传感器节点的发射距离是可控的，因此可以尽量减少发射功率(需要保证网络的连通性)来延长网络的生命周期［5］。网络仿真模拟时更改网络节点的通信范围，可以按照以下的步骤进行。

按照文献中所介绍的关于更改节点通信范围的方法，在NS中通过设定不同的参数来确定节点的通信范围。由于本文的仿真环境为1 200×1 200较大，所以节点的最小通信半径为250 m。

实验仿真结果如图5所示。由图5可见，由于通信距离的改变，数据采集轮数随着通信距离的增加而减少，这是由于通信距离的增加，网络中消耗能量呈现较快的减少趋势，耗能较多。改进后的协议在网络生存期上比EAMCT-G协议有明显的提高。而当通信距离增加到一定数值时，网络中的数据采集轮数并没有多少改变，这是由于信号发射功率的限制。在更改通信距离时，如果信号接收门限RXThresh_值不变，需要改变的是Pt_的值，通过Txpower计算可以得到Pt_的最小值，所以可以通过尽量减小发射功率来提高网络生存周期。

图5 生命周期随传输距离的变化

3 仿真总结

通过对EAMCT-G在分簇过程中选用权值的改进以及引入梯度的思想。通过NS2仿真分析比较，改进后的协议在网络延时、丢包率、吞吐量以及生命周期上都有显著的改善。

［1］AN Na，YAN Xinfang，ZHU Yufang，et al.A virtual backbone network algorithm based on the multilevel cluster tree with gateway for wireless sensor networks［C］//Pro.IET Conference on Wireless Mobile and Sensor Networks，2007.Shanghai，China：IEEE Press，2007：462-465.

［2］马振.基于多跳的无线传感器网络路由协议［D］.广州：华南理工大学.2010.

［3］HEINZELMAN W B，CHANDRAKASAN A P，BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor network［J］.IEEE Trans.Wireless Communications，2002，1(4)：660-670.

［4］阎新芳，张永琦，王志龙，等.无线传感器网络中基于网关的多级簇树维护更新算法［J］.传感技术学报，2010(2)：260-264.

［5］黄化吉，冯穗力，秦丽娇，等.NS网络模拟和协议仿真［M］.北京：人民邮电出版社，2010.

［6］王辉.NS2网络模拟器的原理和应用［M］.西安：西北工业大学出版社，2008.