无线传感器网络中数据可靠传输的节能路由算法

2006年1月

文章编号:1001-9081(2006)01-0025-03

计算机应用

ComputerApplications

Vol.26No.1Jan.2006

无线传感器网络中数据可靠传输的节能路由算法

王　华,柴乔林,杜胜永

(山东大学计算机科学与技术学院,山东济南250061)

(whpdr@sohu.com)

摘　要:提出了一种保证数据可靠传输的节能算法。该算法根据各节点的最多剩余能量(MRE)在感知区域内建立以sink节点为根的源路由树,以剩余能量少于ε的节点作为叶子节点。若数据传输过程中有中间节点死亡,则调用可靠路由算法;并利用ARQ机制检测是否有数据包丢失,采用hop2by2hop机制进行重传。

关键词:无线传感器网络;可靠传输;最多剩余能量;hop2by2hop;路径变换算法中图分类号:TP393.02　　文献标识码:A

Energyefficientroutingalgorithmwithreliabletransferinwirelesssensornetworks

WANGHua,CHAIQiao2lin,DUSheng2yong

(SchoolofComputerScience&Technology,ShandongUniversity,JinanShandong250061,China)

Abstract:Manyapplicationsinwirelesssensornetworksrequirecollectingalldatawithoutanylossfromnodes.Anenergyefficientalgorithmonreliabletransferwasdiscussed.Accordingtomaximumresidualenergy(MRE)ofnodes,atreewhoserootwasthesinknodewassetupinthecoveredfieldinwhichnodeswithmaximumresidualenergylessthanεwereleaves.Datapacketscouldberetransmittedreliablyfromachildtoitsparentwithahop2by2hoperrorrecoverymechanismusingareliableroutingalgorithmwhenitsparentonthereversepathwasdown.ARQschemewasusedtodetectpacketloss.

Keywords:wirelesssensornetwork;reliabletransfer;(MRE)maximumresidualenergy;hop2by2hop;reliableroutingalgorithm

0　引言

由于无线传感器网络中资源有限以及地理环境等原因,其丢包率高达5%～10%(甚至更高)。但是在不可靠的无线传感器网络中传输的数据,某些数据是不允许丢失的,例如代码更新、大型数据传输(例如图片)[3]。目前,传感器网络中路由算法基本上都是以洪泛算法为基础,通过增加一定的约束条件而形成的

[1]

形式传输出去[4]。通过仿真表明,RMST(Reliable

MultiSegmentTransport)在MAC层、传输层和应用层上的可靠性达到了一个良好的平衡。RMST主要用于定向传输,利用

HHR、选择ARQ机制,保证可靠传输并可以实现分段/重

组[2]。

无线传感器网络是一种资源有限的网络,节能是不可忽视的。无线传感器网络中现行的路由算法基本是以洪泛法为主,因此建立的路由往往不是最佳路由,这样在两个节点之间进行数据传输时,数据可能要走很多弯路,另外在数据丢失导致重传时,会消耗更多能量。如图1中,A节点与B节点经过长距离进行通信,不一定经过最佳路径。

。要在不可靠的无线传感器网络中可靠

的传输数据,必须对现有的路由算法进行改进。

影响可靠性的因素主要有:

链路的不对称性使得难以估计链路质量。如障碍物或冲突等原因可能会引起一系列的丢包现象,连接的动态变化使问题更加复杂;

无线传感器网络节点的资源有限。节点由电池供电,能源有限;节点只有很小的通信功率和存储空间。而且,其通信带宽非常窄。故无线传感器网络不可能运行非常复杂的算法以保证可靠性[3]。

1　现有算法分析与比较

目前国内外已经提出了多种基于多跳通信的提高数据传

输可靠性的算法。PSFQ(PumpSlowly,FetchQuickly)采用

(hop2by2hopretransmission,HHR)、无确认机制,为降低传输

图1　无线传感器网络中的普通路由

2　新算法设计

首先在网络中建立起一种能够节能的拓扑结构,在网络覆盖区域内生成路由树,利用节点接收信号的强度RSSI确定节点的父节点;并对现有的可靠传输算法进行改进,利用可靠路由算法保证传输路径的完整性,用ACK确认机制进行丢包检测,使数据能够沿着既定路径成功传输到sink节点。

数据的延迟时间,该协议努力提高成功传输的概率,在下一个包到达之前,接收端删除当前包,通过检查序列号是否正确的方法检测是否有数据包丢失,而对于丢失的包,则采用广播的

　　收稿日期:2005-07-08;修订日期:2005-09-05　　基金项目:山东省信息产业发展专项资金资助项目(2003118)　　作者简介:王华(1980-),女,山东临朐人,硕士研究生,主要研究方向:计算机网络;　柴乔林(1956-),男,山东青岛人,教授,主要研究方向:计算机网络、人工神经网络;　杜胜永(1976-),男,山东枣庄人,硕士研究生,主要研究方向:无线传感器网络.

26　　　　

该算法的流程图如图2所示。

计算机应用2006年

图3　拓扑树的结构2.2　数据可靠传输策略

在无线传感器网络上,成功接收的数据包的数量等于发图2　算法流程

送的数据包与传输成功率的乘积。Nreceived=Psuccess×Nsent

(1)

2.1　路由树生成

在无线传感器网络中,节能是关键问题。如果在网络中建立多条传输路由以保证数据可靠传输,那势必会降低网络效率,耗费能量。下面探讨如何以单路径路由保证数据可靠传输。

首先在感知区域内建立若干以sink节点为根的源路由树,感知数据沿着叶子—中间节点—sink节点的方向传输。为延长网络寿命,考虑到个别接近死亡的节点,在建立树的过程中,先要检测节点的剩余能量(MaximumResidualEnergy,MRE)。若节点的剩余能量少于某个值ε(ε值由用户确定),则此节点不可能成为中间节点,只能作为叶子节点,然后使满足能量要求的节点成为中间节点。之所以提出MRE,因为无线传感器网络应该被作为一个整体来考虑,延长单个节点的寿命是没有意义的,应该侧重于延长整个网络的寿命。建立一棵以sink节点为源节点的路由树。在该树中,所有剩余能量小于ε的节点均作为叶子节点。建立树以后,每个节点存储自身到sink节点的跳数。

一般来说,如果每个节点的通信功率都是相同的话,近距离节点之间的通信质量会比较好[5]。具体实现时,可用节点接收信号的强度(receivedsignalstrengthindicator,RSSI)估计两节点之间的距离。

建立树的算法如下:

(1)以sink节点作为树的根节点,sink节点发出广播;(2)节点根据接收信号的强度RSSI确定父节点;

(3)已确定父节点并且剩余能量在值以上的节点发出广播;

(4)循环第2,第3直至所有节点均被连接到源路由树

由公式(1)可以看出,要提高接收到的数据包的数量,可通过提高发送包的数量或者提高所发送包的成功率来实现。

为提高发送包的数量Nsent,一种方法是重传,对错误的数据包进行重传。目前已经针对无线传感器网络提出了多种重传机制。各种重传机制的不同在于在何处重传。TCP中用到的端到端重传(end2to2endretransmission,以下简称EER)机制是在网络的两端进行重传,由于其功耗过大,虽然该机制适合错误率仅为10-15的有线网,却不适合可靠性较低的无线传感器网络。仿真表明,如果用了EER机制,经过多跳网络成功传输数据包的几率会急剧下降[4]。

另一种重传机制是逐跳重传(HHR)机制。像PSFQ和

RMST这两种传输层协议用的就是HHR机制。当节点发现

有数据包丢失时,该节点就会向到达源节点的路径上的下一跳节点发送修复请求,请求下一跳节点重新发送数据包[1]。

第二种提高成功接收包的数量Nreceived的方法是提高成功传输的概率Psuccess,可以通过提供可靠路由和可靠的丢包检测机制来实现。

本文采用HHR重传机制。原理如下:每个节点都有一个

cache,存放需要转发的数据包。当某节点检测到有数据包丢

失时,向通往源节点的路径上的上游节点发重传要求。上游节点查找本地cache内的数据包,重新向该节点发包,该机制只在相邻节点间重传数据包,为无线传感器网络中的其他节点节省了能源。

在无线传感器网络中只有一个节点没有cache,该节点就是sink节点。其他节点均位于通向sink节点的路径上,需要用cache存储数据。

2.2.1　可靠路由算法

中。

算法具体实现如下所示:

假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0U=V为止。此时,TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。

在数据传输过程中,部分节点可能会由于通信量过大等原因导致死亡,网络中出现断路,针对该情况,调用可靠路由算法重新发现新的路由,如下所述:假设A在发送数据过程中,发现其父节点已经死亡,则A向周围发出广播,并在报文中附上其IP地址,若节点B收到广播,则B向A发送一个消息,并附上自己的跳数及IP地址,当A节点收到消息后,会选择一个RSSI较大且跳数较小的节点作为自己的新父节点。

其工作流程如下:每个节点负责把数据沿着逆向树成功传输给其父节点,如果数据成功被接收,则发送端清空缓冲区,不再为发送出去的数据负责任。这时,父节点成为当前的数据源,父节点继续向树的上一层节点发送数据,如此反复,直至数据传到sink节点。若父节点突然死亡,则发送端发出

算法执行完毕,在网络内建立起一棵或几棵以sink为节点的源路由树,这是由于在较大规模的无线传感器网络中往往配置不止一个sink节点。网络中建树后的拓扑结构图如图3所示。

当收集数据时,数据沿着从叶子节点到sink节点的反向路由树传输,最终到达sink节点,并由sink节点向外传输数据。

第1期王华等:无线传感器网络中数据可靠传输的节能路由算法27　　　　

广播,周围某个RSSI较大且跳数较小的节点成为新的父节点。当数据传到sink节点或者当树中所有的高层节点都死亡的时候,算法终止。

任意n∈C

//C表示一个网络内所有节点的集合,n为节点

while(!receive(message));n.state=active;if(!deadparent(n))

　executesendmessage;else

　executebroadcast;

　if(!find_new_parent)return;　else

//若节点未收集到数据,则处于等待状态

//节点接收到数据//判断父节点是否死亡

//节点发出广播//未找到新的父节点

//找到新的父节点并向其传输数据

　　executesendmessage;

endif

2.2.2　丢包检测

节点对每一个发出去的需确认的数据包都设立一定时器(定时器的时间由用户根据实际情况设定),在定时器时间内,节点若接收到该数据包的ACK,则从本地cache内删除数据包。若时间完毕,仍没有收到ACK,则认为数据包已丢失,进行重传。同时在发送端减小滑动窗口,虽然无线传感器网络的丢包一般是因为位错误(biterror),而不是拥塞,但是在丢包后滑动窗口仍然要减小,以便尽可能降低错误率。在一段稳定时间后,滑动窗口再慢慢恢复。若重传次数过多,例如超过3次,则认为该节点的父节点已经死亡,需要调用可靠路由算法重新发现父节点。在本文中,由于接收端只需要向发送端,也就是它的一个孩子节点发送ACK消息,所以能够有效避免环路问题,不会引起内爆问题;特别的,若节点缓冲区已满,则通知其孩子节点减小滑动窗口,避免孩子节点连续向外发送数据包。丢包检测算法如下:

任意n∈C

//C表示一个网络内所有节点的集合,n为节点

onsendingoutdatapacket;rtr_num=1;//rtr_num表示重传次数while(treduce(windows);//ACK超时,减小滑动窗口retransmitthesamedatapacket;//ACK超时,重传数据包rtr_num++;if(rtr_num>3)//rtr_num>3则表示父节点已经死亡{

executebroadcast;//节点发出广播if(!find_new_parent)return;//未找到新的父节点elseexecutesendmessage;//找到新的父节点并向其传输数据}endif

量是一定的。由于无线通信占据了无线传感器网络功耗的主要部分,因此,在保证网络正常运行的情况下,减少节点向外传输数据包的频率,即可减少无线传感器网络中节点所耗费的能量。下面就该算法如何降低节点传输数据包的次数进行分析。

该算法在建树过程中,利用了最大剩余能量MRE,延长了单个临近死亡节点的寿命。

假设网络中有n个节点,生成源路由树算法过程中,有两层循环,首先须对每个节点进行遍历,其频度为n;其次对每个节点而言,需要对与之邻接的节点进行分析,而最多有(n-1)个节点与该节点连接,因此,生成源路由树算法的时间复杂度为O(n2),在数据沿源路由树传输过程中,数据沿单路径传输,其时间复杂度为O(n),所以算法的总体时间复杂度为2

O(n)。而在无线传感器网络中的路由以洪泛为主,其时间复杂度为O(nn)。

PSFQ算法利用HHR机制传输,当发生丢包时,节点将向周围节点发送广播,引起能量消耗,即使包的丢失率较小,也会造成大量的转发包,消耗过多能量。本文中算法自始至终均为单路径传输,对于不可靠的无线传感器网络而言,有利于节约能量。

RMST协议利用HHR机制传输,由于其需要对sink节点的每个属性信息都需要建立强制路径,建立路径过程需要消耗大量能量,因此该机制在网络的可靠性较低的情况下,会使其效率降低。本文中算法只需建立一条路径即可,在传输信息过程中一般不需再重新建立路径,故节省大量能量。

分析表明,本文提出的算法能够有效降低节点传输数据包的频率,从而降低功耗,有效延长网络寿命。

在数据可靠传输方面,该算法利用了可靠路由算法以保证路由的可靠性,而丢包检测机制则能够迅速发现丢失的数据包,进而利用HHR机制重传,保证数据包能够被传输到sink节点。

4　结语

在综合分析了现有算法的基础上,提出了一种无线传感器网络中数据可靠传输的节能方案。考虑到将要死亡的个别节点,该算法以满足MRE要求的节点为中间节点,从而延长了无线传感器网络的寿命;还提出了可靠的路由方案,保证了数据传输的可靠性。理论分析表明,该算法能够有效提高网络中数据的可靠传输,节约网络功耗,有效延长网络寿命。参考文献:

[1]　孙雨耕,张静,孙永进,等.无线自组传感器网络[M].传感器技

术学报,2004,(2).[2]　STANNF,HEIDEMANNJ.RMST:ReliableDataTransportinSen2

sorNetwork[A].1stIEEEInternationalWorkshoponSensorNet

ProtocolsandApplications(SNPA)[C].Anchorage,Alaska,USA,2003.

[3]　KIMS,FONSECAR,CULLERD.ReliableTransferonWireless

SensorNetworks[EB/OL].http://www.eecs.berkeley.edu/～bi2netude/work/reliable.pdf.

[4]　WANCY,CAMPBELLAT,KRISHNAMURTHYL.PSFQ:ARe2

liableTransportProtocolforWirelessSensorNetworks[A].ProcWS2NA2002[C],2002.

[5]　STOJMENOVICI,NAYAKA,KURUVILAJ.DesignGuidelines

forRoutingProtocolsinAdHocandSensorNetworkswithaRealis2ticPhysicalLayer[J].

(3):101-106.

IEEECommunicationsMagazine,2005,43

接收端:

onreceivingdatapacketif(samepacket)//收到前个数据包的副本,则删除副本deletedatapacket;endif

processincomingpacket;//节点处理收到的数据包if(buffer_size=max_size)//缓冲区已满informitschildstoreducewindows;

3　算法分析

无论以何种算法,每个节点向外传输数据包所耗费的能