软件定义传感器网络重配置算法研究

2016-12-01沈连丰朱亚萍丁兆明燕锋邓曙光

通信学报 2016年7期

关键词：路由链路定义

沈连丰，朱亚萍，丁兆明，燕锋，邓曙光

（1. 东南大学移动通信国家重点实验室，江苏南京 210096；2. 湖南城市学院通信与电子工程学院，湖南益阳 413000）

软件定义传感器网络重配置算法研究

沈连丰1，朱亚萍1，丁兆明1，燕锋1，邓曙光2

（1. 东南大学移动通信国家重点实验室，江苏南京 210096；2. 湖南城市学院通信与电子工程学院，湖南益阳 413000）

为了提高无线传感器网络的性能及其适应性，提出一种软件定义传感器网络的架构并重点研究其网络重配置算法。算法首先运用Voronoi图理论，寻求SDSN全覆盖问题中保证网络能量均衡的最优感知半径分配，以达到目标区域的K重覆盖；其次基于单纯复形理论，提出一种基于边缘链群最小生成元和节点度的集中控制方法，以最简练的网络拓扑结构为目标，同时保证整个系统的连通性以及突发区域的顽健性；考虑SDSN中路由协议在动态环境的自适应性，提出一种基于多业务QoS的SDSN路由优化算法并进行了仿真，结果表明所提路由算法能够有效分配资源，满足多业务QoS需求并延长网络的生命周期。

软件定义传感器网络；覆盖优化；拓扑控制；路由优化

1 引言

无线传感器网络（WSN，wireless sensor networks）一般具有大规模、自组织、随机部署等特点[1]，但受到环境复杂、传感器节点资源有限、网络拓扑经常发生变化等影响，使其应用受到极大挑战[2]，因而拓扑控制等技术成为研究热点。拓扑控制通过功率控制、节点休眠调度等机制尽可能减少传感器节点的能量消耗，同时作用于媒体访问控制（MAC，media access control）层和路由层之间，能有效降低通信干扰、提高MAC协议和路由协议的效率，并为路由层提供足够的路由更新信息，而路由信息表的变化又反过来作用于拓扑控制机制，影响网络的连通性和能量消耗等[3,4]。然而，传统的WSN在网络部署之后，其节点行为和由这些节点所提供的网络功能很难发生改变，导致了网络资源利用率低、策略更改困难和网络难于管理[5]，这主要源于WSN网络节点固有的分布式属性，每一个节点都是一个独立的自治系统，不利于网络功能的灵活扩展。

软件定义网络（SDN，software-defined network）技术可以将网络控制从以连接过程为核心的闭合模式转变成以组网过程为核心的开放模式。SDN将传统的紧耦合网络架构解耦成应用、控制、基础转发设施3层分离架构[6]，实现网络应用的可编程、整体网络控制的中心式管控以及节点网络单元的简单化、通用化和低成本化。将SDN与WSN相结合，可进一步提高无线传感器网络的能量利用效率，简化硬件结构，降低成本，并且有机地整合网内节点的分布式管理机制，实现统一的网络管理控制系统，从而提高WSN的信息采集和管理效率，形成全网优化的无线传输和资源分配。

本文基于 SDN技术，提出一种基于软件定义网络的无线传感器网络架构及其网络重配置算法以解决覆盖优化、拓扑控制和路由选择等问题。该网络简称软件定义传感器网络（SDSN，software-defined sensor network），所提算法运用Voronoi图理论、单纯复形理论并考虑SDSN中路由协议的自适应性及其在动态环境下的性能，以达到目标区域的K重覆盖、全局节点功率最优、保证多个业务同时进行数据传递以及各自QoS（quality of service）的最大化等目标。

2 相关工作

软件定义传感器网络是近年提出的新概念，目前已成为研究热点之一。如文献[7]给出了一种软件定义无线传感器网络（SD-WSN，software-defined WSN）架构，该架构包含应用层、控制平面和数据平面 3部分，控制平面和数据平面之间通过 SOF（sensor OpenFlow）接口协议互连，从而实现了下层网络单元的可编程；文献[8]提出了软件定义传感器网络架构的概念，其所述的软件定义传感器网络中传感器节点可以通过空中下载动态实现系统采集任务的转变；文献[9]定义了控制平面的角色生成和传送机制，以及可配置的传感器节点的硬件实现单元；文献[10]从SDN和WSN模型结合实现的角度对WSN网络拓扑、路由和传输任务等方面获得的有益性进行了分析，结果表明在WSN中采用软件定义的网络架构有利于WSN网络中路由问题和传输问题的解决，能够降低网络成本和能量消耗。

目前，关于SDSN的研究工作主要集中在方案可行性方面，对于如何利用软件定义的优势解决 WSN中几个重要问题方面的研究涉及尚少。为此，本文在SDSN网络架构下对其重配置算法进行较为深入的研究，包括覆盖优化、网络拓扑和路由协议等。

覆盖可以看成是对网络服务质量的一种度量，其重要因素之一是网络对周边事物的感知能力[11]。在WSN节点覆盖问题中，已有不少典型的计算方法，如最坏与最佳情况覆盖[12]、连通传感器覆盖控制算法[13]等，但其优化策略多是通过网络节点的初始部署来实现的，未考虑网络拓扑发生变化或者网络突发事件发生时如何实现网络的实时覆盖优化。近期关于网络覆盖问题的研究注重对覆盖空洞的检测和修复，提出了基于各种理论的空洞检测和修复方法，如基于同调理论的覆盖空洞检测算法[14]、基于Voronoi图的分布式节点协同空洞检测和修复算法[15]、多目标网络覆盖质量约束下可编程节点执行多个重编程任务时所需能量消耗的最小化问题[16]等。

传统的WSN网络拓扑控制，主要通过分布式的功率调节控制、分级拓扑控制或者功率模式控制方法来延长无线传感器网络的生命周期，提高其能量效率[17]。由于采用分布式的方法，网络节点不能有效地获取全网节点在位置、剩余能量、感知范围、发射功率等方面的信息，单节点只能根据自身以及其相邻节点的信息进行局部的网络控制，网络的性能不能达到全局最优。关于拓扑控制算法的研究通常基于随机图理论模型[18]，例如基于邻近图的功率控制算法等。近年来已有更多的拓扑模型被应用于WSN的拓扑控制研究中。如文献[19]将博弈理论模型应用于拓扑控制研究，提出了一种非合作式博弈的分布式拓扑控制方法，用于动态设计高效和能量均衡的网络拓扑；文献[20]提出了一种单纯复形理论应用的简化算法，用来删除网络拓扑中多余的节点，并保持拓扑结构的不变性。

WSN路由算法的目的是寻找优化路径以将有用信息从源节点发到目的节点。经典的路由协议包括低功耗自适应分层路由协议[4]、基于地理位置和能量信息的路由协议等[21]。随着SDN研究的深入，其路由协议的研究也受到重视。文献[22]提出一种将SDN技术用于ad hoc 网络（SDNAN, softwaredefined networking in ad hoc networks）的路由协议，可以动态调整路由规则来适应不同的用户需求。文献[23]提出一种基于 SDN 技术的路由算法，用于Internet 中自治系统间的路由计算。但是，现有的WSN网络路由协议设计主要考虑如何降低整个网络的能量消耗，而在路由协议的自适应性以及动态环境下路由协议的性能方面尚有很大的改进空间。

基于已有软件定义传感器网络架构，本文提出SDSN架构，通过应用层中覆盖优化、网络的拓扑控制和路由协议等相关应用，设计网络重配置算法，从而完成整个传感器网络参数的重新设置。本文提出一种基于Voronoi图的动态覆盖算法，算法中管控中心可以通过调节节点的感知范围实现网络的全局覆盖优化，实现网络资源的全局共享；提出一种基于单纯复形理论的拓扑控制算法，在已求知的网络K重覆盖的基础上，借助于SDSN网络架构的全局信息，算法寻找最简练的网络拓扑结构，使网络性能达到全局最优；提出一种基于多业务QoS的路由算法，利用SDSN的控制器获取整体网络的链路状态和每个节点上的能量消耗等信息，在发生多个并发事件时提高网络路由重配置的准确性和实时性。上述算法有机结合并通过软件定义实现无线传感器网络的拓扑结构和资源的重配置，从而有效提高其性价比并拓展应用领域。

3 软件定义传感器网络架构模型

图1 SDSN体系架构

为了和SDN基本架构一致，本文提出的SDSN体系架构主体上也分为基础设施层、控制层和应用层3层。由图1可见，所提架构实质上是由大量软件定义传感器节点和集中式管控中心2部分构成，其节点结构由传感器模块和通用可编程数据收发单元组成，其网络覆盖、拓扑控制、路由协议等网络控制技术由集中式管控中心统一配置，并将相应配置文件分发到各节点的数据收发单元，以获得全局最优的网络性能。这一架构的主要特点在于可根据用户和网络状态需求，利用可编程控制的网络单元，定制算法、策略、协议等内核可高度重构化的网络支撑系统，通过OpenFlow等相关协议开发面向对象的开放式管理与业务适配接口，实现软件定义传感网信息的抽象化和跨层网络控制集成化，从而建立起具备统一网络控制能力的适应集中控制、节点网络单元简化、网络管理高效、性能全局最优等特点的新型传感器网络架构体系，即该架构的每一层均服务于传感器网络的重配置，也可以说在每一层中都增加了网络重配置单元并且用软件来实现。

在网络部署完毕后，管控中心通过实时配置各感知节点的感知范围，使监测区域被SDSN感知并实现全覆盖。

4 SDSN的网络重配置算法

如前所述，采用所提的SDSN架构及其网络重配置算法来解决传感器网络的覆盖优化、拓扑控制和路由优化等问题，SDSN网络重配置算法由基于Voronoi图的动态覆盖算法、基于单纯复形理论的拓扑控制算法和基于多业务 QoS的路由算法所构成，它们有机结合，共同完成网络的拓扑结构以及资源的重配置。

4.1 基于Voronoi图的动态覆盖算法

SDSN的网络拓扑通常是动态变化的，当有节点产生移动或失效时，网络中各节点的感知范围需进行调整以达到对监测区域的完全感知覆盖；同时，若网络中某一区域产生突发事件，相关联的节点也应实时调整自己的感知范围，以增加对该区域的感知精度，实现对突发事件的协同感知。本文针对SDSN网络重配置算法中的覆盖需求，提出一种基于Voronoi图的动态覆盖方法，通过引入Voronoi图理论将监测区域进行凸域划分，并综合考虑网络的能量均衡和覆盖冗余，寻求一种最优化的节点感知半径重配置方案，来解决网络部署或网络拓扑变化时对监测区域的感知全覆盖问题，以及网络中发生突发事件时对目标事件区域进行多点协同感知、实现K重覆盖的问题。

Voronoi图是计算几何中一种空间分割的重要方法，定义监测区域A和区域内随机部署的感知节点 S = {si|i = 1,2,… , N}，通过计算集合S中元素的最邻近距离，可以将目标区域分割为多个相邻接的凸域，划分后由确定的凸多边形称为关联于si的Voronoi域V(si)，其中，H ( si, sj)表示线段垂直平分线的si一侧的半平面，可知对于每一元素si，其Voronoi域中的任何点到si的距离都小于该点到S中其他元素的距离。若两节点的关联Voronoi域存在公共边，则这两点互为邻居节点，连接两两邻居节点的线段所形成的图是Voronoi图的对偶图，称为 Voronoi划分对应的Delaunay三角剖分。

基于 Voronoi图的动态覆盖算法的执行过程如图 2所示，算法通过实时监测网络的全局信息，将SDSN的覆盖优化问题分为：1）通过对区域的Voronoi划分和构建Delaunay三角剖分，寻求区域全覆盖问题中保证能量均衡的节点感知半径最优化配置；2）通过Voronoi图和多目标决策，选择最优的节点子集并调整其感知半径，求解突发事件区域 K重覆盖问题的2个子问题。具体方法如下。

图2 SDSN中基于Voronoi图的动态覆盖算法执行过程

1) 最优化感知半径配置策略

SDSN覆盖优化算法的Voronoi模型如图3所示。对于监测区域A和区域内的感知节点集S，算法首先对监测区域进行Voronoi凸域划分，具体的Voronoi划分示意如图3（a）所示，其中，实线代表Voronoi多边形，虚线表示对应的Delaunay三角剖分。算法采用逐点插入法构建 Delaunay三角剖分，其步骤为：①构建节点集S的最小凸集，生成初始Delaunay三角剖分；②随机排列节点集S中的所有节点；③对任一节点Sr执行内插操作：首先定位包含Sr的三角形SiSjSk，然后连接Sr和三角形各个顶点，将其剖分成3个子三角形，最后利用边交换法规格化三角剖分。这样，就将全覆盖问题分解为计算局部Delaunay三角形的覆盖问题。

一般认为在覆盖问题中，节点的感知行为是能量消耗的主要因素，将节点si的能耗建模为感知半径Ri的函数Pi(Ri)，引入节点的剩余能量Ei，则整个网络的剩余生命期可以表示为

对任一Delaunay三角形 ∆ S1S2S3，其顶点sj的坐标为(yj)， j∈ {1,2,3}，为最小化覆盖冗余，3个顶点的感知圆盘在三角形内交于一点，算法根据相应节点的权重 l( sj)（在网络初始部署阶段可令Rj=0）计算交点cg，使权重较小的顶点至cg的距离较近，则可得到节点sj的一种半径分配rj=d(si, cg)，计算过程如图3（b）所示。算法对与sj邻接的所有Delaunay三角形进行依次计算，并在所产生的半径分配集中选取最大值作为sj的优化半径分配。其他节点通过依次迭代也可得到各自的优化半径，从而网络获得最优的感知范围配置方案，在保证区域全覆盖的基础上，可以达到能量均衡、最大化网络生命周期的目的。特别地，对位于区域边界处的节点sk，应将sk至V(sj) 与区域边界交点的距离、sk至边界顶点的距离分别与得到的优化半径做比较，取其中的最大值作为sk的半径，以保证区域边界的全覆盖。

2) 最优化节点子集决策策略

采用覆盖重数作为区域覆盖的性能指标。假设突发事件发生时，感知节点sn首先上报事件信息，则将sn感知范围作为目标区域Z，sn在Voronoi图中的M跳邻居节点作为候选节点集Sm={s1,…, sl}，目标区域的覆盖重数可以表示为

对任意 sm∈SM，调整其感知半径使其中，是调整后的半径，则调整后的节点sm可以实现对目标区域的覆盖。管控中心综合考虑候选节点调整半径所付出的代价包括网络生命期的变化及覆盖冗余度的增加，从候选集中决策选择最优的K-1个节点，调整其感知半径以实现对目标事件区域的K重覆盖。式(1)给出

了网络的剩余生命期模型，它与节点的剩余能量 Em和能耗相关，而覆盖冗余度的变化量在监测区域已实现全覆盖的情况下可以表示为这样算法可以建立相应的决策代价函数 H(L,U)进行子集决策，决策过程可以抽象为如下带约束条件的优化模型。

目标函数

约束条件

图3 SDSN覆盖优化算法的Voronoi模型

通过对该优化模型的求解分析，可以寻求最优的节点子集和半径调整方案，如果候选节点集较大，可以考虑采用启发式算法进行子集搜索，以获得问题的次优解。

4.2 基于单纯复形理论的拓扑控制算法

SDSN网络中的传感器节点和节点间通信链路可以抽象为0-单形和1-单形，通过合理地增加或者删除节点间的无线通信链路，生成一个能量高效的优化网络拓扑结构。为了获取SDSN网络连通性的相关信息，引入单纯链复形和贝蒂数的定义。给定一个单复形，它的j维单纯链Dj是由其j维定向单形生成的拓扑空间。单纯链Dj对应的边缘算子∂j的定义如下

其中，vi表示所对应单形的顶点。应用边缘算子∂j可以对单纯复形的j维单纯链进行降维，从而得到单纯复形的单纯链复形

单纯链复形中 ∂j：Dj→ Dj−1的核被称为j维闭链群，记作 Zj； ∂j+1：Dj+1→ Dj的像被称为 j维边缘链群，记作Bj。由引理 ∂j∂j+1= 0可知j维边缘群属于j维闭链群，即 Zj⊃Bj，继而可以定义该复形的j-贝蒂数为

其中，dimZj表示 j维闭链群 Zj的维数，dimBj表示 j维边缘链群 Bj的维数，j-贝蒂数 Bj等于 j维闭链群 Zj维数与 j维边缘链群 Bj维数的差。在SDSN场景下，0维闭链群 Z0的维数就是 SDSN中传感器节点的数量，0维边缘链群B0的维数就是全网各连通分量最小连通子集的1-单形数量之和，从而0-贝蒂数0β表示SDSN中连通分量的个数，1-贝蒂数则表示二维平面上没有无线信号覆盖的空洞的个数。

基于上述定义，本算法提出了基于边缘链群最小生成元和节点度，以最简练的网络拓扑结构为目标，同时保证整个系统的连通性以及突发区域顽健性的全局节点功率最优的问题，并将该最优问题分解为几个子问题进行求解，由2个子过程来执行，即功率预配置过程和功率重配置过程。功率预配置过程确保了网络部署和网络结构发生变化时网络拓扑的精简性和连通性，功率重配置过程确保了网络突发事件发生时突发区域网络拓扑的顽健性。当管控中心检测到网络拓扑发生变化时执行功率预配置过程，删除网络中冗余的无线链路同时确保网络的连通性；当检测到突发事件发生时，由SDSN管控中心执行功率重配置过程，调整突发事件产生区域内节点的无线发射功率，增加区域内无线链路的冗余度以提高局部区域的稳定性和顽健性。

SDSN功率预配置和重配置的具体流程如下。

1) 软件定义传感网络功率预配置过程

首先，SDSN管控中心根据节点的位置和初始发射功率获取网络中所有1-单形的节点构成，然后计算边缘算子∂0、∂1的核空间维数以及像空间维数得到0β。其次，根据0β的取值判断网络是否连通，0β为1表示网络连通，反之表示网络不连通；如果网络不是连通的，计算∂1像空间的最小生成元，根据最小生成元得到各个连通分量的最小连通子集，从而确定连通分量内节点的最佳发射功率。接着，通过综合考虑连通分量中节点的度和剩余能量来决定边缘节点的选择，根据边缘节点的位置信息增大其发射功率使网络的0-贝蒂数降为 1，这里节点的度是指包含该节点网络中1-单形的个数。软件定义传感网络功率预配置流程如图4所示。

图4 软件定义传感网络功率预配置拟定流程

2) 软件定义传感网络功率重配置过程

在确保整个网络连通性的基础上，SDSN管控中心根据突发事件发生的位置和范围得到突发区域内节点的位置信息，根据突发事件的紧急程度来确定对突发区域内节点度的平均增加量。然后，以区域外节点度的变化最小为目标对突发区域内节点的发射功率进行迭代调整，同时确保每个迭代步区域内节点平均度的增量都是一样的，经过多次迭代可以得到最优的重配置节点集以及相应的重配置功率。软件定义传感网络功率重配置过程如图 5所示。

图5 软件定义传感网络功率重配置拟定流程

4.3 基于多业务QoS的路由算法

在SDSN中，源节点到目的节点的路由选择对于整个无线传感器网络系统的性能具有重要作用。在发生多个并发事件时，系统中央控制器会根据各自源节点自身业务的QoS，整体网络的链路状态和每个节点上的能量消耗等信息选择到目的节点的路由，提高因突发事件网络中路由重新配置的准确性和实时性。

图 6是基于多业务 QoS的路由算法拟定系统，当有突发事件发生时，SDSN管控中心接收到源节点发起数据的发送请求，管控中心根据新的突发事件Unew以及SDSN中剩余正在进行的业务集Un′ow进行合并形成新的业务集合 Unow= Un′ow∪ Unew。每个业务集合中的元素包含该业务数据的发送端、数据的到达端和数据发送的QoS需求等网络信息，新的业务集合存储在管控中心中用于路由计算。

随后，根据新的业务集合Unow管控中心集中调取网络中的有效信息用于路由计算，如各节点剩余能量E={E1,…,EN}和各个业务的QoS需求等。考虑到节点的可扩展性，多个无线收发装置同时配置在一个传感器节点成为可能，因此，基于 SDN的传感器网路由算法将收发装置的可扩展性加入路由算法中。由于一个无线传感器节点可同时收、同时发或者部分收和部分发送数据，因此，不同于传统单一收发装置传感器网络的路由计算，整个网络的路由将变得极其复杂。所以，本文将多收发装置作为研究路由算法的一个网络特性，同时可以看到该算法能够退化到单一收发装置的传感器网络中，具有一定的普适作用。业务QoS作为衡量该业务服务质量的标准有着较好的作用，QoS的关键指标主要包括：可用性、吞吐量、时延、时延变化和丢失等。本文将考虑网络单位时间内传输的信息量作为业务QoS的度量准则。路由算法依据业务集中每个业务QoS需求动态分配路由给各个业务，保证最大化每个业务的QoS。

图6 基于多业务QoS的路由算法拟定系统

考虑到节点的可扩展性，假设每个节点可以部署一个或者多个无线收发装置（异构无线传感器网络中的高级节点），同时整个网络配置K个正交子信道来进行数据的传送。假设网络中共有N个节点，每个节点可拥有rn个无线收发装置，节点i所拥有的有效传输半径为Ti，节点i与节点j的欧氏距离记为dij，由此可得网络中可进行一跳传输的链路集合记为 ε= {(i, j)|dij≤ Ti,1 ≤ i, j≤ N, i ≠j} 。

考虑到SDSN干扰受限的特点，同一信道可以在相互独立的链路上同时发送数据，又因为在本文中K个正交子信道都可以用来传输数据。因此，可以得到一个并发数据传输链路集，记为P = [1,… , p, … ,|P|]。从而可以调度每个并发链路集所占用的时间百分比，进而得到每个链路上单位时间内所能传送信息量的上限。根据该信息量上限，可以得到最优传输路径。

定义下面的二元指示变量：① 若链路(i, j)在并发链路集p上被激活且占用子信道k，为1，否

则， vk,p为0；② 若节点i在并发链路集p上被激

i, j

活且占用子信道k，则 xn

k,p为1，否则，为0。因为一个节点在同一时刻最多只能与一个相邻节点在某一子信道上进行通信，由此可得

因为每个节点受到其自身无线收发装置个数的限制，由此可以得到

如果2条链路可在同一子信道上同时传输，那么这2条链路必须相互独立，此时应满足

其中，F[(i,j),(u,w)]为指示链路(i,j)和链路(u,w)是否相互独立的二元变量，若相互独立则为1，否则，为0。

为描述简单，归一化激活链路在一个子信道上的数据速率为单位常量，因此，可以得到每条链路在单位时间内的信息量上限为

其中，λp为并发传输集合p所占用单位时间上的百分比数。

假设系统有M个端到端的业务流，则每个业务的源节点、目的节点和该业务 QoS可以写为Sm=(sm,dm,Im),sm,dm=1,2,… ,N, Im> 0,m =1,2,… , M 。定义 Iim,j为业务 m在单位时间内通过链路(i,j)的信息量。

在无线通信网络中，每个节点在发送或接收每个比特都应消耗一定的能量。若节点发送ψbit数据，则其消耗能量为 ET= Eψ+ αd2ψ；若节点接

elec

收ψbit数据，则其消耗能量为 ER=Eψ。因此，

elec

在单位时间内节点i发送数据所消耗的能量为

同理，可得在单位时间内节点i接收数据所消耗的能量为

在单位时间内，节点i所消耗的总能量为

用iρ表示节点i的能量负载情况为

其中，Ei为节点i剩余总能量，E为每个节点初始化能量。利用Jain公平指数，可得

在节点拥有一个或者多个无线收发装置，即节点间可采用多个正交子信道进行通信和多种业务流同时传送的场景下，通过平衡每个节点的剩余能量在保证每个业务 QoS的前提下延长网络的工作寿命。

该算法可以表述如下。

目标函数

约束条件

目标函数（17）表示最大化网络能量Jain公平指数，以达到网络各节点剩余能量均衡；约束条件（18）表示在单位时间内m业务中流入和流出转发节点的信息量应相等；约束条件（19）和（20）分别表示在单位时间内属于 m业务的源节点流入和目的节点没有相应信息量流出；约束条件（21）表示单位时间内m业务源节点流出的总信息量；约束条件（22）表示单位时间内所有业务在每个链路上的信息量应小于该链路的单位时间内信息量的上限；约束条件（23）表示每个节点上无线收发装置个数的约束。

基于多业务QoS的路由算法执行过程如图7所示。当网络中有突发事件发生时，开始路由计算，管控中心搜集所需信息，依据非线性有约束规划算法进行迭代求解，若解满足收敛条件，则算法终止，若不满足算法收敛条件，算法继续；而当网络中没有突发事件发生时，系统则直接跳过路由计算，保持原路由不变。

5 路由算法性能仿真及其结果分析

为了验证所提网络重配置算法，本节以路由算法为例进行性能仿真并分析其结果，其他算法的仿真及其与已有算法的比较将另文给出。

5.1 仿真场景

图8给出了本文所提SDSN的工作场景，其初始场景如图8（a）所示。管控中心对SDSN节点剩余能量进行衡量，选择了节点 a、b、c成为接入节点，剩下的SDSN节点d、e退化为普通节点，与区域内其他传感器节点一同工作。网络中存在若干业务，在管控中心的集中式调度下，它们分别从各自的源节点到达目的节点，系统处于稳定的工作状态。

随着突发事件A的到来，大量的数据需要上传至管控中心，网络中原有的路由已经不能满足新的传输需求，管控中心需要对网络中的路由进行优化，重新选择接入节点，并对接入节点的发射功率、路由进行重配置，尽可能将系统中的业务数据上传，调整后的系统场景如图8（b）所示。

仿真采用Matlab，仿真环境设置参数如表1所示。

仿真场景如下：SDSN网络使用单信道，并假设 10个普通节点和 4个接入节点随机分布在（x=-50，y=-50)和（x=50，y=50)的矩形区域内，管控中心位于原点（x=0，y=0）处。各普通节点的单跳传输、接收距离均为20 m。网络中业务流数目为10，即每个普通节点都有数据业务需要上传。

图7 基于多业务QoS的路由算法拟执行过程

图8 SDSN工作场景

表1 仿真参数

5.2 仿真结果及其分析

根据上述的联合功率控制的路由协议及仿真参数，对路由算法的性能进行仿真。图9(a)表明接入节点发射功率上限为[1.6 1.6 1.6 1.6]TmW时，接入链路的最优传输速率*r˜随着迭代次数增加的变化情况。可以发现在迭代600次时，曲线逐渐趋于平缓，并最终收敛于[2.219, 2.278, 2.211, 2.201]Tnat/symbol。图 9(b)为接入节点发射功率上限为[1.8, 1.8, 1.8,1.8]TmW时，接入链路的最优传输速率*r˜的迭代变化情况，可以发现当接入节点发射功率上限变化时，所提算法都在1 000次迭代内获得了最优解，这也意味着所提路由协议具有较好的收敛性。

图9 接入节点速率收敛曲线

图10给出接入节点功率上限与流速率关系的仿真结果。由图可见，接入节点发射功率上限从=[1.4 1.4 1.4 1.4]TmW到=[2.6 2.6 2.6 2.6]TmW变化时，管控中心为各接入节点分配的最优流速率的变化情况，可以发现，随着接入节点最大发射功率的增大，最优流速率也逐渐增大，系统的总吞吐量将随之增加，表明管控中心能够充分地对网络中的资源加以调配，满足区域内各业务数据上传需求，尽可能地提高系统性能。此外，当接入节点最大发射功率相同时，管控中心为各接入节点分配的资源相差不大，表明系统能够通过设置节点发射功率的上限有效地均衡系统中接入节点的能耗，以延长网络的生命周期。

图10 接入节点功率上限与流速率关系曲线

6 结束语

本文将软件定义网络技术融合进无线传感器网络，给出了软件定义传感器网络的体系架构，提出了SDSN的网络重配置算法，具体包括覆盖优化、拓扑控制以及路由优化3个方面。对于覆盖优化，提出了一种基于Voronoi图的动态覆盖算法，寻求SDSN全覆盖问题中保证网络能量均衡的最优感知半径分配，并选择最优节点子集和其感知半径，以达到目标区域的K-覆盖；在拓扑控制方面，基于单纯复形理论，提出了一种基于边缘链群最小生成元和节点度的集中控制方法，包括SDSN功率预配置过程中的边缘链群最小生成元高效、次优算法，以及快速、高效的SDSN功率重配置迭代算法，保证了整个系统的连通性以及突发区域的顽健性；考虑SDSN中路由协议的自适应性以及其在动态环境下的性能，提出一种基于多业务QoS的SDSN路由优化算法，依据每个业务的QoS需求动态分配路由，从而保证多个业务同时进行数据传递以及各自QoS的最大化，同时平衡传感器节点的剩余能量。以路由算法为例进行了仿真，结果表明所提路由算法能够有效分配资源，满足SDSN网络中多业务QoS需求并延长网络的生命周期。

7 致谢

东南大学移动通信国家重点实验室博士生张瑞、刘诚毅、茆意伟、章跃跃参与了本文初稿的部分撰写，硕士生李媚、丁翠、曹智勇、唐敏等对本文所提算法研制了实验系统并进行了仿真，在此一并致谢。

[1] YICK J, MUKHERJEE B, GHOSAL D. Wireless sensor network survey[J]. Computer Networks, 2008, 52(12)： 2292-2230.

[2] LOCHER T, RICKENBACH P V, WATTENHOFER R. Sensor networks continue to puzzle： selected open problems[C]//International Conference on Distributed Computing and Networking (ICDCN),c2008：25-38.

[3] RAJARAMAN R. Topology control and routing in ad hoc networks： a survey[J]. ACM SIGACT News, 2002, 33(2)： 60-73.

[4] AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks： a survey[J]. IEEE Wireless Communications, 2004,11(6)： 6-28.

[5] FRANK C, ROMER K. Algorithms for generic role assignment in wireless sensor networks[C]//Proc of ACM SenSys’05, c2005：230-242.

[6] SEZER S, CHOUHAN P K, RAO N, et al. Are we ready for SDN?implementation challenges for software-defined networks [J]. IEEE Communications Magazine, 2013, 51(7)： 36-43.

[7] LUO T, TAN H-P, QUEK T Q S. Sensor OpenFlow： enabling software-defined wireless sensor networks[J]. IEEE Communications Letters, 2012, 16(11)： 1896-1899.

[8] ZENG D, MIYAZAKI T, GUO S, et al. Evolution of software-defined sensor networks[C]// 2013 IEEE Ninth International Conference on Mobile Ad-hoc and Sensor Networks (MSN). Dalian, China, c2013：410-413.

[9] MIYAZAKI T, et al. A software defined wireless sensor network[C]//2014 International Conference on Computing, Networking and Communications (ICNC). Honolulu, HI, c2014： 847-852.

[10] ALEKSANDER M B, et al. Implementation technology software-defined networking in wireless sensor networks[C]//2015 IEEE 8th International Conference on Intelligent Data Acquisition and Advanced Computing Systems： Technology and Applications (IDAACS).Warsaw, c2015：448-452.

[11] MEGUERDICHIAN S, KOUSHANFAR F, POTKONJAK M, et al.Coverage problems in wireless ad hoc sensor networks[C]//IEEE Conf on Computer Communications (INFOCOM). New York, c2001： 1380-1387.

[12] LEE C, SHIN D, BAE S W, et al. Best and worst-case coverage problems for arbitrary paths in wireless sensor networks[J]. Ad Hoc Networks, 2013,(11)：1699-1714.

[13] YU J, CHEN Y, HUANG B. On connected target k-coverage in heterogeneous wireless sensor networks[C]// 2015 International Conference on Identification, Information, and Knowledge in the Internet of Things (IIKI). Beijing, c2015：262-265.

[14] YAN F, VERGNE A, MARTINS P, et al. Homology-based distributed coverage hole detection in wireless sensor networks[J]. IEEE/ACM Transactions on Networking, 2015, 23(6)： 1705-1718.

[15] QIU C X, SHEN H Y, CHEN K. An energy-efficient and distributed cooperation mechanism for k-coverage hole detection and healing in WSNs[C]//2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems (MASS). Dallas, TX, c2015： 73-81.

[16] ZENG D, LI P, GUO S, et al. Energy minimization in multi-task software-defined sensor networks[J]. IEEE Transactions on Computers,2015, 64(11)： 3128-3139.

[17] AZIZ A, SEKERCIOGLU Y A, FITZPATRICK P, et al. A survey on distributed topology control techniques for extending the lifetime of battery powered wireless sensor networks[J]. IEEE Communications Surveys and Tutorials, 2013, 15(1)： 121-144.

[18] 甘从辉, 郑国强, 唐盛禹. 无线传感器网络的拓扑控制研究[J]. 计算机应用研究, 2009, 26(9)： 3214-3218.GAN C H, ZHENG G Q, TANG S Y. Survey of topology control in wireless sensor networks[J]. Applications Research of Computers,2009, 26(9)： 3214-3218.

[19] XU M, YANG Q, KWAK K S. Distributed topology control with lifetime extension based on non-cooperative game for wireless sensor networks[J]. IEEE Sensors Journal, 2016, 16(9)： 3332-3342.

[20] VERGNE A, DECREUSEFOND L, MARTINS P. Reduction algorithm for simplicial complexes[C]//2013 Proceedings IEEE INFOCOM, Turin, c2013：475-479.

[21] SANCHEZ J A, RUIZ P M, STOJMNENOVIC I. GMR： geographic multicast routing for wireless sensor networks[C]//2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks. Reston, VA, c2006：20-29.

[22] BASKETT P, SHANG Y, ZENG W J, et al. SDNAN： software-defined networking in ad hoc networks of smartphones[C]//2013 IEEE 10th Consumer Communications and Networking Conference (CCNC). Las Vegas, NV, c2013：861-862.

[23] BENNESBY R, FONSECA P, MOTA E, et al. An inter-AS routing component for software-defined networks[C]//2012 IEEE Network Operations and Management Symposium. Maui, HI, c2012：138-145.

Study on network reconfiguration algorithms in software-defined sensor networks

SHEN Lian-feng1, ZHU Ya-ping1, DING Zhao-ming1, YAN Feng1, DENG Shu-guang2
(1. National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China;2. College of Communications and Electronics Engineering, Hunan City University, Yiyang 413000, China)

In order to improve the performances and adaptabilities of wireless sensor networks the architecture of software-defined sensor network (SDSN) was proposed and the studies were focused on the network reconfiguration algorithm of SDSN. In the algorithm, the theory of Voronoi diagram was first used to search the optimal allocation of sensing radius to achieve K-coverage on the target region. Then, based on the theory of simplicial complex, a centralized control mechanism based on the minimal generator of boundary chain group and the node degree was proposed to simplify the architecture of network topology and to ensure the connectivity of the whole system and the robustness of the emergency region. Considering the adaptability in dynamic environment of routing protocols in SDSN, a routing optimization algorithm for SDSN was proposed, which was based on quality of service (QoS) of multi-service. Simulation results show that the proposed routing algorithm can efficiently allocate resources to satisfy the requirements of multi-service’s QoS and to prolong the lifetime of network.

software-defined sensor networks, coverage optimization, topology control, routing optimization

s: The National Natural Science Foundation of China (No.61471164), The Research Fund of National Mobile Communication Research Laboratory, Southeast University (No.2016B02)

TP393

10.11959/j.issn.1000-436x.2016132

2016-05-05；

2016-07-01

国家自然科学基金项目资助（No.61471164）；东南大学移动通信国家重点实验室自主研究基金资助项目（No.2016B02）