无线传感器网络中基于节点连通性的机会路由

杨桂松,梁听听,何杏宇

1(上海理工大学 光电信息与计算机工程学院,上海 200093)2(上海理工大学 公共实验中心,上海 200093)

1 引 言

无线传感器网络(Wireless Sensor Networks,WSNs)是由随机部署在监测区域并通过无线网络连接的大量传感器节点组成,因其低功耗、低成本、分布式和自组织的特点使得其在军事、环境、医疗与空间探索等领域得到了广泛的应用[1].

在无线传感器网络通信中,路由算法不仅决定着数据传输的路径,同时也影响着网络性能[2].然而,传感器节点通信能力、能量受限和应用环境不稳定等因素的存在,使得实际网络中的通信链路不可靠,因此经常出现节点故障导致网络不可达和链路不可靠导致数据丢失等问题[3,4].例如,文献[5]对无线链路时延和可靠性的模糊性、随机性以及时变性进行统一建模,来反映真实的链路状态.文献[6]提出了一种基于全局和局部可靠性的无线传感器网络路由协议,该协议中,通过定义节点的中介度和依赖度来分别反映节点的全局可靠性和局部可靠性,其中节点依赖度的定义与相邻节点之间的链路质量有关,在考虑节点的全局可靠性与局部可靠性的同时,保证了数据传输的网络可靠性.

而机会路由也是无线传感器网络中数据传输可靠性的一种常用的方法,它是由Biswas S和Morris R首次提出的[7],其主要思想是在源节点向目的节点发送数据包的过程中选择一系列候选转发节点集,并且为其中的每个节点分配优先级.源节点首先将数据包发送给第一跳候选转发节点集,在转发节点集中收到数据包且具有最有优先级的节点将转发到下一跳候选转发集,如果数据包已由较高优先级的节点转发,则较低优先级的节点将丢弃该数据包,按此重复,直到目的节点收到数据包.

目前已有大量的文献对机会路由进行了研究,比如文献[8]提出机会路由通过充分利用无线信道的广播特性,通过多个潜在中继竞争、自主智能判断进行下一跳选择,进而提高吞吐量和传输可靠性.文献[9]利用机会路由算法,中间节点协作以完成分组转发,提高了传输可靠性和网络吞吐量.文献[10]提出了一种基于多跳最优位置的机会路由算法,源节点将选择目标节点附近的邻居作为候选转发集,并选择其间最短距离和最小跳数的路径.文献[11]提出节能机会路由,通过组合节点到汇聚节点的距离及其自身的剩余能量,在一维队列的网络模型中找到最优的中继节点位置.

文献[12]结合机会路由和网络编码各自的优势,不仅在网络中同时传输多个段的数据包,而且提高了网络吞吐量.文献[13]提出一种感知服务质量的机会路由协议来选择转发集并对其排序,通过实验验证该协议在能量效率、延迟和时间复杂度方面都适合于无线传感器网络.文献[14]基于能耗最优传输距离和节点剩余能量,构建了联合优化目标函数,并根据数据包的时间敏感性相应调整发射功率.在文献[15]中,作者提出了一种基于连通性的节能机会鲁棒路由协议,该协议中,在计算数据转发的预期成本时,它强调高度的网络连接,以确保网络的正常运行.文献[16]针对网络中节点忙或失效造成的数据丢失,设计了一种基于多路径的可靠路由协议,将失效路径上正在转发的数据转移到另一条有效的路径,以保证数据传输可靠性.文献[17]针对传统的基于地理位置的重传代价大,节点能耗高等挑战,提出了一种基于传输方向的机会路由算法,即一种新的候选集选择算法来有效减小机会路由中候选转发集的大小,进而减少网络中的通信开销.

与上述相关工作相比,本文强调节点在数据传输中的相邻节点之间连通性的重要性,旨在选择具有较大节点依赖指数的节点作为中继以保证网络可靠性.而大多数相关工作,例如文献[10]和文献[17],在做出路由决策时没有考虑网络中节点的连通性.另外,在本文的路由算法设计中,在选择下一跳节点时,本文不仅考虑了候选转发集中每个节点的节点依赖指数对网络可靠性的影响,而且考虑了每个节点在作为候选中继时对整体网络可靠性的贡献大小,最终选定了最优中继以保证网络可靠性.

在本文提出的基于节点连通性的机会路由算法中,首先,根据节点间的依赖程度定义了节点依赖指数来量化传输数据过程中节点的重要性[18],建立了网络模型;然后,定义了节点连通性的计算公式,并找到节点的候选转发集使其能满足网络可靠性的要求;最后,通过仿真实验的性能分析可知,数据传输可靠性机会路由使其既能满足目标可靠性又能降低网络能耗.

本文的其余部分如下:第2小节描述了使用的网络模型,第3小节给出了详细的路由算法的设计思想,所提方案的性能分析在第4小节展示,第5小节总结了本文的工作.

2 网络模型

本文的目标是利用机会路由的思想在无线传感器网络中设计可靠的机会路由算法,找到合适的候选转发集并设定候选转发集节点的优先级别.

源节点S把数据包以广播方式发送后,可能有多个邻居节点接收到数据包,只是因为节点间链路不可靠的因素导致了各节点间节点连通性的差异.为了计算任意两点间的节点连通性,我们定义了节点依赖指数(Dependency Index,DI),以找出无线传感器网络中节点i与其邻居j之间连通率P的关系.节点DI表示节点和其邻居之间的依赖关系,以量化每个节点在转发包的过程中对传递过程的重要性.当其他节点较多地依赖于该节点接收数据包时,此节点的重要性增加.

节点i与其邻居j之间的依赖程度在其相应的节点连通性的影响下,与它们之间交换包的数量有关,则DIij的计算公式如下:

(1)

其中,Reci表示i拥有的所有数据包,Sendi表示i发送出去的数据包,SendS表示S发送出去的数据包,Recj表示j拥有的所有数据包.

基于上述定义,当邻居j接收到节点i发出的所有数据包,并且j没有接收到i未发送的数据包时,可以看出i和j之间有较高的依赖性.公式(1)的基本原理是,如果发送者对邻居具有更高的依赖性,则表明发送者的其他邻居不能以更高的概率转发来自它的数据包.

针对节点i和其邻居j之间的依赖指数DI的基本性质及三种可能情况,我们定义了其与网络中节点连通性Pij相对应关系的三条规则,即网络中所有节点及其邻居均满足以下三条规则:

规则1:若DIij=0,i和j之间的节点连通性Pij=0;

规则2:若DIij=1,i和j之间的节点连通性Pij=1;

规则3:若0

Pij=αP0·DIij+(1-α)P0

(2)

其中α是权重系数.

根据以上规则,无线传感器网络的拓扑结构可以表示为基于节点依赖指数的加权图,假设节点间两两通信且相互独立,节点间依赖指数遵循其与节点连通性的三条规则.

3 路由算法

通过以上网络模型的建立及其相关定义,我们可以计算出模型中任意两点间的节点连通性,之后利用其性质,进行节点候选转发集的选择以及优先级排序.

源节点S有数据包要发送到目的节点D,假设i为当前节点,记录其所有邻居jx及位置信息.首先将邻居根据自身与目的节点的距离大小降序排列,记为Dist(jx,D),即节点jx与目的节点之间的距离,并且指定距离越小的节点优先进行判断,有如下假设:

Dist(j1,D)≥Dist(j2,D)≥…
≥Dist(jX-1,D)≥Dist(jX,D)

(3)

根据每对节点间节点连通性的计算,我们选择候选转发集的主要步骤如下.

步骤1.首先将i到jX的节点连通性记为PijX=pijX,将节点jX加入到i的候选转发集listi中.从剩下的节点jx(x=1,2,3,…,X-1)中选出一个节点,按照距离优先的原则选定节点jX-1,此时从i经过jX-1到达jX的路径连通性如下:

PijX-1jX=pijX-1·pjX-1jX

(4)

步骤2.若PijX≥PijX-1jX,则设定i与jX-1之间的直接链路不可靠,即进行如下操作:

Pmax=PijX

(5)

否则,则步骤3;

步骤3.则设定i与jX之间的直接链路不可靠,即进行如下操作:

Pmax=PijX-1jX

(6)

步骤4.按照距离优先的原则从剩下的邻居jx(x=1,2,3,…,X-2)中选出节点jX-2,用同样的方法判断i经过jX-2到达jX的路径连通性PijX-2jX,与之前选出的Pmax进行比较,同样,较小的一方则设置所选中间节点与jX之间不可靠.

从i的所有邻居节点jx(x=1,2,3,…,X)选出一个最大的路径连通率的中间节点时,需要做(X-1)次判断,假定找到的中间节点为jmax,即从节点i的邻居集合中任选一个节点加入到点i到jX路径中的情况下,选定节点jmax的路径连通性PijmaxjX最大,并将其加入到候选转发集Listi中,并将除jmax之外的其他邻居节点与i之间的直接链路都设定为不可靠.

步骤5.若X=max,则说明从节点i到节点jX路径上,在i的邻居集合中没有合适的节点可供选择,则候选转发集的选择结束,为Listi={jX};否则,步骤6;

步骤6.令i=max(1≤max≤X-1),返回步骤1;

根据以上步骤,我们选定了节点i的候选转发集Listi,此时i进行数据传输时,可实现的网络可靠性如下:

(7)

图1中,节点i有4个邻居节点j1,j2,j3,j4,任意两点间的节点连通性已经给出,如图1(a)所示.首先,将节点j4加入到候选转发集Listi={j4}中,有pij4=0.4.按照距离优先的原则,将邻居j3加入到路径中,路径连通性Pij3j4=0.3×0.9=0.27<0.4,则将j3与i之间的直接链路设定为不可靠.之后,

将节点j2加入到路径中,路径连通性有Pij2j4=0.8×0.6=0.48>0.4,故i与j4之间的直接链路设定为不可靠.将节点j1加入到路径中,路径连通性Pij1j4=0.7×0.5=0.35<0.4,故j1与i之间的直接链路设定为不可靠.

经过上述步骤,将节点j2加入到候选转发集Listi={j4,j2},如图1(b)所示.接下来需要在j2和j4之间找到连通性最大的路径,有pj2j4=0.6.先将节点j3加入到j2与j4之间的路径,路径连通性Pj2j3j4=0.7×0.9=0.63>0.6,故将j2与j4之间的直接链路设定为不可靠.之后将j1加入,有路径连通性Pj1j2j4=0.9×0.6=0.54<0.6,将j1与j2之间的直接链路设定为不可靠,选定节点j3加入到j2与j4之间的路径,如图1(c)所示.

节点j3加入到候选转发集Listi={j4,j2,j3},需要判断j3和j4之间连通性最大的路径,有pj3j4=0.9,将节点j1加入到其路径中有Pj1j3j4=0.6×0.9=0.54 < 0.9,令j1与j3之间的直接链路为不可靠,如图1(d)所示.最后,i与j4之间连通性最大的路径已经确定为i-j2-j3-j4,此时i的候选转发集Listi={j4,j3,j2}.因此,根据公式(7),节点i进行数据传输时,可实现的网络可靠性为Ri=1-(1-0.8)×(1-0.3)×(1-0.4).

基于节点连通性的机会路由算法伪代码如下.

算法1.基于节点连通性的机会路由算法

1.输入:节点i和邻居jx(x=1,2,…,X);

2. 初始化:listi=null;

3. 按照邻居与目的节点之间的距离大小降序排列,记为{j1,j2,j3,…,jX};

4.for(n=1;n<=X;n++)

5. 计算pijX;

6.Pmax=PijX;

7.for(m=X-1;m<=1;m--)

8. 计算PijmjX=pijm·pjmjX;//公式(3)

9.if(PijmjX>Pmax)

10.Pmax=PijmjX;//公式(6)

11.endif

12.endfor

13. //选择候选转发集

14.listi=listi∪{jm};

15.if(PijX==Pmax)

16. break;

17.else

18.i=jm;

19.endif

20. end for

21. 计算网络可靠性Ri;//公式(7)

22.while(Nodeibroadcaststhepackets)

23. sort the listlistiin increasing order based on the distance node and the destination node;

24.for(k=1;k<=|listi|;n++)

25.if(Thekth node inlistireceived the packets from nodei)

26. Thekth node is selected as the next hop to forward the packets;

27. The other nodes inlistiwill drop the packets;

28.end

29.endfor

30.endwhile

4 性能分析

我们的模拟实验在MATLAB下进行.在该模拟中,传感器节点在网络区域中随机部署.本文中,我们将提出的基于节点连通性的机会路由算法NCOR与POFA路由算法[19]和ExOR路由算法[7]进行比较,分别评估其在网络可靠性和能耗方面的性能.部分参数选择如表1所示.

表1 实验室的网络环境参数
Table 1 Network environment parameters

参数取值检测区域范围(0,0)-(400,400)m节点通信半径30m节点个数200,400,600,800,1000,1200初始化能量1J节点依赖指数0.55,0.6,0.65,0.7,0.75,0.8,0.85,0.9,0.95εamp0.0013Pj/bit/m4εfs10Pj/bit/m4数据包大小512bytes传输速率1MbpsMACIEEE802.11

在图2中,所有算法的网络可靠性均随着节点依赖指数的增加而增加,且NCOR优于其他路由算法.原因是节点之间的依赖指数的增加说明节点之间包的交互增加,而包交互和链路质量紧密相关,这直接提高了节点之间的连通性,也因此提高了网络可靠性.POFA仅使用预期的传送概率度量来选择一些能够保证可靠性的节点作为下一跳以确保网络可靠性.

图3中,我们验证了节点数的变化对网络可靠性的影响,当节点数量在200到1600之间增加时,与POFA和ExOR算法相比,NCOR实现的网络可靠性较高,而且随着节点个数的增加,网络可靠性曲线呈现上升趋势.因为节点数量的增加,增加了节点间的连通性,提高了节点成功传输数据包的概率,进而改善了网络可靠性.如图3所示,随着网络中节点数的增加,POFA算法所实现的网络可靠性总是优于ExOR算法.事实上,POFA是一种改进的泛洪算法,其主要思想就是在传输数据包的过程中,可以充分选择收到数据包的节点作为中继完成数据包的传输,而随着网络中节点个数的增加,参与数据包的传输的节点数也随之增加,因此,相较于ExOR算法,POFA算法能获得较高的网络可靠性.

能耗是指网络在数据传输过程中节点消耗的总能量,能耗越小,说明算法在综合情况下的能量消耗越小.

图4中,随着节点依赖指数的增加,所有算法的能耗均呈现下降趋势.从节点依赖指数的定义可知,它与相邻之间数据包的交互有关,而包的交互受到节点间链路质量的影响,因此,节点依赖指数越大,说明链路质量较好,因此保证了数据包的可靠传输,降低了节点的能耗.

图5说明的是网络中能耗随着节点个数的变化趋势,NCOR的能耗相较POFA和ExOR较低,且POFA的能耗高于ExOR.ExOR算法的中继是由候选转发集中的节点的竞争产生,每个接收者依据它在列表里的位置在发送确认包之前延迟一段时间,各个节点查看收到的确认包集合来决定是否转发包.在ExOR算法每一次路由中继选择的过程中,均会选择一个最优的节点进行数据包的传输,而在POFA算法中,收到数据包的节点均可被中继节点继续数据包的传输过程,且随着节点依赖指数或者网络中节点数的增加,该过程造成了大量的冗余传输,产生大量的消耗.因此,相比于POFA算法,ExOR算法的能耗较低.

剩余能量对网络生命周期有直接影响,如果具有较少剩余能量的节点总是被选为中继节点,则它将很快耗尽,造成网络寿命大幅度减少.因此,图6和图7分别验证了节点依赖指数以及网络中的节点数对节点的剩余能量的影响.在该实验中,我们记录了多轮源节点与目的节点之间所有中继节点的剩余能量,并以所有节点在所有轮次中的剩余能量的平均值作为输出结果,最终得到了剩余能量随着节点依赖指数以及节点数的变化趋势.

如图6所示,随着节点依赖指数的增加,三种算法中所呈现的剩余能量均为上升趋势,其中,随着节点依赖指数的增加,NCOR的剩余能量一直高于ExOR和POFA算法,而且POFA算法中节点的剩余能量要低于ExOR算法.根据公式(2)中的定义,我们可知,节点依赖指数越大,则相邻节点间的连通性则越来越好,在该相邻节点之间的数据包成功传输概率也越来越高,因此节省了冗余传输带来的节点传输数据包所消耗的能量,即节点本身的剩余能量随着节点依赖指数的增加而增加.

图7中,随着网络中节点个数的增加,三种算法中的剩余能量均呈现下降趋势,其中,随着节点个数的增加,NCOR的剩余能量一直高于ExOR和POFA算法,而且POFA算法中节点的剩余能量要低于ExOR算法.

经验证,随着节点数的增加,相对于其他两种算法,NCOR算法的性能一直保持最优状态,受到网络密度的影响较小,而且与经典的机会路由算法ExOR相比,NCOR算法的性能较优.POFA算法是对传统泛洪算法的一种改进,其最大的缺点仍然是随着节点个数的增加,参与数据包传输的节点也随之增加,因此造成了网络中大量冗余数据包的传输,因此其节点的剩余能量加速减少.

5 总 结

在本文中,我们提出了一种基于节点连通性的机会路由算法,该算法在选择候选转发节点时考虑了相邻节点之间的节点连通性,以保证数据传输的可靠性.仿真结果表明,该算法在网络可靠性和网络能耗方面优于现有的经典路由算法.未来的研究工作是设计一种更可靠的路由算法,促进传感器节点之间的协同工作,保证数据传输中更高的节点可靠性,如使用信誉补偿将数据传输到其他更合格的节点[20].