移动边缘计算(MEC，mobile edge computing)将计算负载从核心云数据中心转移到靠近用户端的移动边缘侧，减轻网络负担^[1].在接入点(例如基站、路由器)覆盖范围内，MEC服务器为移动用户提供云服务，将云计算放置到用户侧的网络边缘，加速访问内容、服务、应用程序，实现边缘端迅速响应. MEC服务器为用户提供高度分布式计算环境，加快网络信息分发，提供辅助计算、存储资源，提高服务、程序响应速度，降低时延，节省网络资源^[2-3].

集中式云计算模型不能很好地解决当前所面临的问题，于是诞生一种新型边缘计算模型.边缘计算(EC，edge computing)在网络边缘处理数据，减少请求响应时间，提升电池续航能力，减少网络带宽，并且保证数据的安全与隐私^[4-5].

第5代移动通信系统时代的到来，互联网多媒体应用，例如视频聊天、网络直播、网络通话、远程教育层出不穷. Internet开始从单一的数据传输转向数据、语音、图像、视频多媒体信息的综合传输^[6-7].数据传输需要满足不同服务质量(QoS，quality of service)要求，多QoS约束路由成为解决QoS问题的一种有效途径^[8-10].

QoS路由协议包括多径QoS路由协议、节点控制的单跳路径QoS路由协议.前者能够保证信息传输的可靠性、端到端之间的延迟，但是能耗较高，因此单路径QoS路由成为本文的研究重点. QoS路由算法能够改善网络吞吐量、网络性能退化，优化资源配置，平衡网络负载，实现网络全局资源利用率优化，并且最大化网络接受其他QoS参数需求.考虑端到端可靠性、时延、能量消耗，采用节点原始数据预处理、剪枝规则加快收敛、节点能量感知唤醒机制降低网络整体能量消耗，提出一种面向边缘计算节点能量优化的QoS约束路由算法(MQEN，multi-QoS constrained routing algorithm for edge computing and node energy optimization).实验结果证明，在保证端到端可靠性、延迟的前提下，MQEN算法比基于链路质量的QoS机会路由算法(LQOR，link quality based opportunistic routing algorithm for QoS)、基于集路的多路径QoS路由算法(CMQRA，cluster-base multipath QoS routing algorithm)、基于动态规划的QoS多约束路由算法(QMCRA-DP，QoS multi-constraints routing algorithm based on dymanic programming)降低了网络能量消耗，延长了网络生命周期.

1 算法基本原理

采用边缘计算将学习自动机部署于各个节点，每个节点分配的任务由对应学习自动机依据客观环境优化配置(单节点运算能力、节点间的通信强度)，最大限度地提升各节点的运算能力、存储能力.预处理传感器节点采集的原始数据，减少有效数据的传输时间、传输能耗，保证通信质量，提高算法效率.

定义1  环境.面向边缘计算自动机的运行环境是一个三元函数组〈E_a, E_b, C〉，E_a={α₁, α₂, …, α_r}是环境输入行为集合，E_b={β₁, β₂, …, β_m}是环境输出行为集合，C={c_ij=Pr[β(n)=β_j|α(n)=α_i]}，其中1≤i≤r, 1≤j≤r.若c_ij的值不是随着时间变化而变化，则称该环境变量是稳定的；否则称该环境变量是不稳定的.

定义2  自动机.不需要外界指导的自引导工作系统，自动机的数学模型是一个五元函数组〈E_a, E_b, Q,T, G〉，Q=[q₁(n), q₂(n), …, q_s(n)]是自动机在n时刻的状态，T:Q×E_b×E_a→Q是自动机状态转移函数，决定自动机如何由n时刻状态转变到n+1时刻状态q(n+1)=T[q(n), α(n), β(n)]. G决定自动机根据n时刻状态产生输出

$ \alpha \left( n \right) = G\left[ {q\left( n \right)} \right] $

定义3  学习自动机.能与随机环境交互，改变自己行为的自动机.在n时刻，学习自动机在当前状态q(n)下，按照一定概率从集合A中选择一个行为α(n)，该行为进入随机环境.随机环境反馈此行为β(n).学习自动机收到该反馈β(n)后，按照一定的算法修改自己的状态q(n+1).直到选择最小惩罚行为概率为1，循环结束.

定义4  随机估计器学习自动机.随机估计器学习自动机被定义为一个四元函数组〈A, B, Q, T〉，其中A, B, T与定义2中的自动机定义相同，而Q=〈P, E〉是学习自动机的状态，表示为

$ \begin{array}{c} \boldsymbol{P}\left( n \right) = \left[ {{k_1}\left( n \right), {k_2}\left( n \right), \cdots , {k_r}\left( n \right)} \right]\\ {k_i} = {\rm{Pr}}\left[ {\alpha \left( n \right) = {\alpha _i}} \right] \end{array} $

(1)

P(n)表示所有行为在n时刻概率的概率向量. E=[D(n), U(n)]为随机估计器，表示为

$ \begin{array}{c} \boldsymbol{D}\left( n \right) = \left[ {{{g'}_1}\left( n \right), {{g'}_2}\left( n \right), \cdots , {{g'}_r}\left( n \right)} \right]\\ {{g'}_r}\left( n \right) = R_r^n/G_r^n \end{array} $

(2)

D(n)是指自动机在n时刻确定性(奖励)估计器向量，而每一个行为的奖励估计值表示为

$ \boldsymbol{D}\left( n \right) = \left[ {{{g'}_1}\left( n \right), {{g'}_2}\left( n \right), \cdots , {{g'}_r}\left( n \right)} \right] $

(3)

U(n)是指自动机在n时刻的随机估计器向量，即

$ {u'_1}\left( n \right) = {g'_i}\left( n \right) + H_i^n $

(4)

其中H_iⁿ是服从区间(-r/G_iⁿ, r/G_iⁿ)均匀分布的随机变量.

随机估计器学习自动机在收到ENV的增强信号后，更新其动作概率矩阵P(n)，如果β(n)=1，则有

$ \left. \begin{array}{l} {k_j}\left( {n + 1} \right) = \max \left[ {{k_j}\left( n \right) - 1/m{n_0}, 0} \right], j \ne m\\ {k_m}\left( {n + 1} \right) = 1 - \sum\limits_{j \ne m} {{k_j}\left( {n + 1} \right)} \end{array} \right\} $

(5)

其中m和n₀分别为摄动参数、解析参数.如果β(t)=0，则有

$ {k_j}\left( {n + 1} \right) = {k_j}\left( n \right), 1 \le j \le r $

(6)

2 边缘计算网络模型

在智慧农场QoS路由约束条件下，描述和定义网络模型参数，包括边缘计算网络、数据包投递率、端到端延迟、能量消耗.

2.1 边缘计算网络

首先设定边缘计算网络节点，一个边缘计算网络由n个任意排列的节点构成V={v₀, v₁, …, v_n}，其中v₀是网络中的Sink节点.每个节点都有一个感知范围R_s和一个通信范围R_c，初始能量为E₀，并且每个节点都具有一定的计算能力N_c、存储能力N_s.

针对边缘计算网络的QoS路由问题，构建传感器网络为一个多约束最优路径模型.其网络拓扑结构图为G={V, E}，其中，V是图G的顶点集合，E为图G的边集合.在G的每条边(u, v)∈E上设定一个权值w(u, v)，设置每条边上的QoS约束参数为q_k(u, v)(k=1, 2, 3).因此，边缘计算网络的QoS路由问题转化为在k个QoS约束条件下，寻找一条从源节点到Sink节点的最短路径l，满足

$ \begin{array}{c} {q_k}\left( l \right) = \sum\limits_{\left( {u, v} \right) \in l} {{q_k}\left( {u, v} \right)} \\ {q_k} \le c\left( {u, v} \right), k = 1, 2, 3\\ w\left( l \right) = \sum\limits_{\left( {u, v} \right) \in l} {w\left( {u, v} \right)} \end{array} $

(7)

其中w(u, v)是满足上述条件的所有可行路径中的最小权值.

2.2 数据包投递率

采用一种通过统计探测包方法计算端到端之间的包接收率(PRR，packet receive ratio)，被定义为某段时间内接收节点接收的数据包总数与发送节点发送的数据包总数的比值，表示为

$ {P_{{\rm{PRR}}}} = {P_{{\rm{Rec\_Packets}}}}/{P_{{\rm{S\_Packets}}}} $

(8)

其中：P_{Rec_Packets}表示一段时间内接收节点接收的数据包总数，P_{S_Packets}表示这段时间内发送节点发送的数据包总数.假设R(u, v)表示任意单跳节点之间的PRR，则从源节点到Sink节点路径l的数据包投递率(PDR，packet delivery rate)表示为

$ {P_{{\rm{PDR}}}} = \mathop \Pi \limits_{\forall \left( {u, v} \right) \in l} R\left( {u, v} \right) $

(9)

数据包投递率PDR越高，表示Sink节点接收到的可靠数据越多，传输过程越可靠，因此可使用PDR计算端到端传输的可靠性.

2.3 端到端延迟

数据包在端到端之间发送的延迟包括传输延时、传播延迟，其中传播延迟可以忽略不计(通常是纳米单位级).主要考虑传输延迟模型，表示为

$ {D_{{\rm{DT}}}}\left( l \right) = \sum\limits_{\forall \left( {u, v} \right) \in l} {{\rm{d}}t\left( {u, v} \right)} $

(10)

其中dt(u, v)表示节点u到节点v的传输延迟.

2.4 能量消耗

节点的能量消耗主要为无线通信模块上的数据传输，当k bit信息传送距离d时，每个传感器节点在T时间内消耗的能量表示为

$ \begin{array}{c} {E_{{\rm{node}}}}\left( {{v_i}} \right) = T\left( {{E_{{\rm{elec}}}}k + {\varepsilon _{{\rm{amp}}}}k{d^n}} \right), \\ d ＜ {R_{\rm{c}}} \end{array} $

(11)

其中：E_elec为传感器发射装置、接收电路发送或接收单位bit的能耗，ε_amp为发射放大器将每bit传送单位平方米的能耗，d为发送装置所在的节点与其相邻单跳节点接收电路之间的距离，n为传播衰减指数(通常为2＜n＜5).因此，每个节点在T时间内的剩余能量表示为

$ \begin{array}{c} {E_{{\rm{rem}}}} = {E_0} - {E_{{\rm{node}}}}\left( {{v_i}} \right) = \\ {E_0} - T\left( {{E_{{\rm{elec}}}}k + {\varepsilon _{{\rm{amp}}}}k{d^n}} \right) \end{array} $

(12)

3 MQEN算法描述

如图 1所示，设定V为源节点，J为Sink节点.算法开始向整个网络发送一条携带T_k、m、threshold初始值的消息，通知网络中的所有节点，算法已开始运行. V节点加入活动集合ACTIV_SET中，并在通信范围R_c内向它的单跳邻居节点B、D、E、F广播一条携带地址、同步信息的数据包，B、D、E、F收到数据包后，返回V一条包含自己地址、同步信息的数据包，V收到B、D、E、F的数据包后返回一个确认字符(ACK，acknowledgement character)包，告知B、D、E、F已经建立联系，可以彼此互传信息. V节点动作集形成E_v={α₁, α₂, α₃, α₄}. V从动作集中随机选择一个动作，例如α₃、α₃对应的节点为E. E节点加入集合ACTIV_SET，随后E的学习自动机被激活，E节点建立动作集E_e={α₁, α₂}(由于采用决策树剪枝规则的自修剪算法，所以E的动作集不再有指向V节点的动作)，E的自动机随机选择一个动作，例如α₂、α₂对应的节点为H，H节点加入集合ACTIV_SET，此时H节点的自动机被激活，H建立动作集E_h={α₁, α₂}. H从动作集中随机选择一个动作，例如α₁、α₁对应的节点为J. J节点加入集合ACTIV_SET，第1轮循环结束.选择的路径为V→E→H→J.

算法的奖惩阶段开始，由于最小活动集合MIN_ACTIV_SET初始化为整个网络中的节点，所以MIN_ACTIV_SET集合的节点数大于集合ACTIV_SET，将集合ACTIV_SET中的节点赋给集合MIN_ACTIV_SET.因为只进行一轮循环，所以算法终止条件不满足.集合ACTIV_SET中节点数量、DT(l)的值都小于上一轮(上一轮为空)迭代的值，并且PDR大于或等于上一轮迭代的值，所以β(n)的值为1，ENV奖励自动机，更新其动作概率矩阵P(n). ENV提供一个增强信号给上一轮被激活的自动机，m的值自增一，再重新开始第2轮节点选举.

4 实验测试

采用Matlab仿真工具对MQEN算法模拟仿真，并且测试性能，分析数据，与LQOR路由协议^[8]、CMQRA路由协议^[9]、QMCRA_DP路由协议^[10]实验进行对比.由于上述协议采用的机制、原理各不相同，为确保实验的准确性、完整性，将仿真实验设置为同一网络拓扑结构、相同的参数，网络参数的设置如表 1所示.

网络仿真场景设置如图 2所示，网络大小为200 m×200 m，所有传感器节点随机部署在整个网络中，每个节点的感知范围为R_s，通信范围是R_c，初始能量为E₀，每个节点都具有一定的计算能力N_c、存储能力N_s.所有节点都是随机调度运行，可以在网络工作期间动态地自适应更新维护.网络场景外有一个基站，覆盖整个网络，用于信息处理、发送、接收.

图 3所示为4种算法迭代次数与PDR的关系. PDR表示端到端之间信息传输的可靠性，4种算法在多轮迭代后，PDR均提高，并且MQEN算法在端到端信息传输中的可靠性最高，其次是LQOR算法、CMQRA算法、QMCRA_DP算法.由于多轮迭代后，每种算法都选出适合本协议的最优传输路径.在MQEN算法中传感器采集到数据后，预处理感知数据，减少无效数据的传输.算法多轮迭代后，选择少量且高效的节点传输数据，提高网络传输信息的可靠性.

5 应用案例测试

使用Lab Center Electronics公司发行的proteus软件模拟多个传感器节点，使用MQEN算法采集数据，用virtual serial port driver导出proteus软件采集的数据，并由路由将数据实时回传，后台数据中心利用大数据分析、外部系统综合决策，使用python编写程序代码在网站上实现远程管理、运维、预测性维护. MQEN路由协议可应用于智慧农场，实时采集数据，无差传输、实时监控传感器设备. 图 4所示为模拟传感器采集数据电路.经过对比可知MQEN算法具有较好的应用性.

6 结束语

考虑到端到端延迟、能量消耗、端到端可靠性，提出一种面向边缘计算、节点能量优化的多QoS约束路由算法.采用边缘计算将学习自动机部署于各个节点，节点所分配的任务由对应的学习自动机依据客观环境优化配置，最大限度提升各个节点的运算能力.预处理传感器节点采集的数据，减少数据传输时间、传输能耗，保证通信质量，降低网络能量消耗，延长网络生命周期.实验结果证明，MQEN算法具备高效性、低能耗性，可实现最优路由节点选择路径.