基于LF-GFG的物联网动态路由算法①

梁艺怀,张立臣

(广东工业大学 计算机学院,广州 510006)

引言

物联网装置一般是通过无线网络传输,装置可能会移动,并且可能使用电池作电源.这就要求物联网的路由协议不仅需要具备低耗能的特性,还必须能适应动态网络环境的特性.

目前最常见的路由协议有AODV与DSR等,这些路由协定会先通过一个或多个洪泛广播,得到将封包送达目的地的传输路径,再将数据沿着这条路径传到目的地.但是,随着物联网的规模逐渐扩大,这些洪泛广播会造成大量的广播风暴,导致网络效能低下.因此,通过目的地的位置信息来取得所需要的传输路径,来避免洪泛广播风暴问题位置路由协议(Geographic Routing Protocol,GRP)颇受学界关注和研究.

位置路由协议假设每个装置都有一样的传输半径,并且每个装置都能通过一些定位的方法取得自己的精确位置.目前,位置路由协议研究意向产生了GPSR[1]、GFG[2]、GOAFR+[3]、VRR[4]、VPC[5]、和 ABVCap[6]等方法,这些方法大都将网络转换为一个平面化的图形,然后通过右手法则设置虚拟坐标动作,取得所需的传输路径.但是,这些方法完全解决了假设的问题,可以实际应用到真实的环境中,但是为了要保持虚拟坐标所具备的特殊性质,反而让它们失去了适应动态网络的能力.当物联网内的装置有移动或是开关,这些方法的传输能力就会开始下降并且不容易修复.针对这一问题,本文根据LF-GFG方法,设计一种动态物联网的路由算法.算法可以不需要额外的封包就将整个网络转换成一个平面化的图形,取得所需的传输路径,克服了实际环境应用的问题.

1 算法设计

1.1 设计思路

GFG路由协议中提出的右手法则是早期所有位置路由协议的基础.在右手法则中,将图上的边想象成墙壁,将右手放在墙上往前走(走在墙的左侧),若这是一个平面化图形,则右手法则保证可以越走越靠近目的地.简而言之,如能将网络联机转化成一个平面化图形,重复地使用右手法则来决定路由路径,可以在理论上保证将封包送达目的地.并且不用任何额外的封包,仅仅通过无线网络传输时的RTS、CTS封包,就直接将数据传到传输路径上的下一点.在研究多跳无线随意网络路由协议时,最常使用的方法是将每个装置表示成一个二维平面上的节点,若2个装置间可以互相传输数据,就在这2个节点间加上一条边.如此,网络就可以表示成一个图形,而路由协议问题就转化成图形学问题了.在一个平面化图形中,所有边都不会交叉,如何将图形平面化,是一个很复杂的问题.在物联网中,为了减少网络的负担,每个节点不可能有完整的网络架构信息,只会有其邻近节点信息.因此,让每个节点,利用邻近节点的信息,就能分布式地将整个图形平面化,这就是使用右手法则要面临的问题.传统做法是通过让每个节点分布式地满足Gabriel Graph(GG)[7]或Relative Neighborhood Graph(RNG)[8]等图形特性,来取得平面化图形,但是这个做法很难在实际的环境中实现.另一个方法是通过维诺图(Voronoi diagram)来取得,即LF-GFG所使用的虚拟坐标方法.

为了能够适应动态网络环境,必须让LF-GFG所使用的虚拟坐标转化为一个分布式的平面化图形.因此,如何设计这个二维虚拟坐标尤为关键.本文按照维诺图理论,将每个节点划分一个区域.再将区域相邻的节点连起来,就会得到一个平面化图形[9].

在图1中,有A到L共12个节点,两个节点之间若有联机则表示这两个装置可以互相通讯.每个节点都划分一个区域,在执行算法时,先进行网络拓扑图平面化动作,通过判断两个区域是否相邻,移除网络拓扑中不必要的连接,从而达到节省运算开销问题.图中的粗线表示可以联机通信,虚线表示被移除的不必要连接.由于这种方法不需要复杂的计算和多余的封包传输被广为应用.但这种算法没有考虑通信节点的通信半径,且只能将网络拓扑图进行平面化计算.

图1 LF-GFG的概念示意图

1.2 分配虚拟坐标

假设现在有一个物联网网络如图2所示.在网络中,共有A到K共11个装置,彼此间可以互相通讯的装置就会有一条边将它们连起来.这些装置并不知道它们自己的位置,只知道它附近有哪些其它节点.

图2 实际网络联机情形

首先,LF-GFG会从一个预先设定好的起始点开始分配虚拟坐标的工作.由于本研究中针对坐标点层级不会太深,且更需保证及时性,要求求解速度且目标节点的层次较浅的情况下深度优先搜寻优于宽度优先搜寻,所以我们使用较优的深度优先搜寻.在提出的算法中,A点是这个起始点.A点会先被分配到一个虚拟坐标a1(0,0),注意这里的坐标是用极坐标表示.同时A点会为这个虚拟坐标划分出一个区域R(a1).把R(a1)用4个字段(0,1,0,2π)来记录,分别代表这个区域的内半径、外半径、起始角度、结束角度,如图3中间的圆形所示.接下来,A会发出一个封包,将刚才被分配的虚拟坐标与区域信息通知给周围的其它节点B、C、D.这个控制封包内还会包含一个串行FL(A),它包含了深度优先搜寻(Depth-First Search,DFS)算法在由A、B、C、D所组成的子图(subgraph)中间节点造访的顺序[10],也就是FL(A)=(B,C,D,A).收到这个封包的节点就会开始分配虚拟坐标.分配的方法如下：

图3 分配虚拟坐标

(1)观察FL(A)内有几个节点,就将封包内存的角度区间分成几等分,依序分给每个节点.而每个节点的角度坐标就设为分得角度区间的正中间.

(2)距离坐标则是封包内存区域的外半径.这样一来,如图3中的A、B、C、D4个点都各被分配到一个虚拟坐标a2、b1、c1、d1.a2、b1、c1、d1也会被分配到相对应的区域,其中角度区间就是前面通过FL(A)分得的角度区间,而内半径就是a1的外半径,新的外半径则会被设成比内半径的1/cosθ大的值,其中θ是所分配到的角度区间.例如c1分配到的区域R(c1)就会被记录成(1,1 cos 4,2,π),其中δ是一个很小的常数.虚拟坐标计算公式如下：

在A、B、C、D分配完虚拟坐标后,会检查是否有相邻的节点还没有被分配到虚拟坐标,然后重复之前的动作,将坐标分配给还没有坐标的节点.其中因为A和B的所有相邻节点都有至少一个虚拟坐标了,所以A和B并不会再发送分配坐标的指令封包.而假如D先发送了分配坐标的指令封包,里面包含的FL(D)会是(F,G,D).此时C要发送分配坐标的指令封包时,它周围就只剩下E还没有拿到任何的虚拟坐标,所以FL(C)=(E,C).每个分配到虚拟坐标的节点都重复这个动作,最后整个网络的节点就会都分配到至少一个虚拟坐标了,如图3所示.

1.3 建立平面化图形

在每个节点都有虚拟坐标之后,先将代表网络的图2转化成一张虚拟的二维网络图.由于每个节点可能会分配到超过一个虚拟坐标,所以每个节点可能会对应到超过一个虚拟节点.属于同一个节点的虚拟节点之间当然可以互相沟通,所以我们会在它们之间加上虚拟的边.而对照图2,若两个虚拟节点属于可以互相沟通的两个节点,则我们也在它们之间加上虚拟的边.最后的虚拟网络图如图4所示.

图4 建立虚拟网络图

这时,就能获得平面化的虚拟图形,方法如下：如两个虚拟节点所分配到的区域是相邻的,而且它们之间有一条边相连,那么我们就把这条边加入平面化的虚拟图形中.例如c2和h1之间有一条边而且R(c2)和R(h1)相连(参考图4和图3),所以c2和h1之间的边会被加入平面化的虚拟图形中,如图5所示.

是否保证取得平面化的虚拟图形和分配虚拟坐标的方法有很大关联,并不是随意分配的虚拟坐标和区域都能用这个方法取得平面化的图形,而其中的关键在于分配区域的内外半径差距.从图3我们可以看出来,其实这些分配的区域会形成一个的类似同心圆的架构.每一层同心圆的厚度如果不足,就不能够保证这个方法取得的图形是一个平面化的图形.而我们在分配虚拟坐标时所设定的外半径需大于内半径的1/cosθ倍,就是满足平面化的最低半径要求,我们可以设定任何大于1/cosθ倍内半径的值,都能够保证让我们得到平面化的图形[11].

图5 虚拟平面化结果图

1.4 决定路由路径

在取得平面化图形之后,可以开始运行GFG的右手法则.在GFG中,先使用贪婪算法尽量地将封包送到更靠近目的地的地方.但是贪婪算法并不能保证将封包送达,有些时候,封包会卡在某个节点,而相邻的节点都比这个节点离目的地更远.这个时候,就需要靠右手法则来帮我们解决这个问题[12].当有一个封包要从K点送往E点时,我们会先找到K点的一个虚拟坐标k1,然后将目的地设定成E点的一个虚拟坐标e1.我们会发现没有其它与k1相连的虚拟节点比k1更靠近e1,所以开始使用右手法则.在使用右手法则的时候,我们只看平面化图形,想象人站在k1的位置,将右手放在k1上沿着平面化图形走,这样我们就会遇到了下一个虚拟节点g4,而G就被我们选择为路由路径上的下一个节点,并将封包传送给G.

在节点G,我们会进行同样的动作,先检查是否可以使用贪婪算法决定下一个节点,这时我们就发现有与g4相连的其它节点比g4更靠近e1,而我们通过贪婪算法选择了其中最靠近e1的f1,并将封包传给f1由拥有者F.最后封包就成功地被送往了E.如图6所示.

图6 确定路由路径

1.5 适应动态网络

在动态网络中,要怎么迅速的维护虚拟坐标,让网络维持高效能不受影响.动态网络的各种行为,可以简化为节点离开与节点加入这两种,随着节点从甲地离开到乙地加入则可以组成各种动态网络的移动行为.因此,当LF-GFG在有节点离开或加入时,则会重新分配虚拟坐标.假设D节点离开了网络,这时候首先与节点D相连的节点会发现D已经离开了,然后属于节点D的虚拟节点会被移除,与这些虚拟节点相连的虚拟边也会被移除.最后的虚拟坐标分配情形如图7所示.

图7 D节点离开后虚拟坐标分配

当有一个新的节点L加入这个网络时,与L相邻的节点会发现L还没有虚拟节点,并发送一个分配虚拟节点的控制封包给L.假设是由节点B先发现L的加入,并且要发送分配虚拟节点的控制封包,这个控制封包内会包含B的一个最外层的虚拟节点信息,还有FL(B)=(L,B).这个例子中因为B只有b1一个虚拟节点,所以会将b1的信息传给L.当L收到这个控制封包后,B和L都会再分配到新的虚拟节点.

如图8中的l1和b2所示.上述情形虚拟节点的区域外相邻的区域,在还没有分配给其它的虚拟节点情况下,当有新的节点加入时,就可以保证找到这种虚拟节点,发送控制封包分配新的虚拟节点给这些新加入网络的节点.从而实现可以不需要额外的封包就可将整个网络转换成一个平面化的图形,使物联网装置快速获得所需的传输路径.并能有效避免网络拥塞及洪泛广播风暴问题.

图8 L节点加入后虚拟坐标分配

2 算法实验与结果分析

采用NS-2进行仿真实验.在实验中,用不同颜色区分APIT+GFG、ABVCap、VCP和LF-GFG等4种路由协定.随机建立了100张网络图,每张网络图都有450个物联网的装置.实验持续了500个时间单位,在第50个时间单位的时候,我们让网络发生随机的1个(粗线)、5%个相连(虚线)、5%个分散(细线)的节点故障,观察节点故障对网络效能的影响.每0.1个时间单位,网络中就有随机一个装置送出一个封包到另一个随机选择的装置,我们将10秒内100个网络图的所有封包传输结果平均之后,得到了下面的实验结果.

图9显示了封包传达率的实验结果,我们可以发现,在网络内有450个节点时,虽然这4个方法在理论上都有百分之百的封包传达率,但是实际实验却会有封包传输失败的情形发生.其中APIT+GFG会传输失败是因为它需要假设每个节点的传输半径都是一个完美的圆,但是计算机程序会有小数点精确度的限制,无法达到这个假设.当第50个时间单位发生节点故障时,VCP因为没有维护的机制,会导致封包传达率大幅下降且难以回复；APIT+GFG受影响比较小是因为它假设每个节点都是被散布在一个二维平面且都有精确的坐标,在这个情况下,GFG本身就能理论上有100%的封包传达率.LF-GFG在节点坏掉时受影响较小也是因为它使用了GFG的右手法则的关系.ABVCap和LFGFG都有维护的机制,所以随着维护机制的启动,我们会发现封包传达率降低后会慢慢的回升,其中我们发现,由于LF-GFG的维护机制十分简单迅速,所以封包传达率回升的速度比ABVCap高出很多.

图9 封包传达率比较图

图10显示了封包传输时间的比较图,封包传输的时间除了受到路径长度的影响之外,还会受到网络壅塞程度影响.从图中我们会发现,虽然LF-GFG较能够适应动态的网络环境,但是由于它的虚拟坐标分配并没有真的平均分散在二维平面上,当使用GFG的右手法则时会容易产生一些热点,让这些热点的负担很大,造成网络壅塞,拉长传输时间.当有节点坏掉,LFGFG进行维护之后,因为维护时分配的虚拟坐标会在较外层的位置,所以反而让虚拟坐标的分配较为分散,降低了网络拥塞的情形.

实验还比较了LF-GFG和ABVCap在维护动态网络时所需要的封包量.同样是5%相连节点坏掉时,在LF-GFG中平均只需要使用9.3个封包就能够使网络效能恢复,而ABVCap则平均需要112.9个封包.当只有1个节点坏掉时的数据则是1.3与3.7个封包,从数据中我们可以发现LF-GFG具有较好的容错效能.实际上,我们发现假如只有1个节点坏掉,60%概率下网络的效能不会受到影响.

图10 封包传输时间比较图

3 结语

本文根据LF-GFG提出的路由概念,结合传统位置路由协议所使用的右手法则和虚拟坐标系统的易实现特性,提出了一种动态物联网的路由算法.NS-2实验结果表明,该算法相较于其它的路由协定,具有较高的容错率,较低的维护成本,和较快的维护速度.