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

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²衰减；否则采用多路衰减模型，信号功率呈d⁴衰减。

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报文，则启动从第一轮开始新的簇头选择过程，相对于大多数算法只支持静态网络，本文的算法支持了小范围地理位置变动的传感器网络。