2024年3月15日发(作者：)

您的论文得到两院院士关注

文章编号

:1008-0570(2012)10-0469-02

软件时空

基于

SUSAN

算子的

LEACH-C

路由算法

Leach-croutingalgorithmresearchbasedonsusanalgorithm

(

长沙医学院

)

唐启涛刘蓉张燕伍海波

TANGQi-taoLIURongZHANGYanWUHai-bo

摘要

:

在前人提出的

LEACH-C

路由算法的基础之上

,

提出了对

LEACH-C

的改进

,

在过去的

LEACH-C

路由算法中

,

采用模拟

退火算法

,

来实现选取簇头

,

改进后的算法应用图像角点检测算子

—

——

SUSAN

算子

,

使其在簇头的选取上

,

定位更准

,

速度更

快

,

同时

,

在簇头选好后

,

为了节能

,

通过应用最小树原理

,

把各个簇头节点连接起来

,

簇内成员与簇头之间

,

采用直接通信

。

通

过仿真试验表明

,

改进后的

LEACH-C

路由算法

,

能更好的节能

,

有效的延长了整个无线传感器网络的寿命

。

关键词

:SUSAN

算子

;

最小生成树

;

簇头

;

路由协议

中图分类号

:TP3

文献标识码

:A

Abstract:

BasedonthepreviousLEACH-Croutingalgorithmbringsupimprovements,theoldLEACH-Croutingalgorithmusesim-

ulatedannealingalgorithmtoachievetheselectionofclusterheads,thispaperappliesimagecornerdetectionoperator--SUSANop-

eratortotheimprovedalgorithm,thistheorycausespositioningfasterandmoreaccuratetheforselectionoftheclusterhead,atthe

sametime,aftertheclusterheadbeingselected,inordertosaveenergy,withtheapplicationofprincipleofminimumtree,the

headnodeofeachclustercanbeLinked,bet-

ulationresultsshowthattheimprovedLEACH-Croutingalgorithmcanbebetterforenergyconservationandextendtheeffectivelife

oftheentirewirelesssensornetwork.

Keyword:SUSANalgorithm;minimumspanningtree;clusterhead;routingprotocol

1

引言

在无线传感器网络中

,

通过传感器网络的高效的路由和可

靠的数据传输方法

,

从而实现延长网络寿命。路由技术是无线传

感器网络通信的核心技术

,

也是当今国内外研究的热点。与传统

网络相比

,

无线传感器网络的路由协议具有以下特点

:

能量优先

;

以数据为中心

;

具有数据融合特性

;

基于局部的拓扑信息

;

频繁变

化的拓扑结构。

2LEACH-C

路由协议分析

传感器网络设计的路由协议可以分为两类

:

平面型路由协

议和分层路由协议。作为一种分层协议

,LEACH

协议将网络中

的节点分为簇头和一般节点。簇头将簇内的数据进行压缩后

,

集

中传送给信息收集节点

,

从而达到节省网络资源的目的

,

在

LEACH

协议中

,

簇头是随机选择的

,

然后其它节点轮流充当簇

头

,

以平衡各节点之间的能量消耗。在数据传输中

,

簇内节点采

用时分复用

(Time-DivisionMultipleAccessing,TDMA)

的方式轮

流使用信道资源

,

而

TDMA

中时隙的分配是由簇头完成的。簇

之间采用码分多址

(Code-DivisionMultipleAccessing,CDMA)

的方式减小相互的干扰

,

即不同的簇采用不同的正交码同时进

行扩频传输。

Leach

协议的提出者后来在此基础上改进得到了一种集中

式的路由协议

Leach-C

协议。

Leach-C

根据全局信息挑选簇首

,

唐启涛

:

硕士讲师

基金项目

：

基金申请人

:

唐启涛

;

基金资助项目名称

:

基于

基站根据所有成员节点到簇头的距离平方和最小的原则

,

采用

模拟退火算法解决了簇数目不确定

,

和簇内的簇头节点选取最

优化的问题。最后

,

基站把簇首集合和簇的结构广播出去这样做

的优点是通过合理的安排簇首

,

可以得到一个合理的簇的分布

,

减少了原

leach

算法中因为随机组成的簇的位置或数目不理想

而造成的能耗。在

LEACH-C

协议中

,

形成的簇头之间没有形成

合理的拓扑结构

,

而且

,

在使用模拟退火算法中

,

所需时间也会更

多

,

从而影响系统的整体运行

,

在此基础之上

,

提出了该路由算法

的改进方案。

技

术

创

新

3

改进的路由算法描述

在改进的算法中

,

引入图像角点检测算子

SUSAN

算子

,

该

算子是用在图像处理中

,

提取图像的特征点

,

用于图像匹配。在

这里

,

利用该算子原理

,

选出最佳的簇头。在一幅图像中搜索图

像角点或边缘点

,

就是搜索

USAN

最小

(

小于一定值

)

的点

,

即搜

索最小化同化核分割相同值

[3]

。这样可得到特征点检测的

SUSAN

算法。而在无线传感器网络中

,

是寻找最佳的簇头

,

在一

定范围内找出最合适的簇头

,

在这里

,

确定一个节点是否为簇头

,

主要取决于两个方面

,

一个是节点的能量

,

一个是节点的连通

度。在本路由算法设计中

,

是基于以下几个方面的假设的

:

各个

节点的初始能量值是相同

;

各个节点的初始位置是已知的

;

各个

节点是均匀分布的

,

因此

,

相对于大部分的节点而言

,

其连通度是

相等的。在引用

SUSAN

算子过程中

,

由于第一轮时

,

各个节点的

能量是相等的

,

因此选用簇头就不能简单的采用

SUSAN

算子

,

而是根据节点位置

,

选择出若干个簇头节点。具体簇头节点的个

数

,

根据已有的计算最佳簇头个数公式

,

可以得出。最佳簇头个

数为

:

邮局订阅号

：

82-946120

元

/

年

-

469

-

SUSAN

算子的

LEACH-C

路由算法

;

颁发部门

:

湖南省教育

厅

:

基金编号

:(10C0458)

《PLC技术应用200例》

软件时空

《微计算机信息》2012年第28卷第10期

4

算法分析与试验仿真

其中

N

为传感器节点个数

,M

为传感区域的面积是

,d

toBS

是

传感区域到基站节点的距离

,ε

amp

信号放大器的放大倍数

,Estatic

则是发送电路和接受电路消耗的能量。根据最佳的簇头个数

,

结

合传感节点的位置

,

从而确定第一轮的簇头

,

从第二轮开始

,

开始

应用

SUSAN

算子。

在应用

SUSAN

算子过程中

,

对其原来引用的参数稍做变

化

,

在这里

,

采用每个节点的能量值作为比较节点相似的参数。

比较函数如下

:

综合以上提出的几点改进

,

与传统的

LEACH-C

协议进行

了对比分析。本文的仿真实验是基于

C++

代码基础之上的。用

MATLAB

绘出了改进后的

LEACH

–

C

路由算法在网络生存

时间方面的优势

,

如下图所示

:

技

术

创

新

I(x,y)

是掩模区其它节点的能量值

,I(x0,y0)

是掩模核的能量

值

,

先统计出整个传感区域的能量平均值

V,

然后让它先与

I(x0,

y0)

值进行比较

,

如果该值低于平均值

V,

则该点不可能为簇头

,

就不对该点进行统计比较。阈值

t

决定了

2

个点相似的最大差

异

;t

的大小与传感区域中能量的变化有关

,

根据所做试验的结

果

,

得出

t

为

5

—

10

为佳。

C

为比较输出的结果。比较完一个掩

模区的所有节点后

,

统计出与掩模核相差

t

值以上的传感器节

点个数。

统计所得结果为

n(r0),

决定

r0

点是不是簇头节点

,

还需要

确定另一方面

,

它是比较相邻簇头间的距离

,

只有满足与相邻的

簇头之间距离达到条件后

,

才能真正成为簇头。把所有特征点选

出后

,

然后统计与

r0

点相邻特征点之间的距离

P,

要求对于簇头

的节点

,

簇头结点之间的距离必须满足以下关系

:M

为

系统给出的两个参数。在多个相邻特征点中

,

选择一个既满足以

上关系

,

且

P

最大的点为该区域的特征点

,

然后比较其它的特征

点

,

直到所有的特征点比较完

,

最后确定整个区域中所有的特征

点作为簇头。

簇头选好后

,

根据最小生成树原理

,

生成最小能耗树。

建立路由树的过程如下

:

以

sink

节点作为树的根节点

,

统计出所有与

Sink

节点

(1)

、

相邻的簇头节点间的距离

,

选择一个距离值

S

最小的特征点作

为下一级父节点。

已确定的簇头节点统计与其相邻传感器特征节点距离

,(2)

、

确定下一级父传感节点

;

循环第

2,

直至所有节点均被连接到源路由树中。

(3)

、

算法具体实现如下所示

:

假设

N=(V,{E})

是连通网

,TE

是

N

上最小生成树中边的集

合。算法从

U={u0}(u0

开始

,

重复执行以下操作

:

在所

有

u

的边

(u,v)∈E

中找一条

S

值最大的边

(u0,v0)

并入集合

TE,

同时

v0

并入

U,

直至

U=V

为止。此时

,TE

中必有

n-1

条边

,

则

T=(V,{TE})

为

N

的最小生成树。算法执行完毕

,

在

网络内建立起一棵以

sink

为节点的源路由树

传感器网络拓扑图建好后

,

由

SINK

节点广播各个簇头节

点的

ID

号信息及簇头节点的上一级父簇头节点

ID

号信息。广

播后

,

在传感器节点区域各个节点

,

根据广播的信息

,

确定自己是

否为簇头

,

同时

,

对确定是簇头节点的

,

根据信息进一步确定其父

簇头节点。最终使各个簇头节点按照广播的路由信息

,

连接好各

簇头节点。对于非簇头节点

,

根据与邻近簇头节点的距离

,

选择一个最近的一个簇头加入。最终使所有节点连成一个网

络。

-

470

-

120

元

/

年邮局订阅号

：

82-946

图

1

网络生命周期

其中

,LEACHNEW

表示本文提出的新的分簇算法

,

可以看

出

,

当网络中有效节点的个数为

65

时

,

它所经过的回合数“

(

轮”

)

最多。虽然该对比实验没有考虑外界因素使节点失效的情况

,

但

实验结果已经可以显示本文算法在系统能量有效性及网络生

存时间上优势。

5

结语

在综合分析了现有

LEACH-C

与

LEACH

算法的基础上

,

提

出了一种改进后的

LEACH-C

路由算法方案。考虑到充分使传

感器节点的能耗实现均衡

,

改变了以往的在

LEACH-C

算法所

使用的模拟退火算法

,

改进后

,

采用

SUSAN

算子原理

,

选出整个

传感区域的簇头

,

使选出的簇头成为最优的簇头

,

从而延长了无

线传感器网络的寿命。同时

,

通过利用最小生成树原理

,

将所选

出的簇头结点生成最小能耗树

,

从总体上实现了无线传感器网

络的节能。理论分析表明

,

该算法能够节约网络功耗

,

有效延长

网络寿命。

本文作者创新点

:

首次将图像角点检测算法—

SUSAN

算法

应用于无线传感器网络中

,

同时结合最小生成树算法

,

改变了以

往的路由策略

,

延长了网络寿命。

本文无抄袭

,

作者全权负责版权事宜。

参考文献

[1]-Karaki,.

“

RoutingTechniquesin

wirelesssensornetworks:asurvey,

”

IEEEWirelessCommunica－

er2004pp.6-28

[2]IbriqJ,MahgoubI,Cluster-Basedroutinginwirelesssensor

networks:2004Int

’

performanceEvaluationofComputerTelecommunicationnSystems,

SanJose,2004:709~~766

[3]

李红梅

,

黄梦涛

,

田爱玲

,

等

.

亚像素级标定角点提取新算法

[J].

西安科技大学学报

,2006,26(4):536-540.

[4]

吴臻

,

金心宇

.

无线传感器网络的

LEACH

算法的改进

[J].

传

感技术学报

,2006,19(1):34-36.

[5]

李梁

,

刘琳岚

,

舒坚

,

陈英

.

基于可靠最小跳数场的路由协议研

究

[J].

微计算机信息

.2007,12-1,38-41.

[6]

郑增威

,

吴朝晖若干无线传感器网络路由协议比较研究计算

机工程与设计

,2003Vol.24No.9P.28-31

[7]STOJMENOVICI,NAYAKA,Guide

linesforRoutingProtocolsinAdHocandSensorNetworkswitha

RealisticPhysicalLayer[J].IEEECommunicationsMagazine,2005,

43(3):101-106

[8]

王华

,

柴乔林

,

杜胜永

.

无线传感器网络中数据可靠传输的节

能路由算法

[J].

计算机应用

,2006,26(1):25-27

《现场总线技术应用200例》