改进无线传感器网络路由算法

张晓伟

泰山职业技术学院 山东 泰安 271000

0 引言

无线传感技术在信息化的社会得到飞速发展和应用，无线传感器网络简称WSN（wireless sensor networks），其特征由传感器节点组成，众多节点组织成网络系统，通过无线网络间信息的处理并传递给用户。在农业、航天、交通、物业管理、地质灾害等诸多方面得到广泛应用。大多传感器节点的能量通过外在能源（电池）提供，在进行无线传感器网络路由设计过程中，要考虑降低节点的能量损耗，延长节点的使用寿命。

无线传感器网络的特点是节点数目大，节点能量有限，节点失效概率高。无线传感器网络与传统无线网络的路由算法相比，需要进行改进。从无线网络拓扑结构角度考虑，无线传感器网络的路由算法分为：平面路由算法、分簇路由算法。在平面路由算法中，传感器各节点地位平等，结构简单、容易扩展，通过信息反馈和相应操作生成网络路由，维持路由表需要占用大量的存储空间，路由信息发送时会增加通信负担，通信资源的优化管理欠缺，因此平面路由算法不适合大规模传感器网络。分簇路由算法弥补了平面路由算法的缺陷，一是可扩展性好，二是网络中控制信息相对较少。该算法是无线传感器网络中应用最为广泛的路由算法。其基本思想是：整个无线传感器网络划分为多个小的区域，小区域称为簇（cluster）。簇内所有众多节点中只能产生一个簇首节点，这个簇首节点就是负责本簇内信息收集、融合及簇间数据的转发。其余节点称为普通节点，负责数据的采集和发送。

无线传感器网络中基于分簇的路由算法之一是低功耗自适应分簇路由算法 （low-energy adaptive clustering hierarchy，LEACH）， LEACH算法存在一些不足，主要表现两点：一是无线传感器节点数巨大，由于采用随机部署方式，造成本簇内节点分布不均而导致簇首节点负载的不均衡；二是簇首节点能量损耗大，主要是因为簇首节点距离基站较远，在与基站进行通信时损耗能量，从而形成盲节点，会使网络生存时间寿命缩短。对于LEACH算法存在的不足，提出一种改进的无线传感路由算法。本算法对LEACH算法的簇首节点随机选择进行改进，在通信机制中考虑簇首节点的位置，采用单跳（single－hop）和多跳（multi－hop）相互结合的通信方式提高算法的有效性和优越性。

1 LEACH算法的工作原理

1.1 LEACH算法的工作进程

LEACH算法是一种低功耗自适应无线传感器路由算法，该算法是指：通过等概率、周期性的方式选择簇首节点，簇内的普通节点是通过“就近原则”进行划分确定的，形成虚拟簇；簇首节点对簇内节点感知的信息进行数据融合，将融合好评的数据再以单跳的通信方式转发给Sink（基站节点），其网络拓扑结构如图1所示。

图1 LEACH算法的拓扑结构

在LEACH算法中包括簇建立阶段和稳定工作阶段，稳定工作阶段持续时间相对簇建立阶段要长。

第一阶段是簇建立，簇的建立首先选择建立簇首，在LEACH算法中随机循环方式选择簇首，因此在每一轮簇建立阶段，各个节点都要判断自己是否可以成为簇首。具体的过程是：每一个节点随机生成0～1之间的随机数，如果得到的随机数小于规定的一个阀值T（i），那么该节点就成为簇首节点。

其中，n表示进行的选举轮数，p表示本轮中簇首节点在全部网络节点中所占百分比数，G表示余下1/p轮循环中没有成为簇首节点的节点集合。

选出簇首节点成功后，通过广播通知整个网络簇首节点的相关信息，网络中的普通节点根据收到的信息及信号强度决定要加入哪一个簇，向簇首发出加入簇的请求信息，至此完成簇的确定过程。

第二阶段是簇的稳定工作阶段，进入稳定工作阶段过程，普通节点在属于自己时间间隙的时刻利用CSMA MAC协议向本簇首发送数据，其余时间进入休眠状态，关闭发送，以节约能量。簇首节点接收本簇成员节点的数据信息后，进行融合后发送到基站。经过这个稳定工作阶段时间后，再进入新一轮的循环。

2.2 LEACH算法不足

LEACH算法是通过随机选择簇首，使全部所有节点公平地分担能量的消耗，通过融合机制减少数据传输过程的数据包的大小，节约能耗，延长了整个无线传感器网络的生存周期，但仍存在许多不足。

随机选择簇首时没有考虑节点剩余能量的多少，会产生当前剩余能量较小的节点承担簇首的工作，这样的簇首节点生存周期短而成为盲节点。同时在选择簇首过程中忽略了节点位置信息，在每一轮选择簇首节点时就不能保证选出的簇首都是最合适的，如果簇首位置处于边缘位置时，与基站节点距离增加，会增大能量的耗损，寿命很短。盲节点出现的频率大就会降低网络平均寿命，导致算法效率低下。

LEACH算法中能量消耗与距离有直接关系。设网络中传感器节点属于同构节点；通信是对称的，即从A传输到B一个信息与从B传输到A消耗的能量相同。则传感器网络通信过程中传送k bit数据且传送距离d时，消耗的能量：

其中，Eelec是发送电路和接收电路所消耗的能量，εfs、εmp是两种情况下放大器功率放大需要的能量，d0为门限值。

从上述公式中可以看出，节点发送信息消耗的能量与距离d成正比，当距离小于门限值d0时与距离平方成正比，大于门限值d0时与距离的四次方成正比，这表明离簇首越远的节点完成数据通信需要消耗更多的能量，这就引起传感器网络内节点的剩余能量不均衡的状态出现。在LEACH算法中，与基站距离远的簇首的能量消耗很快，成为盲节点。同时所有节点都能与簇首节点和基站进行通信，这种单跳机制限制了网络规模，传感器网络的扩展性不强。

3 改进的LEACH算法

对于上面提到LEACH算法中存在的不足，对算法进行如下的改进。

3.1 簇首的选择

在传统的LEACH算法中是假设所有节点初始能量相同，每一个节点都有相同的概率担任簇首节点，经过几轮簇首选择之后，节点剩余能量就会出现很大的差异，选择出的簇首节点能耗可能会远大于普通节点。为此可将节点的剩余能量作为选取簇首的重要因素，按照此思路，可确保能量较大的节点成为簇首的概率增加，改善网络的稳定性。

设某轮节点当前剩余能量为Ec，初始能量为Eo，将二者的比值考虑到传统选择簇首的阈值计算中，依据公式（1），改进后的阈值公式为：

或者 T（i）=0 其它

引进EC、EO比值后，可避免剩余能量相对较小的节点成为簇首，减少了簇首能量因消耗过快而出现盲节点的现象。

图2 改进LEACH算法的流程

3.2 簇首的分布

从考虑传感器节点在网络中均匀分布出发，要使簇首节点与基站距离不能太远，不能出现簇首分布聚堆现象。

设在一个面积为S区域内有n个节点，在这n个节点中产生簇首比例为P。要使整个区域被覆盖，应满足条件，R为簇的平均半径，即假设两个相邻簇首节点之间的间距为D，D就应该满足：D＜2R。在一轮簇首选择过程中，为使簇首分布均匀，相邻簇首节点间距D应满足下面条件：

通过这样一种机制，某一簇首确定后，在通信半径R内的节点就是此簇的成员，使传感器网络中所有簇首节点的间距均限定在一个相对合理的范围内，确保了簇首的较为合理的分布。

3.3 通信方式

在LEACH算法中规定了簇首与Sink（基站节点）采用单跳通信方式，前面提到这种方式容易使离基站远的簇首消耗能量过大成为盲节点。采用混合的通信机制方式，基本思路是一个簇内的节点间采用单跳的通信方式；簇间进行信息传递时，若簇首靠近基站就采用单跳的通信方式，如果与基站距离很远就采用簇首之间的多跳通信方式。

改进后的LEACH算法同样按轮划分，某一轮分成簇的建立和簇稳定两个阶段，流程图如图2所示。

4 结束语

无线传感器网络的路由算法中的LEACH算法是分簇算法的一种典型代表，在量能受限的网络中得到了广泛应用。本文在分析LEACH算法存在的不足基础上，提出了簇首选择、网络通信两方面的改进，考虑了节点能量在选择簇首节点的因素，提出了基于LEACH的改进路由算法。

[1] 武春涛，胡艳军.无线传感器网络LEACH算法的改进[J].计算机技术与发展，2009，19（3）： 80－83.

[2] 付华，赵刚. 无线传感器网络中一种能量均衡的分簇策略[J].计算机应用研究，2009，26（4）：1949－1496.

[3] 顾明霞.一种新的基于LEACH的WSN路由算法[J].计算机仿真，2011，28（8）：129－133.