基于人工电场优化的软件定义物联网路由算法

赵 芳，贺 怡

(新乡学院 计算机与信息工程学院，河南 新乡 453000)

0 引 言

5G时代的到来再次推动了物联网的发展，当前的物联网通常为异构的大规模网络拓扑结构，包含大量的终端设备和基础设施[1]，为用户提供了透明的通信环境。物联网技术在监控领域具有巨大的应用价值，如智慧城市、医疗监管、农业自动化控制等[2]。随着终端设备愈发地多样和复杂，物联网包含了大量不同类型的设备，这为物联网的管理带来了挑战。软件定义网络[3]将数据平面与控制平面解耦合，具有高度的开放性和可编程性，为大规模异构物联网的管理提供了解决方案[4]。当前的物联网协议和传感器网络协议均假设节点具有相似的计算能力和通信能力，难以适用于当前的物联网智能监控系统，例如在智慧城市的应用场景下，智能手机和一些传感器之间的性能差异极大，如果选择通信能力不足的节点作为中继节点，则会导致数据传输失败，因此可靠性是软件定义物联网的一个关键指标，直接决定了物联网监控系统的性能[5]。

在主流的软件定义物联网研究[7-10]中，大多将物联网的所有设备考虑为性能接近的节点，不符合目前许多的实际应用场景。人工电场优化算法(artificial electric field algorithm，AEFA)[11]的收敛速度快、参数少且易于实现，并且具有较强的全局搜索能力和局部开发能力，在连续优化问题上具有良好的性能。为了提高物联网路由的可靠性，基于人工电场优化算法提出了软件定义物联网的可靠路由算法。该算法主要包含两个部分：首先利用滞环曲线[12]分析邻居节点的可靠性，设计了高可靠性的邻居发现方法；其次提出了离散人工电场优化算法，利用其较强的连续优化能力选择最优的层次路由路径。

1 可靠邻居发现方法

1.1 基于滞环曲线的节点可靠性分析

图1所示是一个物联网应用场景的网络示意图，包括物联网层、接入网层和云计算层。物联网层包含大量的智能终端负责采集数据，接入网层将物联网层的数据路由至云计算层，云计算层具有强大的计算能力，最终对聚集的海量数据进行处理。

图1 软件定义物联网应用

(1)节点可靠性的评价指标

邻居发现的滞环函数曲线共考虑3个可靠性指标：接收信号强度(RSS)、期望传输数(ETX)和排名指数Rank(R)。

设d为设备间的距离，无线连接RSS的计算式为

(1)

式中：pt为传输能量，δ为天线常量，d*为参考距离，β和γ分别为信道路径的损耗因子和衰落因子。

软件定义物联网的终端设备向接入网层发送的请求设为rr，从云计算层返回的响应设为rs。为每个无线连接分配一个权重W，W定义为用户的请求被邻居节点处理的比例，W依赖于邻居设备的计算能力和通信能力，W的计算式为

(2)

ETX的计算式为

(3)

式中：m为传输数量，rl为请求损耗，rl= (rs-rr)∀tr>tmax，变量tr和tmax分别为请求的响应延迟和网络的最大TTL值(time to live)。

源节点可能发现多个路由中继节点，使用排名指数Rank(R)过滤一部分不可靠的路径，Rank(R)计算为

(4)

式中：k为路由路径上的节点数量，(1-rs/rr)计算了信号经过k个节点后的损耗。理想情况是选择R值最大、RSS值最高的路径。

(2)基于滞环曲线的可靠性分析

经典滞环函数h(f)的一般形式为

(5)

式中：x(Δ)和y(Δ)表示在滞环曲线上的变化坐标，(x1,x2)和(y1,y2)表示两个状态的变化，状态分为可靠或不可靠。

通过滞环曲线检测状态的变化vp，vp的计算式为

(6)

式中：ym=((y2-y1)/2)+y1。将式(6)改写为

(7)

图2(a)所示是一个典型的滞环曲线，标注了(x1,x2)和(y1,y2)，图2(b)为通过滞环曲线分析可靠性状态的示意图。根据式(7)，图中的变化点为x(Δ)=1/2×y(Δ)，h(f)=3/2×y(Δ)，∀x(Δ)=x(Δ)+x2(Δ)。在节点可靠性的问题中，x1的值为tr，x2的值为ts，假设ts为线性过程，那么上一个状态x(Δ)加上ts获得x2(Δ)，因此对3/2×y(Δ)曲线进行优化，即可发现高可靠性的邻居节点。

图2 滞环曲线分析可靠性指标

1.2 中继节点的可靠性评估

通过分析滞环函数h(f)的激活因子af识别每个可靠性指标的(x1,x2)和(y1,y2)，af的一般形式为

af=[y2-y(Δ)]=arg.fun[ym-vp]

(8)

通过下式评估(y1,y2)相较于(x1,x2)的变化

(9)

式中：yf表示评价邻居可靠性的指标。

以RSS指标为例描述可靠性评估的流程：接收信号强度(received signal strength，RSS)与节点的移动性相关，设d*为参考RSS值，如果d*>d，那么RSS较小；如果d*1/2，那么ym=y2/2，因此将式(9)修改为

(10)

图3所示是可靠中继节点的判断流程框架，该流程图以RSS指标为例，其它两个指标与之相似，如果d*>d，那么节点为可靠节点，否则为不可靠节点。

图3 可靠中继节点选择流程

2 基于人工电场优化的路由算法

在大规模异构物联网中虽然高性能的智能设备不断增加，但传感器和RFID依然是物联网采集信号的主要设备，因此提高网络的生命期也是物联网的首要研究目标。人工电场优化算法对于连续优化问题具有极好的性能，效果好于传统的粒子群优化算法、人工蚁群优化算法和遗传算法等。本文对人工电场优化算法进行离散化修改，将人工电场优化算法应用于物联网路由发现问题。

2.1 SDN物联网的路由问题模型

图4所示是SDN物联网路由发现程序的流程图。

图4 SDN物联网路由发现程序的流程

(1)网络分簇

初始化阶段，接入层基站(base station，BS)向所有节点广播一个报文，根据RSS选择最接近BS的节点作为簇头。簇头负责聚集簇内节点的数据，将数据转发到云计算层。簇头的适应度评价函数定义为

(11)

式中：engi表示节点i的剩余能量，dstbs表示节点和BS的距离，即选择剩余能量较多且与BS距离较近的节点作为簇头。

确定簇头之后，簇头向其通信范围内的节点发送一个JOIN(SDN协议)请求，将网络分簇。

(2)基于SDN建立路由

根据SDN协议，需要通信的节点首先向簇头发送一个请求，簇头检查其内存中的路由表。簇头发出一个路由请求报文，报文的格式为

RRpkt∶

(12)

式中：Cid为簇的ID，CLid为簇头的ID，HC为传输的跳数，NN为节点的标记，PNid为当前节点的ID，PRid为上一跳节点的ID。

(3)网络能耗和网络生命期函数

簇内节点与簇头通信的平均能耗为

E(C1)=E[E(C1|n=n0)]

(13)

簇头节点与接入层BS通信的平均能耗为

(14)

物联网平均总能耗为

E(Ct)=E(C1)+E(C2)

(15)

簇头或普通节点的能耗计算式为

(16)

路由路径的平均能耗计算式为

eout(r)=pE(RD(ci))Ec(r)

(17)

将式(7)与式(8)结合，可得

et(d)=ech,mn+er

(18)

(19)

本文将网络生命期作为优化目标，将中继节点的可靠性作为约束条件，通过离散人工电场算法寻找最佳的路由路径。

2.2 人工电场算法

AEFA受库伦定律启发，若干的带电粒子组成一个种群，粒子的电量越大，产生的引力越大。AEFA根据全局最优和个体最优更新粒子的位置，粒子的个体最优位置定义为

(20)

两个带电粒子间的引力为

(21)

(22)

Kt的计算方法为

(23)

式中：α为参数，K0为库伦常量的初始值，it和itmax分别为当前迭代次数和最大迭代次数。每个粒子的电量通过适应度函数计算获得，计算方法为

(24)

式中：fitpi为pi的适应度值，bstt和wstt分别为目前为止的最优适应度和最差适应度。粒子电量的更新计算式为

(25)

粒子i在d维空间中受到的总作用力为

(26)

式中：r为[0,1]区间均匀分布的随机数，ps为粒子总数量。粒子i的电场为

(27)

粒子i单位质量的加速度为

(28)

粒子在搜索空间内的速度为

(29)

粒子在搜索空间内的位置为

(30)

2.3 离散人工电场算法

本文提出了离散化AEFA以满足物联网路由问题的要求，离散人工电场算法的主框架如算法1所示。

算法1：离散AEFA算法的框架

输入：图GD,GM和网络图H。

输出：最优粒子;

/*初始化阶段*/

(2)初始化每个粒子的速度V={V1,V2,…,Vps};

(3)计算每个粒子Xi的目标函数值；

/*迭代优化阶段*/

(4)while 未达到结束条件 do

(5) 评估Kt，计算bst和wst值；

(6) foreachifrom 1 topsdo

(7) 计算Xi的目标适应度;

(8) 计算总作用力和加速度；

(9) 更新第i个粒子的速度和位置；

(10) endfor

(11)endwhile

(1)离散位置表示

带电粒子的位置对应问题的一个可能解。在物联网路由发现问题中，将网络的路由表示为节点的位置向量Xi={xi1,xi2,…,xiD}，D为路由的节点数量，向量Xi的每个元素表示路由路径的节点列表。图5所示是两个粒子的示意图，粒子1和粒子2的位置向量分别为X1={1,2,3,4,5,6}和X2={1,2,3,6,4,5}，X1表示的路由转发过程为节点1→节点2→节点3→节点4→节点5→节点6，X2表示的路由转发过程为节点1→节点2→节点3→节点6→节点5→节点4。

图5 路由路径的两个实例

(2)离散速度表示

(3)人工电场优化算法的加减法算子

设两个粒子的位置分别为X1={x11,x12,…,x1D}，X2={x21,x22,…,x2M}，两者的差值X1-X2为一个D×M的矩阵。算法2是离散减法算子的伪代码，减法算子与加法算子相似。

算法2：离散减法算子

(1)A=X1-X2=zeros(D,M);

(2)foreachifrom 1 toDdo

(3) ifXOR(x1i,x2i) == 1 then

(4)A(x1i, i)=1;

(5) endif

(6)endfor

(4)速度更新

因为路由表中的路径是之前发现的候选解，因此通过将发现的路由与路由表比较可提高优化的速度。首先搜索当前的个体最优位置，最优粒子和最差粒子分别记为pbst=max(score(Yi))和pwst=min(score(Yi))，Yi表示路由表中和当前粒子Xi匹配的邻接矩阵，邻接矩阵的计算方法如算法3所示。

算法3：邻接矩阵算法

输入：粒子矩阵X；

输出：邻接矩阵Y；

(1)s←|X|,k=1; //初始化

(2)Y=zeros(s,s);//初始化Y

(3)foreachifrom 1 tosdo

(4)Y(k,X(i)) =1；

(5)k=k+1;

(6)endfor

计算粒子作用力的步骤为：①使用离散减法算子计算Xi和Xj间的距离Rij;②计算每个粒子的加速度;③使用离散速度更新算法更新粒子的速度，每个速度元素的取值范围为[0,1]。

(5)位置更新

每个粒子基于当前速度和加速度更新其位置，速度向量的每个元素表示该节点与路由表匹配的概率。设Xi={xi1,xi2,…,xiD}为当前的位置向量，Vi+1为更新的速度。

在路由搜索过程中为位置更新规则增加可靠性约束条件：①生成一个在[0,1]区间均匀分布的随机数，然后依次更新Xi向量的每个元素。②在Xi的第k个元素更新完成之后，选择速度矩阵Vi+1第k列中大于c的所有元素。然后，从中随机选择一个满足可靠性约束的元素，Xi第k个元素的值作为随机选择元素的行元素。③如果所选元素不满足可靠性约束，则暂时跳过该元素，更新向量的其它元素。

(6)离散人工电场优化算法的复杂度分析

计算适应度是离散人工电场优化算法的主要部分。在建立三阶张量的过程中随机选择了ND×NM个三元组，ND和NM分别为图GD和图GM中的节点数量。因此每次计算适应度的复杂度为O(ND2NM2)，电场优化算法的总计算复杂度为O(p·iter·ND2NM2)，其中p为种群大小，iter为迭代次数。

3 仿真实验与结果分析

实验环境为Intel Xeon E5-2630V3 CPU, CPU主频为2.4 GHz,内存为16 GB。在Matlab2018a平台编程实现本文算法，使用Contiki Cooja 2.7软件作为物联网的仿真器。

3.1 参数设置和实验方法

表1所示是物联网相关的仿真参数，仿真物联网共有200个设备，每个设备随机向云计算层发送资源请求消息，消息大小为32 Kb。

表1 网络仿真参数的基本信息

表2所示是人工电场优化算法的相关参数。

表2 人工电场优化算法的参数设置

选择3个软件定义物联网的路由协议作为对比方法，横向评比本文算法的有效性。SDN_AODV[13]是经典的无线自组网按需平面距离向量路由协议(Ad hoc on-demand distance vector routing，AODV)在软件定义物联网上的实现方法，该协议针对SDN的规范对AODV进行了修改。ACO[14]采用多agent的人工蚁群优化算法实现了软件定义物联网的路由算法，该算法重点解决了重叠区域的计算冗余和通信冗余，有效地延长了物联网的生命期，该算法可用来评估本文人工电场优化算法的有效性。AQRA[9]是一种以保障网络QoS性能为目标的软件定义物联网路由算法，该算法以保障网络服务质量为基础，与本文可靠性路由算法的目标相似。

3.2 实验结果与分析

通过5个物联网协议的常用性能指标评价本文算法的优劣，分别为：网络吞吐量、平均传输延迟、报文传递率、平均网络能耗和网络生命期。

(1)吞吐量实验结果

实验统计了路由路径不同跳数下的平均吞吐量数值，结果如图6所示。随着传输路径的延长，报文传输的距离增加，导致平均吞吐量下降。SDN_AODV的吞吐量较低，可见传统的ad-hoc协议在软件定义物联网问题上的效果不佳。ACO和AQRA的吞吐量性能明显优于SDN_AODV，由此验证优化技术人工蚁群优化算法和QoS优化技术对于软件定义物联网的性能具有明显的提高效果。本文算法在数据传入接入层之前，通过滞环函数筛选出可靠的中继节点，有助于提高请求处理的可靠性和鲁棒性，并且在路由中途发生传输失败和丢包的概率下降，因此提高了整体的吞吐量。最终本文算法的吞吐量性能好于其它3个路由算法。

图6 吞吐量性能的结果

(2)平均延迟实验结果

实验统计了路由路径不同跳数下的平均传输延迟数值，结果如图7所示。随着传输路径的延长，报文传输的距离增加，平均传输延迟随之增加。SDN_AODV的延迟较高，可见传统的ad-hoc协议在软件定义物联网问题上的效果不佳。ACO和AQRA的平均延迟性能明显优于SDN_AODV，验证ACO和QoS两个优化技术对于软件定义物联网的性能具有明显的提高效果。本文算法在数据传入接入层之前，通过滞环函数筛选出可靠的中继节点，有助于提高请求传输的可靠性，并且在路由中途发生传输失败和丢包的概率下降，因此降低了整体的传输延迟。最终本文算法的传输延迟性能好于其它3个路由算法。

图7 平均传输延迟的结果

(3)报文传递率实验结果

实验统计了路由路径不同节点密度下的报文传递率数值，结果如图8所示。随着节点密度的提高，路由传输容易出现冲突，引起网络拥塞，导致报文传递率降低。SDN_AODV的报文传递率较低，可见传统的ad-hoc协议在软件定义物联网问题上的效果不佳。ACO和AQRA的报文传递率性能明显优于SDN_AODV，由此验证优化技术人工蚁群优化算法和QoS优化技术对于软件定义物联网的性能具有明显的提高效果，尤其AQRA对网络QoS进行了优化，降低不同路由路径之间发生拥塞的概率。本文算法在数据传入接入层之前，通过滞环函数筛选出可靠的中继节点，有助于提高请求处理的可靠性和鲁棒性，最终本文算法的报文传递率性能好于其它3个路由算法。

图8 报文传递率的结果

(4)网络能耗实验结果

实验统计了平均节点总能耗随着仿真时间的数值变化情况，结果如图9所示。随着仿真时间的延长，网络的能耗提高。因为ACO算法针对每个请求运行一次人工蚁群优化算法，而ACO算法的计算成本较高，为网络带来较大的能耗负担。本文算法在人工电场优化过程中充分利用了路由表中已有的路由记录，极大地加速了搜索的过程，因此由于计算带来的能耗负担较小。最终本文算法的网络能耗性能好于其它3个路由算法。

图9 平均网络总能耗的结果

(5)网络生命期实验结果

实验统计了网络中存活节点数量随着仿真时间的数值变化情况，结果如图10所示。随着仿真时间的延长，网络的能耗提高，能量耗尽的节点增多。本文算法通过人工电场优化算法对网络生命期进行了优化处理，有效地均衡了网络中节点的能量，降低了节点能量耗尽的速度。最终本文算法的网络能耗性能好于其它3个路由算法。

图10 平均传输延迟的结果

4 结束语

本文为软件定义物联网设计了可靠路由算法，算法首先利用滞环曲线分析邻居节点的可靠性，设计了高可靠性的邻居发现方法，另外设计了离散人工电场优化算法，利用其较强的连续优化能力选择最优的层次路由路径。该算法在数据传入接入层之前，通过滞环函数筛选出可靠的中继节点，有助于提高请求传输的可靠性，并且在路由中途发生传输失败和丢包的概率下降，因此降低了整体的传输延迟。通过人工电场优化算法对网络生命期进行了优化处理，有效地均衡了网络中节点的能量，降低了节点能量耗尽的速度。实验结果表明，本文算法在多个物联网的性能指标上均实现了较好的效果。