时延要求感知的空洞抑制WSNs路由的研究*

黄 祎

(重庆电子工程职业学院通信工程学院,重庆 沙坪坝 401331)

无线传感网络WSNs(Wireless Sensor Networks)已在多类应用中使用,如战场监视、紧急报警、空难检测[1]。这些应用均要求传感节点在预定时间限制内将感测数据传输至基站,并且不同的应用具有不同的时间限制。即使在同一应用中,不同类型的感测数据也具有不同的时间要求。例如,在火灾检测应用中,携带异常高温的数据应尽可能快地传输至基站,而对于携带常温的数据[2],可允许一定的时延。因此,讨论不同WSNs内数据的传输时延是十分必要的。

然而,由于WSNs网络的固有特性,如能量供应受限、传感节点存储容量和计算能力有限以及无线链路的不可靠性,满足数据传输的端到端时延要求是不易的。

基于网络局部信息的地理位置路由[3]在WSNs内广泛使用。地理位置路由常假定网络内每个节点知道自己的位置以及邻居节点位置,并以贪婪[4]转发策略传输数据包,如多径多速度MMSPEED(Multipath Multispeed)[5]协议、 服务质量感知的地理机会路由QAGOR(Qos Aware Geographic Opportunistic Routing)[6]、多约束的地理路由MCGR(Multi-Constrained Geographic Routing)[7]和基于流量差异的定位路由TDLR(Traffic-differentiation-based Localized Routing)[8]。

这些协议通常将端到端的服务质量QoS(Quality of Service)限制划分为Hop-to-Hop限制。在时间领域内,现存协议通过Hop-to-Hop速度HTHS(Hop-to-Hop Speed)决策路由,进而保证端到端传输时延。从节点(假定si)至它的邻居节点sj的HTHS等于它们间的欧式距离与从si向sj转发一个数据包所要求的时间比值。这些协议总是将具有更高HTHS的选择为下一跳转发节点。

传统的HTHS值正比于离目的节点距离。据以这个观点,几乎所有数据包均是沿着源节点至目的节点的连线路径传输。这种路由策略适合于高密度节点区域,然而,当出现路由空洞时,这种路由策略会产生两个问题:①路由空洞(局部最小问题),如图1(a)所示,在连通目的节点方向上没有邻居节点,在这种情况下,数据包可能无法快速地传输至目的节点,甚至会导致数据包丢失。

当遭遇路由空洞时,常将数据包沿着空洞边界传输,这就导致第2个问题:②空洞边界拥塞,如图1(b)所示,这就增加端到端传输时延。

图1 地理位置路由的两个问题

为此,本文考虑了路由空洞问题,并提出基于时延要求的抑制路由空洞的地理位置路由DG-SHGR(Delay-Guaranteed-based Suppressing Hole Geographic Routing),进而解决上述的两个问题。DG-SHGR路由的主要目的在于预先检测路由空洞,然后再合理地选择路由。

具体而言,对于每个数据包,先依据空洞区域定义“雷区”FAR(Forbidden Area),进而使得数据包能避开FAR,进而抑制空洞路由。而FAR的尺寸和位置随数据包时延要求不同而变化,从而平衡网络流量。为了保证数据包能及时到达目的节点,DG-SHGR路由利用端到端时延要求调整FAR尺寸。实验数据表明,提出的DG-SHGR路由有效地提高了数据包传递率,并平衡网络负载。

1 系统模型及定义

DG-SHGR路由假定每个节点知道自己的位置和一跳邻居节点位置。此外,源节点知道目的节点的位置。

路由空洞:将路由空洞定义为多边形,且在每个顶点上的传感节点S1,…,Sn满足3个条件:①多边形内部区域不包含任何传感节点;②节点Si与Si+1间的欧式距离小于传输范围R,且i∈|1,n|,Sn+1=S1;③节点Si与Si+2间的欧式距离大于传输范围R,且i∈[1,n],Sn+1=S1,Sn+2=S2。

令Θ为多边形,顶点表示为Q1,Q2,…,Qn。此外,引用|·|表示欧式距离,例如|AB|表示点A与点B间的欧式距离,||表示线的欧式长度。pΘ表示Θ的边。令A、B是Θ边上的点,而分别表示从A至B的逆时针、顺时针边。

凸包(convex hull):Θ凸包的定义为能够覆盖整个Θ的凸多边形,且与Θ具有相同的顶点。

本文引用H表示空洞的凸包。令N表示Θ边外的任意一个节点。节点N的视图控制顶点VLV(View Limit Vertex)是Θ内的顶点,且此顶点与节点N的连线不与Θ相交,如图2(a)所示。Qi、Qj是Θ的VLV。从N至Θ的视图控制角θ定义为NQi与NQj的夹角。

绕开-最短路径BSEP(Bypassing Short Euclidean Path):从源节点s至目的节点t的绕开-最短路径LΘ(s,t)是沿着Θ的最短折线构成,如图2(b)所示。

图2 VLV定义示例

2 DG-SHGR路由

提出的DG-SHGR路由主要解决图1所示的两个问题:局部最小问题和空洞边界拥塞问题。DG-SHGR路由先检测空洞,然后再选择能避开空洞的路由传输数据包。具体而言,DG-SHGR路由主要由空洞检测、空洞信息传输以及数据转发3个阶段构成。

2.1 空洞检测

引用文献[9]的TENT规则,节点检测自己是否在空洞边上。如果在空洞边上,节点(称为边界节点)就产生边界坐标决策BCD(Boundary Coordinates Determination)消息,再利用文献[9]引用的右手规则,沿着空洞边界转发BCD消息,进而收集信息。

当收到来自其他节点发送的BCD消息,节点就检测自己的横坐标是否小于发送节点的横坐标。如果小于,则利用右手规则转发BCD消息,否则就丢失。通过这种方式,最终只有一条BCD消息沿着边界转发,并且被转发的BCD消息是由横坐标最大的边界节点产生的。将此节点称为BCD的初始节点(BCD-I)。

2.2 空洞信息传输

所谓空洞信息传输就是将空洞凸包H的信息传输至围绕着空洞的节点。传输半径是由预定参数αmin控制,且0≤αmin≤π。若αmin=0,则表示将凸包H的信息传输至整个网络;若αmin=π,则传输区域限制于凸包H。

由于BCD-I节点获取了凸包H的信息,BCD-I节点就利用空洞核心信息HCI(Hole Core Information)消息向邻居节点传输凸包H信息。一旦接收到HCI消息,节点就计算凸包H的视图控制角θ。如果θ大于αmin,就存储凸包Ω的信息,再将HCI消息传输至它的邻居节点;否则就丢弃HCI消息。

当节点Ν离空洞越远,它的视图控制角θ就越小。当节点Ν离空洞足够远时,视图控制角θ就趋近于零。因此,当αmin=0时,凸包H的信息传输区域是整个网络。本文将信息传输区域内的节点称为空洞感知节点HAN(Hole Aware Nodes),其他节点称为盲节点BN(Blind Nodes)。

2.3 数据包传输

DG-SHGR路由引用两种转发模式:直接转发GSF(Go Straight Forwarding)[10]和空洞绕开转发HBF(Hole Bypassing Forwarding)。当节点未遭遇路由空洞时,即正常情况,就利用地理位置路由的贪婪转发模式传输数据包,将这种方式称为GSF。这不是本文研究的重点。本文的研究重点是HBF。

2.3.1 雷区FAR的定义

沿着HBSP传输数据包能够减少端到端传输时延,并且防止数据包到达空洞边界,缓解了局部最小问题。然而,如果所有数据包沿着HBSP传输,则增加了边界网络区域的负载,如图1(b)所示。

设计DG-SHGR路由的目的就是依据数据包的时延要求,尽可能选择最短路径传输数据包。为此,针对每个数据包,定义雷区FAR。雷区 FAR的尺寸正比于数据包传输的时延要求。

以图3为例。源节点s需向目的节点t传输一个数据包,且传输时延要求为15 s。即在15 s内完成数据包的传输。图3中的蓝线表示从源节点s至目的节点t的HBSP路径。假定这个路径长度为100 m。

图3 雷区FAR定义示例

因此,若沿着HBSP传输的话,则只需10 s。为了减少边界传输的负载,并满足数据包传输时延要求,数据包可沿着更长的路径传输,只要路径长度不超过150 m。为此,在传输时延的允许条件下,可适当增加传输路径,为此,定义雷区FAR。

DG-SHGR路由将雷区FAR定义为凸包H的扩展区域,区域中心点位于H内,再依比例因子(scale factor)扩展。

雷区 FAR:基于比例因子,对凸包H进行相似转换所形成的区域为雷区FAR F。如果s和t是凸包H外的两个任意节点,且满足式(1):

|LF(s,t)|≤|LH(s,t)|+(ξ-1)pH

(1)

式中:pH表示凸包H的边。而LF表示雷区F的长度,相应地,LH表示凸包H的长度。

2.3.2 下一跳节点的选择

DG-SHGR路由引用特定的数据包格式,如图4所示,其中转发模式有GSF和HBF。scaleCenter表示雷区FAR的中心位置,存储了中心位置的坐标。scaleFactor为比例因子。传输时延D表示传输数据包所限定的时延。速度门限SpeedThreshold表示满足传输时延D的最小HTHS。最后,数据Data为要传输的数据包。

图4 数据包格式

①Hop-to-Hop 速度HTHS的计算

分别在GSF和HBF两种转发模式下,计算HTHS。

(2)

(3)

②速度门限SpeedThreshold的计算

当转发模式为GSF时,SpeedThreshold的定义如式(4)所示:

(4)

式中:D表示预定的数据包传输时延要求,即必须在时延D内将数据包传输至目的节点t。而elapsedtime表示数据包到达节点si已消耗的时间。因此,D-elapsedtime表示剩余时间remainingtime。

当转发模式为HBF时,SpeedThreshold的定义如式(5)所示:

(5)

③雷区中心位置以及比例因子的计算

当转发模式为GSF时,雷区中心位置和比例因子均为空。当转发模式为GSF时,需利用雷区转发数据包,进而平衡网络负载。因此,对凸包H进行相似变换,且从凸包H内随机选择中心位置,而比例因子ξ的定义如式(6)所示:

(6)

式中:R为节点传输范围。而dm表示节点si的所有邻居节点中的最大HTHD时延,其定义如式(7)所示:

(7)

式中:B表示节点si的邻居节点集。

最后,依据节点的HTHS速度,构建下一跳转发节点的候选集C。如果节点的HTHS速度大于SpeedThreshold,则将此节点加入候选集C,如式(8)所示:

(8)

然后再从C内随机选择一个节点作为下一跳转发节点,整个流程如图5所示。

图5 传输数据包的基本流程

3 性能仿真

3.1 仿真参数及性能指标

依据NS2.35[12]建立仿真平台。仿真区域为1 200×1 200 m2,200个源节点随机分布在仿真区域内,且基站位于区域顶部。建立仿真的目的就是分析DG-SHGR路由处理路由空洞的能力。为此,在 1200 m×1 200 m区域内分别产生18个空洞,分别标注为Topology1、Topology2,…,Topology18,且空洞尺寸逐步增大。图6显示了3个空洞示例。

图6 Topology1、Topology2和Topology3示例

此外,源节点每10 s产生一个数据包,数据包大小为50 byte。且每个数据包的传输时延要求从0.2 s、0.5 s和0.8 s中随机选取,即D={0.2,0.5,0.8}。整个仿真时间为500 s。

为了更好地分析DG-SHGR路由的性能,选择MMSPEED[5]和QAGOR[6]路由作为参照,并分析它们的数据包传递率和平衡指标BI(Balance Index)[13]的性能。其中数据包传递率是指基站所接收的数据包数与源节点所发送的数据数比值。而BI反映了传感节点间的流量负载的平衡性,其定义如式(10)所示:

(10)

3.2 数据包传递率

图7显示了在D=0.2、D=0.5和D=0.8 3种情况下的数据包传递率。

从图7可知,DG-SHGR路由所获取的数据包传递率高于MMSPEED和QAGOR路由,并且随着空洞尺寸的增加,优势越发明显。

此外,MMSPEED和QAGOR路由随空洞尺寸增加而数据包传递率迅速下降,而DG-SHGR路由仍保持稳定。原因在于:DG-SHGR路由引用雷区概念。从图7可知,即使在D=0.2 s时,DG-SHGR路由仍保持75%的数据包传递率,而在D=0.5 s和D=0.8 s时,数据包传递率保持95%以上。相反,在最糟糕的情况下(Topologies 18),MMSPEED路由在D=0.2 s、D=0.5 s和D=0.8 s 3种条件下的数据包传递率下降至30%、55%和61%。

从图7可知,QAGOR路由的数据包传递率最差。例如,在Topology 16-19时,QAGOR路由的数据包传递率低至1.0%。这也说明,空洞对QAGOR路由的影响最大。相比QAGOR,MMSPEED路由利用回压机制能较好地处理路由空洞。尽管回压机制能处理路由空洞,但是相比DG-SHGR路由,MMSPEED路由的数据包传递率仍较低。

图7 数据包传递率

3.3 平衡性能

本次实验分析QAGOR、MMSPEED路由和DG-SHGR路由的BI性能,实验数据如图8所示。

图8 BI性能

从图8可知,DG-SHGR路由获取高的BI的性能,这说明DG-SHGR路由利用动态的雷区机制,有效地平衡负载。相比于QAGOR和MMSPEED相比,DG-SHGR路由的BI得到有效地提高。例如,在Topology 4时,MMSPEED路由获取最高的BI,但DG-SHGR路由的BI是MMSPEED路由的2倍。

与MMSPEED路由相比,QAGOR路由的BI得到提高,但是仍低于DG-SHGR路由。在空洞为Topology 6时,DG-SHGR路由的BI是QAGOR路由的1.9倍。

4 总结

本文强调地理位置路由的路由空洞问题,并着力解决局部最小问题和边界拥塞问题,提出基于时延要求的抑制路由空洞的地理位置路由。该路由以满足数据包的传输时延要求为基础,即依据这个时延要求计算每个数据包的雷区,进而避开路由空洞,也缓解边界拥塞问题。实验数据表明,与同类路由相比,提出的DG-SHGR路由提高了数据包传递率,平衡了负载。

后期,将进一步优化路由,并扩展路由协议,使其满足更多的路由指标,如可靠、吞吐量。这是后期研究工作的重点。