第24卷第5期2011年5月
传感技术学报
CHINESE JOURNAL OF SENSORS AND ACTUATORS
Vol．24No．5May 2011
收稿日期：2010－11－04
修改日期：2010－12－22
Energy Optimized Approach Based on Clustering Routing Arithmetic
不锈钢镀钛
for Wireless Senor Networks
LIU Tieliu ，WU Yongqun *
（College of Electronics and Information Engineering ，Nanjing University of Technology ，Nanjing 210009，China ）
Abstract ：Designing clustered routing protocol for Wireless Sensor Networks （WSNs ）needs consider the energy of single node and the balance consumption of the whole network energy．Clustering resolves effectively node energy bottleneck and unbalanced consumption of clusters in WSNs．On the basis of analyzing the characteristics and short-comings of traditional clustered routing LEACH （low energy adaptive clustering hierarchy ）protocols and some recent representative improved routing algorithms based on the idea of LEACH ，a routing improvements protocol based on clustering in wireless sensor network is proposed．It adopts a new cluster head competition parameter ，which can re-duce the control message cost of during cluster formation and solve the net nodes energy heterogeneous problem in a better way．Yet it reduces the quantity of cluster-head communicate with the base station by multi-hop．Simulation results show that the protocol can save the node energy consumption effectively and prolong the network lifetime．Key words ：wireless sensor networks ；clustering routing protocol ；LEACH ；multi-hop communication ；network lifetime EEACC ：7230；6150P
doi ：10．3969/j．issn．1004－1699．2011．05．027
刘铁流，巫咏
*
（南京工业大学电子与信息工程学院，南京210009）
摘
要：无线传感器网络的路由协议设计要同时关注单个节点的能耗及整个网络能量的均衡消耗。分簇算法能有效解决节 点能耗受限与不同节点能量开销不平衡问题。在分析了传统分簇路由LEACH （low energy adaptive clustering hierarchy ）协议中选择簇头算法不足和当前一些典型基于LEACH 思想的路由改进算法的基础上，提出了一种改进的传感器网络分簇路由协议，通过采用一种新的簇首竞争参数，减小了簇形成过程中的控制消息开销，从而能够更好地解决网络节点能量异构问题。同时让簇头采用多跳通信方式向传输数据，进一步降低了能量开销。仿真结果表明，该协议能有效节省节点的能耗，延长网络生存周期。 关键词：无线传感器网络；分簇路由；LEACH ；多跳通信；网络生存周期
中图分类号：TP393文献标识码：A 文章编号：1004－1699（2011）05－0764－07低功耗无线电通信技术、嵌入式计算技术和微型传感器等技术的飞速发展和日益成熟，使得大量低成本的微型传感器
可以通过无线链路自组织成为无线传感器网络（Wireless Senor Networks ，简称WSNs ）［1］。虽然无线传感器网络与现有的无线自组织网络有许多相似之处，但同时也存在很大差别
［2－3］
，其中最显著的便是由于无线传感器网络节点一般采取随机一次性部署的方式
［4－6］
，不同于无线自组织网络节点通常具有持续的能量供应。无线
传感器网络中节点的能量是由内置的电池提供，因
此，整个传感器网络的生存期受到电池容量限制。为延长整个网络的生存期和提高网络的利用率，较好的途径是寻一种更好的节省网络节点消耗能量的算法，而分簇正是为了解决这些问题引入对网络分层方法的重要技术
［7］
。分簇技术是实现上述目
标的重要而有效的手段
［8］
，分簇算法可以减少节点发送数据的距离和数据包碰撞次数，加之经过数据融合处理，减少发送数据的长度，从而极大地降低每
第5期刘铁流，巫咏：基于能量优化的无线传感器网络分簇路由算法研究
个节点的能耗由于节点能量的限制，簇内节点与簇首的通信方式以及簇的拓扑结构决定了整个网络能量的消耗速度。
本文在分析现有分簇路由协议特点和不足的基础上，提出了一种改进的能量优化的分簇路由协议。除采用了新的簇首竞争参数，同时又在簇首集合上构造了簇间多跳路由，通过多跳传输的方式减少直接与通信的簇首数量，从而可以进一步降低能量的开销。
1现有分簇路由算法
分簇算法（Cluster Algorithm）是无线传感器网络中实行分层路由所采用的一种重要方法。分簇的概念最早是在分组无线网中提出，主要是针对网络中的节点进行层次划分，若干个相邻节点构成—个簇，
然后每个簇内选举一个簇头（Cluster Header），由簇头节点管理和维护本簇范围内节点，负责簇内节点通信，同时为簇间节点通信提供合适的路由信息，簇头之间的连接构成上层骨干网，所有簇间通信都通过骨干网进行转发。迄今为止，在无线自组网（Wireless Ad Hoc Network）中已经提出较多的分簇算法用于实施层次路由协议，而无线传感器网络中的分簇算法正处于研究的阶段。同无线自组网相比，无线传感器网络中的分簇算法更侧重于保持网络整体的能量消耗的均衡，避免出现热点（Hotspot）问题，最大化地延长网络的生存时间。
在分簇的拓扑管理机制下，网络中的节点分为簇头节点和成员节点两类。在每个簇内，根据一定的机制选取某个节点作为簇头，用于管理和控制整个簇内成员节点，协调成员节点之间的工作，负责簇内信息的收集和数据的融合处理以及簇间转发。1．1LEACH协议算法
LEACH协议的全称是“低功耗自适应集分层协议”（Low Energy Adaptive Clustering Hierarchy）［9］，是分簇路由算法中一种专门用于无线传感器网络的分簇协议。采用动态分簇技术，使网络中的所有节点轮换充当簇头，以均衡网络中的能量消耗，延长整个网络的生命周期。在LEACH算法中，节点自组织成不同的簇，每个簇只有—个簇头。所有非簇头节点将自己的数据发给所属簇的簇头节点，为减少冗余数据的传输，簇头节点在数据融合后将数据发送给远方的接收器。这样，每个非簇头节点都只需要知道自己所属簇的簇头信息即可，簇头也只需要维持很小的路由表，为了避免簇头能量消耗过快，每个节点须轮流担任簇头。因此LEACH算法的实现分成若干轮，每一轮又可分成簇形
成阶段和簇传输阶段，而簇传输阶段远远长于簇形成阶段。在簇形成阶段，每一个还没有担任过簇头的节点分别生成0 1之间的随机数，如果生成的随机数小于给定的阈值T（n），则选择为簇首。这里T（n）的计算方法如下：
T（n）=
p
1－pˑ［rmod（1/p）］
，n∈G
0，
{其他（1）
其中：P是簇首在所有节点中所占的百分比，r 是选举轮数，G是第r轮之前尚未当过簇首的节点集合，n是表示某节点。
一旦节点被选为簇头后，就向外发送簇头广播信息。非簇头节点根据根据收到的簇头广播信息的信号
大小决定要加入哪个簇，并向决定加入的簇的簇头发送加入簇的请求。簇头在收到请求后将该节点加入自己的路由表并为每个节点设定一个TDMA 定时消息，并且通知该簇中所有节点。此后的簇传输阶段，这些分布式的节点即按照该TDMA时间表、以一跳式或多跳式的路由拓扑结构进行数据传输。每隔一定时问，整个网络重新进入簇形成阶段开始新一轮的簇头选举过程。
LEACH算法是让网络中的节点自组织地形成簇，簇头是随机产生的，这种随机产生的方式无法保证簇头节点的合理分布。当簇头节点位置比较集中时，簇的覆盖区域将出现部分重叠的现象，网络拓扑结构不够优化；当簇头分布在边缘区域时，簇内节点到簇头的距离将变大，使得簇的载荷也相应变大，而且簇头选举中没有考虑节点剩余能量不均等的问题，使得有些能量较少的节点被选举为簇头，这就加速了节点的死亡，故不能有效地延长网络生存周期。另外由于簇头选举的随机性使得网络的簇头需要负担的节点数不同，加重了个别簇头节点的负担，使得网络的负载平衡程度下降［10］，也降低了网络寿命。1．2其他改进的LEACH算法
LEACH-C（LEACH-centralized）和LEACH-F （LEACH-fixed）［9］都是集中式的簇头产生算法，由负责挑选簇头。
LEACH的簇头由节点根据随机数自主决定，没有明确的数目和位置，而LEACH-C根据全局信息挑选簇头，每个节点把自身地理位置和当前能量报告给。根据所有节点的报告计算平均能量，当
前能量低于平均能量的节点不能候选簇头。从剩余候选节点中选出合适数量和最优地理位置的簇头集合是一个NP问题［11－12］。根据所有成员
567
传感技术学报
www．chinatransducers．com第24卷节点到簇头的距离平方和最小的原则，采用模拟退
火（Simulated Annealing）算法解决该NP问题。最
后，把簇头集合和簇的结构广播出去。
LEACH-F也是在LEACH基础上做了一些改
变。簇的形成与LEACH-C一样，同时，为每个
簇生成一个簇头列表，指示簇内节点轮流当选簇头
的顺序。最大的优点就是无须每轮循环都构造簇，
减少了构造簇的开销。但是，LEACH-F并不适合真
实的网络应用，因为它不能动态处理节点的加入、失
败和移动。同时，它还增加了簇间的信号干扰。
LEACH-E是分布式簇头产生算法，针对
LEACH没有考虑节点的剩余能量情况而选择簇头
的不足提出的。每个节点使用式（2）的概率来决定
自己是否成为簇头节点：
p（S
i ）=min
E
i
（r）
E
total
（r）
k，
{}1（2）
其中，k是总簇头数目，E
i
（r）为节点i在第r轮
的剩余能量，E
total （r）=∑N
i=1
E
i
（r），为当前网络的总
能量。式（2）的改进，使剩余能量比较高的节点优先当选簇头，避免了选择剩余能量低的节点导致节点快速死亡的缺点，第一个死亡节点时间比LEACH 稍有延长。
PEGASIS（Power—Efficient Gathering in Sensor Information Systems）协议［13］借鉴了LEACH中分簇算法的思想。根据节点的地理位置，采用贪婪算法将所有节点形成一条相邻节点之间距离最短的链，这样每个节点都能以最小功率发送数据，并且每轮只随机选择一个簇头与通信，减少了数据通信量。但是PEGASIS算法需要知道每个节点地理位置信息，且信息传输有较大时延。还有一些针对能量高效利用的路由协议被提出，TEEN（Threshold sensitive Energy Efficient sensor Network）协议［14］是一个基于集的路由协议，也是由LEACH发展而来的。TEEN和LEACH的实现机制非常相似，只是前者是响应型的，而后者属于主动型传感器网络。EERP［15］基本也和HEEN一样，没有从节点间能量的角度考虑。
2改进的新算法
2．1新算法协议设计思想
目前针对LEACH算法改进研究主要是针对两方面：①改进簇头选择算法；②簇间考虑利用多跳通信传输数据到Sink。针对上述的设计要求，本文分别对LEACH算法的簇头选择算法和数据传输方式做了改进，设计了一种新的基于非均匀分簇的传感器网络路由算法（Energy Optimal-based Unequal Clustering Protocol，EOUCP），其基本思想是在簇头竞争过程中，同时考虑节点及其邻居节点的剩余能量，提高对低能量节点的保护；成簇后对簇内活动节点进行调度，在不影响监测区域覆盖率的情况下，让一部分节点进入休眠状态，既节约了节点能量，也减小了数据信息的冗余度，簇头与汇聚点间通信采用多跳的路由方式，避免长距离传输造成能量浪费。2．2网络模型
网络由N个随机部署的传感器节点组成，同时有以下假设：①传感器网络为高密度静态网络，部署在方形观测区域A的外侧，传感器节点和部署后均不再发生位置移动，且唯一；②节点具备数据融合功能，每个传感器节点都有一个唯一的标识（ID）；③节点可以根据接收方距离的远近自由调整其发射功率以节约能量消耗；④链路是对称的。若己知发送方的发射功率，节点可以根据接收信号的强度计算出发送者到自己的近似距离。
EOUCP算法采用与LEACH协议相同的无线通信模型［16］。节点发射每比特的数据到距离为d的位置，消耗的能量有发射电路和功率放大功耗两部分组成，即轮胎帘布
E
Tx
（l，d）=
lE
elec
电子标签生产设备+lε
fs
d，d＜d
lE
elec
+lε
mp
d4，d≥d
{0（3）
其中，E
elec
：表示发射电路的能耗。若传输距离
小于阈值d
，功率放大损耗采用自由空间模型；当
传输距离大于等于阈值d
时，采用多路径衰减模
型。ε、ε
mp
分别为这两种模型中功率放大所需的能量。
节点接收l比特数据的能耗为：E
Rx
（l）=lE
elec
。
将k个长度为l比特的数据包融合的能耗为：
E
Rx
（l）=lkE
DF
．其中，E
DF
为融合单位比特数据所需的能量。
2．3算法描述
2．3．1EOUCP算法思想
EOUCP是基于LEACH基本思想提出的改进算法，在簇的建立阶段和稳定数据传输阶段与传统LEACH算法的过程大致相同，主要的思想体现在改进了簇头的选择过程和簇头到Sink节点之间采用多跳的传输方式。EOUCP算法是一个分布式竞争算法，每个传感器节点都参与竞争，使簇头的分布更均匀合理。竞争的主要依据是节点的剩余能量和邻居节点的平均剩余能量的比值，不再以式（1）中的阈值作为簇头竞争的参数。在EOUCP协议中，规
667
第5期刘铁流，巫咏：基于能量优化的无线传感器网络分簇路由算法研究
定每个节点需要保存一张邻居表，以存储器邻居节
点的相关信息，包括节点ID、剩余能量、距离等，见
表1。
表1邻居表内容
ID state剩余能量距本节点的距离
1unclustered1．568
2head2．236
3clustered0．452
…………
2．3．2簇的组建和运作
考虑到LEACH中簇头竞争存在的不足，
EOUCP中将节点的剩余能量和邻居节点的平均剩
余能量的比值作为簇头节点选择的重要参数。
算法开始时，先以给定的功率向全网发送
广播信号，节点根据接收到的信号强度计算出它到
的距离d，由该距离值得到自己的竞争半径Ri，
计算如下：
R
i =c
E
residual
珔E+（1－c）·
d
d
max
－d
[]
min
R
c
（4）
其中，0≤c≤1，c为控制取值范围的参数，为常系
数，用来调整网络中节点能量和距离这两个参数所占的大小。实验中可选择c=0和c=0．5，通过仿真比较，可以观察到c取不同值时，簇头数目与R
c
之
间的关系。当R
c
固定时，c增大对应簇头数目要多，这是因为c的增大导致候选簇首的竞争半径变
小，因此簇头的数目增多。E
residual
为节点在第m轮运行时的剩余的能量，珔E为第m轮运行时簇内节点
的平均能量。d
max 和d
min
代表节点到的距离的
最大值和最小值。R
c
代表节点的最大竞争半径。
每个节点将竞争半径内的区域作为自己的竞争区域，将竞争区域内的所有其他节点看作是自己的
邻居。节点首先以半径R
i
广播消息，这样算法将簇
头覆盖区域大小限制在半径R
i
的区域内，即在簇头
节点通信半径R
i
内的节点才能成为此簇类的成员，实现了地理分布上的均匀分簇。再根据邻居节点发送的消息更新邻居表，最后由式（5）得到其开始簇
首竞争的时间t
c
。
t c =μTE
residual
/珔E（5）
其中，μ为分布在［0．9，l］的随机实数，为常系数，在实验时选取合适的常数值，用来调整节点剩余能量和簇内节点平均能量所占的比重，进而可以控制节点i开始竞争簇首时间的大小。由式（5）可桥壳
知，当节点剩余能量较小时，其开始竞争簇首的时间t
c 变短，有效保护了当节点能量较低时避免成为簇头而加剧其死亡的可能性。T代表事先规定的簇首竞争持续时间，珔E代表邻居节点的平均剩余能量，E
residual
代表节点的剩余能量。
若节点在竞争时刻到来之前已经收到邻居节点的簇头申明消息，则退出竞争并发送消息加入该簇。否则，节点统计邻居中已加入簇的节点数并与阈值k（t）进行比较。当节点数小于阈值k（t）时，广播消息宣布竞争成功。阈值k（t）的计算公式：k（t）= m（1－e－t/T），其中t代表当前时间，m代表全部邻居
节点数。
阈值k（t）的推导过程简要说明如下：
因m代表全部邻居节点总数目，节点统计邻居中已加入簇的节点数必然要小于最大值m，所以阈值可设为m（1－α），其中α∈（0，1）。利用指数函数e－x特性，当x∈（0，1）时，e－x∈（0，1），即阈值k（t）=
m（1－e－x），而μE
residual
/珔E∈（0，1），所以可令μE
residual
/珔E来代替x，即有阈值等于m（1－e－μE residual/珔E）；又有式（5）分析，可得阈值k（t）=m（1－e－t/T）。
簇首竞争结束后，若节点有多个邻居节点成为簇首，则加入距自己最近的簇以减少通信干扰，未加入簇的节点发送消息至剩余能量最大的邻居节点，通过该邻居节点成为其他簇的多跳成员。进入稳定运行阶段后，簇内成员节点持续采集监测数据，传与簇头节点后发送到Sink节点。持续一段时间以后，整个网络进入下一轮工作周期，重新选择簇头节点。2．4EOUCP协议的簇间动态多跳路由算法
该算法对簇头与Sink之间的通信方式做进一步的改进，算法中簇头利用权值［17］来选择下一跳路由。在数据传输阶段，采用多跳传输，需要建立一棵以簇头节点组成的树，簇头结点为Sink，在路由表建立的过程中不再考虑时间延迟的特点，将模型理想化，忽略其延迟时间。因为相对节点之间数据的传输和簇头与Sink多跳通信时间来说，节点本身的路由建立时间非常短，要相差几个数量级，同时
在数据传输阶段可以设定一较长时间，避免频繁建簇的能耗。首先假设簇间多跳路由协议中，中继簇头收到的上一跳的数据间没有冗余信息，并且来自不同簇的数据无法进一步融合，中继簇头只是简单转发来自其它簇头的数据。网络结构如图1所示。
如何从邻居簇头集合中选择合适的下一跳路由是簇间路由策略的关键，文中假设通信采用自由空间模型，链路消耗的能耗与距离的平方d2呈线性关系。假设簇头i有数据传送，如果有中继簇头j帮助传输数据，则到Sink的消耗的链路能耗代价归结为［dtosink（j）］2，ditoj2，与簇头i直接将数据传给BS
767
传感技术学报
www．chinatransducers．com第24
卷
图1EOUCP算法的网络结构图
的链路能耗代价［dtosink（i）2］，相比，只有满足
［dtosink（j）］2+dito j2＜dtosink（i）2，中继传输才能
节省能量消耗。
为了综合考虑节点的剩余能量和链路的消耗代
价最低，在选择下一跳簇头作为路由时，考虑到中继
节点的剩余能量和中继转发的链路消耗代价两方
面。引入定义如下：
W
j =
E（j）
E_（r－1）
+
dtosink（i）2
dtosink（j）2+dito j2
（6）
其中dtosink（i）、dtosink（j）为簇头i，j到Sink的距离，ditoj为第i簇头到第j簇头的距离，E_（r－1）为上一轮的平均能量，E（j）是节点的剩余能量。
簇头i将它的邻居簇头j加入到邻居簇头集合中，并计算这些邻居簇头的权值Wj，然后从权值Wj ＞2的邻居簇头中选择下一跳路由。依照权值大小的顺序来选择该簇头的下一跳路由顺序排列在下一跳路由表中。权值越大的簇头优先被选择为下一跳路由，若发现权值相等的情况则根据节点的ID大小来选择下一跳路由，下一跳路由表在每轮形成簇头后构建形成。考虑节点的存储量有限，下一跳路由表中只放三个路由项，分别按照权值W的大小依顺序存放在路由表中。例如：如图2，在某一轮中簇头节点3的路由表如表2中所示，该簇头3会选择簇头6作为其下一跳的中继簇头
。
图2簇头3的路由选择路径
表2路由表
顺序号下一跳簇头节点的ID权值W 163．5
292．7
312．4
在实际工作过程中，有些簇头可能担任多个簇
头的中继，这样该簇头的能量消耗较多，容易快速死亡，造成“热点”出现。中继簇头引入一个合理的能量变化阈值ΔE。考虑到每个中继节点要发送自己的数据和允许转发两个其邻居簇头节点的数据，所以实验中设置ΔE为3倍的自己到Sink转发数据的通信能耗，即ΔE=3（lε保温炉
fs
d2
itosink
）。簇头节点能量变化阈值ΔE的设置要根据节点的转发能力来设置，与节点和sink间的通信能耗代价有关。当中继节点能量超过ΔE时，向邻居簇头广播一能量消息通知各邻居簇头不再作为中继转发数据。邻居簇头就会将路由表中这个路由项删除。选择路由表中下一个路由项作为下一跳路由。当中继6的能量大于阈值时，发送一消息，簇头3收到后就会将6的这个路由项删除。而选择1的路由项即簇头节点9作为下一跳路由。如果路由表中的每一个路由项的能量变化都达到阈值ΔE，那么路由表就是空的，节点3就不能利用中继转发，而是自己将数据送至Sink 节点。
在路由选择结束，簇头节点组成了一棵以Sink 为根节点的树，数据沿着Sink的方向在边上传输。3仿
真实验与性能分析
3．1场景设置
本文采用了与文献［18］中类似的场景，在100mˑ100m的矩形区域内随机放置100个传感器节点，Sink节点位于（150，50）处，所有节点的通信距离为20m。
假设节点的初始能量均为2J，且原始数据产生速率均为1kb/s，每个节点发送或接收数据时，发射
电路需要消耗的能量E
elec
=50nJ/bit，功率放大器
消耗的能量E
fs
=100pJ/（bit·d－2），簇头融合数据
消耗的能量E
df
=50pJ/bit，信号放大器的放大倍数εmp=0．0013pJ/bit/m4，信号传输距离d0=87m，采样周期10s。
3．2结果与分析
本文利用NS－2仿真平台，选取了簇头能耗、簇头个数、网络能耗、存活节点数等指标来比较LEACH算法和新算法的性能，并在不考虑外界破坏
867
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议