无线传感器网络中的节能路由算法

Vol.34 No.7 Computer Engineering · 网络与通信 ·

文章编号：1000—3428(2008)07—0113—02

文献标识码：A

2008年4月

April 2008

中图分类号：TP312

无线传感器网络中的节能路由算法

乐世成，王培康

(中国科技大学电子信息工程系，合肥 230027)

摘 要：针对传感器网络中的节点能源有限的特点，文章在分析LEACH的基础上，提出一种高能效的路由算法。该算法根据各节点剩余能量大小和簇成员数控制簇的形成，使簇头之间通过多跳合作的方式与基站进行通信，从而使网络能量均匀消耗。仿真结果显示，与原LEACH协议相比，改进后的算法提供了更长的网络生存时间。 关键词：无线传感器网络；路由算法；节能

Energy Efficient Routing Algorithm for Wireless Sensor Networks

YUE Shi-cheng, WANG Pei-kang

(Department of Electronic Information Engineering, University of Science and Technology of China, Hefei 230027)

【Abstract】The nodes have limited available power in wireless sensor networks. In view of the trait, this paper analyzes leach protocols, and anenergy-efficient routing algorithm is proposed and evaluated in which the cluster formation is controlled by the residual energy and the number ofcluster members. In addition, the cluster heads take hierarchical routing scheme to communicate with the base station. Simulations show that the newalgorithm provides longer lifetime than leach protocols.

【Key words】Wireless Sensor Networks(WSN); routing algorithm; energy saving

无线传感器网络(Wireless Sensor Networks, WSN)是由一组微型传感器节点以自组织方式构成的无线网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者[1-2]。近年来，随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟，传感器网络在商业和军事上的应用越来越多。在无线传感器网络中，除了少数节点需要移动以外，大部分节点都是静止的。它们通常运行在人无法接近的恶劣甚至危险的远程环境中，能源补充非常困难，因此，设计有效的协议和算法延长网络的生命周期是WSN的核心问题之一。LEACH(Low Energy Adaptive Clustering Hierarchy)[3-4]是一种低能耗自适应分簇结构传感器网络协议。它的分层结构具有很好的扩展性，数据融合能力可以减少通信量，节约能量。本文在对LEACH研究分析的基础上，指出该协议存在的问题，并作出改进。 k⎧

⎪N−k×(rmod(N/k))P(n)=⎨

⎪0⎩

n∈G其他

(1) 1 LEACH协议 LEACH协议的基本思想是通过随机循环的选举过程生成簇头节点，并基于接收信号的强度来形成簇，以簇头节点作为路由器负责将簇内节点采集到的信息传输到基站节点；定期轮换簇头节点以保证每个节点公平负担网络能耗、提高网络整体生存时间。LEACH在运行过程中每过一定时间就要执行簇重构过程。每次重构分为2个阶段：簇的建立阶段(setup phase)和稳定数据传输阶段(steady-state phase)。为了节省资源开销，稳定阶段的持续时间要长于建立阶段的持续时间。该协议中簇头节点产生过程如下：每个节点产生一个0~1之间的随机数，同时每个节点计算一个概率值P(n)，P表示在当前时刻该节点能够当选为簇头节点的概率。如果随机数的值小于P(n)，则发布自己是簇头节点的公告消息。在假设各个节点在成簇阶段开始前各自的能量是相等的情况下，P(n)的计算公式如下：

在每轮循环中，如果节点已经当过簇头，则把P(n)设置为0，这样这个节点不会再次当选。式(1)中，k/N为节点中簇头数占总节点数的百分比(k是预设的值，也就是在这一轮选举中在N个节点中担当簇头节点的数目)；r表示当前的轮数；在某一轮中担当了簇头的节点，在随后的N/k轮中都要将自己的P(n)值计为0，以增加其他节点做簇头节点的概率；G表示到当前轮数为止的N/k轮中没有担当过簇头节点的节点集。每N/k轮后，每个节点都重新有k/N的概率当选为簇头节点，如此重复循环，达到均衡能耗和延长网络生存期的 目的。 在各个节点能量不等的情况下，考虑剩余能量的大小，计算概率值的公式如下： ⎧E(n)⎫

×k,1⎬ (2) P(n)=min⎨⎩Etotal⎭

其中，E(n)表示成簇阶段开始时当前节点的剩余能量；Etotal表示成簇开始时网络中所有节点的剩余能量总和。节点通过生成的随机数与概率值比较，如果小于P(n)，则确定此轮自己是簇头，并立即向周围节点广播Adv消息。在对称信道环境下，其余节点根据接收信号的强度(received signal strength)，选择自己所要加入的簇，并向该簇头发送应答消息。根据簇成员的数目，簇头基于TDMA的方式为每个成员节点分配时隙。在这个过程结束后，簇结构形成，数据开始传输。在每个簇内，簇头节点使用TDMA/DS-SS(Direct Sequence Spread 作者简介：乐世成(1983－)，男，硕士研究生，主研方向：无线传感器网络，Ad hoc网络；王培康，教授

收稿日期：2007-04-10 E-mail：scle@mail.ustc.edu.cn

—113—

Spectrum)协议依次接收每个成员节点采集、传输的数据。此阶段各个成员节点在不属于自己的时隙中关闭无线收发模块，以节约能耗。簇头节点在对数据做融合处理后，各个簇头节点采用CSMA协议竞争信道，获得信道的簇头节点将融合后的数据直接发给基站(BS)。这个稳定工作阶段结束后，进行下一轮工作周期。 由于LEACH协议采用每一轮都随机选择簇头的机制，使能量消耗均匀分布到每个节点，并且由簇头节点进行数据融合后直接发送给基站，减少了与基站直接通信的节点的数量，因此延长了网络的生存期。但是该协议也存在一些问题：由于簇头节点的产生很大程度上依赖于各个节点生成的随机数，这种通过随机数与计算得到的概率值比较的机制只是从簇头节点数目的期望值是最优的角度考虑，而簇头节点的分布、相应的簇成员数目、簇的大小都不稳定，簇头节点位置分布较差时，会产生簇内通信不再满足自由空间模型，而且可能产生簇间信号干扰、负载不平衡等问题，从而导致很大能量开销[5-6]；簇头节点直接与基站通信，在LEACH的无线通信模型中，节点发送消息的信道模型服从自由空间模型(与距离的2次方成正比)，当距离大于一定值时，服从多径衰弱模型(与距离的4次方呈正比)，因此，在基站距离较远的情况下，直接通信的代价很大；各个簇的建立过程都是在全网的所有节点间进行协商，由此带来的计算控制和通信开销很大，相应增加了每个节点的能耗；簇头节点的选择在考虑节点 当前剩余能量的状况时，需要计算网络全部节点的当前能量总和。 2 对LEACH协议的改进 针对上面提出的一些问题，改进后的协议采用从控制簇成员的范围和数目并且结合考虑节点剩余能量的方式来形成簇。在簇内采用单跳通信，在簇头节点与基站之间采用多跳的方式。和LEACH一样采用轮的方式工作，每一轮分为簇的构建和稳定工作阶段。 2.1 簇的建立 初始阶段网络中各个节点以一定的半径开始向周围广播，同时接收各个邻居节点的广播消息。每个广播消息只有一跳的生命期。在成簇阶段，如果产生的簇头节点在一跳范围相互影响时，它们通过协商选择剩余能量较大的节点作为簇头；对于成员节点通过接收信号强度选择要加入的簇。在簇头节点竞选的时间段内，如果节点收到来自邻居节点的广播消息数达到N/k，节点宣布成为候选的簇头节点，对周围的邻居节点广播这个消息，并且把自身的信息加入到自己候选簇头节点表中。如果收到来自其他邻居节点的宣布成为候选簇头的消息，则与其比较剩余能量的大小，对于比自身剩余能量小的邻居节点的消息不予理睬；如果是比自身剩余能量大的邻居节点的消息，则都加入到候选簇头节点表中。如果判断自己是候选节点表中剩余能量最大的节点，则宣布成为正式的簇头节点，否则根据收到的其他邻居节点宣布成为正式簇头节点的消息，选择接收信号强度最大的一个作为要加入的簇的簇头节点。 如果到簇头节点竞选阶段结束时没有收到具有较大剩余能量的候选邻居节点宣布成为正式簇头节点的消息，则自己立即宣布成为正式簇头节点的消息。然后成员节点根据收到的邻居节点成为正式簇头的消息的接收信号强度，确定要加入的簇，并向簇头节点发去应答的消息；如果没有收到任何邻居节点宣布成为正式簇头的消息，则该节点自己宣布成为—114

— 的簇头节点。在这个过程结束后，每个簇头节点根据应答的消息可以知道自己的簇成员情况。然后簇头节点为每个簇成员分配一个TDMA时隙，并且通知给每个簇内成员。 2.2 簇头节点与基站之间的通信 由于簇头节点与基站之间直接通信的代价很大，为了减少这种远距离的通信能耗，考虑各个簇头节点之间通过多跳合作的方式与基站进行数据传输[7]。为了建立簇头节点的多跳的树型结构，基站预先进行全网广播消息。对于成员节点要忽略此消息。根据传感器节点可以调节自身发射功率的特点，调节簇头节点的发射能量[8-9]，使簇头节点之间的通信距离大于簇内通信的范围。每个簇头节点接收相邻的簇头节点转发的来自基站的广播消息，根据收到的消息选择离基站跳数最少；在跳数相同的情况下，根据接收信号强度选择通信代价最小的邻居簇头节点，记录下该邻居节点的id，以后该簇所收集融合的数据就通过这个邻居转发给基站。簇头节点选择好上一级的邻居后，更新跳数信息，再进一步转发基站的广播消息；如果后来收到更优的路径消息，则重新转发来自其他邻居的广播消息，否则丢弃以减少通信量。广播结束后，每个簇头节点都保存与基站通信的上一级邻居节点(基站附近的簇头节点直接与基站通信)。 2.3 稳定传输数据 在簇头节点给每个成员分配好TDMA时隙，各个簇头与基站的通信路径建立后，开始数据的采集与传输工作。每个成员节点直接将收集到的数据发送给簇头节点，簇头节点在收到所有成员的数据后，进行数据的融合处理，然后根据记录的转发id把数据信息发送给邻居簇头节点或者基站。在稳定传输阶段和LEACH一样，每个成员节点只在属于它自己的时隙才打开无线通信模块，否则处于休眠状态。 3 仿真实验和分析 本文基于NS-2平台，在100 m×100 m的范围内随机部署100个同构的传感器节点，基站位于(50, 175)。每个节点的初始能量为2 J。采用文献[1]中的通信能耗模型：节点每发送1K b消息所需的能量计算公式为 Ed)=E⎧⎪kEε2

elec+kfsd

0tr(k,tr-elec(k)+Etr-amp(k,d)=⎨delec+kεmpd

d节点每接收1 Kb消息所需的能量的计算公式为E=kEE2reelec，其中参数如下：elec=50 nJ/bit, εfs=10 pJ/bit/m, ε4mp=0.001 3 pJ/b/m,d0=75 m，初始设定簇头数目为6，数据包的大小是500 b，报头和广播包的大小是25 b。节点能量为0时成为死亡节点。 在实验中分别采用LEACH协议和改进后的LEACH_NEW协议进行传感器网络的运行。对网络中节点生存时间和基站接收的数据量进行对比分析得到图1和图2所示的变化。图1表明，改进后的协议的稳定周期要比原来LEACH协议提高了近20%，第1个节点的死亡时间比原来延迟了160 s。这是因为改进的协议使得网络的分布更加合理均衡，节点能量消耗得到降低，簇头节点之间通过多跳合作进一步节省了向基站发送数据的能耗。图2给出了基站接收到的数据随网络时间的变化，由于新协议的节点最后死亡时间要比原来协议更集中，也就是进一步延长了网络正常工作的时间，这也可以从基站得到的有效数据量的对比中得到说明。在网络对比实验中，运行改进协议的基站多收集了近25%的有效数据量。 （下转第117页）