基于恢复域的传感器网络路由保障算法研究

文章编号：1007-5321（2005）04-0000-00基于恢复域的传感器网络路由保障算法研究摘要:由于无线传感器网络通常采用多跳路由传输数据，且能量受限，极易在传输过程中因为链路失效而导致传输失败。针对以上问题，采用恢复域模型，对传输路径按区域进行恢复。首先，证明了使用恢复域模型并且最小化传输时延是一个NP完全问题；其次，通过整数线性规划(ILP)计算出网络中恢复域大小的最优值并且将整个网络按照最优值进行划分；最后，当网络中节点或链路发生故障时，在恢复域内采用备用路径进行恢复。实验表明，采用的恢复域模型能够有效降低传输时延，同时只消耗较少的能量，达到了传输时延与能量消耗之间的均衡。关键词:无线传感器网络;路由;恢复域;能量;延迟中图分类号:TP393文献标识码:ARecoveryDomain-BasedGuaranteedRoutingAlgorithminWSNsAbstract:WirelessSensorNetworksusuallytransmitdatausingmulti-hoprouting,it'senergyislimitedaswell,thereforethetransmissionisinterruptedeasilyduetothelinkfailure.Inaccordancewiththeabovequestions,thepaperadoptstherecoverydomainmodel,whichdividestransmissionpathintoseveralregionstoberecovered.ThepaperprovesthatusingrecoverydomainmodelwhileminimizingthetransmissiondelayisanNP-completeprobleminthefirstinstance.ThencalculatetheoptimalvalueoftherecoverydomaininthenetworkwithIntegerLinearProgramming(ILP).Inaddition,thepaperdividethenetworkintoseveralrecoverydomainsbasedonthecalculatedoptimalvalue.Finally,thebackuppathintherecoverydomainwhichtorecoverthefaultynodesorlinksinthenetworkisadopted.Simulationresultsshowthattheemployedrecoverydomainmodelcaneffectivelyreducethetransmissiondelaywhileonlyconsuminglittleenergy,whichmakesagoodbalancebetweenenergyconsumptionandtransmissiondelay.Keywords:WirelessSensorNetworks;routing;recoverydomain;energy;delay在有线网络中，针对某条主路径，可以找到一条固定的备用路径，当主路径发生拥塞时，采用备用路径进行传输。但是在无线传感器网络中，由于拓扑的动态性，导致无法为主路径找到一条固定的备用路径。需要根据网络实时变化，在传输链路或节点失效的情况下，动态的找到一条新的备用路径，对传输失败路径进行路由恢复。本文采用的恢复域模型能够根据网络当前状态，对备用路径进行定时更新。恢复域的选取是根据在主路径上给定恢复参考节点，两个或多个恢复参考节点之间构成的区域称为恢复域[2]，恢复域能够对其范围内的传输提供保护。如图1所示，对于某条主路径，给定节点1、2、3、4作为4个恢复参考节点，构成3个恢复域，图中实线表示主路径，虚线表示备用路径，当节点2、3之间的主路径发生故障后，在恢复域2内进行恢复，采用备用路径继续进行传输。需要注意的是节点2、3并没有在恢复域中，所以这些节点称为恢复域覆盖盲点。图1给出的恢复域均由两个相邻参考节点构成，称之为标准恢复域。由多个参考节点构成的恢复域称为嵌套恢复域。如图2所示，恢复域1和恢复域2嵌套于恢复域3中。通过恢复域嵌套的方法可以有效解决恢复域覆盖盲点的问题，图2中节点2对于恢复域1和恢复域2来说是覆盖盲点，但是由于恢复域嵌套，可以被恢复域3保护。收稿日期:2014-07-21基金项目：作者简介:图1采用恢复域的多跳传输图2嵌套恢复域对于路由恢复问题，选定合适的恢复域大小至关重要。当恢复域范围设定较小时（例如为1），需要对主路径上的每一条链路都找到一条备用路径，这样需要较大的能量消耗，但是在某条链路失败时，所用恢复时间较短；当恢复域范围设定较大时（假设为主路径长度）相当于为主路径找到一条备用路径，此时能量消耗较小，但恢复时间较长。通过以上分析，本文需要为恢复域找到一个合适的范围，使得能量消耗与传输时延达到均衡。基于上述恢复域模型，本文首先证明在最小化时延的前提下使用恢复域模型是一个NP完全问题；其次通过整数线性规划(ILP)求出恢复域大小的最优值；之后给出了在划分好的区域中对传输失败链路进行恢复的策略；最后通过实验验证了本文所采用的恢复域模型能够有效降低传输时延，同时减少能量消耗。1相关工作与传统网络相比，在无线传感器网络中，节点能量受限，通信质量容易受到外界干扰，网络经常会发生断接，导致通信中断。尤其在多跳网络中，传输失败概率随着跳数成指数级别增长。因此如何在使用较少能量的前提下为传输路径提供可靠路由保障是传感器网络研究所面临的重要研究问题。LePH等人主要研究了MANET上的多路径路由问题，基于最优链路状态的路由协议(OLSR)，提出了一种节点不相交、冲突自知的多路径路由算法IA-MPOLSR[3]。P.Pan等人通过利用多协议标签交换(MPLS)的优点，提出了快速重新路由(FRR)算法，FRR是一种局部恢复策略，当传输路径上某个节点失效后，从失效节点的上一个节点重新路由到传输路径上的一个汇合节点[4]。Zhang等人针对无线AdHoc网络提出了一种基于迭代的多路径路由协议IMPR[5]，该方法可以有效提高可靠性，增加网络带宽同时平衡网络负载。Xiao等人提出了一种针对延迟容忍网络的机会路由算法[6]，当网络中缺少端到端直接数据传输链路的情况下，传输优先级最高的候选组节点。Li等人针对无线传感器网络存在的数据丢失现象，提出了一种基于桥链的多路径可靠路由协议MPRR[7]，通过建立路径之间转移关系，使得数据可以通过桥链从一条失效路径转移到另一条有效路径。为了解决冲突网络中的路由问题，Wu等人在延迟容忍网络中提出了一种基于社交特性的多路径路由策略[8]，通过抽取不同社交特性构建超立方体，并且在超立方体中按照维序寻径的方法找到多条点不相交路径进行数据传输。GanesanD等人针对网络中不存在足够数量的不相交路径或者寻找不相交路径复杂性过高的情况提出缠绕多路径路由协议[9]，在建立主路径后在主路径的附近寻找备用路径，具有较强的路径备份能力。KupermanG等人针对多跳无线网络提出了一种无线可靠保护(WGP)策略[10]，通过利用网络中存在的冲突，使用点不相交路径对网络进行保障，有效提高了网络吞吐量。上述对无线网络提供路由保障的算法中，一部分采用全局恢复策略，另一部分虽然采用局部恢复，但需要对故障节点的上一跳节点进行重新路由，越过故障节点，继续进行传输，这种方式能量消耗较大。本文采用一种局部预恢复策略，当传输路径出现故障时，采用局部备用路径直接进行路由恢复，减少传输时延，同时降低能量消耗。2系统模型及问题定义2.1系统模型在无线传感器网络中，假定节点均匀分布在一个二维平面区域，可以将整个网络定义为一个有向图G=(V,E)，其中V={v|v表示网络中的节点}，E={l|l=(u,v)，l是节点u与节点v之间的一条链路，u,vV}。给定源节点s和目的节点t，可以找到一条最优传输路径P={s,i,j,...,k,t}作为主路径。对于主路径P，求出最优恢复域范围后，可以推导出恢复参考节点集合R={s,a,...,b,t}，通过R进行恢复域划分。在每一个恢复域内都找到一条与主路径点不相交的备用路径，通过备用路径进行数据恢复。路径花费主要是指传输时延，包括数据传输时间，故障检测时间和信道切换时间，信道切换时间在本文中可忽略不计，可以使用故障检测时间和数据传输时间之和来估算总传输时延。不失一般性，本文采用恢复域内最长恢复时间来表示该恢复域所用恢复时间。本文采用单链路失败模型，即在传输过程中，路径P上只可能有一条链路发生传输失败。对于多链路失败模型，可以通过多次使用恢复域模型予以解决。2.2问题定义在链路传输失败的情况下，需要有可靠的路由恢复机制来保障数据传输。针对以上问题，本文采用恢复域模型，用局部恢复代替全局恢复，目的在于减少路由恢复时间，同时减少节点能量消耗。定义1.采用恢复域模型的路由保障(RoutingProtectionusingRecoveryDomain，RPRD)：在数据传输不可靠的网络中，任意两个节点s与t使用路径P进行通信，对于P中传输失败链路采用恢复域模型进行局部路由恢复，保障网络中数据传输的可靠性，同时使得网络中的传输时延T能够最小化。RPRD问题是一个NP完全问题，不存在多项式时间算法。为了证明RPRD问题是NP完全的，首先给出两个引理。引理1.网络传输时延T是与恢复域大小srd成正比。证明：首先，对于网络时延T，给出公式(1)。(1)其中Tn表示数据正常传输所用时间，Tf表示传输数据恢复时间(包括故障检测时间Td和数据重传时间Tr)，γ表示网络中数据成功传输的概率。其次，在单链路失败的约束条件下，对于当前失败链路所在恢复域，可以求出恢复时间Tf，Tf与恢复域大小显然成正比(传输时间与跳数成正比)。因此，对于一条给定路径P，Tn已知，在γ确定的情况下，T只与Tf有关系，故网络传输时延T是与恢复域大小srd相关的一个函数，且T与srd成正比。特别需要注意的是，当srd=|P|时，恢复域退化为全网，也就在节点s和t之间找出两条点不相交路径，这是采用恢复域条件下的最坏情况。■引理2.一个包含n个恢复域的网络中，设每个恢复域内的恢复时间为Tfi(i=0,1,...,n)，当每个Tfi取最小值的情况下，整个网络的延时T达到最小化。证明：首先，根据公式(1)，对于一条给定路径P，Tn已知，在γ确定的情况下，T只与Tf有关系，所以需要最小化Tf来满足目标函数。其次，对于每个恢复域，给出一个恢复时间Tfi，通过公式(2)求出Tf的期望值。()∑(2)将公式(1)中Tf用公式(2)中的E(Tf)表示，可以得到公式(3)。∑(3)通过公式(3)可以发现，Tfi与T成正比。因此，为了最小化T，需要最小化每一个恢复域内的恢复时间Tfi。■定理1.RPRD问题是一个NP完全问题。证明：首先，需要证明RPRD∈NP。对于RPRD问题，根据引理1可知，传输时延T是与恢复域大小srd相关的一个函数，所以对于该问题的一个实例T(srd)，本文构造一个不确定算法，该算法第一阶段猜测srd∈Hrd，其中Hrd是恢复域可能大小的一个集合，且|Hrd|=m。第二阶段检测T(srd)是否满足最小时延的条件。这个阶段的时间复杂度是多项式的，所以RPRD问题可由多项式时间不确定算法解决。因此，RPRD∈NP。其次，将一个已知的NP完全问题规约到RPRD问题。本文采用n附加指标问题(thenadditivemetricsproblem)[11]来进行规约。在n附加指标问题中，目标是发现一条简单路径P使其满足给定的n个约束条件。而在RPRD问题中，目标是在每个恢复域内找到一条备用路径，使得在网络发生故障的情况下，能够最小化传输时延T。根据引理2，为了最小化T，需要最小化每一个恢复域内的恢复时间Tfi。对于I=