基于路径计算方法的WSN时延优化研究

朱鹏,任继军,任智源

(1.西安邮电大学 通信与信息工程学院,陕西 西安 710121;2.西安电子科技大学 综合业务网理论及关键技术国家重点实验室,陕西 西安 710071)

无线传感器网络(wireless sensor network,WSN)对整个物联网(internet of things,IoT)行业的发展起着非常重要的作用，是实现物联网应用的关键技术，其应用领域十分广泛，包括智慧城市、预警灾害、精细农业以及军事应用[1]。一般而言，在这些应用中WSN的主要作用是通过大量传感器节点捕获和发送关于监测区域内感知对象的信息，并使用多跳、自组织无线移动通信网络将这一信息传送给用户，以便用户能够及时了解感知对象的变化。

目前，WSN融合云计算技术因其强大的任务处理能力和存储能力，已在各领域得到充分应用。比如：由WSN组成的智能交通系统，通过中心云处理实时大数据，实现车流量的管控；由WSN组成的环境监测系统，通过大量传感器收集环境数据，经大数据处理和分析后，达到污染治理和预防自然灾害的目的。然而，这项技术要求将WSN收集的数据上传到云中心进行处理，远程数据传输往往会产生较高的传输时延，同时部署在环境复杂的WSN存在着能量供应问题，因此无法用于监测具有低时延和低能耗要求的任务[2]。

为了解决云计算模式存在的问题，国内外许多研究人员在实现数据的低时延和低功耗传输方面开展了诸多研究[3]。在时延优化的研究中，学者们提出了一种路径式协同计算方法，利用分布在网络边缘的设备集群进行多点协同计算，使数据在传输的过程中得到处理。Shukla等[4]为了改变通信网路径计算速率缓慢的状况，使用有向无环图表示计算任务，同时提出一个函数流模型和线性程序公式，以此确定最大化计算速率，但未将计算节点的处理能力考虑进去。在能耗优化的研究中，牛祺君等[5]针对WSN能耗受限的问题，采用了按照WSN节点剩余能量的簇首轮询机制，提出了一种依靠蜂群算法进行分簇的层次路由选择算法，解决了节点能耗过快的问题，延长了WSN寿命。虽然该能耗优化方法可以在一定程度上降低WSN的能耗，但是没有考虑到节点在空闲时的能耗。

针对上述存在的问题，本文研究了一种云雾网络架构，并基于此架构设计了一种路径计算方法。首先，该方法使用有向无环图(DAG)表示WSN的监测任务，即中心云平台利用WSN上传的实时数据进行大数据分析和处理的任务，同时利用无向图(UG)表示雾计算层的雾设备集群；其次，指定DAG至UG的任务映射规则，将监测任务分配给边缘网络设备，并依靠边缘网络设备的高算力实现协同任务处理；最后，为了求解DAG至UG的最优映射关系，建立了一个关于时延与能耗的二值优化问题，通过模拟退火-离散二值粒子群优化(SA-BPSO)算法得到问题的最优值[6]。仿真结果表明，该路径计算方法可以在能耗约束下实现降低任务处理时延的目的，能够完成低时延和低能耗要求的监测任务。

1 云雾网络架构

为了发挥边缘网络设备的任务处理能力，实现路径计算，本节研究了一种云雾网络架构，该架构从上至下有3层，分别为云计算层、雾计算层和感知层[7]，如图1所示。

图1 云雾网络架构

在该网络架构中，感知层主要由传感器节点和无线链路连接的智能终端组成，通常用于数据采集和传输。雾计算层与感知层相连，由计算和存储能力较弱的边缘网络设备(汇聚节点)组成，汇聚节点之间通过无线链路连接。当云计算中心下发的监测任务到达数据传输路径中的汇聚节点后，监测数据会被卸载到该节点上实现任务的协同计算，使数据在传输过程中完成处理，并将数据的处理结果发送给管理用户。云计算层与雾计算层相连，由存储和处理能力十分优越的云服务集群组成，主要负责管理和监测WSN，同时需要按照汇聚节点的任务处理能力、链路状况等信息制定监测任务的调度规则，并将该规则发放到具体的汇聚节点。

2 任务映射规则

为了实现将WSN的监测任务从云中心迁移到汇聚节点，首先需要将具体的监测任务划分成多个子任务。由于子任务之间存在数据依赖关系和处理顺序的优先级，本文使用DAG表示它们，其中图的有向边集可以表示子任务之间的这种依赖关系，图中的箭头指向能够表示子任务之间的优先权约束，这也意味着某个任务在其前面任务处理完成之前不能开始执行。同时，图中的无环代表任务流程的方向，即总任务的执行需要通过若干个子任务逐步执行，最后汇总到任务终点，不能出现折返式处理子任务的情况。为了将DAG表示的监测任务映射到UG表示的雾网络，本节介绍了具体的映射方法。

2.1 DAG至UG的映射规则

本文通过有向无环图D=(Ω,Γ)表示监测任务模型，并使用Ω={n1,n2,…,ns,ns+1,ns+2,…,nt-1,nt│s≥1,t≥s+1}代表所有的监测子任务，其中n1,n2,…,ns表示监测任务起点，ns+1,ns+2,…,nt-1表示中间监测任务节点，nt表示监测任务终点；定义Γ为图D的有向边集合，Ψ↑(ni)={nj│(nj,ni)∈Γ}为子任务节点ni的所有前向任务节点。

此外，本文通过无向图U=(V,S)展现雾网络的拓扑关系，其中V={v1,v2,…,vs,vs+1,vs+2,…,vm-1,vm│s≥1,m≥s+1}为图U中的所有子节点，即雾网络中的汇聚节点，v1,v2,…,vs为任务起始节点，vs+1,vs+2,…,vm-1为任务中转节点，vm为任务目标节点；S为图U中的所有边。

图D至图U的映射规则主要包含两部分:①将图D中的子任务节点映射至图U中的汇聚节点；②将有向边映射为图U中节点间的最短通路Pvivj。结合文献[8]，具体映射规则如下：

1) 子任务映射规则

图D中的所有监测子任务Ω映射至图U中的汇聚节点V的规则为γ，如(1)式所示：

(1)

γ将Ω中的任务起点n1,n2,…,ns映射到V中的任务起始节点v1,v2,…,vs；将中间子任务节点ns+1,ns+2,…,nt-1随机映射到任务中转节点vs+1,vs+2,…,vm-1；将任务终点nt映射到任务目标节点vm。

同时，在子任务节点通过γ映射至汇聚节点时存在着多对多的映射关系，本文使用关系矩阵X来表示这种映射关系，矩阵X如(2)式所示

在(2)式中，t和m分别表示监测子任务和汇聚节点的个数；(3)式中的xnpvq表示某个监测子任务到某个汇聚节点的映射情况，当xnpvq=1时，说明子任务节点np可以映射至汇聚节点vq；当xnpvq=0时，说明子任务节点np无法映射至汇聚节点vq。

2) 有向边映射规则

图D中的集合Γ映射至图U中的集合P的规则为T，如(4)式所示

T(ni,nj)={Pγ(ni )γ(nj)│γ(ni),γ(nj)∈V}

(4)

T将集合Γ中的有向边(ni,nj)映射到图U中的节点γ(ni)至节点γ(nj)的最短路径Pγ(ni)γ(nj)。

2.2 映射规则的改进模型

对于相同的图D和图U，如果遵循上述映射规则，将会有多个映射关系，从而对应于多种任务计算路径和任务处理时延。为了筛选出最小任务处理时延所对应的映射关系，从时延与能耗角度对2.1节的映射规则做出改进，同时建立一个关于任务处理时延的最优化问题模型。

在某次任务的映射关系中，子任务节点ni的处理总时延等于进行到此任务节点的累积时延与完成此任务所用的计算时延之和[9]，计算公式为

Ttotal(ni)=Taccu(ni)+Tcalc(ni)

(5)

因为要考虑任务节点与汇聚节点的映射关系，所以需要对公式(5)进行修改，其中Taccu(ni)与Tcalc(ni)的具体表达式分别为：

在(6)式中，Dnjni表示子任务节点nj与ni之间需要传递的数据量，根据子任务映射规则可知，它还表示图U中汇聚节点γ(nj)与γ(ni)之间需要传递的数据量；xnjvq和xnivp分别表示子任务节点nj到汇聚节点vq的映射关系和子任务节点ni到汇聚节点vp的映射关系。由于某一个具体的子任务节点与汇聚节点之间的映射关系是一对多，对于每个子任务节点的累积时延计算都需要遍历它们与所有的汇聚节点之间的映射关系并进行求和。同时，因为子任务节点可能存在多个前向任务节点，所以对应的会有多个累积时延，本文选择其中的最大值作为该子任务节点的累积时延。

在(7)式中，Dni代表在此次映射中子任务节点ni的计算数据量，通过子任务映射规则可知，它也代表图U中汇聚节点γ(ni)所需计算的数据量；α为当前任务的难度系数；pvp为图U中汇聚节点vp的任务处理能力系数。考虑到单一子任务节点与汇聚节点的映射关系，在计算子任务的计算时延时需要遍历该节点与其他所有汇聚节点之间的映射关系并进行求和。

通过以上分析可知，模型D的任务总时延等于节点nt的处理总时延，即

T(D)=Ttotal(nt)

(8)

同时，由于在处理总时延公式中变化的只有任务节点与汇聚节点的映射关系，因此图D的任务总时延可以表示为关于X的函数，如(9)式所示

T(D)=F(X)

(9)

尽管从时延优化方面可以进一步求解出最优映射关系，得到最小任务处理时延，可是考虑到WSN通常部署在野外，面临着能耗受限的问题，在求解最优映射关系时就必须将能耗约束考虑进去。此外，本文的工作在于如何将监测任务映射至雾网络中的汇聚节点和优化映射规则，以此改善WSN融合云计算的时延性能。因此，接下来在时延优化的基础上，主要从雾网络的总能耗要求出发进一步优化映射规则。WSN执行监测任务时，汇聚节点可能处于工作或者待机状态。因此，在活动和空闲时所产生的能耗是图U中节点vi的主要能耗来源[10]，即

(10)

结合上述分析，整个雾网络的总能耗为

(13)

假设在某次监测任务中雾网络的最大能量为Emax，通过时延优化模型得出的最优映射关系所对应的能耗必须满足整个雾网络的能耗约束，即小于或等于Emax。

根据上文可知，为了找到这种既符合能耗要求，又满足任务最小总时延的最优映射关系，需要建立一个优化问题模型。同时，由于图D至图U的映射关系结果只存在是与否2种可能，相当于该时延优化问题的问题变量只取0或1，所以该问题是一个二值优化问题，因此建立(14)式的二值优化问题模型。

3 基于SA的BPSO算法

为求解该二值优化问题模型，本文使用了一种基于BPSO的改进算法(SA-BPSO)。因为BPSO算法在迭代后期容易收敛于局部最优，同时会出现停滞状况，从而导致误差结果较大。相比BPSO算法，SA-BPSO提高了算法的收敛和全局搜寻能力，减少了发生陷入局部最优的概率，能够更加快速和准确地求解数学模型(14)的最优映射关系。

3.1 模拟退火算法

模拟退火(SA)算法在迭代期间有一定的概率接收到不理想的解，因此可以避开局部最优。它的思想受固体退火过程的启发，利用控制温度参数T、降温速率R和终止条件温度E等参数来控制算法的流程，在参数T逐渐衰减的过程中利用Metropolis接受准则持续更新可行解，其中接受新可行解的概率如(15)式所示。该算法只要参数T的取值充分大，且T的衰减速度十分慢，就可以收敛到优化问题的全局最优可行解。SA算法流程图如图2所示。

(15)

图2 SA算法流程图

3.2 SA-BPSO算法

在使用SA-BPSO算法求解数学模型(14)时，假设粒子群的总体个数为Q；算法的当前迭代次数为n，其范围为n∈{1,2,…,Pmax}，Pmax为迭代的总数，则第i个粒子的位置矩阵和速度矩阵分别表示如下：

(16)

(17)

在算法的第n次迭代过程中，第i个粒子的速度更新公式为

适用于该算法的自适应函数如(22)式所示

f(X)=F(X)=T(D)

(22)

综上所述，SA-BPSO算法求解该二值优化问题模型的总体流程图如图3所示。通过图3可知，在使用SA-BPSO求解(14)式的优化问题模型中，关于算法复杂度的分析主要包含三部分。第一个是使用Dijkstra算法寻求图U中两节点间传送单位数据量的最短时间和最短路径，该算法复杂度主要体现在顶点的个数，即图U中节点数量，同时本文需要求各个节点之间的最短距离，所以复杂度是O(n3)。第二个是针对任务总时延和总能耗的计算，该过程的算法复杂度主要体现在遍历任务节点到所有雾节点的映射情况，所以复杂度为O(n2)。第三个是针对粒子群寻找最优映射关系的过程，其中算法复杂度主要由粒子群数目和迭代次数决定，也就是O(NmaxQ)。

图3 SA-BPSO算法总体流程图

4 仿真实验与结果分析

仿真参数设置如表1所示，emax为单个汇聚节点所能携带的最大能量，本次仿真共设有18个汇聚节点，所以这些汇聚节点具有的最大能量范围为[10,40]J；fc为云服务器的任务处理能力；pfog为汇聚节点的任务处理能力；Rfog为雾网络的链路数据传输速率；α为子任务的平均难度系数[13-15]。SA-BPSO算法的参数为：粒子群的总体数量Q=40，算法的总迭代次数Nmax=100，加速常数c1=c2=1，惯性权重w=1.5。仿真采用的DAG与UG模型分别如图4～5所示。

表1 参数设置表

图4 任务模型图

图5 网络拓扑结构图

4.1 路径计算与WSN融合云计算的任务处理时延对比

为验证本文提到的路径计算方法优于传统的云计算任务处理方式，在平均任务难度系数α和Emax相同的情况下进行仿真，其中Emax设置为40 J，仿真结果如图6所示。由图6可知在数据量为1 Mb时，路径计算的总时延为0.771 s，而云计算的总时延(0.895 s)稍大于路径计算。在数据量从1 Mb增加至10 Mb的过程中，路径计算的计算时延平均增速大于传输时延，分别是0.451 s/Mb和0.173 s/Mb；云计算的传输时延平均增速较大，为0.8 s/Mb，而计算时延平均增速仅为0.095 s/Mb。在数据量为10 Mb时，路径计算的任务处理总时延比云计算减少了3.547 s，性能提升约40%。综上可知，路径计算的时延性能优于云计算。

图6 路径计算与云计算的时延性能对比

4.2 任务处理时延与任务难度系数的变化关系

在数据量和Emax分别取10 Mb和40 J的情况下，仿真结果如图7所示。

图7 任务难度系数对任务处理时延的影响

从图7得知，在任务难度系数从0.6α提高到1.4α的过程中，路径计算的传输时延与计算时延分别增加了0.184,3.486 s；云计算的传输时延未发生改变，计算时延只增加了0.76 s。路径计算与云计算的传输时延几乎无变化，两者的计算时延虽然都呈上升趋势，但是路径计算的增幅远大于云计算。主要原因是任务难度系数只会影响计算时延，不会对传输时延造成影响，同时随着任务难度系数逐渐提高，云计算会体现出其任务处理能力优势，而汇聚节点的任务处理能力有限，从而导致两者的计算时延存在较大差距。

4.3 总能耗与数据量和任务难度系数的关系

为说明在不同数据量和任务难度系数下雾网络的总能耗特性，在时延优化的基础上进行仿真，其仿真结果如图8所示。

图8 数据量和任务难度系数对总能耗的影响

仿真结果显示当任务难度系数固定时，随着数据量增加，雾网络的总能耗呈逐渐上升趋势，同时随着任务难度系数增大，相应的总能耗上升幅度也在增加。具体来讲，当数据量由2 Mb增加至12 Mb，任务难度系数分别取0.6α,1.4α时，总能耗的增幅分别为22.8和46.7 J。因为随着数据量与任务难度系数的增加，雾节点处理任务所需的时延将升高，导致能耗变大。当任务难度系数逐渐增大时，较小数据量的总能耗增长趋平缓，但随着数据量的增加，增幅变得越来越大。比如：在任务难度系数从0.6α增加至1.4α时，数据量取2 Mb与12 Mb的能耗分别增加了13%和105%。原因是在数据量较小时，任务难度系数的改变对任务处理时延的影响不大，因此能耗变化程度很小；但随着数据量的增加，任务难度系数的影响会越发明显，所以能耗急剧增长。

4.4 多种映射算法的时延性能对比

本小节从Emax角度出发，比较了SA-BPSO算法同贪婪负载均衡算法(Greedy-LB)、加权轮转算法(WRR)和随机动态算法(Pick-KX)的任务计算时延，仿真结果如图9所示。同时将SA-BPSO算法与BPSO算法从收敛速度方面进行了对比，仿真结果如图10所示。

图9在数据量与任务难度系数分别取10 Mb和α时，随着Emax的增加，4种算法对应的计算时延都逼近为一个常数，同时在这个过程中SA-BSPO算法的任务计算时延一直优于其他3种算法。在Emax取40 J时，SA-BSPO、Greedy-LB、WRR和Pick-KX的计算时延分别为2.919,6.032,6.647和7.701 s，SA-BSPO算法相比其他3种算法分别降低了51.60%，56.08%和62.09%。

图9 不同雾网络最大能耗对四种算法计算时延的影响

图10 BPSO算法与SA-BPSO算法收敛速度对比

图10在Emax取40 J、数据量取10 Mb和任务难度系数为α的情况下，2种算法随着迭代次数增加，都呈现先下降后趋于5.3 s的趋势，但可以看出SA-BPSO收敛所用的迭代次数明显少于BPSO。在迭代次数为100时，SA-BPSO与BPSO算法的路径计算总时延分别为5.317 3，5.331 8 s。因此，SA-BPSO算法相比于BPSO算法具有良好的收敛性和鲁棒性，求得的解更准确。因为SA-BPSO算法随着代次数增加，接收劣值的概率逐步降低，从而改善了BPSO算法收敛性较差的问题；同时SA-BPSO算法相比BPSO算法增强了全局搜索能力，使算法的迭代速度与收敛的精确度得到提高。

5 结 论

本文针对WSN融合云计算技术时效性不好的问题，提出了基于云雾网络架构的路径计算方法，并研究了基于SA-BPSO算法的映射规则，同时将WSN的能耗问题纳入研究范围。仿真结果表明，该方法有效地解决了云计算模式中任务处理时延比较高的问题，同时对比其他映射算法，本文的映射算法降低了任务计算时延，实现了对监测任务的最优映射。虽然本次研究验证了该方法的有效性，但是依然存在着许多未考虑的地方，比如：任务映射规则仅研究了单任务场景和约束条件只考虑了雾网络的总能耗要求。因此，在以后的研究中应该从单个汇聚节点的能耗要求和剩余能量、多任务场景或WSN链路质量等方面出发继续深化研究内容，进一步在能耗约束下减少任务处理时延，延长WSN寿命。