面向软件定义网络的多跳D2D通信的路由协议∗

苑毅，王星锐，周泽，刘治福

(兰州文理学院电子信息工程学院，甘肃兰州，730000 )

0 引言

作为新兴的网络结构，软件定义网络(Software Defined Networking, SDN)将控制平台和数据平台进行分离[1].控制平台采用集中式管理，并具有可编程特点，通过SDN控制器决策路由，这不同于逐跳机制，依据数据转发节点决策路由.因此，基于SDN的结构提高了网络兼容性，降低了数据转发时延.

近期，研究人员将基于SDN结构应用于未来5G网络，将网络内的一个或多个模块虚拟化.现有的研究表明，SDN能够提高服务的灵活性、编程化，这要归功于SDN能够以简单、智能方式控制和管理网络.

此外，多数研究人员基于SDN控制[2,3]下，研究设备至设备(Device-to-Device, D2D)通信[4].这些研究表明，相比于传统自组织网络路由协议，由于SDN能够快速响应于网络拓扑的变化，基于SDN的路由服务具有更好的扩展性和数据包传递率.

Mehran等[5]针对无线分布网络(Wireless Distributed Networks, WDNs)，提出SDN的混合结构.该结构通过两个不同的频带将控制信号与数据转发进行隔离，即带内的P2P数据转发(未注册频带)和控制器与移动节点间的点到多点控制信号.仿真数据表明，提出的网络结构通过避免多跳泛洪，提高WDNs的扩展性和可靠性.然而，该结构仍要求SDN控制器向所有终端用户泛洪链路状态数据库(Link State Data Base, LSDB)，其限制了网络的扩展性.

文献[5]针对WDNs，提出混合SDN结构(HSAW).HSAW算法要求控制器泛洪所有链路状态LSDB，增加了通信开销，也限制了网络的可扩展性.

为此，针对基于SDN的蜂窝网络，提出多跳D2D路由协议(Multi-hop D2D Routing, MD2D).MD2D路由只需下一跳节点信息，子控制器无需向节点广播LSDB信息.该路由机制适用于大型的移动行人通信网络环境.该网络环境内，移动节点想与周边节点分享信息.

1 网络结构

基于SDN控制器的控制和管理，考虑如图1所示的网络结构.在该控制结构中，SDN控制器连接每个基站(Base Station, BS)或接入点(Access Point, AP).将这些BSs和Aps统称为子控制器.

每个子控制器管理其覆盖范围内移动节点的数据转发.并且，每个子控制器通过蜂窝核心网络(Evolved Packet Core, EPC)连接Internet或其他外网.在EPC内有个核心的SDN-控制器，其管理EPC覆盖范围内的子控制器.

如图1所示，EPC内设SDN控制器，并由SDN控制器负责管理EPC覆盖范围内的子控制器.同时，它给每个子控制器分配Id，命名为CR-Id.此外，SDN控制器管理每个子控制器的接入、数据存储.

图1 系统结构Fig 1 System structure

每个移动节点至少具有两个接口：LTE(蜂窝频率)[6]和WiFi(未注册频率).LTE接口用于连接子控制器，而WiFi用于完成多跳的D2D通信.每个移动节点通过蜂窝频率向子控制器发送链路状态信息LSDB.子控制器依据移动节点所接收信息进行数据转发决策.当移动节点初始一条数据流，它就从子控制器接收数据转发的指导意见.

2 MD2D路由

2.1 路由发现

在MD2D路由中，每个移动节点建立两个表：流量表(Flow Table, FT)和邻居表(Neighbour Table, NT).其中，FT用于存储来自子控制器的传输的转发规则，而NT用于维持一跳邻居节点的信息.

当移动节点有数据Data需要传输时，首先从NT表寻找是否已有合适的路由.若已有通往目的节点路由，就将此路由Rid加载到Data包，并依据Rid转发至下一跳节点.若NT内没有合适的路由，移动节点就将数据Data缓存.并向子控制器发送流量请求消息(Flow Request Message, FREQ), 请求一个有效路由.FREQ消息携带了目标节点的地址，FREQ的编号(Req-Num)以及流量类型.

与移动节点类似，子控制器也建立了两个表：转发信息表(Forwarding Information Base, FIB)和流量请求表(Flow Request Table, FREQT).其中，FIB保存了已有路由信息.而FREQT保存了所收到的流量请求消息的信息.一旦收到FREQ消息，子控制器首先从FREQT表确认是否已收到相同编号(Req-Num)的消息.若收到相同编号的FREQ消息，子控制器就直接丢弃此消息[7].如果没有收到，则将此FREQ消息存于FREQT，并为此FREQ消息所请求的数据传输构建合适的路由Rid，并将此Rid加入FIB.源节点依据SPF算法构建从源节点至目的节点路由.并确认已选择路由是否满足传输数据的服务质量.

收到FREQ后，子控制器需要向移动节点回复消息(Flow reply,FREP)，其包含了蜂窝指示(Cellular Indicator, CI) .且CI为二值变量.如果有满足服务质量的路由，就将CI设置为False，若没有满足服务质量的路由，就将CI设置为True.

FREP消息携带了路由ID，CI和未到达标志(Unreachable Flag, UnF)和中间节点的顺序列表(Ordered List of Intermediated Nodes, OLINs)，其格式如表1所示.

?

OLINs包含从源路由至目的节点间的中间节点列表.而CI表示数据转发方式.若CI为True，则进行蜂窝数据传输；若CI为False，则进行MD2D数据传输.

一旦收到FREP消息，移动节点就从FREP表中获取数据包的下一跳转发节点.并依据节点数据转发.

图2显示了移动节点与子控制器间的FREQ、FREP转发过程.

图2 FREQ、FREP间的传输过程Fig 2 The transmission process of FREQ and FREP packet

此外，子控制器设定蜂窝指示(Cellular Indicator, CI)，并将已选择路由加入流量请求回复消息(Flow reply,FREP).

2.2 路由维护

数据包传输阶段的每一跳需负责数据包转发至下一跳节点.为了维护数据传输的可靠性，每跳均采用确认机制.如果一个移动节点在数据传输过程中检测错误，该移动节点就产生一个流量错误消息(Flow Error Message,FERR).

FERR消息携带了此数据包的路由ID以及错误类型. 错误类型指链路断裂(Link_ broken)、低能量(Low battery)、未知错误(Unknow_ Error).一旦收到FERR消息，子控制器就广播FERR，其携带了路由Rid.随后，子控制器从它的FIB进行搜索，寻找与路由Rid匹配的路由信息，再更新LSDB，并重新执行SPF算法，重新寻找从源节点至目的节点的最短路径.

一旦收到FERR消息时，移动节点就停止依据路由Rid传输数据，并从FL表中寻找匹配的路由Rid，并将此路由设置无效.

2.3 SPF路由算法

作为链路状态算法，最短路径优先(Shortest Path First, SPF)算法广泛应用于移动网络.SPF路由先获取网络全局拓扑信息，再依据这些拓扑信息，并结合Dijkstra最短路径计算最短路径，再依据最短路径传输数据.

图3 SPF路由算法示例Fig 3 Example of SPF routing algorithm

3 性能分析

3.1 仿真环境

引用Matlab仿真器建立仿真平台，并分析MD2D路由性能.在方形区域1 000 m × 1 000 m内部署2 000个节点，每个移动节点的通信半径为250 m.令q(t)表示在间隔[t,t+ς]内链路状态变化概率，其定义如式所示：

其中λu表示移动网络内链路断裂率.在实验仿真过程中，λu值从0.5至5变化.假定网络内所有链路变化q(t)保持一致.

此外，为了更好地分析MD2D路由性能，选择HSAW路由作为参照，并分析它们在WiFi带宽和蜂窝带宽内的开销.

3.2 数据分析

3.2.1 实验一

本次实验参数如下：λu从0.5至5变化，节点数为500，流量路由数为2 000，ς=1 s.实验数据如图4、5所示.

图4显示了在WiFi带宽内MD2D和HSAW的路由开销.

图4 在WiFi带宽内路由开销Fig 4 Routing overhead in WiFi band

图5 在蜂窝带宽内路由开销Fig 5 Routing overhead in Cellular-band

从图4可知，在WiFi带宽内, MD2D路由的开销高于HSAW.原因在于：MD2D路由将路由ID号加入至数据包首部.但从图3可知，增加的路由开销并不多，只是微略地增加.此外，观察图4不难发现，路由开销随λu变化呈正态分布变化.当λu从0.5增加至1.5时，路由开销呈增长趋势，但当λu从1.5增加至5时，路由开销又随之下降.这主要是因为：最初λu增加，导致多个链路断裂，需要重建路由，但当λu增加至一定数量后，在开始传输数据前，存有可连通的链路并不多，这反而无需去建立路由.

图5显示了蜂窝带宽内的路由开销.从图5可知，两个路由协议的路由开销随λu变化趋势一致.相比于HSAW，提出的MD2D路由具有更低的路由开销.这主要因为：HSAW路由需消耗额外带宽，广播网络拓扑变化信息.

依据MD2D路由和HSAW路由机制的不同，MD2D的路由维护阶段所产生的开销高于HSAW，原因在于子控制器需要发送FREP消息，更新移动节点信息.然而，从图5可知，MD2D路由的总体路由开销仍低于HSAW.

3.2.2 实验二

本次实验分析移动节点数对路由开销的影响.实验参数如下：λu=5，移动节点数从0至2 000变化，流量路由数为4倍的移动节点数，例如，当移动节点数为500，则流量路由数为2 000.ς=1 s.实验数据如图6所示.

从图6可知，节点数的增加提升了路由算法的开销.相比于HSAW，MD2D的路由开销随节点数增加的速度更为缓慢.且MD2D的路由开销低于HSAW.尤其在节点数大的情况，MD2D的路由开销远低于HSAW.例如，当节点数为2 000时，MD2D的开销约15 Mbits，而HSAW路由的开销上升至40 Mbits.

图6 路由开销随节点数的变化情况Fig 6 Routing overhead versus number of nodes

图7 存储空间的消耗节点数的变化情况Fig 7 Memory usage versus number of nodes

3.2.3 实验三

本次实验分析移动节点数对节点存储空间的消耗.实验参数如下：λu=5，移动节点数从0至1 000变化，流量路由数为5倍的移动节点数，例如，当移动节点数为500，则流量路由数为2 500.ς=1 s.实验数据如图7所示.

从图7可知，MD2D路由的存储空间的消耗远低于HSAW路由.这归功于：在MD2D路由中，每个移动节点只需保持跟踪FT表中的需求.而子控制器完成路由的计算以及相应处理.与MD2D路由不同，HSAW路由的移动节点需要周期地更新NT表.由于需频繁地执行SPF和计算NT表，必然增加CPU处理数据.

此外，观察图7不难发现，MD2D路由的存储空间的消耗随节点数增加而变化缓慢，而HSAW路由随节点数增加而呈指数上升.

4 总结

本文基于软件定位网络SDN，提出新的多跳MD2D路由.该MD2D路由能适应于不同的基于SDN的无线网络.通过抑制子控制器向移动节点广播LSDB信息，只需简单地传输下一跳信息，降低了路由开销.仿真结果表明，提出的MD2D路由的控制开销得到有效控制.

后期，将进一步分析MD2D路由，扩展其应用环境，并分析能耗以及数据传输时延.