无线传感器网络的动态拓扑能量有效成簇算法

摘要：在研究无线传感器网络低能耗自适应分簇路由算法LEACH等路由协议基础上，提出了无线传感器网络的动态拓扑能量有效成簇算法：其主要内容包括：1、采用引入能量因子的低复杂度簇头选择算法。2、支持部分节点移动的拓扑动态的网络。3、在数据传输上通过多跳方式进行信息路由。理论和仿真结果证明，本算法相对于LEACH算法，在网络生命周期上得到了提高。

1 引言

无线传感器网络（Wireless Sensor Network，WSN）作为下一代的信息获取技术引起了世界各国的重视，日渐成为国内外学术机构的研究热点。无线传感器网络通常是由大量传感器节点通过射频通信形成的一个自组织网络系统。它通过对被监测对象目标信息的感知，获取和处理，提供给管理者以有用的信息，可以广泛地应用于智能家居、医疗卫生、工业控制、农业种植、军事预警以及防洪救灾等特殊场合。但是，WSN与移动Ad Hoc网络（MANET）是有着很大区别的，它们的通信方式、通信目的和网络拓扑很不相同，尤其在能量来源方面，WSN是采用电池供电，路由算法对传感器网络的存活周期起着重要的影响，所以移动Ad Hoc网络的路由协议不能完全适应于WSN，我们需要单独研究适合于无线传感器网络的通信协议。

2动态拓扑能量有效成簇算法

针对层次路由协议中存在的各种问题，本文提出了适用于WSN的动态拓扑能量有效成簇算法(DTEE)。此算法引入基于能量因子的低复杂度的簇头选择机制，同时通过协议的设计使其支持节点部分离去或有新节点加入的拓扑动态传感器网络。在簇间数据传输上通过多跳算法使数据以最优路径传向汇聚节点，系统能耗很小，网络的生命周期最大化。

3．1网络模型

本文中假设传感器节点随机分布在一个长方形形监测区域内，并且该传感器网络具有以下性质：

1) 网络中所有传感器节点都是同构的，具有相同的初始能量，并且能量有限；

2) 传感器节点的发送功率可以进行离散调节，可以根据传输距离的远近来调节其发射功率

3) 汇聚节点具有较强的计算能力和较大的存储容量，且能量无限制，其无线信号可以覆盖整个传感器网络。

4) 传感器网络部署以后，可以出现部分节点随着时间的推移而移动；

5) 传感器节点具有数据融合功能。

6) 位置上相邻的节点采集到的数据具有很大的关联性。

3．2能量模型

在无线传输中，信号强度随着传输距离的增加而呈指数衰减。文献[3]提出了两种信道模型：自由空间(free space)模型和多路衰减(multi-path fading)模型。当发射器与接收器的距离d小于阈值时，采用自由空间模型，信号功率呈d²衰减；否则采用多路衰减模型，信号功率呈d4 衰减。

3．3成簇策略

在LEACH算法中执行过程是周期性进行的，每一轮包括簇的建立阶段和稳定的数据传输阶段。在簇的建立阶段，通过选举使某个节点成为簇首节点，成为簇首的节点向周围节点广播消息，其他节点根据接收到的广播消息的强度来选择它所要加入的簇，并告知相应的簇首。在本文提出的DTEE算法中，也是以轮为形式周期进行的，但在簇头选举引入了能量因子，同时第一轮和以后轮的算法过程是不同的，从第二轮开始在成簇阶段可以不用计算公式，相比LEACH及一些改进算法需要计算复杂公式的开销，降低了复杂度，使簇头选举能量开销最低，成簇过程中采用的非均匀成簇方法更是使网络能量分布更加均衡。

由于本文采用的是簇内单跳，簇间多跳的数据传输，因此离Sink节点远的簇头节点，数据转发量越少，能量消耗的慢；而离Sink节点越近的簇头，其所承担的数据转发业务越多，消耗能量越大，所以更容易出现能量耗尽而死亡的情况。为此，本文抛弃了传统算法中采用的均匀分簇的方法，而是采用非均匀成簇的策略。使离Sink节点越近的簇，其规模越小一些，从而这些簇其簇内路由及数据融合开销小，又因为其所承担的簇头间数据转发开销多，综合起来无论离Sink远还是近的簇头都将能量相对均衡消耗，网络生命周期得以最大化。

非均匀分簇的实现过程是这样的：首先，Sink节点向网络所在区域广播一个NOTICE报文，网络中所有节点根据接收到的此报文能量强度信息确定自己与Sink节点的距离d(i)。根据监测区域范围、传感器节点个数以及能量自由空间模型确定网络分层数n, 然后，本文采用文献[14]中的均匀分层的方法，各节点所在的层号i=d(i)*n/R，R为监测区域半径。因为靠近Sink节点的簇规模小，簇内节点少，也就是所在不同层次的节点成为簇头的概率不一样，各节点成为簇头的最佳概率为pi=p/(i*i)。其中p为第一层节点成为簇头的概率。将传感区域进行划分这个动作只出现在第一轮循环开始的时候，以后的循环过程不用再进行传感区域划分。

3．4簇头选择

之后开始第一轮的选举，各节点产生一个随机数 r(n) ，并与T(n)进行比较，若r(n)小于T(n)，则节点自选举成为簇头。

G为这一轮循环中未成为簇首的节点的集合。

当节点成为簇头后，以适当的半径RC广播簇头加入消息，周围的节点根据接收信号强度决定加入哪个簇并发送一个请求加入消息。之后簇头在接收到相关节点的请求加入消息后，建立TDMA调度表并广播出去。簇内节点在收到此消息后，在属于自己的时隙内打开无线电模块开始数据传送，在其它不属于自己的时隙内关掉通信功能以最大限度节省能量。在簇内节点向簇头发送数据报文时，在其中加入一个本节点此刻剩余能量的数据信息，供之后算法使用。

第二轮及以后轮的簇头产生过程中，首先是上一轮的旧簇头对收到各节点报文中含有的各节点能量信息及自己的剩余能量进行比较，从中选出剩余能量最大的节点为新簇头，之后旧簇头以半径RC发出new_CH报文，报文中包括报文类型及新簇头的ID，当指定的新簇头收到此报文后发现ID与之相匹配，就广播簇头加入报文，其余节点再根据接收信号强度决定加入哪个簇头，之后过程与第一轮相同。但在实际应用中，网络节点有可能意外被移动了，或者出故障死亡了，这样指定的新簇头就可能不存在了，从而这一簇范围内节点由于没收到簇头加入报文就会整体停止工作，使网络出现死区。考虑此方面，本文设定旧簇头节点在一定的时间阈值内若没有指定的新节点发来的簇头加入报文，它就确认指定的新节点被意味移动走了，从而它指定剩余能量第二多的节点为新节点，并发送新的new_CH报文。这样新算法就支持了部分节点移动或者有新节点加入的动态拓扑的网络。

同时本文设计所有节点在任一轮循环中，从收到簇头加入报文或new_CH报文开始，启动一个计时器Timer，若在最大时限Tmax内没有收到新的簇头加入报文或new_CH报文，则启动从第一轮开始新的簇头选择过程，相对于大多数算法只支持静态网络，本文的算法支持了小范围地理位置变动的传感器网络。

3．5数据传输

在传感器网络中，簇内数据传输为单跳的，在簇首和各成员节点之间进行，而对于簇头到Sink节点的数据传输，LEACH算法及一部分改进算法是采用簇头到汇聚节点的单跳传输，这种方法使簇头使用了多径衰落的通信模型(文献[3])，能量消耗很大，本文采用基于距离因子的多跳传输方式。由于采用多跳通信，能量消耗为自由空间模型，而且消息在传送过程中进行了多次数据融合，使各级数据转发中的数据量都有所减少，也减少了通信能耗。网络所有节点都存储有根据接收到Sink节点的信号确定的自己到Sink的距离值，这一距离值在第一轮成簇前就已确定，我们称之为距离因子。当每个簇的簇内数据融合进行之后，就会开始各簇到Sink的多跳数据传输。

首先，发送数据的簇头以确定的半径RD发送出消息，消息报文中还包含了此簇头的距离因子，周围的簇头收到消息后，各簇头将些距离因子与自己的进行比较，若发现其距离因子小于报文中的距离因子，且自己的剩余能量值不低于簇间传输所需的最小能量阈值Emin后，确定自己将此数据进行转发，将消息报文中的距离因子替换为其距离因子后以半径RD继续转发，之后传输过程相似。由于转发消息的簇头的距离因子小，从而其离Sink节点更近，这样消息报文在簇间就以多跳的最优路径传向了汇聚节点。传输能量开销得以最小化。

3 仿真研究

NS2(Network Simulator 2)是著名的用于网络研究的离散事件仿真工具，里面包括了大量的用于有线和无线、本地连接或通过卫星连接进行TCP协议、路由算法、多播协议仿真的网络协议、调度器和工具。NS的核心部分是一个离散事件模拟引擎。NS中有一个“调度器”(Scheduler)类，负责记录当前时间，调度网络事件队列中的事件，并提供函数产生新事件，指定事件发生的时间。在仿真过程中，将执行相关算法，并且将网络运行的具体情况写到文件当中，包括数据分组的传递情况、节点的能量状况等，这些文件对算法之间进行比较有很大的作用。本文在仿真场景设置方面，使用了如下场景设置方案：

(1) 仿真区域大小为(100*100)。

(2) 所有节点的初始能量相同。

(3) 传感器节点在区域(100*100)内随机分布。

仿真开始时，网络内传感器节点的分布状态如图1所示。

仿真结束之后得到了LEACH和DTEE算法生成的相关文件，使用awk程序提取算法生成的相关文件中的关键数据，然后利用gnuplot工具将这些数据显示于图表上，得到两个算法相比较的曲线图如图2所示。

从图可以看出在仿真过程中，节点的能量会随着时间的推移逐渐减少，直至节点能量耗尽而死，所以在各个时段传感区内仍存有能量的节点数是不同的，图对两种算法在不同时段仍然存活的节点个数做出了比较。首先，LEACH算法在第120秒时第一个节点出现了死亡，而DTEE是在130多秒时第一个节点死亡。从节点存活数目图可以看出，在300秒左右，LEACH算法的存活节点数已经为0，而DTEE算法仍有8个节点能量并未耗尽，直到320秒左右，DTEE算法的节点才全部死亡，所以DTEE算法中节点的生命周期比LEACH提高了约6%，可以看出，DTEE算法由于采用多跳的路由方式，网络生命周期得到了一定程度的延长。

本文通过采用引入能量因子的低复杂度簇头选择算法降低了网络通信能耗，在数据传输上通过多跳方式进行信息路由。仿真结果显示,改进后的DTEE协议能更好地平衡网络负载、节约能量消耗且具有更高的能量使用效率，对分簇算法的的路由协议实现了优化。

仿真结束之后得到了LEACH和DTEE算法生成的相关文件，使用awk程序提取算法生成的相关文件中的关键数据，然后利用gnuplot工具将这些数据显示于图表上，得到两个算法相比较的曲线图如图2所示。

从图可以看出在仿真过程中，节点的能量会随着时间的推移逐渐减少，直至节点能量耗尽而死，所以在各个时段传感区内仍存有能量的节点数是不同的，图对两种算法在不同时段仍然存活的节点个数做出了比较。首先，LEACH算法在第120秒时第一个节点出现了死亡，而DTEE是在130多秒时第一个节点死亡。从节点存活数目图可以看出，在300秒左右，LEACH算法的存活节点数已经为0，而DTEE算法仍有8个节点能量并未耗尽，直到320秒左右，DTEE算法的节点才全部死亡，所以DTEE算法中节点的生命周期比LEACH提高了约6%，可以看出，DTEE算法由于采用多跳的路由方式，网络生命周期得到了一定程度的延长。

本文通过采用引入能量因子的低复杂度簇头选择算法降低了网络通信能耗，在数据传输上通过多跳方式进行信息路由。仿真结果显示,改进后的DTEE协议能更好地平衡网络负载、节约能量消耗且具有更高的能量使用效率，对分簇算法的的路由协议实现了优化。