SNDQ-WISE：一种新的基于SDWSN的QOS路由协议

2019-09-13谭小波

沈阳理工大学学报 2019年4期

汤季，谭小波，朱腾

(沈阳理工大学信息科学与工程学院，沈阳 110159)

无线传感器网络(Wireless Sensor Networks，WSNs)是一种面向任务的自组织网络，其由大量密集部署的传感器节点、一个或者多个汇聚节点和基站组成[1]。随着物联网科技的不断进步，多功能新型传感器节点逐渐取代了经典无线传感器网络中的节点。这种节点具有识别多种数据类型的能力、更强和更远的无线通信能力和更完善的数据处理能力，从而使传统传感器网络焕然一新。随着无线传感器网络(WSNs)应用的广泛普及，高数据流量变化和多类型数据并存的应用场景逐渐增多，这些应用场景对路由协议的服务质量(QoS)的要求也逐渐提高。由于传统无线传感器网络本身的特殊性，随着无线传感器网络应用多样性和复杂性的增加，对网络的QoS保障能力也提出了更高的要求。传统的QoS路由面临的一些具体问题如下[2-4]：

(1)自身资源受限：传感器网络节点的资源约束主要是能量、带宽、内存，其中最重要的就是能源问题。(2)路由算法局部有效性：由于现阶段大多数路由协议都是分布式的，路由协议通过邻居节点相互交换信息来计算路径。这种局部的特性会导致路由算法只是在局部信息下是最优的结果。(3)QoS路由的指标参数复杂：无线传感器网络中不同的应用数据类型，对应不同的QoS需求。(4)多业务并存：传统的无线传感器网络QoS路由协议存在一个多业务并存的缺陷。传统的传感器网络QoS路由协议大多数搭建在只负责一种任务、采集一种信息的传感器节点上。

为了解决以上缺陷，软件定义无线传感器网络(SDWSN)概念被提出。SDWSN借鉴了有线网络端的软件定义网络(SDN)技术，SDN是一种数据控制分离、软件可编程的新型网络体系架构[5]。采用了集中式的控制平面和分布式的转发平面，两个平面相互分离。控制平面利用控制-转发通信接口和交换机对转发平面上的网络设备进行集中式控制，并提供灵活的可编程能力。控制平面的控制器可以掌握全网信息，转发平面只负责数据的转发[6]。大多数SDWSN由一个或多个控制器和多个软件定义传感器节点组成，通过集中式管理和可编程提高网络的灵活性[5]。但是SDWSN的研究还处于初级阶段，大多数的研究只给出了相应的概念，也有部分研究给出了具体方案具有一定的借鉴性。

软件定义无线传感器网络在WSN的基础上引入SDN技术，其已经成为了下一代WSN技术探索的主流方向。Luo等[7]在2012年首先提出了WSN与SDN结合的概念，可视为SDWSN的雏形。其在著名的OpenFlow基础上提出了Sensor OpenFlow，该协议初始化了SDWSN的南向接口协议，使其适用于WSN。同年，A Mahmud等[8]以另一种角度优化OpenFlow协议，在不改变OpenFlow协议本身的基础上设计了以一种基于OpenFlow的传感器设备flow-sensor，并赋予传感节点可编程能力。Faraci等[9]在SDN-WISE架构上，通过节点状态信息来提高网络的QoS。通过判断节点拥塞的状态和考虑数据等级来设置不同的丢包率从而提升整个网络的性能。该研究虽然在一定程度上解决了数据丢包率的问题，但是并没有涉及路由协议。冯凯鹰[10]提出了SDWSN路由协议切换技术，根据不同的时间段在控制端切换路由协议。该方法能有效提高网络生命周期，但是并没有涉及新的网络协议与QoS。

本文针对以上的路由协议都没有涉及QoS的问题，对比不同SDWSN架构的特点，最终以SDN-WISE架构作为设计的基础，设计一种新的SDNQ-WISE路由协议。提出了一种新的集中式非均匀分簇算SD-CUQCA和SD-QRA路由算法来实现SDNQ-WISE路由协议。该协议下构建的WSN网络拥有单网双拓扑结构，并结合时延与丢包率的敏感程度对数据进行分级，根据不同数据所需QoS等级的不同构建多路径路由，从而达到优化无线传感器网络QoS的目的。

1 SDNQ-WISE分簇路由算法

1.1 数据分级

本文提出的SDNQ-WISE路由协议应可以满足不同类型数据的不同QoS需求，当多功能传感器节点同时收集到多种类型数据，如果节点以相同的处理方式来处理这些数据时，就很难满足其不同的QoS需求，所以数据分级是本文的前提和基础[11]。

本文提出的数据分级依据是根据数据对时延与丢包率的敏感程度来进行交叉数据分级。具体的交叉优先级别划分如表1所示。

由表1可知，对时延和丢包率都很敏感的告警数据的数据优先级别最高，其次是对时延很敏感的视频和音频数据以及对丢包率比较敏感的具体物品批量数据。最后则是诸如温度、湿度等周期型数据。

表1 数据分级排序表

1.2 SDNQ-WISE体系结构

图1为SDNQ-WISE的体系结构。

图1 SDNQ-WISE体系结构图

本体系结构由应用层、控制器层和数据层组成。应用层通过配置文件可以动态修改分簇算法的参数配置和路由算法的配置。控制器层由网络链路模块、网络拓扑模块和网络路由模块组成。数据层是由一个Sink节点、若干簇头和许多簇成员节点组成。

控制器层中的网络链路模块通过经典的LLDP协议来发现和维护全网的链路信息将每个节点的相关信息上传到控制器，并存储到控制器中来为接下来的模块做准备。网络拓扑层通过网络链路模块获取的传感器节点信息来建立和维持全局网络拓扑。数据层中，Sink节点是由许多支持SDNQ-WISE的多功能传感器节点构成的[12]。

1.3 SD-CUQCA分簇算法

集中式非均匀分簇算法SD-CUQCA结合控制器中存在的初始全网拓扑信息将原有的扁平平面拓扑拉伸成层次型单网多拓扑结构。层次型单网多拓扑结构采用多跳的方式将数据传输到汇聚节点，节省了传输消耗的能量。不同的拓扑结构对应不同类型的数据，每种类型的数据在对应的拓扑结构下被提供最优的QoS保证。层次型单网多拓扑模型，为骨干网的路由算法SD-QRA提供了前提条件。

SD-CUQCA借鉴非均匀分簇算法(CUCA，Centralized Unequal Clustering algorithm)思想，并在选取簇头时综合考虑了节点拥塞度、节点链路连通度、节点能量和节点间的距离来选取簇头节点。SD-CUQCA使簇头的产生更加均匀，并提出了异簇双簇头的思想，与传统双簇头思想不同[13]，异簇双簇头解决了传统双簇头可能产生的簇头节点并不能完全覆盖簇内成员的问题，异簇双簇头使整个网络形成两种拓扑结构。对于每一个簇，簇内成员根据感知数据的类型来选择相对应的簇头节点传输，提供了QoS保障，控制器端通过其掌握的全网信息执行簇头的选择与簇成员入簇，减少了节点之间频繁的信息交换，减小网络负担，增加了网络寿命。

(1)

式中：Ri为节点i的竞争半径；Rmax为网络初始化设置的最大竞争半径；c为节点竞争半径的权重参数；Di为节点i到Sink的距离；Dmax为网络中所有节点距离Sink最远的距离；Dmin为网络中所有节点距离Sink最近的距离。

SD-CUQCA采取的是非均匀分簇方式，其核心思想是：网络中距离Sink越近的节点的簇半径更小，通过这种方式靠近Sink的区域就会形成更多的簇，并且这些簇内将会包含更少的簇成员；网络中远离Sink的簇半径尽量大，簇成员较多。这样的分簇方式使靠近Sink区域的节点有更多的能量来转发网络数据包而不是将更多的能量消耗在大量数据的处理上，避免了靠近Sink区域的簇头节点能量过早消耗殆尽而产生“能量空洞”。簇半径和簇成员的多少取决于每个簇头节点的竞争半径，设定竞争半径的距离小于而且在与簇头距离为的范围内不存在另一个簇头，这样就保证簇头与簇成员、簇头与簇头之间消耗的能量较小。所以本文应用Min-Max Scaling思想定义公式(1)来计算每个节点的竞争半径。

(2)

(3)

控制器结合网络初始化阶段获取的全网初始拓扑信息，选出簇头与簇成员。在选择簇头时，根据节点拥塞度、节点链路连通度、节点能量和节点间的距离来综合选取簇头节点，权重参数α、β、δ、ε、η用来调节各个属性在选择簇头时的影响程度。控制器对于每个节点首先根据公式(1)计算竞争半径，并维护一个邻居列表(rNb)来存储节点竞争半径内的邻居节点ID。根据公式(2)、公式(3)计算每个节点成为低拥塞度簇头和高链路连通度簇头的概率[14]。

(4)

(5)

SEi=∑j∈Nb(i)REj

(6)

式中：Qi为节点i缓存区队列被占用长度；Li为节点i区队列总长度；Nb(i)为节点i的邻居节点集合；si,j为节点i向节点j发送数据包成功到达的大小；mi,j为节点i向节点j发送数据包的大小。

控制器对每个节点的和进行从大到小排序并存到两个簇头概率列表(LPnc，LPlc)中，将LPnc和LPlc中最大值节点ID依次放到簇头列表(LCHnc、LCHlc)中，并在LPnc和LPlc中删除该节点rNb，直到整个LPnc和LPlc为空，即所有节点被覆盖。具体算法伪代码如表2所示。

经过算法1后，得到了簇头列表LCHnc和LCHlc。当确定网络簇头后，描述簇成员入簇过程。簇成员入簇取决于其所处的位置，但是有的节点会在多个簇的交叉位置，需要判断该节点的归属。所以定义了一个簇头连接度来判断节点的归属。

表2 簇头选取机制伪代码表

(7)

式中：Coni为簇头节点i通度；REi为簇头节点i的剩余能量百分比；Di,j为簇头节点i点j的距离；α为权重参数。

节点j根据公式(7)计算其到候选簇头i的连通度，选择值最大的作为自己的簇头节点。控制器对每类簇头维护两个簇成员列表(LCMnc、LCMlc)，对每一个非簇头节点维护两个候选簇头列表(LCHnctoJion、LCHlctoJion)，根据算法1来初始化两个候选簇头列表。簇成员入簇伪代码如表3所示。

本次展览是一份复兴传统工笔画艺术的文化自觉，一种发展现代工笔画创作的文化担当，同时也是张伟民对自身学术与艺术道路的一次梳理。

表3 簇成员入簇伪代码

经过算法2后，控制器中维护了两个簇头列表LCHnc和LCHlc，以及与之对应的两个簇成员列表LCMnc和LCMlc。控制器会生成并下发簇头通知包(CH_NP)、簇成员通知包(CM_NP)和相应的流表规则到对应的传感器节点。整个分簇过程结束后，将会形成如图2所示的网络拓扑图。

图2 非均匀QoS分簇形成图

如图2所示，整个网络被分为无数个圆形簇，每一个簇有一个簇头节点与若干个簇成员节点。整个网络拥有两种簇头节点，低节点拥塞度簇头节点和高链路连通度簇头节点。两类簇头节点分别与其簇成员形成两种网络拓扑结构。为本文接下来的骨干网路由协议SD-QRA提供了现行条件。

1.4 SD-QRA路由算法

全网拓扑结构形成后，控制器执行SD-CUQCA算法，传统WSN原有的扁平平面拓扑被拉伸为层次型非均匀拓扑。根据其覆盖半径内的节点，建立无向连通图，如图3所示。

(8)

图3 簇头节点无向连通图

通过公式(8)计算其下一跳节点直到下一跳节点是Sink为止。大部分满足QoS需求的路由算法的设计都是根据数据的不同而采用不同的算法公式实现的，但是其并没有给出具体的算法公式，并且多个算法公式的轮换会使算法的容错率降低。本文将多路径的构建融入一个算法，并通过改变不同公式因子的权重参数来构建不同的路径，提高了算法的容错率。表4针对表1给出不同数据类型级别的权重的取值。

表4 不同数据类型级别对应权重表

由表4可以看出，本文将权重的值设置为0或者1，并根据其对应数据级别时延和丢包率的敏感度选取。

控制器根据表2中每种数据级别对应的权重与公式(8)为每种数据级别计算下一跳选节点，形成的路由树如图4所示。

图4 网络路由树初始化图

如图4所示，每个簇头节点理想情况下存在两条不同的路径来传输不同数据级别的数据，也可能出现两种路径重叠的情况，经过以上过程骨干路由树建立结束。值得注意的是，可能会产生簇头节点接收到的数据并不适合其传送，当发生这种情况时，簇头节点会主动发送消息给控制器，控制器根据改数据类型和全网拓扑来重新规划路径并下发流表规则转发该类型数据。

2 仿真验证与结果分析

针对传统的无线传感器QoS路由算法存在的节点能量消耗过大、很难选取最佳路径的问题，引入软件定义无线传感器网络的概念，并使用SDN-WISE架构来设计一种新的SDNQ-WISE路由协议，包括对数据进行分级及设计了一种SD-CUQCA分簇算法和SD-QRA路由算法来实现该路由协议，并对其进行仿真验证，仿真环境如表5所示。

表5 仿真参数明细表

图5为簇头的个数随Rmax的改变而改变的情况。

图5 SD-CUQCA簇头形成数量

由图5可知，当控制因子c不变时，Rmax的增大会导致簇头数量的减少。由公式(1)可知，Rmax和竞争半径成正比关系，竞争半径越大就会导致簇头节点覆盖的簇成员越多，又因为一个簇头的竞争半径内不存在同一类簇头节点，所以覆盖整个网络所需的簇头节点减少，得出簇头的个数与Rmax的值成反比的结论。当Rmax不变时，簇头的个数会随着控制因子c的增大而减少，根据公式(1)，c代表了节点到基站的距离对该节点的竞争半径的控制，c增加竞争半径随其增加，使得整个网络的簇头减少。

通过以上分析得出，SD-CUQCA分簇算法的簇头数量没有明显的抖动，说明整个网络的簇分布比较均匀，并没有发生Leach协议中大量簇头聚集的情况。

图6描述的是SDN-WISE与SDNQ-WISE协议运行时间与数据丢包率的关系。

图6中Class0表示SDN-WISE方案的数据、Class1、Class2、Class3和Class4分别表示SDNQ-WISE协议中表4数据级别1、数据级别2、数据级别3、数据级别4数据。由图6可知Class1类型的数据与Class3类型的数据丢包率明显低于Class0、Class2和Class5类型数据，这是因为Class1与Class3类型数据是对丢包率敏感的数据，它在向Sink节点传输数据时的路径会考虑节点的链路连通度选择连通度高的路径。而Class0表示SDN-WISE数据类型，其选择路径时并没有考虑链路质量只按照最短路径来传输所以其丢包率相对于SDNQ-WISE协议平均高出1个百分点。Class2和Class5类型数据对丢包率不敏感所以其丢包率与Class0类型数据相差无几。由此可得出，SDNQ-WISE降低了对丢包率敏感数据的丢包率，有效的提高了网络的QoS。

图6 包率统计图

图7描述的是SDN-WISE与SDNQ-WISE协议的数据端到端时延。

图7 端到端时延

图7中Class0代表的是SDN-WISE数据，Class1、Class2、Class3和Class4分别表示SDNQ-WISE协议中表4数据级别1、数据级别2、数据级别3、数据级别4数据。从整体上来看，所有类型的数据时延随着仿真时间的增长而增长。Class2与Class1类型数据是对时延敏感的数据类型，其时延明显低于那些对时延不敏感的数据类型。Class0代表SDN-WISE方案数据时延情况，可以看出其时延要比SDNQ-WISE中Class3和Class4类型数据时延要低，比Class1和Class2类型数据时延要高。这是因为SDN-WISE原路由方案采取的是最短路径路由，其在选择下一跳的时候只考虑了距离因素并没有考虑节点的拥塞度，所以其时延要高于既考虑了节点拥塞度也考虑了距离的Class1与Class2类型数据。但是由于Class3与Class4类型数据对时延不敏感，其选择下一跳只考虑了能量因素，所以其时延要高于Class0类型数据。综上，可以得出SDNQ-WISE协议相对于SDN-WISE提高了特定数据类型的时延，有效的提高了网络的QoS服务质量。