一种支持单向链路的PUMA改进组播路由协议

邱 静 怡

(广东外语外贸大学 广东 广州 510006)

一种支持单向链路的PUMA改进组播路由协议

邱 静 怡

(广东外语外贸大学 广东 广州 510006)

研究表明在无线自组网场景中通常存在非对称、单向链路，但是目前大部分路由协议都是针对双向链路设计的。故针对单向链路问题，提出改进的组播路由算法PUMA-UD，收集单向链路信息进行路由选择，这有利于邻域管理且提高通信质量。使用NS2仿真平台进行仿真验证，将改进后的协议与原PUMA和FLOOD进行比较，结果显示当网络负载增大时，PUMA-UD在报文投递率和端到端延时方面优于PUMA和FLOOD。

移动自组网 组播 路由 单向链路 PUMA

0 引 言

组播服务对于团队密切协作的应用非常重要，如共享文件和视频会议等。然而在移动Ad Hoc网络中，节点移动、无线信道脆弱、缺乏中心协调机制为组播路由的设计提出了更高的要求。当前已有组播路由的运行网络环境必须是完全双向链路。可是部分文献[1-2]表明在实际无线场景部署中存在大量单向、非均衡链路(简称：单向链路)。单向链路的存在大大影响Ad Hoc网络的连通性，使得真实环境下部署组播路由协议的效率明显下降。因此，设计一种能支持单向链路传输的Ad Hoc网络组播路由协议具有一定的研究意义。

1 研究现状

国内外学者的研究一般先进行单向链路检测，如果存在单向链路，则针对单项链路进行路由调整。单向链路检测包括在周期性发送的Hello报文中携带节点信息[4]、修改载波侦听多路访问协议的RTS帧和CTS帧、计算邻节点间的欧几里德距离等。路由调整方法可分为去除单向链路和利用单向链路[5-10]。去除单向链路的方法包括将单向链路节点加入黑名单、利用RREQ报文等待双向链路机制和反向深度优先搜索等；利用单向链路的方法包括正反向路由分开查询法、利用中间节点法、改进距离矢量路由算法和修改MAC层协议等。研究人员针对单向链路研究态度也是对立的。部分研究表明无线网络中的单向路径稳定性高、连通性好，在不增加网络代价的情况下能节约通信成本。也有文献(如文献[13])指出维护单向链路的成本很高。

移动Ad Hoc通信时网络拓扑、路由变动频繁的应用中，设计支持单向链路的单播路由协议已经非常困难，而针对组播路由协议的单向链路问题研究几乎没有[11-12]。基于上述的考虑，本文从网络拓扑变动侦测、路由及时更新调整、有效利用单向链路等方面入手，研究在Ad Hoc网络场景下如何设计支持单向链路的高效组播路由协议。

2 PUMA无法解决单向链路问题

PUMA[14]是典型的基于mesh组播协议，mesh结构能为接收节点提供冗余链路，有效保障了网络的稳定性。且已有研究表明PUMA性能要优于ODMRP和MAODV，故本文选择PUMA作为单向链路组播研究的基础协议。

PUMA协议几乎没有考虑网络中存在单向链路的风险，其路由机制不能有效避开单向链路的影响，这严重影响报文传输的可靠性。如图1所示，A→B是一条单向链路，核心节点11发送组播组维护控制报文(MA报文)。由于11-A-B-9-7链路长度比11-3-4-8-5-7短，所以节点7先接收到来自节点9的MA报文，并且选择11-A-B-9-7链路作为到核心节点的最优路径。节点7更新连接链表选项，生成自身的MA继续转发。节点1收到MA后，将节点7作为路由核心节点的下一跳。当源节点1发送数据到节点7时，节点7则按照选择的路径11-A-B-9-7转发数据，数据达到节点B后，B→A链路不通，数据报文丢失。报文ACK计时器超时后，节点B、9、7删除连接链表记录。节点7启动链路修复机制，激活备用路径11-3-4-8-5-7转发数据报文。但是当核心节点再次发送下一轮MA报文链路维护时，节点7再次接收到来自11-A-B-9-7链路的MA报文，此链路要优于正在使用的11-3-4-8-5-7链路，故节点7并再次选择11-A-B-9-7链路进行报文传输。如此循环反复，不仅数据报文投递率降低，而且链路维护时产生大量控制报文使得网络性能严重下降。因此，PUMA协议不能解决网络中的单向链路问题。

3 PUMA-UD算法

PUMA-UD是在PUMA协议基础上提出的支持单向链路组播路由协议。本节主要从单向链路检测机制、路由建立和路由维护等方面阐述PUMA-UD路由协议的实现过程。

3.1 单向链路检测机制

在描述单向链路检测机制前，先进行以下说明：

(1) 如果存在A→B单向链路，那么A为单向链路的前向节点，B为单向链路的后向节点。

(2) 所有节点新增邻居链表，每个邻居链表表项中包含邻居节点id和是否为单向链路后向节点的标识。邻居链表是与连接链表中的nexthop_信息同步。节点周期性更新邻居链表，以保证邻居链表中所有邻节点信息未过期。

(3) MA报文中增加两个字段为邻居链表和链路是否含有单向链路的标识，生成MA报文时将节点中的邻居链表复制到MA的邻居链表中。

PUMA-UD利用核心节点周期性发送的MA报文进行单向链路检测，实现过程如图2所示。

图2 单向链路检测流程图

节点A一跳广播MA报文，MA报文中包含了节点A接收的所有未过期邻居节点id。节点B收到来自节点A的MA报文后，更新其邻居链表并进行如下判断：如果MA报文中携带的邻居链表中不包含节点B的id，则说明节点A与节点B之间存在单向链路(节点A为单向链路前向节点，节点B为后向节点)，并在节点B的邻居链表中标记与节点A的关系是单向的；如果MA报文的邻居链表中包含节点B的id，则节点B在其邻居链表中标记与节点A的关系是双向的。

3.2 路由建立

当网络中没有检测到单向链路时，PUMA-UD建立路由方式与PUMA类似，核心节点发送MA控制报文，接收节点更新连接链表，然后根据收到的MA报文生成自身的MA报文继续转发。如果网络中存在单向链路时，PUMA-UD路由建立机制发生变化，如图3所示。

图3 路由建立流程图

当网络中存在单向链路A→B，节点B收到节点A的MA报文后，节点B更新连接链表。将节点A的id与节点B的邻居链表中选项进行匹配得知节点A、B之间是单向链路，那么节点B启动定时器等待更多MA报文。如果定时器超时之前，节点B收到同一核心节点发送的、具有相同序列号的、只包含双向链路的MA报文，则更新连接链表，停止定时器。节点B利用双向链路的MA报文生成新MA报文继续转发。否则定时器等待超时，仍没有收到同一核心节点发送、相同序列号的双向MA报文。此时说明节点B与核心节点之间只有单向链路，故节点B启动定时器生成并向节点A单跳广播控制报文uMA(报文包括发送节点id、核心节点id、单向链路的前向节点id和MA报文序列号)。中间节点收到uMA后，向节点A单跳广播转发uMA。节点A收到uMA报文后，节点A设置连接链表nexthop_表项，表示转发来自节点B的数据报文。且将uMA中的MA报文序列号从ACK链表中移除，然后向节点B发送uMA。此时，节点B得知单向链路前向节点A已经收到报文确认信息，故单向链路A→B路由建立。节点B接着生成新的MA报文(填充报文邻居链表而且单向链路标志为true)，继续转发MA报文。如果在定时器超时前节点B没有收到uMA报文，则认为节点B没有到节点A的回路，不再转发MA报文。

更新连接链表应按优先次序对链表表项进行排序，排序规则：序列号相同而且是双向链路的情况下，跳数少的表项排前面；序列号相同的情况下，双向链路排单向链路表项前面；序列号相同的情况下，按到达时间先后排序单向链路表项。最优的连接链表选项就是连接链表中最靠前的连接链表选项。也就是说，一般情况下，节点收到包含单向链路的MA报文后，启动定时器等待更多MA报文，如果接收到双向MA报文则尽量选择双向链路路由，如果没有任何双向链路MA报文则选择最先收到的单向链路路由。

3.3 加入或退出组播组

由PUMA-UD路由建立方式可知，PUMA-UD构建的网络中仅存在两种类型的链路：双向链路和环状单向链路(如图4所示A->B-9-7-5-8->4-A链路属于环状单向链路)。针对仅存在双向链路的网络，PUMA-UD加入和退出组播组操作与PUMA协议完全相同。针对存在环状单向链路的网络，核心节点MA传输路径上的单向链路后向节点(如图4的节点B)每次收到来自核心节点的MA报文，都要使用uMA向单向链路前向节点(图4的节点A)发送确认信息。因此，节点B需要加入/退出组播组，均需要向节点A发送加入组播组加入/退出控制报文uMA。节点A收到控制报文后，加入和退出组播组的其他操作均与PUMA算法相同。为了降低算法复杂度，单向链路后向节点(图4的节点B)将不直接参与核心节点选举过程，即PUMA-UD在核心节点选举时，尽量避免单向链路的后向节点。

图4 环状单向链路场景示意图

3.4 路由维护

与PUMA协议一样，通过核心节点周期性发送MA报文进行路由维护。在三个MA报文到达时间间隔后，如果节点没有收到来自邻节点的MA报文，且其连接链表中将该邻节点作为下一跳的路由表项，那么删除该路由表项，并启动连接链表中备用路径，如果没有备用路径，节点只能等待核心节点发送下一轮的MA报文进行路由修复。

3.5 数据分组转发方式

当节点到核心节点的双向链路时，PUMA-UD的数据分组转发机制与PUMA类似，组播网外数据单跳广播，组播网内数据广播。如果节点与核心节点之间仅存在单向链路(如图4中的A->B)时，那么节点B采取单跳泛洪方式向节点A转发数据分组，节点A收到数据分组后，继续向核心节点转发数据分组。节点B收到节点A转发的数据分组来确认数据分组是否成功转发。如果节点B数据分组确认超时，节点B则启动类似FLOOD协议机制进行数据分组全网广播。在数据分组转发过程中，如果节点获得双向链路路由信息，则即可停止单向链路数据分组分发，切换成双向链路转发数据分组。

4 仿真实验结果分析

由于均采用核心节点单一广播机制对组播组结构进行构建和维护，因此PUMA-UD协议和PUMA协议的收敛性能是一致的。为进一步定量分析PUMA-UD协议性能，通过路由协议 FLOOD、PUMA和 PUMA-UD 协议进行仿真对比，旨在分析PUMA-UD协议对单向链路处理的有效性。主要的性能指标参数包括：

(1) 报文投递率S：

(1)

式(1)中，PA表示成功传输到目的地的分组数；PT表示发送的总分组数。在网络负载相同的情况下，报文投递率越高，则说明路由性能越佳。

(2) 平均端到端延迟D：

(2)

式(2)中，N表示成功传输的分组数，rti表示第i个分组到达目的节点的时间，sti表示第i个分组产生时间。在网络负载相同的情况下，平均端到端延迟越低，则说明路由性能越佳。

本文提出的基于单向链路的路由算法是建立在作者早前论文[15]设定当向链路网络模型的基础之上。首先将无线网络分成两个强连通的子网络N1和N2，节点A1、A2∈N1，节点B1,B2∈N2，且N1与N2之间有一条或多条链路连通。考虑到路由维护的可操作性，本实验将不考虑N1和N2之间仅存一条单向链路场景。故本文实验仿真场景将考虑以下三种情况：(1)环状单向链路，即N1到N2通信必须通过A1->B1，N2到N1通信则需要另一条单向路径B2->A2。(2)N1到N2之间存在最短路径A1->B1，但还存在其他可选的双向路径A2<->B2。(3)大范围不均衡网络环境。

仿真场景一：在发送源与组播组之间仅存在单向链路的场景中，在网络负载不断增加情况下，验证新的路由算法适应纯单向链路环境的性能，与图4结构类似。仿真实例参数设置如表1所示。

表1 仿真场景一实验参数表

仿真环境中，节点数量50个，采用Two-ray ground reflection 无线传播模型，单向链路前向节点信号传输范围为250米，其他节点信号传输范围为400米，节点不移动。组播组1个，发送节点1个，接收节点20个。所有的接收节点在起始时刻加入组播组中，在30秒开始发送CBR，900秒结束发送，仿真时长910秒。并且要求CBR长度为256 KB，CBR每秒发送节点数量从2个到14个之间变化。

PUMA协议不支持仅包含单向链路的数据传输，故本场景实验中仅显示FLOOD和PUMA-UD协议比较，如图5和图6所示。随着单位时间内发送数据报文增加，端到端的平均延迟变大。随着数据报文发送数量增加，需要等待的中转时间增加，节点的端到端延时也增加。FLOOD性能略优于PUMA-UD。究其原因：FLOOD不需要PUMA-UD单向链路检测机制，因此FLOOD报文投递效率高且延迟低。当数据报文发送间隔越来越密，网内广播报文数量增加，数据报文碰撞概率增大，FLOOD和PUMA-UD报文投递率急剧降低10%以上。

图5 场景一中PUMA和FLOOD报文投递率示意图

图6 场景一中PUMA和FLOOD端到端延迟示意图

仿真场景二：在发送源与组播组之间存在双、单向链路且双向链路要比单向链路长(跳数多)的场景中，在网络负载不断增加情况下，验证新的路由算法适应双、单向链路环境的性能，与图1结构类似。仿真实例参数设置如表2所示。

表2 仿真场景二实验参数表

仿真环境中，节点数量50个，采用Two-ray ground reflection 无线传播模型，节点接收阈值RXThresh_随机设置(节点信号传输范围250～400米之间)，节点不移动。组播组1个，发送节点1个，接收节点20个。所有的接收节点在起始时刻加入组播组中，在30秒开始发送CBR，900秒结束发送，仿真时长910秒。并且要求CBR长度为256 KB，CBR每秒发送节点数量从2个到14个之间变化。

在单向路径跳数少于双向路径跳数的场景中，三种协议都能通信，仿真结果如图7和图8。总的来讲，随着单位时间内发送数据报文增加，端到端的平均延迟变大。随着数据报文发送数量增加，需要等待的中转时间增加，平均端到端延时也增加。FLOOD与PUMA-UD报文投递率和端到端延迟几乎持平，性能均大大超过PUMA。场景二中节点信号传输范围不同会产生大量单向链路，单向链路严重影响PUMA路由效率，故PUMA报文投递率最低且网络延迟最大。在负载较大(CBR超过8个)的场景中，PUMA-UD性能要略好于FLOOD。因为PUMA-UD中节点能避开单向链路，选择跳数多的双向链路，保障了报文投递的可靠性。

图7 场景二中三种协议报文投递率示意图

图8 场景二中三种协议端到端延迟示意图

仿真场景三：在发送源与组播组之间存在大规模不均衡链路的场景中，在节点无序移动且网络负载不断增加情况下，验证新的路由算法适应不断变化的单、双向链路共存环境的性能。仿真实例参数设置如表3所示。

表3 仿真场景三实验参数表

仿真环境中，节点数量50个，采用Two-ray ground reflection 无线传播模型，节点接收阈值RXThresh_随机设置(节点信号传输范围250～400米之间)，节点最大移动速度为20米/秒。组播组1个，发送节点数量从1个到10个之间，接收节点20个。所有的接收节点在起始时刻加入组播组中，在30秒开始发送CBR，900秒结束发送，仿真时长910秒。并且要求每秒传输CBR数量为2，且CBR长度为256 KB。

从图9和图10中可以看出，在节点无序移动的场景中，发送节点报文数量增多，网络中报文数量增多，报文传输碰撞概率增大，大量数据传输过程中被丢弃，数据报文传输率也就随之下降，端到端延迟增加。当网络中少于4个发送节点时，PUMA-UD报文投递率略低于FLOOD，且延迟更高，这是因为节点收到包含单向链路的MA报文时，发送uMA控制报文进行前向节点应答，并启动定时器等确认报文，所以整体报文投递率要低且端到端延迟也有所增加。当网络中多于8个发送节点时，PUMA-UD因为采用组播通信方式，大幅减少网络中数据报文传输数量，避免因数据传输碰撞导致的报文丢失的可能性，其性能略优于FLOOD。

图9 场景三中三种协议报文投递率示意图

图10 场景三中三种协议端到端延迟示意图

因此，在包含单向链路的无线网络场景中，网络负载低的情况下PUMA-UD和FLOOD都能获得较好的传输性能，FLOOD延迟略低于PUMA-UD。随着网络负载不断增大，PUMA-UD报文传输性能最终能略优于FLOOD。

5 结 语

本文提出的支持单向链路的PUMA-UD路由协议在路由建构时能主动探测网络传输过程中的单向链路，并在单双链路并存的场景中尽量使用双向链路进行数据报文传输，从而规避了单向链路的影响。在仅有单向链路的场景中，PUMA-UD设计uMA应答报文建立单向链路前向路由，利用单向链路来构建组播组mesh结构，从而最大程度上保证数据报文能达到组播组内所有节点。在仿真实验阶段，通过构建尽可能包含单向链路的仿真场景类型，评估了PUMA-UD支持单向链路传输的能力，并得出在网络负载较大时，PUMA-UD比PUMA和FLOOD性能更优。PUMA-UD路由协议存在以下不足：路由建立阶段，需要一跳广播uMA报文来建立前向路由，从而大量控制报文增加路由开销；路由维护阶段，在单向链路数据传输失败后全网广播控制报文，然而网络中大量控制报文可能引发网络风暴，继而导致数据报文投递率急剧下降。

[1] Zhao J,Govindan R.Understanding packet delivery performance in dense wireless sensor networks [C]//Akyildiz I,Estain D.Proc.of the SenSys 2003.LosAngeles ACM Press,2003:1-13.

[2] Jain K,Padhye J,Padmanabhan V N,et al.Impact of Interference on Multi-Hop Wireless Network Performance[J].Wireless Networks,2005,11(4):471-487.

[3] Duros E,Dabbous W,Izumiyama H,et al.A Link-Layer Tunneling Mechanism for Unidirectional Links[J].Ieice Transactions on Communications,2001,84(8):2058-2065.

[4] Fang Z,Wang W L.Research on unidirectional link routing algorithm for Mobile Ad Hoc Networks[C]//International Conference on Advanced Computer Theory and Engineering.IEEE,2010:V5-287-V5-290.

[5] Ji K,Li T J.Detection and Analysis of Unidirectional Links in Mobile Ad Hoc Network Under Nuclear Power Plants Environment[M]//Emerging Technologies for Information Systems,Computing,and Management.Springer New York,2013:871-878.

[6] Karnapke R,Lohs S,Nolte J,et al.Simulation of unidirectional links in wireless sensor networks[C]//International ICST Conference on Simulation TOOLS and Techniques.ICST (Institute for Computer Sciences,Social-Informatics and Telecommunications Engineering),2014:118-125.

[7] Wan S,Yu J,Wang N,et al.An Algorithm for Constructing Strongly Connected Dominating and Absorbing Sets in Wireless Networks with Unidirectional Links[M]//Advances in Wireless Sensor Networks.Springer Berlin Heidelberg,2014:41-50.

[8] Liu S,Ölveczky P C,Meseguer J.Formal Analysis of Leader Election in MANETs Using Real-Time Maude[M]//Software,Services,and Systems.Springer International Publishing,2015:231-252.

[9] Liu B H,Hsun C H,Tsai M J.Cooperative diagnosis for realistic large-scale wireless sensor networks[J].Computer Communications,2014,53:95-101.

[10] Karnapke R,Nolte J.Buckshot Routing with Distance Vectors in Three Application Scenarios for Wireless Sensor Networks with Unstable Network Topologies and Unidirectional Links[J].Sensors & Transducers,2015,185(2):53-67.

[11] Pokavanich W.Packet delivery scheduling for reliable multicasting over unidirectional link[OL] .2015.http://www.cs.ait.ac.th/xmlui/handle/123456789/198.

[12] 刘颖,于莉,李旭,等.针对单向链路的MAODV改进路由协议[J].北京邮电大学学报,2015,38(3):121-125.

[13] Marina M K,Das S R.Routing performance in the presence of unidirectional links in multihop wireless networks[C]//Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing.ACM,2002:12-23.

[14] Vaishampayan R,Garcia-Luna-Aceves J J.Efficient and robust multicast routing in mobile ad hoc networks[C]//IEEE International Conference on Mobile Ad-Hoc and Sensor Systems.IEEE,2004:304-313.

[15] 邱静怡,许骏,许德兴,等.移动自组网的单向链路优化路由算法AODVUD[J].小型微型计算机系统,2010,31(2):206-210.

IMPROVEDPUMAMULTICASTROUTINGPROTOCOLFORUNIDIRECTIONALLINKS

Qiu Jingyi

(GuangdongUniversityofForeignStudies,Guangzhou510006,Guangdong,China)

Studies show that asymmetric and unidirectional links are common in MANETs. However, most routing protocols are designed for bidirectional links. Therefore, we present an improved routing for unidirectional links (PUMA-UD), a multicast routing protocol that collects information about the unidirectional links on a path to make routing decisions. The collected information can furthermore be used for more effective neighborhood management and better communication quality. We adopted NS2 to simulate PUMA-UD and compared with the original PUMA (Protocol for Unified Multicasting through Announcement) and FLOOD in the same scene with unidirectional links. Simulated results indicate that PUMA-UD is superior to PUMA and FLOOD in packet delivery rate and end-to-end delay when network load increases.

MANET Multicast Routing Unidirectional links PUMA

TP393

A

10.3969/j.issn.1000-386x.2017.10.034

2016-12-22。广州市青年育苗项目(YM10075)；广州市科联共建项目(13G38)；广州市青年育苗项目(15Q11)。邱静怡，博士生，主研领域：无线自组织网络，传感网，车载网路由协议。