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

文章编号：1007-5321（2005）04-0000-00基于恢复域的传感器网络路由保障算法研究摘要: 由于无线传感器网络通常采用多跳路由传输数据，且能量受限，极易在传输过程中因为链路失效而导致传输失败。针对以上问题，采用恢复域模型，对传输路径按区域进行恢复。首先，证明了使用恢复域模型并且最小化传输时延是一个NP完全问题；其次，通过整数线性规划(ILP)计算出网络中恢复域大小的最优值并且将整个网络按照最优值进行划分；最后，当网络中节点或链路发生故障时，在恢复域内采用备用路径进行恢复。实验表明，采用的恢复域模型能够有效降低传输时延，同时只消耗较少的能量，达到了传输时延与能量消耗之间的均衡。关 键 词: 无线传感器网络; 路由; 恢复域; 能量; 延迟中图分类号: TP393文献标识码: ARecovery Domain-Based Guaranteed Routing Algorithm in WSNsAbstract: Wireless Sensor Networks usually transmit data using multi-hop routing, its energy is limited as well, therefore the transmission is interrupted easily due to the link failure. In accordance with the above questions, the paper adopts the recovery domain model, which divides transmission path into several regions to be recovered. The paper proves that using recovery domain model while minimizing the transmission delay is an NP-complete problem in the first instance. Then calculate the optimal value of the recovery domain in the network with Integer Linear Programming (ILP). In addition, the paper divide the network into several recovery domains based on the calculated optimal value. Finally, the backup path in the recovery domain which to recover the faulty nodes or links in the network is adopted. Simulation results show that the employed recovery domain model can effectively reduce the transmission delay while only consuming little energy, which makes a good balance between energy consumption and transmission delay.Key words: Wireless Sensor Networks; routing; recovery domain; energy; delay在有线网络中，针对某条主路径，可以找到一条固定的备用路径，当主路径发生拥塞时，采用备用路径进行传输。但是在无线传感器网络中，由于拓扑的动态性，导致无法为主路径找到一条固定的备用路径。需要根据网络实时变化，在传输链路或节点失效的情况下，动态的找到一条新的备用路径，对传输失败路径进行路由恢复。收稿日期: 2014-07-21基金项目： 作者简介: 本文采用的恢复域模型能够根据网络当前状态，对备用路径进行定时更新。恢复域的选取是根据在主路径上给定恢复参考节点，两个或多个恢复参考节点之间构成的区域称为恢复域2，恢复域能够对其范围内的传输提供保护。如图1所示，对于某条主路径，给定节点1、2、3、4作为4个恢复参考节点，构成3个恢复域，图中实线表示主路径，虚线表示备用路径，当节点2、3之间的主路径发生故障后，在恢复域2内进行恢复，采用备用路径继续进行传输。需要注意的是节点2、3并没有在恢复域中，所以这些节点称为恢复域覆盖盲点。图1给出的恢复域均由两个相邻参考节点构成，称之为标准恢复域。由多个参考节点构成的恢复域称为嵌套恢复域。如图2所示，恢复域1和恢复域2嵌套于恢复域3中。通过恢复域嵌套的方法可以有效解决恢复域覆盖盲点的问题，图2中节点2对于恢复域1和恢复域2来说是覆盖盲点，但是由于恢复域嵌套，可以被恢复域3保护。图1 采用恢复域的多跳传输图2 嵌套恢复域对于路由恢复问题，选定合适的恢复域大小至关重要。当恢复域范围设定较小时（例如为1），需要对主路径上的每一条链路都找到一条备用路径，这样需要较大的能量消耗，但是在某条链路失败时，所用恢复时间较短；当恢复域范围设定较大时（假设为主路径长度）相当于为主路径找到一条备用路径，此时能量消耗较小，但恢复时间较长。通过以上分析，本文需要为恢复域找到一个合适的范围，使得能量消耗与传输时延达到均衡。基于上述恢复域模型，本文首先证明在最小化时延的前提下使用恢复域模型是一个NP完全问题；其次通过整数线性规划(ILP)求出恢复域大小的最优值；之后给出了在划分好的区域中对传输失败链路进行恢复的策略；最后通过实验验证了本文所采用的恢复域模型能够有效降低传输时延，同时减少能量消耗。1 相关工作与传统网络相比，在无线传感器网络中，节点能量受限，通信质量容易受到外界干扰，网络经常会发生断接，导致通信中断。尤其在多跳网络中，传输失败概率随着跳数成指数级别增长。因此如何在使用较少能量的前提下为传输路径提供可靠路由保障是传感器网络研究所面临的重要研究问题。Le P H等人主要研究了MANET上的多路径路由问题，基于最优链路状态的路由协议(OLSR)，提出了一种节点不相交、冲突自知的多路径路由算法IA-MPOLSR3。P.Pan等人通过利用多协议标签交换(MPLS)的优点，提出了快速重新路由(FRR)算法，FRR是一种局部恢复策略，当传输路径上某个节点失效后，从失效节点的上一个节点重新路由到传输路径上的一个汇合节点4。Zhang等人针对无线Ad Hoc网络提出了一种基于迭代的多路径路由协议IMPR5，该方法可以有效提高可靠性，增加网络带宽同时平衡网络负载。Xiao等人提出了一种针对延迟容忍网络的机会路由算法6，当网络中缺少端到端直接数据传输链路的情况下，传输优先级最高的候选组节点。Li等人针对无线传感器网络存在的数据丢失现象，提出了一种基于桥链的多路径可靠路由协议MPRR7，通过建立路径之间转移关系，使得数据可以通过桥链从一条失效路径转移到另一条有效路径。为了解决冲突网络中的路由问题，Wu等人在延迟容忍网络中提出了一种基于社交特性的多路径路由策略8，通过抽取不同社交特性构建超立方体，并且在超立方体中按照维序寻径的方法找到多条点不相交路径进行数据传输。Ganesan D等人针对网络中不存在足够数量的不相交路径或者寻找不相交路径复杂性过高的情况提出缠绕多路径路由协议9，在建立主路径后在主路径的附近寻找备用路径，具有较强的路径备份能力。Kuperman G等人针对多跳无线网络提出了一种无线可靠保护(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. 采用恢复域模型的路由保障(Routing Protection using Recovery Domain，RPRD)：在数据传输不可靠的网络中，任意两个节点s与t使用路径P进行通信，对于P中传输失败链路采用恢复域模型进行局部路由恢复，保障网络中数据传输的可靠性，同时使得网络中的传输时延T能够最小化。RPRD问题是一个NP完全问题，不存在多项式时间算法。为了证明RPRD问题是NP完全的，首先给出两个引理。引理1. 网络传输时延T是与恢复域大小srd成正比。证明：首先，对于网络时延T，给出公式(1)。T=Tn+(1-)Tf (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的期望值。ETf=i=1nTfin(2)将公式(1)中Tf用公式(2)中的E(Tf)表示，可以得到公式(3)。T=Tn+1-i=1nTfin(3)通过公式(3)可以发现，Tfi与T成正比。因此，为了最小化T，需要最小化每一个恢复域内的恢复时间Tfi。定理1. RPRD问题是一个NP完全问题。证明：首先，需要证明RPRDNP。对于RPRD问题，根据引理1可知，传输时延T是与恢复域大小srd相关的一个函数，所以对于该问题的一个实例T(srd)，本文构造一个不确定算法，该算法第一阶段猜测srdHrd，其中Hrd是恢复域可能大小的一个集合，且|Hrd| = m。第二阶段检测T(srd)是否满足最小时延的条件。这个阶段的时间复杂度是多项式的，所以RPRD问题可由多项式时间不确定算法解决。因此，RPRDNP。其次，将一个已知的NP完全问题规约到RPRD问题。本文采用n附加指标问题(the n additive metrics problem)11来进行规约。在n附加指标问题中，目标是发现一条简单路径P使其满足给定的n个约束条件。而在RPRD问题中，目标是在每个恢复域内找到一条备用路径，使得在网络发生故障的情况下，能够最小化传输时延T。根据引理2，为了最小化T，需要最小化每一个恢复域内的恢复时间Tfi。对于I = 1, 2, ., n，令每个恢复域内的最短恢复时间为Mi， minTr=i=1nMin，当满足约束条件Tfi Mi时，T达到最小化。对于一条主路径P，将其划分为n个恢复域，同时给定n个约束条件，在n个约束条件同时满足的情况下，就达到了最小化网络传输时延的目的。至此，已经将n附加指标问题多项式规约成为RPRD问题。因此，RPRD是一个NP完全问题。定理1得证。3 基于线性规划的恢复域划分策略本文主要研究的问题是采用恢复域模型进行路由保障，并且最小化传输时延T，由定理1可知该问题是一个NP完全问题。根据引理1分析，网络传输时延T是与恢复域大小srd成正比，但当srd取最小值时，可能无法在恢复域内找到备用路径。解决这一问题的关键在于找到一个合适的恢复域范围，下面利用整数线性规划方程求出恢复域取值的最优解。3.1 整数线性规划给定源节点s和目的节点t，s有若干个数据包要发送给t。假设网络中已经找到一条默认花费最小的主路径P，现在需要确定恢复域大小的最优值srd，在保障路由可靠性的情况下，最小化传输时延T。最后通过srd求出恢复参考节点，对主路径P进行恢复域划分。一个端到端最小化传输延迟的整数线性规划(ILP)方程如下：min T(1)s. t.Fin(s)=Fout(t)=0; (2)Finm=Foutm,mV, ms, mt; (3)Fout(s)=Fin(d); (4)Tf = dp/rp+3srd(1/rp); (5)srd|P|;(6)Pn(srd)2; (7)Tn0, Tf0;(8)在上述线性规划方程中，目标函数(1)是最小化源节点到目的节点传输时延。方程(2)表示源节点接收的数据包与目的节点发送的数据包数量均为0。方程(3)表明对于网络中除源节点与目的节点外任意中间节点m满足流守恒约束，即m接收的数据包数等于发送的数据包数。方程(4)是对源节点和目的节点的数据流守恒约束，即源节点发送的数据包数等于目的节点接收的数据包数。方程(5)给出了数据恢复时间Tf与恢复域范围srd之间的关系，其中dp为需要传输的数据包数，rp为传输速率，使用srd + 2作为恢复域内备用路径长度的估计值。故障检Td=1/rp，数据回退到源节点需要2srd-2(1/rp)，采用流水线的方式进行数据传送，从到目的节点需要 dp/rp+srd+1(1/rp)， Tr=dp/rp+3srd-1(1/rp)，根据公式(1)，Tf =dp/rp+3srd(1/rp)。方程(6)表示恢复域范围srd的最大值不能超过主路径长度|P|。方程(7)给出了恢复域内备用路径数量关于恢复域范围的函数Pn(srd)，由于在网络中，给定两个恢复参考节点，它们之间距离越长，恢复域范围就越大。恢复域范围与内部存在节点数量成正比，节点数量变多，潜在路径数量也会增加，故恢复域内路径数量随着恢复域范围变大而增加，同时限定了恢复域内路径数量要大于等于2条(1条主路径和1条备用路径)。方程(8)是对正常传输时间Tn与传输恢复时间Tf的非负约束。定理2. 给定恢复域范围，求两个恢复参考节点a、b之间所有路径数量(#PRD)是一个#P完全问题。证明：首先，判定a、b之间是否存在路径(PRD)是一个NP问题，可以使用一个不确定图灵机(NTM)对网络进行遍历，采用搜索树在多项式时间内能够完成判定。故PRDNP。其次，需要证明#PRD#P。构造两带NTM M如下求解PRD问题：1. 第一条带为输入F，保存恢复域内链路信息；2. 扫描F，识别F中的每条链路；3. 在第二条带上不确定的猜测每个赋值C(0, 1)|F|。对于链路l，Cl = 1表示取该链路，反之不取；4. 判断链路集合C是否能构成a、b之间的一条路径，可以的话则进入接受状态。用(C)来表示满足条件的路径数量，显然，(C) = a、b之间路径个数 = #PRD。由于M是多项式时间NTM，#PRD#P。最后，用已知的#P完全问题(#HC问题)在多项式时间规约到#PRD。假设恢复域内有n个节点，主路径节点集合Pab，最短备用路径需要经过srd + 3个节点。由恢复域内主路径和备用路径可以构成一条关于节点a(b)的哈密顿回路，如图3所示，实线表示主路径，虚线为备用路径。令#HC(I)表示当网络节点集合为I时，哈密顿路径的个数。使用公式(4)将#PRD问题划分为一系列子问题，通过在网络中删除节点，求出各个子网中满足条件的哈密顿路径个数，其中Nk表示由k个节点构成的子网(不包含P中节点)。最后通过公式(5)相加得出#PRD问题的解。I = Nk + Pab；(4)#PRD = k=Srd+1n-|P|#HC(I)；(5)至此，已经将#HC问题多项式规约为#PRD问题，所以#PRD是一个#P完全问题，定理2得证。图3 恢复域内一条哈密顿回路3.2 恢复域路径数量计算#PRD问题是一个#P完全问题，不存在多项式时间确定算法，除非P = NP，下面本文提出恢复域路径发现算法(PRD)，如算法1所示。当网络节点个数较少时，可以利用状态压缩动态规划方法(CSDP)来解决，时间复杂度为O(2n)。但是当网络节点个数超过阀值Vt，该方法失效，此时采用多项式近似算法APRD。算法1：恢复域路径发现算法(PRD)：输入：网络G = (V, E)，恢复域大小srd，路径存在权值()，阀值Vt，路径数量矩阵A输出：Pn(srd)1) if V Vt2) return CSDP(G, srd)()；3) else4) return APRD(G, srd)()；在APRD算法中，通过将普通网络转化为网格状网络，限制走向，求得路径数量近似值，如算法2所示。算法2：恢复域路径发现近似算法（APRD）：输入：网络G = (V, E)，恢复域大小srd，路径数量矩阵A输出：Asrd, srd1) for i = 0.srd2) A0, i = 1, Ai, 0 = 13) for i=1.srd4) for j=1.srd5) Ai, j = Ai-1, j + Ai, j-1；6) return Asrd, srd；3.3 恢复域范围srd与网络密度、传输成功率之间的关系表1 srd与、之间的关系 0.20.40.60.810.31974210.61974211|P|P|P|P|P|通过选取不同的、值带入ILP方程中求解，在传输延时最小时，得到最优的srd值，如表1所示。从表中观察可以发现在网络中所有数据包均能正确传输( = 1)的情况下，srd为主路径长度|P|；当网络存在丢包情况时，srd与无关，与成反比。4 恢复域构建与保障算法在给出了具体的恢复域模型定义与计算方法后，本节提出两个关于恢复域的内部算法：恢复域构建算法(BRD)与恢复域保障算法(RDP)，并对其时间复杂度进行分析。4.1 恢复域构建在网络G中给定源节点s与目的节点t，使用Dijkstra算法计算出一条主路径p，其中边权值为节点之间时延、拥塞度与传输可靠性的加权平均值。通过求解上一节提出的ILP方程组，计算出合适的srd并将网络划分恢复域。利用Suurballe算法12的变形求出恢复域内一条与主路径点不相交的备用路径，如果在恢复域内无法找到备用路径，则增大部分节点传输功率，采用多功率方式。具体算法伪代码如下：算法3：恢复域构建算法(BRD)：输入：网络G = (V, E)，源节点s，目的节点t，网络密度，传输成功率输出：恢复域RD1. RDn及备用路径pb1.pbn1) 主路径p = Dijkstra(s, t, G)；2) srd = ILP(G, , )；3) 根据求出的srd值划分恢复域；4) for i = 1.p/srd5) 删除恢复域内主路径上所有节点(恢复参考节点a、b除外)；6) RDi内备用路径pbi = Dijkstra(a, b, RDi)；上述算法中，语句1时间复杂度为O(|V|2)，语句2时间复杂度为O(|E|V|2)，语句3时间复杂度为O(|V|)，语句4-6循环的迭代次数最多为O(|V|)，循环体内语句5需要的时间为O(|V|)，语句6需要的时间为O(|V|2)，所以BRD算法所需时间复杂度为O(min(|E|V|2)，(|V|3)。4.2 恢复域保障在传输过程中，如果主路径p上出现故障节点，首先判断该节点是否为划分参考节点，如果是则采用恢复域嵌套特性进行解决，反之采用该节点所在恢复域备用路径进行恢复。具体算法伪代码如下：算法4：恢复域保障算法(RDP)：输入：主路径节点集合P，恢复域覆盖盲点集合Nd，恢复域数量x，故障节点n输出：备用路径pb1) 主路径中间节点集合Nm = P - Nd；2) if nNm3) 找到节点n所在的恢复域RDi；4) 采用备用路径pbi进行恢复；5) else if nNd6) 合并节点n两侧恢复域，建立一个新恢复域RDx+1；7) 更新恢复域内备用路径pbx+1，采用pbx+1进行恢复；8) x = x + 1；上述算法中，语句1时间复杂度为O(1)，语句2-4时间复杂度为O(|V|)，语句5-8时间复杂度为O(|V|2)，所以RDP算法所需时间复杂度为O(|V|2)。5 实验结果与分析为了评估本文提出的RDP(Recovery Domain Protection)算法的性能，本文进行了模拟实验，并与GRP(Global Routing Protection)、FRR(Fast ReRoute)和WGP(Wireless Guaranteed Protection)进行比较。其中GRP是一种在全局范围内寻找备用路径的经典算法。算法采用C+语言编写，所有实验均在2.93GHz，8G内存，64位操作系统的计算机上完成。本文实验选取不同的网络规模、通信半径与传输包数，通过多次运行仿真程序，在平均能量消耗与平均传输时延方面比较RDP、FRR、WGP和GRP这四种算法的结果并进行相应分析。其中，模拟实验参数默认值如表2所示。表2 实验参数默认值实验参数默认值网络覆盖范围50m50m节点数量1500通信范围1m成功传输率80%数据包大小32Kb通信带宽10Kbps5.1 网络规模变化本组实验主要分析网络规模对传输延迟和能量消耗的影响。网络覆盖范围表示当前网络的有效传输范围，假设网络中节点均匀分布。随着网络规模的增大，可以发现GRP、FRR、WGP和RDP四种算法的传输延迟与能量消耗均有所增加，如图4(a)、图4(b)所示。这是因为网络规模变大会导致传输路径变长，同时链路服务质量也会有所下降。其中，GRP算法传输时延增长最快，FRR算法由于重新路由带来很高的开销，所以能量消耗最大，RDP算法与WGP算法在平均传输时延上基本相同，但RDP算法比WGP算法更加节约能量。图4(a) 网络规模对平均传输时延的影响图4(b) 网络规模对平均能量消耗的影响5.2 通信半径变化在本组实验中，主要考察通信半径与传输延迟、能量消耗之间的关系。通过观察图5(a)与图5(b)可以发现，随着通信半径的增加，GRP、FRR、WGP和RDP四种算法的传输延迟呈下降趋势，而且趋于稳定，但是能量消耗则随着通信半径的增加而增大。这是因为随着通信半径的增大，源节点到目的节点可选路径增多，传输跳数变少，传输时延也相应减少；而通信半径与传输功率成正比，在功率增大的情况下，能量消耗随之提升。其中，WGP算法与RDP算法相比在传输时延上略有优势，但是在能量消耗方面，RDP算法明显低于WGP算法。5.3 传输包数变化本组实验主要通过改变传输包的数量，观察传输延迟与能量消耗的变化。如图6(a)、图6(b)所示，随着传输包数的增加，GRP、FRR、WGP和RDP四种算法传输时延与能量消耗均呈上升趋势。其中，算法GRP所需传输时延最长，算法FRR的能量消耗比较接近算法GRP。WGP与RDP算法在传输时延上基本相同，RDP算法的能耗略微少于WGP算法，而且二者的能量消耗随着传输包数的增加逐渐接近。这是因为WGP算法在构造时比RDP算法消耗更多能量，但是随着传输包数的增加，这种差别变得越来越小。图5(a) 通信半径对平均传输时延的影响图5(b) 通信半径对平均能量消耗的影响图6(a) 传输包数对平均传输时延的影响图6(b) 传输包数对平均能量消耗的影响6 结论在无线传感器网络中，针对节点能量受限，多跳传输可靠性差，本文采用恢复域模型为网络传输提供可靠路由保障。本文首先证明了选取合适的恢复域范围使得传输时延最小是一个NP完全问题。其次采用整数线性规划方法求出恢复域范围的最优值，并且提出两个恢复域相关算法：BRD与RDP，利用恢复域特性有效保障数据传输。模拟实验结果表明，本文提出的算法与其他算法相比能耗较少，同时能够有效降低传输时延，达到了传输时延与能量消耗之间的均衡。参考文献:1 孙利民, 李建中, 陈渝, 等. 无线传感器网络M.第一版.清华大学出版社,2005,3-23.Sun Limin, Li Jianzhong, Chen Yu, et al. Wireless Sensor NetworksM. First edition. Tsinghua University Press, 2005, 3-23. 2 N. Sprecher and A. Farrel, MPLS-TP Survivability Framework, IETFRFC 6372, Tech. Rep., 2011.3 Le P H, Pujolle G. An interference-aware multi-path routing protocol for mobile ad hoc networkC/Networking, Sensing and Control (ICNSC), 2011 IEEE International Conference on. IEEE, 2011: 503-507.4 Pan P, Swallow G, Atlas A. Fast reroute extensions to RSVP-TE for LSP tunnelsJ. 2005.5 Xiao M, Wu J, Liu C, et al. Tour: Time-sensitive opportunistic utility-based routing in delay tolerant networksC/INFOCOM, 2013 Pro