-
摘要:
车辆群智感知旨在利用智能车辆配备的车载传感器和计算资源，收集一系列区域的感知数据. 目前，根据车辆轨迹是否可更改，通常可将感知车辆分为机会型车辆和参与型车辆. 其中，机会型车辆轨迹路线固定，不可随意更改. 而参与型车辆轨迹路线可根据现实需求进行更改. 因此，如何选择合适的机会型车辆完成感知任务，以及如何规划参与型车辆的轨迹是一项挑战性研究问题. 这里，以2种类型感知车辆的不同移动特性为出发点，通过群智感知平台（CSP）管理2种类型的车辆，并分别针对机会型车辆和参与型车辆解决不同的问题. 首先，针对机会型车辆，需选择特定的车辆集合，以完成感知任务并最小化CSP开销. 为解决此问题，提出一项基于反向拍卖的激励机制以选择开销最小的车辆集合完成感知任务，主要包括获胜车辆选择和报酬支付2个阶段，同时验证了所提方法可保证机会型车辆的个体合理性和真实性；其次，针对参与型车辆，需通过CSP调度以规划每个参与型车辆的轨迹，执行感知任务并最小化CSP的开销. 为解决此问题，提出一项基于深度强化学习的方法以调度车辆行驶轨迹，为车辆分配不同的感知任务. 此外，在最小化CSP开销的同时，还考虑感知任务执行的公平性问题，引入感知公平指数以确保不同子区域感知任务完成的均衡性. 最后，基于真实世界数据集的广泛评估表明，所提方法效果良好，并优于其他基准方案.
Abstract:Vehicular crowdsensing aims to utilize a large number of on-board sensors and computing resources in intelligent vehicles to collect sensing data in a series of areas. Currently, sensing vehicles are usually divided into opportunistic vehicles and participatory vehicles, according to whether the vehicle trajectory can be changed. Here, opportunistic vehicles are with fixed trajectories and cannot be changed. The trajectories of participatory vehicles can be changed based on actual needs. Therefore, selecting the appropriate opportunistic vehicle to complete the sensing task and planning the trajectory of the participatory vehicle is a challenging research problem. We take the different mobility characteristics of the two types of sensing vehicles as the starting point, and manage the two types of vehicles through the crowdsensing platform (CSP). Then, different problems are solved for opportunistic and participatory vehicles, respectively. Specifically, for opportunistic vehicles, it is necessary to select an appropriate vehicle set to complete the sensing task and minimize the cost of CSP. To solve this problem, we propose a reverse auction-based incentive mechanism to select the minimum cost vehicle set to complete the sensing task. It mainly includes two stages: winning vehicle selection and reward payment. Meanwhile, we verify that the proposed method can ensure individual rationality and authenticity. For participatory vehicles, it is necessary to plan the trajectory of each vehicle through CSP scheduling, perform sensing tasks and minimize the cost of CSP. To solve this problem, we propose a deep reinforcement learning-based method to schedule vehicle trajectories and assign different sensing tasks to vehicles. In addition, while minimizing CSP overhead, we also consider the fairness issue of sensing task. The sensing fairness index is introduced to ensure the balance of completion of sensing tasks in different sub-regions. Finally, extensive evaluations based on real-world datasets show that the proposed method performs well and outperforms other benchmark schemes.
-
软件定义网络（software-defined networking, SDN）作为一种新兴网络架构，将网络控制功能从数据交换设备中解耦出来，形成逻辑上集中的控制平面. SDN控制平面负责构建并维护全局网络视图，根据网络拓扑结构制定流规则，并通过以OpenFlow为代表的南向接口协议下发到数据交换设备中，从而实现灵活高效的数据传输. 基于OpenFlow的SDN技术有力地打破了传统网络的封闭和僵化问题，大大提升了网络的灵活性、可管控性和可编程能力，被普遍认为是未来网络最有发展前景的方向之一[1-2]. 经过十来年的不断发展与演进，SDN技术已广泛应用于各种网络场景，尤其是数据中心网络. 软件定义数据中心网络（software-defined data center network, SD-DCN）显著简化了网络功能管理，降低了部署成本，提高了数据传输效率，优化了网络应用性能，为数据中心的优化部署提供了新的技术方案[3-4].
数据中心作为承载海量数据处理的重要基础设施，广泛应用于在线购物、网络电视、短视频分享等数据密集型产业，目前已进入井喷式的高速建设和发展时期[5]. 然而，在数据中心规模飞速扩张的同时，能耗问题已成为制约其可持续发展的瓶颈. 在数据中心能耗中，网络设备产生的能耗占比可达50%以上[6]，主要由提供高速数据传输服务的交换机产生. 在SD-DCN网络中，OpenFlow交换机通常采用三态内容可寻址存储器（ternary content addressable memory, TCAM）存储流表以支持快速通配查找，其查找能耗高（15~30 W/Mbit）[7-8]，约为静态存储器的50倍[9]. 同时，SD-DCN网络采用等价多路径路由机制，将产生不少额外的流规则并存储到TCAM中，导致能耗问题更加凸显. 因此，如何设置OpenFlow交换机的TCAM容量，以平衡分组转发时延和TCAM查找能耗，是SD-DCN实际部署需要解决的一个关键问题.
目前已有不少研究工作关注OpenFlow交换机的TCAM能耗问题. 为降低TCAM查找能耗，部分研究人员采用内容可寻址存储器（CAM）缓存流表中的活跃流[10-11]，进而直接转发大多数分组，以大幅度减少TCAM流表查找操作. 然而，CAM同样采用并行查找方式，查找能耗仍高. 也有研究者利用过滤器预测流表查找失败情形[9]，减少不必要的TCAM查找操作，但只能过滤每条流的首个分组，节能效果极为有限. 还有研究人员关注OpenFlow交换机的TCAM流表优化模型[12-13]，但却主要关注流超时设置、流规则放置等问题，缺乏对其最优容量的考量. 此外，许多工作关注OpenFlow交换机的分组转发时延，利用排队论构建OpenFlow分组转发性能模型[14-15]，但却同样忽略了TCAM容量对分组转发时延的影响.
针对上述问题，本文面向SD-DCN网络场景，拟提出一种OpenFlow分组转发能效联合优化模型，以求解TCAM最优容量. 为此，本文首先描述了一个典型的SD-DCN网络部署场景，分析其分组转发过程和排队特性，构建OpenFlow分组转发时延模型. 然后，根据数据中心网络中的流分布特性，建立TCAM命中率模型，进而求解OpenFlow分组转发时延与TCAM容量的关系式. 进一步，结合TCAM查找能耗，建立OpenFlow分组转发能效联合优化模型，并设计对应的优化算法求解TCAM最优容量. 最后，通过模拟实验评估本文所提OpenFlow分组转发时延模型，并利用优化算法求解不同参数配置下的TCAM最优容量.
本文的主要贡献有4个方面：
1） 针对SD-DCN网络典型部署场景，在分析其分组到达和处理过程的基础上，为OpenFlow交换机构建了多优先级M/G/1排队模型，进而建立了一种更准确的OpenFlow分组转发时延模型；
2） 基于SD-DCN网络中的流量分布特性，为OpenFlow交换机建立了TCAM命中率模型，以求解OpenFlow分组转发时延与TCAM容量的关系式；
3） 以分组转发时延和能耗为优化目标，建立OpenFlow分组转发能效联合优化模型；
4） 证明了优化目标函数的凸性质，进而设计了优化算法求解TCAM最优容量，为SD-DCN实际部署提供有效指导.
1. 相关工作
针对OpenFlow交换机的TCAM能耗问题，部分研究人员设计了TCAM流表节能查找方案. Congdon等人[10]根据网络流量局部性，为交换机的每个端口设置CAM缓存，存储包签名与流关键字之间的映射关系，以预测包分类结果，使大部分分组绕过TCAM查找过程. 然而，CAM存储器同样采用并行查找方式，查找能耗仍高. 针对OpenFlow多流表的流水线查找模式，Wang等人[11]利用马尔可夫模型选取每个流表中的活跃表项，并集中存放到流水线前的Pop表中，使大部分分组查找命中Pop表，以避免复杂的多流表查找过程. Kao等人[9]提出了基于布鲁姆过滤器的流表查找方案TSA-BF，通过优化设计布鲁姆过滤器以预测流表查找失败情形，使新流分组绕过TCAM失败查找操作. 但该方案只能过滤每条流的首个分组，节能效果极为有限.
同时，许多研究工作利用排队论建立OpenFlow分组转发时延模型. 针对OpenFlow交换机的分组处理过程和SDN控制器的Packet-in消息处理过程，Xiong等人[14]将其分别建模为MX/M/1和M/G/1排队模型，Abbou等人[15]则分别建模成M/H2/1排队模型和M/M/1排队模型，Chilwan和Jiang[16]分别建模成M/M/1/∞和M/M/1/K排队模型，进而推导OpenFlow平均分组转发时延. 针对多控制器部署场景，Zhao等人[17]为SDN控制器集群和OpenFlow交换机分别建立M/M/n和M/G/1排队模型，分析平均分组转发时延，并结合SDN控制器集群的部署成本，求解最优控制器数量. 然而，文献[14-17]所述模型未考虑不同类型网络分组的优先级差异. 对此，Rahouti等人[18]将SDN网络建模成带反馈机制的双队列排队系统，将分组划分成多个优先级队列，以提供差异化的QoS服务. Li等人[19]为OpenFlow虚拟交换机的分组转发过程建立排队系统，以分析丢包率、流表查找失败概率、分组转发时延等关键性能指标，进而利用多线程处理、优先制队列设置、分组调度策略和内部缓存区设置等多种方法优化分组转发性能. 然而，文献[18-19]所述模型均未考虑TCAM容量对OpenFlow分组转发时延的影响.
进一步，已有部分研究工作关注OpenFlow交换机的TCAM流表优化模型. Metter等人[20-21]建立基于M/M/∞排队系统的流表解析模型，分析不同网络流量特性下流超时时长对Packet-in发送消息速率和流表占用率的影响. 进一步，AlGhadhban等人[12]为流安装过程建立基于类生灭过程的解析模型，分析流表匹配概率的影响因素，进而推导不同流超时时长下的流表容量. Zhang等人[13]采用M/G/c/c排队系统分析流超时时长对流规则的截断时间、冗余时间和安装失败率的影响，进而提出自适应流超时算法，以提高TCAM流表资源利用率. 然而，文献[12-13, 20-21]所述模型未考虑TCAM容量优化设置问题. 对此，Shen等人[22]将流表项生命周期划分为Packet-in消息发送、控制器处理和流表项超时3个阶段，并分别建立M/M/1，M/M/1和M/G/c/c排队模型，进而提出流表空间估计模型，求解流安装失败概率约束下的TCAM最小容量. 然而，该工作仅关注TCAM容量对流安装成功率的影响，却没有考虑流表命中率和分组转发时延等关键性能指标. 本文则考虑TCAM容量对分组转发时延和能耗的影响，建立OpenFlow分组转发能效联合优化模型，求解TCAM最优容量，为SD-DCN实际部署提供参考依据.
2. 面向SD-DCN的OpenFlow分组转发时延模型
本节在描述SD-DCN网络典型部署场景的基础上，为OpenFlow交换机的分组处理过程构建多优先级M/G/1排队模型，进而建立OpenFlow分组转发时延模型.
2.1 SD-DCN
随着在线购物、网络电视、视频分享、搜索引擎等数据密集型应用的日益盛行，数据中心作为承载海量数据处理的重要基础设施，其规模不断扩大，网络通信量正快速增长[23]. 传统数据中心网络因扩展性差、缺乏灵活的管理，无法满足数据处理业务中日益增长的网络需求. 基于OpenFlow的SDN技术将控制逻辑与数据转发相解耦，进而对网络设备进行逻辑上集中的管理和控制，并为上层应用提供统一的编程接口，大大提升了网络的灵活性、开放性和可管控能力，为构建高性能数据中心网络提供了新的解决思路. SD-DCN具备动态路由控制、服务质量管理、安全智能连接等技术优势，降低了数据中心网络的部署成本，有助于构建更加灵活高效的数据中心，已成为一种新的发展趋势[24].
图1描述了一种典型的SD-DCN网络架构，分为基础设施平面、数据平面、控制平面和应用平面. 基础设施平面包含众多服务器，提供强大的存储和计算能力. 数据平面大多采用fat-tree拓扑结构组网[25-26]，交换机自下而上分为边缘交换机、汇聚交换机和核心交换机，为众多服务器提供高性能的网络互联和数据传输服务. 在数据平面中，每个交换机根据控制平面下发的流规则，快速转发网络分组. 控制平面根据上层应用需求，基于全局网络视图制定流规则，并通过以OpenFlow为代表的南向接口协议下发到各个交换机中，指导分组转发行为. 应用平面基于控制平面提供的北向接口，实现服务编排、安全控制、QoS管理、资源调度等功能.
在图1所示的SD-DCN网络场景中，OpenFlow交换机根据SDN控制器制定的流规则转发分组. 对于每个到达的分组，交换机从分组首部提取匹配字段，进而查找流表. 若查找成功，则依据流表项中给定的动作集转发分组. 否则，交换机判定该分组属于新流，将其首部信息或整个分组封装成流安装请求发送到控制器. 控制器根据全局网络视图生成流规则，并下发到流传输路径上的各个交换机中. 交换机将流规则安装至流表，并据此转发该流后续到达的分组.
2.2 OpenFlow交换机排队模型
在SD-DCN数据平面中，来自服务器的大量分组汇聚到OpenFlow交换机，形成队列等待处理. OpenFlow交换机的分组排队和处理过程如图2所示. 对于到达的每个分组，交换机首先将其缓存到入端口队列，然后逐个解析分组首部信息，提取关键字段，以计算流标识符. 再根据流标识符查找OpenFlow流表，以定位对应的流表项. 若查找成功，交换机在ACL应用、计数器更新等一系列相互独立的操作后，将分组发送到出端口等待转发；若查找失败，交换机发送Packet-in消息给控制器，待收到相应的Flow-mod消息后，将其中的流规则安装到TCAM流表，并据此转发该流后续到达的分组. 控制器下发的Flow-mod消息同样以分组的形式到达交换机，但优先级高于数据分组，以保证分组转发行为的一致性和高效性.
![]()
图 2 OpenFlow交换机的分组排队和处理过程Figure 2. The queueing and processing of packet in the OpenFlow switch网络测量结果表明：在数据中心等大规模网络场景下，流量汇聚程度高，并发流数量庞大，趋于相互独立[27-28]. 因此，OpenFlow交换机的分组到达过程和流到达过程均可视为泊松过程[17,22]. 在OpenFlow分组转发过程中，所有新流的首个分组在Open-Flow交换机中的处理步骤相同，且处理过程相互独立. 根据Burke定理[29]，交换机发送的Packet-in消息流仍为泊松流. 假设每台交换机发送的Packet-in消息流相互独立，根据泊松流的可加性，汇聚到控制器的Packet-in消息流可叠加为泊松流. 控制器为每个Packet-in消息独立生成流规则后，以Flow-mod消息的形式下发至流路径上的各个交换机. 因此，OpenFlow交换机的Flow-mod消息到达过程同样为泊松过程. 假定控制器收到交换机Sk发送的Packet-in消息后，生成流规则并下发Flow-mod消息给交换机Si的概率为δik，则有δii=1. 若交换机Sk的Packet-in消息发送速率为
λ(in)k ，控制器共管理K台交换机，则交换机Si的Flow-mod消息到达速率如式（1）所示：λ(m)i=K∑k = 1δikλ(in)k. (1) OpenFlow交换机的分组处理过程可分解为首部解析、流表查找、计数器更新等相互独立的步骤，不妨假设其共有M步. 假设交换机Si中第j(1
⩽ j\leqslant M)步的处理时间Tij服从速率为μij的负指数分布，则其均值E(Tij)=1/μij，方差D(Tij)=1/{\mu_{ij}^2} . 由于每个步骤相互独立，因此交换机Si的分组处理时间Ti服从一般分布，其均值E(Ti)如式（2）所示：E({T_i}) = \displaystyle\sum\limits_{j = 1}^M {E({T_{ij}}) = } \displaystyle\sum\limits_{j = 1}^M {\frac{1}{{{\mu _{ij}}}}} . (2) 因此，交换机Si的平均分组处理速率
\mu _i^{({\text{s}})} 和分组处理时间方差\sigma _i^{{{({\text{s}})}^2}} 分别如式（3）（4）所示：\mu _i^{({\text{s}})} = \frac{1}{{E({T_i})}} = \frac{1}{{\displaystyle\sum_{j = 1}^M {{1 \mathord{\left/ {\vphantom {1 {{\mu _{ij}}}}} \right. } {{\mu _{ij}}}}} }}, (3) \sigma _i^{{{({\text{s}})}^2}} = D({T_i}) = \sum\limits_{j = 1}^M {D({T_{ij}}) = } \sum\limits_{j = 1}^M {\frac{1}{{\mu _{ij}^2}}} . (4) 基于以上排队分析，本文将OpenFlow交换机的分组处理过程建模为多优先级M/G/1排队模型：1）交换机Si的Flow-mod消息和分组到达过程为泊松过程，到达速率分别为
\lambda _i^{\left( {\rm{m}} \right)} 和\lambda _i^{( {\rm{p}})} ；2） OpenFlow交换机的入端口有Flow-mod消息高优先级队列和分组低优先级队列，按非抢占式多优先级调度策略依次处理；3）交换机Si的分组处理时间服从一般分布，分组处理速率和分组处理时间方差，分别如式（3）（4）所示. 根据排队论，可计算出Flow-mod消息和分组在交换机中的平均逗留时间为W_i^{({\text{m}})} 和W_i^{({\text{p}})} ，分别如式（5）（6）所示：W_i^{({\text{m}})} = \frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{1{{ - }}\rho _i^{({\text{m}})}}} + \frac{1}{{\mu _i^{({\text{s}})}}}, (5) W_i^{({\text{p}})} = \frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{\left( {1{{ - }}\rho _i^{({\text{m}})}} \right)\left( {1 - \rho _i^{({\text{m}})} - \rho _i^{({\text{p}})}} \right)}} + \frac{1}{{\mu _i^{({\text{s}})}}}. (6) 其中
\rho _i^{({\text{s}})} = {{(\lambda _i^{({\text{m}})} + \lambda _i^{({\text{p}})})} \mathord{\left/ {\vphantom {{(\lambda _i^{({\text{m}})} + \lambda _i^{({\text{p}})})} {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}} ，\rho _i^{({\text{m}})} = {{\lambda _i^{({\text{m}})}} \mathord{\left/ {\vphantom {{\lambda _i^{({\text{m}})}} {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}} ，\rho _i^{({\text{p}})} = {{\lambda _i^{({\text{p}})}} \mathord{\left/ {\vphantom {{\lambda _i^{({\text{p}})}} {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}} ，\bar R_i^{({\text{s}})} 为交换机处理分组时的剩余服务时间均值，如式（7）所示：\bar R_i^{({\text{s}})} = \frac{{E(T_i^2)}}{{2E({T_i})}} = \frac{{\sigma _i^{{{({\text{s}})}^2}} + {1 \mathord{\left/ {\vphantom {1 {\mu _i^{{{({\text{s}})}^2}}}}} \right. } {\mu _i^{{{({\text{s}})}^2}}}}}}{{{2 \mathord{\left/ {\vphantom {2 {\mu _i^{({\text{s}})}}}} \right. } {\mu _i^{({\text{s}})}}}}}. (7) 2.3 OpenFlow分组转发时延模型
根据SD-DCN网络中的分组转发流程，结合2.2节所述的OpenFlow交换机排队模型，可建立OpenFlow分组转发排队系统如图3所示. 在图3中，网络分组以速率
\lambda _i^{({\text{p}})} 到达OpenFlow交换机Si，在入端口处排队等待处理. 交换机Si依据TCAM流表以速率{\mu _i^{({\text{s}})}} 逐个处理分组. 假定TCAM流表命中率为hi，则交换机Si以速率\lambda _i^{({\text{in}})} = \lambda _i^{({\text{p}})}(1 - {h_i}) 发送Packet-in消息到SDN控制器. 控制器接收其管理的所有交换机发送的Packet-in消息流，并统一存入队列等候处理. 控制器的Packet-in消息到达速率为{\lambda ^{({\text{c}})}} = \displaystyle\sum_{i = 1}^K {\lambda _i^{({\text{p}})}(1 - {h_i})} ，处理速率为\mu^{({\rm{c}})} . 控制器为每个Packet-in消息生成流规则后，以速率\lambda _i^{({\text{m}})} = \displaystyle\sum_{k = 1}^K {{\delta _{ik}}\lambda _k^{({\text{p}})}(1 - {h_k})} 下发Flow-mod消息到交换机Si. 交换机将所有流规则依次安装到流表，进而转发新流的分组.在上述OpenFlow分组转发排队系统中，到达控制器的Packet-in消息流相互独立，其到达过程为泊松过程，且控制器对每个Packet-in消息的处理过程相互独立，处理时间可视为服从负指数分布[30-31]. 因此，可将控制器的Packet-in消息处理过程建模为M/M/1排队模型，进而可知Packet-in消息在控制器中的平均逗留时间W（c）如式（8）所示：
{W^{({\text{c}})}} = \frac{1}{{{\mu ^{({\text{c}})}} - {\lambda ^{({\text{c}})}}}}. (8) 根据上述OpenFlow交换机的分组处理排队模型和控制器的Packet-in消息处理排队模型，可推导出交换机Si的平均分组转发时延. 根据OpenFlow分组转发过程可知，交换机Si中的分组转发过程可分为2种情况：直接转发和请求控制器安装流规则的间接转发. 分组直接转发时延即为分组在交换机中的逗留时间
W_i^{({\text{p}})} . 分组间接转发时延包含分组在交换机中的逗留时间W_i^{({\text{p}})} 、Packet-in消息在控制器中的逗留时间W^{({\text{c}})} 、Flow-mod消息在交换机中的逗留时间W_i^{({\text{m}})} ，以及Packet-in消息和Flow-mod消息在交换机到控制器之间的总传输时延W_i^{({\text{t}})} . 因此，交换机Si的平均分组转发时延可表达如式（9）所示：{D}_{i}=\left\{\begin{array}{ll}{W}_{i}^{(\text{p})}, & 概率为{h}_{i}. \\ {W}_{i}^{(\text{p})}+{W}_{i}^{(\text{m})}+{W}_{i}{}^{(\text{t})}+{W}^{(\text{c})}, & 概率为\left(1-{h}_{i}\right)\text{.} \end{array}\right. (9) 将式（5）（6）（8）代入式（9）可得，交换机Si的平均分组转发时延Di如式（10）所示：
\begin{split} {D_i} =& {h_i}W_i^{({\text{p}})} + \left( {1 - {h_i}} \right)\left( {W_i^{({\text{m}})} + W_i^{({\text{p}})} + W_i^{({\text{t}})} + {W^{({\text{c}})}}} \right) =\\ &\frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{\left( {1- \rho _i^{({\text{m}})}} \right)\left( {1 - \rho _i^{({\text{m}})} - \rho _i^{({\text{p}})}} \right)}} + \frac{1}{{\mu _i^{({\text{s}})}}} +\\ & \left( {1 - {h_i}} \right)\left( {\frac{{\rho _i^{({\text{s}})}\bar R_i^{({\text{s}})}}}{{1- \rho _i^{({\text{m}})}}} + \frac{1}{{\mu _i^{({\text{s}})}}}+ \frac{1}{{{\mu ^{({\text{c}})}} - {\lambda ^{({\text{c}})}}}}+ W_i^{({\text{t}})}} \right). \end{split} (10) 3. 面向SD-DCN的OpenFlow分组转发能效联合优化模型
本节根据SD-DCN中的网络流分布特性建立TCAM命中率模型，进而结合2.3节所述的OpenFlow分组转发时延模型，建立OpenFlow分组转发能效联合优化模型，以求解TCAM最优容量.
3.1 TCAM命中率模型
在分组交换网络中，网络流量存在明显的局部性特点，大部分分组集中分布在少数流中[32]. 以数据中心网络为例，众多测量研究结果表明：20%的top流占据分组总数的80%以上[33]. 根据网络流量局部性，众多研究利用Zipf分布刻画网络流中的分组数量分布特性[34-37]. 假设网络中有N条流，则可按照流大小即流的分组数量依次递减排序为（f1, f2, …, fN）. 根据Zipf分布可知，流fr的分组数量Q(r)与其大小排名r（r=1, 2, …, N）存在式（11）所示的幂律关系.
Q(r) = \frac{C}{{{r\,^\alpha }}}. (11) 其中C和α均为大于0的常数，α表示分组在网络流中分布的倾斜程度. 假设OpenFlow交换机的TCAM容量为n条流表项，且存储所有网络流中排名靠前的n条流，则TCAM命中率h（n）如式（12）所示：
h(n) = \dfrac{{\displaystyle\sum_{r = 1}^n {Q(r)} }}{{\displaystyle\sum_{r = 1}^N {Q(r)} }} = \dfrac{{\displaystyle\sum_{r = 1}^n {{r^{ - \alpha }}} }}{{{{{\varGamma }}_\alpha }(N)}}. (12) 其中
{{{\varGamma }}_\alpha }(N) = \displaystyle\sum_{r = 1}^N {{r^{ - \alpha }}} . 假定网络流总数N=20000，对于不同的网络流分布倾斜度α，根据式（12）可得 TCAM命中率与TCAM容量的估计关系如图4所示.![]()
图 4 TCAM命中率与TCAM容量的估计关系Figure 4. Estimated relationship between TCAM hit rate and TCAM capacity从图4中可看出：α越大，相同容量下的TCAM命中率越高，即相同数量top流所占据的分组比例越高，网络流量局部性越明显. 当TCAM容量为4000条流表项，即可存储前20%的流时，若α=0.95，则TCAM命中率可达81.05%，与数据中心网络中的流量测量结果基本一致.
3.2 OpenFlow分组转发能效联合优化模型
在OpenFlow分组转发过程中，每个到达交换机的分组都需要查找TCAM流表，进而实现分组转发处理. 根据2.3节所述的OpenFlow分组转发时延模型和3.1节所述的TCAM命中率模型可知：TCAM容量越大，存储的流规则越多，TCAM命中率越高，即TCAM流表查找成功的分组占比越大，平均分组转发时延越小. 因此，平均分组转发时延与TCAM容量呈负相关关系. 由于TCAM采用并行匹配方式查找整个流表，查找能耗基本上与其容量成正比，假定分组转发过程中的其他能耗固定，则分组转发能耗可视为与TCAM容量呈正线性相关关系. 因此，可将TCAM容量作为决策变量，以分组转发时延和能耗为优化目标，建立能效联合优化模型求解TCAM最优容量.
对于TCAM容量为n的OpenFlow交换机，根据式（12）所示的TCAM命中率，定义TCAM流表命中失败概率q(n)=1− h(n). 进而结合式（10），可求出交换机的平均分组转发时延D(n)：
\begin{aligned} D(n) =& {W^{({\text{p}})}}(n) + q(n)\left[ {{W^{({\text{m}})}}(n) + {W^{({\text{c}})}}(n) + {W^{({\text{t}})}}} \right]= \\ & \frac{{{{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{\left[ {1 - {a_1}q(n)} \right]\left[ {1 - {a_1}q(n) - {\rho ^{({\text{p}})}}} \right]}} + \frac{1}{{{\mu ^{({\text{s}})}}}} +\\ & q(n)\left\{ \begin{gathered} \frac{{{{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{1 - {a_1}q(n)}} + \frac{1}{{{\mu ^{({\text{s}})}}}} + \frac{1}{{{\mu ^{({\text{c}})}} - {a_0}q(n)}} + {W^{({\text{t}})}} \\ \end{gathered} \right\}, \\ \end{aligned} (13) 其中
{a_0} = \displaystyle\sum\limits_{i = 1}^K {\lambda _i^{({\text{p}})}} , \;\; {a_1} = \dfrac{{\displaystyle\sum_{k = 1}^K {{\delta _k}\lambda _k^{({\text{p}})}} }}{{{\mu ^{(s)}}}}, {{\bar R}^{({\text{s}})}} = \frac{{{\sigma ^{{{({\text{s}})}^2}}} + {1 {/ {\vphantom {1 {{\mu ^{{{({\text{s}})}^2}}}}}} } {{\mu ^{{{({\text{s}})}^2}}}}}}}{{{2 {/ {\vphantom {2 {{\mu ^{({\text{s}})}}}}} } {{\mu ^{({\text{s}})}}}}}}. (14) 同时，根据式（12）给出的TCAM命中率，可建立OpenFlow交换机的分组转发能耗模型. 假定每条TCAM流表项的平均查找能耗为e1，由于TCAM容量为n条流表项，且采用并行查找方式，因此每个分组的TCAM查找能耗为ne1. 若分组转发过程中的其他处理能耗为e0, 则交换机的平均分组转发能耗E(n)如式（15）所示：
E(n) = n{e_1} + {e_0}. (15) 以式（13）和式（15）分别给出的平均分组转发时延和能耗为优化目标，可建立式（16）所示的OpenFlow分组转发能效联合优化模型，求解TCAM最优容量.
\mathop {\arg \min }\limits_n \left( {D(n),E(n)} \right). (16) 其中约束条件为
\begin{gathered} D(n) < {D_{\max }}, \\ E(n) < {E_{\max }}, \\ n \in {\mathbb{N}_ + }. \\ \end{gathered} (17) 式（16）优化模型包含3个约束条件：1） 平均分组转发时延D(n)不能超过QoS规定的最大时延Dmax；2） 平均分组转发能耗E(n)不能超过上限值Emax；3） TCAM容量n为正整数.
3.3 优化模型求解
OpenFlow分组转发能效联合优化模型是一个不等式约束下的多目标优化模型. 在该模型中，以TCAM容量n为决策变量，平均分组转发时延D(n)可通过定理1证明具有单调递减性，平均分组转发能耗E(n)显然单调递增. 而约束条件限定了D(n)和E(n)的最大值，即决定了TCAM容量的最小值nmin和最大值nmax，进而可求得D(n)和E(n)的最小值分别为Dmin=D(nmax)和Emin=E(nmin).
定理1. 对于式（13）中的平均分组转发时延D(n)，若其参数均为正，且ρ(m)+ρ(p)=ρ(s)<1，ρ(c)=λ(c)/μ(c) <1，则D(n)具有单调递减性，即
D'(n) < 0 .证明. 对于式（13），不妨假设n为连续自变量，利用复合函数求导法，可得D(n)的一阶导数：
{D^\prime }(n) = {D^\prime }\left( {q(n)} \right){q^\prime }(n). (18) 其中
D'\left( {q(n)} \right) 如式（19）所示：\begin{aligned} {D^\prime }\left( {q(n)} \right)=& \frac{{{{\bar R}^{({\text{s}})}}{a_1}}}{{g\left( {q(n)} \right)}} + \frac{{ - g'\left( {q(n)} \right){{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{g{{\left( {q(n)} \right)}^2}}} + \\ &\frac{{{{\bar R}^{({\text{s}})}}\left[ {2{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{1 - {a_1}q(n)}} + \frac{{{{\bar R}^{({\text{s}})}}{a_1}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]q(n)}}{{{{\left[ {1 - {a_1}q(n)} \right]}^2}}} + \\ & \frac{1}{{\mu _i^{({\text{s}})}}}+ \frac{1}{{{\mu ^{({\text{c}})}} - {a_0}q(n)}} + \frac{{{a_0}q(n)}}{{{{\left[ {{\mu ^{({\text{c}})}} - {a_0}q(n)} \right]}^2}}} + {W^{({\text{t}})}}. \\ \end{aligned} (19) 其中
g\left( {q(n)} \right) = \left[ {1 - {a_1}q(n) - {\rho ^{({\text{p}})}}} \right]\left[ {1 - {a_1}q(n)} \right], (20) g'\left( {q(n)} \right) = {a_1}\left[ {2{a_1}q(n) + {\rho ^{({\text{p}})}} - 2} \right]. (21) 在式（20）中，有
{a_1}q(n) = \dfrac{{\displaystyle\sum_{k = 1}^K {{\delta _k}\lambda _k^{({\text{p}})}q(n)} }}{{{\mu ^{({\text{s}})}}}} = {\rho ^{({\text{m}})}} < 1. (22) 进而可知1−a1q(n)>0. 由于ρ(m)+ρ(p)=ρ(s)<1，则有1−a1q(n)−ρ(p)=1−ρ(s)>0. 带入式（20）（21）中可得
g\left( {q(n)} \right) > 0, (23) g'\left( {q(n)} \right) = {a_1}\left[ {{\rho ^{({\text{s}})}} - 1 + {\rho ^{({\text{m}})}} - 1} \right] < 0. (24) 同时
{a_0}q(n) = \displaystyle\sum_{i = 1}^K {\lambda _i^{({\text{p}})}q(n)} = {\lambda ^{({\text{c}})}} ，而{\mu ^{({\text{c}})}} > {\lambda ^{({\text{c}})}} ，因此可得{\mu ^{({\text{c}})}} - {a_0}q(n) = {\mu ^{({\text{c}})}} - {\lambda ^{({\text{c}})}} > 0. (25) 加之各项参数为正，因此式（19）等号右边的每项均为正，进而可得
D'\left( {q(n)} \right) > 0 . 对q(n)求导有q'(n) = - \frac{{{n^{ - \alpha }}}}{{{{{\varGamma }}_\alpha }(n)}} < 0. (26) 将上述结论带入式（18）可知：
D'(n) < 0 .证毕.
此时，可将优化目标D(n)和E(n)分别进行归一化处理，进而利用线性加权法将式（16）中的多目标优化函数转换成单目标优化函数f(n)：
f(n) = \omega \frac{{D(n) - {D_{\min }}}}{{{D_{\max }} - {D_{\min }}}} + (1 - \omega )\frac{{E(n) - {E_{\min }}}}{{{E_{\max }} - {E_{\min }}}}, (27) 其中ω为OpenFlow 平均分组转发时延所占的权重. 该函数具有凸性质，如定理2所证.
定理2. 对于式（27）所示的目标函数，若其参数均为正，且ρ(s)<1，ρ(c)<1，则该函数具有凸性质，即
f''(n) > 0 .证明. 对f（n）二阶求导有
\begin{aligned} &f''(n) = \\ &\frac{\omega }{{{D_{\max }} - {D_{\min }}}}\left[ \begin{gathered} {D^{\prime \prime }}\left( {q(n)} \right)\frac{{{n^{ - 2\alpha }}}}{{{{{\varGamma }}_\alpha }{{(N)}^2}}} + {D^\prime }\left( {q(n)} \right)\frac{\alpha }{{{{{\varGamma }}_\alpha }(N)}}{n^{ - \alpha - 1}} \end{gathered} \right]. \end{aligned} (28) 其中
\begin{aligned} {D^{\prime \prime }}\left( {q(n)} \right) =& \frac{{ - 2{{\bar R}^{({\text{s}})}}{a_1}g'\left( {q(n)} \right)}}{{g{{\left( {q(n)} \right)}^2}}} + \\ & \frac{{2{{\bar R}^{({\text{s}})}}\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]\left[ {g'{{\left( {q(n)} \right)}^2} - {a_1}^2g\left( {q(n)} \right)} \right]}}{{g{{\left( {q(n)} \right)}^3}}} + \\ & \frac{{2{{\bar R}^{({\text{s}})}}{a_1}}}{{1 - {a_1}q(n)}} + \frac{{2{{\bar R}^{({\text{s}})}}{a_1}\left[ {2{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]}}{{{{\left[ {1 - {a_1}q(n)} \right]}^2}}} + \\ & \frac{{2{{\bar R}^{({\text{s}})}}{a_1}^2\left[ {{a_1}q(n) + {\rho ^{({\text{p}})}}} \right]q(n)}}{{{{\left[ {1 - {a_1}q(n)} \right]}^3}}} + \\ &\frac{{{a_0}}}{{{{\left[ {{\mu ^{({\text{c}})}} - {a_0}q(n)} \right]}^2}}} + \frac{{2{a_0}q(n)}}{{{{\left[ {{\mu ^{({\text{c}})}} - {a_0}q(n)} \right]}^3}}}. \end{aligned} (29) 其中
g\left( {q(n)} \right) 和g'\left( {q(n)} \right) 分别如式（20）和式（21）所示. 根据定理1的证明过程可知\begin{gathered} g'\left( {q(n)} \right) = {a_1}\left[ {{\rho ^{({\text{s}})}} - 1 + {\rho ^{({\text{m}})}} - 1} \right] < {a_1}\left[ {{\rho ^{({\text{m}})}} - 1} \right] < 0, \\ \end{gathered} (30) 因此有
\begin{gathered} g'{\left( {q(n)} \right)^2} = {a_1}^2{\left[ {{\rho ^{({\text{s}})}} - 1 + {\rho ^{({\text{m}})}} - 1} \right]^2} > {a_1}^2{\left[ {{a_1}q(n) - 1} \right]^2}. \\ \end{gathered} (31) 而
\begin{split} {a_1}^2g\left( {q(n)} \right) = &{a_1}^2\left[ {1 - {a_1}q(n) - {\rho ^{({\text{p}})}}} \right]\left[ {1 - {a_1}q(n)} \right] <\\ & {a_1}^2{\left[ {1 - {a_1}q(n)} \right]^2}, \end{split} (32) 因此，在式（29）中，有
g'{\left( {q(n)} \right)^2} - {a_1}^2g\left( {q(n)} \right) > 0. (33) 根据定理1的证明过程可知1−a1q(n)>0，μ(c)−a0q(n)>0，g(q(n))>0，g'(q(n))<0. 加之各项参数均为正，则式（29）等号右边的每项均为正，进而可知
D''\left( {q(n)} \right) > 0 . 同时，根据定理1的证明过程可知D'\left( {q(n)} \right) > 0 . 代入式（28）可得f''(n) > 0 .证毕.
由于目标函数f(n)具有凸性质，因此可利用二分法在整数范围[nmin, nmax]内搜索TCAM最优容量nopt，使f(n)取最小值. 算法1给出了OpenFlow分组转发能效联合优化模型的求解算法.
算法1. OpenFlow分组转发能效联合优化算法.
输入：1）网络拓扑信息G(V,E)；2） OpenFlow交换机的分组到达速率λ(p)，每个步骤j的处理速率
\lambda _j^{\left( {\rm{s}} \right)} ，控制器的Packet-in处理速率μ(c)；3） 平均每条TCAM流表项的查找能耗e1，分组转发过程中其他处理步骤的能耗之和e0，分组转发能耗上限Emax；4） QoS允许的分组转发时延上限Dmax.输出：交换机的TCAM最优容量nopt.
① 计算交换机的分组处理速率μ(s) 和分组处理时间方差
{\sigma ^{{{({\rm{s}})}^2}}} ;② 计算控制器收到交换机Sk发送的Packet-in消息后，生成流规则并下发Flow-mod消息给交换机Si的概率为δik ;
③ if λ(p)>μ(s)
④ exit；
⑤ end if
⑥
{n_{\max }} = \left\lfloor {{{({E_{\max }} - {e_0})} \mathord{\left/ {\vphantom {{({E_{\max }} - {e_0})} {{e_1}}}} \right. } {{e_1}}}} \right\rfloor ；⑦
{n_{\min }} \leftarrow {D_{\max }} ；⑧ while nmin ≠nmax do
⑨
{n_{{\text{mid}}}} = \left\lfloor {{{({n_{\min }} + {n_{\max }})} \mathord{\left/ {\vphantom {{({n_{\min }} + {n_{\max }})} 2}} \right. } 2}} \right\rfloor ；⑩ 计算目标函数f(nmid) , f(nmid +1)；
⑪ if f(nmid) > f(nmid +1)
⑫ nmin = nmid +1；
⑬ else
⑭ nmax = nmid ；
⑮ end if
⑯ end while
⑰ return nopt
= nmin. 算法1分为3个步骤：1）计算中间参数，包括交换机处理速率μ(s)（行①），交换机Sk发送的Packet-in消息触发控制器下发Flow-mod消息到交换机Si的概率δik（行②）；2）确定TCAM容量n的整数范围[nmin, nmax] （行⑥⑦）；3）二分查找TCAM容量的最优值nopt（行⑧~⑰）.
4. 实 验
本节首先通过模拟实验评估本文所提OpenFlow分组转发时延模型的准确性，然后采用数值分析方法分析不同因素对分组转发时延的影响，进而求解不同参数下的TCAM最优容量.
4.1 时延模型对比
实验采用Mininet平台模拟典型的Fat-tree网络拓扑结构[22]，SDN控制器共管理10台OpenFlow交换机，包含2台核心交换机、4台汇聚交换机、4台边缘交换机. 其中，SDN控制器采用OpenDaylight，OpenFlow交换机采用Open vSwitch v2.13. 在模拟实验中，利用OFsuite性能测试工具测得控制器的Packet-in消息处理速率为21 kmsg/s，每台交换机的分组处理速率为20 kpkt/s. 同时，将交换机的流表容量设置为8000条流表项，流超时间隔为10 s. 实验利用Iperf工具为每台交换机模拟产生不同速率的网络流量，其中新流分组占比约为10%，进而测得平均分组转发时延如图5所示. 同时，将上述参数代入本文所提的OpenFlow分组转发时延模型和现有模型，其中控制器均采用M/M/1模型，OpenFlow交换机分别采用多优先级M/G/1模型、M/G/1模型[17]、Mk/M/1模型[14]，进而计算出平均分组转发时延的估计值如图5所示.
![]()
图 5 不同分组到达速率下的时延模型对比Figure 5. Comparison of delay models with different packet arrival rates从图5中可以看出：与现有模型相比，本文所提基于多优先级M/G/1的OpenFlow分组转发时延模型具有更接近于测量值的估计时延. OpenFlow交换机的分组处理过程包含多个相互独立的步骤，而Mk/M/1模型将分组处理时间简单地看作服从泊松分布，故其估计时延与测量值相差较大. M/G/1模型可较为准确地估计OpenFlow交换机的分组处理时间，但在分组到达速率较大时，其估计时延明显较小. 这是因为该模型只考虑到达OpenFlow交换机的数据分组，而忽略了控制器下发的消息分组. 多优先级M/G/1模型则着重考虑了Flow-mod消息的分组处理时延，因而其分组转发时延估计值更接近于测量值.
实验采用4.1节所述参数，将OpenFlow交换机的分组到达速率
\lambda _i^{( {\rm{p}} )} 设为10 kpkt/s，并不断调整OpenFlow交换机的流表容量值，可测得平均分组转发时延如图6所示. 同时，将上述参数代入本文所提的OpenFlow分组转发时延模型和现有模型，计算出平均分组转发时延的估计值如图6所示.![]()
图 6 不同流表容量下的时延模型对比Figure 6. Comparison of delay models with different flow table capacities从图6中可以看出：本文所提OpenFlow分组转发时延模型的估计时延比现有模型更接近于测量时延. 现有模型由于忽略了流表容量对分组转发时延的影响，其分组转发时延始终保持不变，估计不准确. 与此形成对照的是，随着流表容量的不断增大，本文所提模型的分组转发时延估计值逐步降低，并趋于稳定，与测量值接近. 这是因为交换机的流表命中率随流表容量的增大而升高，进而导致发送给控制器的Packet-in消息逐渐减少，其估计时延逐步接近于M/G/1模型. 特别地，当交换机的流表容量小于3000条流表项时，模拟实验中的控制器负载过大，将会丢弃部分Packet-in消息，导致分组转发时延测量值急剧升高. 此时，对于OpenFlow分组转发时延模型，由于流表命中率过低，控制器的Packet-in消息到达速率高于其处理速率，导致模型失效.
4.2 分组转发时延
进一步，实验采用数值分析方法研究平均分组转发时延的主要影响因素. 实验参数设定为：假定分组在网络流中的分布倾斜程度α = 0.95，每台OpenFlow交换机的分组到达速率λ(p) = 10 kpkt/s，分组处理过程分为10个步骤，且每个步骤的处理速率相同，分组处理速率μ(s) = 20 kpkt/s. 同时，SDN控制器的Packet-in消息处理速率μ(c) = 21 kmsg/s，每台控制器管理10台OpenFlow交换机.
实验设置不同的TCAM容量，可得到平均分组转发时延与分组到达速率之间的关系如图7所示. 从图7可看出：当TCAM容量一定时，分组到达速率越高，交换机和控制器的负载越大，平均分组转发时延越高. 同时，当分组到达速率一定时，交换机的TCAM容量越大，流表命中率越高，Packet-in消息的发送速率越低，其在控制器中的逗留时间越短，平均分组转发时延越低. 此外，TCAM容量越大，允许的分组到达速率越高. 具体而言，当交换机的TCAM容量n分别为4000，6000，8000，10000条流表项时，平均分组转发时延在分组到达速率λ(p)分别超过10 kpkt/s，11.6 kpkt/s，12.8 kpkt/s，13.8 kpkt/s时急剧上升，且允许的最大分组到达速率分别为10.7 kpkt/s，12.6 kpkt/s，14.3 kpkt/s，15.3 kpkt/s.
![]()
图 7 平均分组转发时延与分组到达速率的关系Figure 7. Relationship between average packet forwarding delay and packet arrival rate实验设置不同的TCAM容量，可得到平均分组转发时延与分组处理速率之间的关系，如图8所示. 从图8可看出：当TCAM容量一定时，分组处理速率越高，分组在交换机中的逗留时间越短，平均分组转发时延越低；同时，当分组处理速率一定时，交换机的TCAM容量越大，流表命中率越高，发送给控制器的Packet-in消息越少，相应收到的Flow-mod消息也越少，平均分组转发时延越低. 此外，TCAM容量越大，交换机的分组处理速率需求越低. 具体而言，当交换机的TCAM容量n分别为4000，6000，8000，10000条流表项时，平均分组转发时延在分组处理速率μ(s)分别小于16 kpkt/s，14.5 kpkt/s，13.7 kpkt/s，13.2 kpkt/s时急剧上升，且交换机允许的最小分组处理速率分别为14.3 kpkt/s，13.4 kpkt/s，12.7 kpkt/s，12.1 kpkt/s.
![]()
图 8 平均分组转发时延与分组处理速率的关系Figure 8. Relationship between average packet forwarding delay and packet processing rate实验设置不同的TCAM容量，可得到平均分组转发时延与Packet-in消息处理速率之间的关系如图9所示. 从图9中可看出：当TCAM容量一定时，Packet-in消息处理速率越高，其在控制器中的逗留时间越短，平均分组转发时延越低. 同时，当Packet-in消息处理速率一定时，交换机的TCAM容量越大，流表容量越高，Packet-in消息的发送速率越小，其在控制器中的逗留时间越短，平均分组转发时延越低. 此外，交换机的TCAM容量越大，控制器允许的Packet-in消息处理速率越低. 具体而言，当交换机的TCAM容量n分别为4000，6000，8000，10000条流表项时，平均分组转发时延在Packet-in消息处理速率μ(c)分别低于18 kmsg/s，15 kmsg/s，12 kmsg/s，8 kmsg/s时急剧上升，且控制器允许的最低Packet-in消息处理速率分别为18.9 kmsg/s，14.1 kmsg/s，10.6 kmsg/s，7.9 kmsg/s.
![]()
图 9 平均分组转发时延与Packet-in消息处理速率的关系Figure 9. Relationship between average packet forwarding delay and Packet-in message processing rate4.3 TCAM最优容量
对于OpenFlow分组转发能效联合优化模型，不妨假设每条TCAM流表项的平均查找能耗e1为1个单位，其他处理步骤的能耗e0为3000个单位，分组转发能耗上限为Emax为15000个单位，即最大TCAM容量为12000条流表项. 同时，QoS要求的最大分组转发时延Dmax=1.5 ms. 基于上述参数配置，将单目标优化函数f(n)中的权重ω设置不同值，进而实现OpenFlow分组转发能效联合优化算法，求解不同分组到达速率下的TCAM最优容量如图10所示.
![]()
图 10 不同分组到达速率下的TCAM最优容量Figure 10. Optimal TCAM capacity with different packet arrival rates从图10中可看出：当每个交换机的分组到达速率增加时，TCAM最优容量将随之增大，以提高TCAM命中率，保证Packet-in消息发送速率不会过高，从而防止控制器过载，Packet-in消息逗留时间过大. 具体而言，当交换机的分组到达速率λ(p)分别为5 kpkt/s，10 kpkt/s，15 kpkt/s，且权重ω = 0.8时，TCAM最优容量nopt分别为1400，4600，10800条流表项. 当分组到达速率超过16 kpkt/s时，交换机需要继续增大TCAM容量，以保证分组转发时延，但分组转发能耗将会超出上限，因而无解. 此外，当分组到达速率一定时，分组转发时延的权重越高，TCAM最优容量越大，以使TCAM命中率越高，平均分组转发时延越小.
采用上述同样的参数配置，并将交换机的分组到达速率λ(p)设为10 kpkt/s，进而求解不同分组处理速率下的TCAM最优容量，如图11所示. 从图11中可看出：当交换机的分组处理速率升高时，TCAM最优容量将随之减小，并趋于稳定. 这是因为在保证分组转发时延的情况下，交换机的分组处理速率越高，需要的TCAM容量越小. 具体而言，当交换机的分组处理速率μ(s)分别为14 kpkt/s，16 kpkt/s，18 kpkt/s，且权重ω = 0.8时，TCAM最优容量nopt分别为8900，5800，4900条流表项. 此外，当交换机的分组处理速率低于12 kpkt/s时，由于逐步接近于分组到达速率，平均分组转发时延将超出QoS规定的上限，因而无解.
![]()
图 11 不同分组处理速率下的TCAM最优容量Figure 11. Optimal TCAM capacity with different packet processing rates采用上述同样的参数配置，并将交换机的分组处理速率μ(s)设为20 kpkt/s，进而求解不同Packet-in消息处理速率下的TCAM最优容量，如图12所示. 从图12中可看出：当控制器的Packet-in消息处理速率升高时，TCAM最优容量将随之降低，并趋于稳定. 这是因为控制器的Packet-in消息处理速率越高，其允许的Packet-in消息到达速率越高，进而交换机所需的TCAM容量越少. 具体而言，当Packet-in消息处理速率μ(c)分别为15 kmsg/s，25 kmsg/s，35 kmsg/s，且权重ω = 0.8时，TCAM最优容量nopt分别为6600，3800，2900条流表项. 此外，当Packet-in消息处理速率小于7 kmsg/s时，交换机需要继续增加TCAM容量，以提高TCAM命中率，保证平均分组转发时延，但分组转发能耗将会超出上限，因而无解.
![]()
图 12 不同Packet-in消息处理速率下的TCAM最优容量Figure 12. Optimal TCAM capacity with different Packet-in message processing rates5. 结 论
本文针对SD-DCN网络场景，利用多优先级M/G/1排队模型刻画OpenFlow交换机的分组处理过程，进而构建OpenFlow分组转发时延模型. 进一步，基于网络流分布特性建立TCAM命中率模型，求解OpenFlow分组转发时延与TCAM容量的关系式. 在此基础上，结合TCAM查找能耗，建立OpenFlow分组转发能效联合优化模型，以求解TCAM最优容量. 实验结果表明：与已有排队模型相比，本文所提时延模型更能准确估计SD-DCN网络场景下的OpenFlow分组转发性能. 同时，数值分析结果表明：交换机的TCAM容量和控制器的Packet-in消息处理速率对OpenFlow分组转发时延有着关键性的影响，而交换机的分组到达速率和分组处理速率影响较弱. 最后，通过OpenFlow分组转发能效联合优化算法，求解出不同参数配置下的TCAM最优容量，为SD-DCN网络的实际部署提供参考依据.
作者贡献声明：罗可提出研究思路，并设计研究方案，以及修订论文最终版本；曾鹏完善论文创新点，并完成模型的建立和推导，以及撰写论文初稿主要部分；熊兵设计了实验思路，以及审查和修改润色论文；赵锦元协助创新点推导和论文修改；所有作者都参与了实验分析和手稿撰写.
-
![]()
图 1 机会型车辆和参与型车辆感知示意图
Figure 1. Illustration of opportunistic and participatory vehicles sensing
![]()
图 2 基于反向拍卖的机会型车辆选择图
Figure 2. Illustration of reverse auction-based for opportunistic vehicles selection
![]()
图 3 基于 DRL 的参与型车辆调度示意图
Figure 3. Illustration of DRL-based for participatory vehicles scheduling
![]()
图 5 CSP 开销随机会型车辆数量的变化
Figure 5. CSP overhead changes with the number of opportunistic vehicles
![]()
图 6 CSP 开销随机会型车辆单位任务成本的变化
Figure 6. CSP overhead changes with the unit task cost of opportunistic vehicles
![]()
图 7 精度 0.01 时不同子区域网格感知任务完成次数可视化
Figure 7. Visualization of the number of completed sensing tasks in different sub-region grids at 0.01 accuracy
![]()
图 8 精度 0.005 时不同子区域网格感知任务完成次数可视化
Figure 8. Visualization of the number of completed sensing tasks in different sub-region grids at 0.005 accuracy
![]()
图 11 CSP 开销随参与型车辆数量的变化
Figure 11. CSP overhead changes with the number of participatory vehicles
![]()
图 12 CSP 开销随参与型车辆单位任务成本的变化
Figure 12. CSP overhead changes with the unit task cost of participatory vehicles
表 1 PA方法相关结果
Table 1 Related Results of PA Method
获胜车辆ID 单位成本 单位付款 CSP开销降低的幅度 任务完成次数 370 0.140326 1.233298 26.23132 24 179 0.152087 1.648364 35.91063 24 174 0.208489 0.918434 14.90886 21 290 0.140510 0.641551 17.03537 34 14 0.152216 1.260109 37.66836 34 339 0.202298 0.412341 6.721365 32 19 0.114158 0.350992 11.36804 48 278 0.299363 1.869238 31.39749 20 349 0.212298 1.412341 16.72136 32 30 0.121529 0.394767 15.57460 57 
下载: 导出CSV
-
[1] Yu Zhiwen, Ma Huadong, Guo Bin, et al. Crowdsensing 2.0[J]. Communications of the ACM, 2021, 64(11): 76−80 doi: 10.1145/3481621
[2] Liu Yutong, Kong Linghe, Chen Guihai. Data-oriented mobile crowdsensing: A comprehensive survey[J]. IEEE Communications Surveys & Tutorials, 2019, 21(3): 2849−2885
[3] Capponi A, Fiandrino C, Kantarci B, et al. A survey on mobile crowdsensing systems: Challenges, solutions, and opportunities[J]. IEEE Communications Surveys & Tutorials, 2019, 21(3): 2419−2465
[4] Ma Guoqi, Chen Honglong, Huang Yang, et al. Utility-based heterogeneous user recruitment of multi-task in mobile crowdsensing[J]. IEEE Internet of Things Journal, 2023, 10(11): 9796−9808 doi: 10.1109/JIOT.2023.3236679
[5] Li Xiaoqian, Feng Gang, Liu Yijing, et al. Joint sensing, communication, and computation in mobile crowdsensing enabled edge networks[J]. IEEE Transactions on Wireless Communications, 2022, 22(4): 2818−2832
[6] Ji Guoliang, Yao Zheng, Zhang Baoxian, et al. Quality-driven online task-bundling-based incentive mechanism for mobile crowdsensing[J]. IEEE Transactions on Vehicular Technology, 2022, 71(7): 7876−7889 doi: 10.1109/TVT.2022.3170505
[7] Liu Luning, Wang Luhan, Lu Zhaoming, et al. Cost-and-quality aware data collection for edge-assisted vehicular crowdsensing[J]. IEEE Transactions on Vehicular Technology, 2022, 71(5): 5371−5386 doi: 10.1109/TVT.2022.3151859
[8] Tong Yao, Zhu Shuli, Ren Xiaotong, et al. Vehicle inertial tracking via mobile crowdsensing: Experience and enhancement[J]. IEEE Transactions on Instrumentation and Measurement, 2022, 71: 1−13
[9] Yang Xinxin, Gu Bo, Zheng Beichen, et al. Toward incentive-compatible vehicular crowdsensing: An edge-assisted hierarchical framework[J]. IEEE Network, 2022, 36(2): 162−167 doi: 10.1109/MNET.104.2000773
[10] Ren Yilong, Jiang Han, Feng Xiaoyuan, et al. ACP-based modeling of the parallel vehicular crowd sensing system: Framework, components and an application example[J]. IEEE Transactions on Intelligent Vehicles, 2022, 8(2): 1536−1548
[11] Lai Yongxuan, Xu Yifan, Mai Duojian, et al. Optimized large-scale road sensing through crowdsourced vehicles[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(4): 3878−3889 doi: 10.1109/TITS.2022.3147211
[12] Fu Yanming, Qin Xiaoqiong, Zhang Xian, et al. Hybrid recruitment scheme based on deep learning in vehicular crowdsensing[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(10): 10735−10748 doi: 10.1109/TITS.2023.3276162
[13] 于瑞云,王鹏飞,白志宏,等. 参与式感知:以人为中心的智能感知与计算[J]. 计算机研究与发展,2017,54(3):457−473 doi: 10.7544/issn1000-1239.2017.20151021 Yu Ruiyun, Wang Pengfei, Bai Zhihong, et al. Participatory sensing: People-centric smart sensing and computing[J]. Journal of Computer Research and Development, 2017, 54(3): 457−473 (in Chinese) doi: 10.7544/issn1000-1239.2017.20151021
[14] 应臣浩,夏福源,李颉,等. 区块链群智感知中基于隐私数据真值估计的激励机制[J]. 计算机研究与发展,2022,59(10):2212−2232 doi: 10.7544/issn1000-1239.20220493 Ying Chenhao, Xia Fuyuan, Li Jie, et al. Incentive mechanism based on truth estimation of private data for blockchain-based mobile crowdsensing[J]. Journal of Computer Research and Development, 2022, 59(10): 2212−2232 (in Chinese) doi: 10.7544/issn1000-1239.20220493
[15] Chen Fangzhe, Huang Lianfen, Gao Zhibin, et al. Latency-sensitive task allocation for fog-based vehicular crowdsensing[J]. IEEE Systems Journal, 2022, 17(2): 1909−1917
[16] Xiang Chaocan, Cheng Wenhui, Lin Chi, et al. LSTAloc: A driver-oriented incentive mechanism for mobility-on-demand vehicular crowdsensing market[J]. IEEE Transactions on Mobile Computing, 2023, 23(4): 3106−3122
[17] Li Mengge, Ma Miao, Wang Liang, et al. Multi-task-oriented collaborative crowdsensing based on reinforcement learning and blockchain for intelligent transportation system[J]. IEEE Transactions on Industrial Informatics, 2022, 19(9): 9503−9514
[18] Xu Ying, Wang Yufeng, Ma Jianhua, et al. PSARE: A RL-based online participant selection scheme incorporating area coverage ratio and degree in mobile crowdsensing[J]. IEEE Transactions on Vehicular Technology, 2022, 71(10): 10923−10933 doi: 10.1109/TVT.2022.3183607
[19] Li Xin, Lei Xinghua, Liu Xiuwen, et al. Collision-free parking recommendation based on multi-agent reinforcement learning in vehicular crowdsensing[J/OL]. Digital Communications and Networks, [2023-05-10].https://doi.org/10.1016/j.dcan.2023.04.005
[20] Hu Miao, Zhong Zhangdui, Niu Yong, et al. Duration-variable participant recruitment for urban crowdsourcing with indeterministic trajectories[J]. IEEE Transactions on Vehicular Technology, 2017, 66(11): 10271−10282 doi: 10.1109/TVT.2017.2718043
[21] Abdelhamid S, Hassanein H S, Takahara G. Reputation-aware, trajectory-based recruitment of smart vehicles for public sensing[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 19(5): 1387−1400
[22] Wang En, Luan Dongming, Yang Yongjian, et al. Distributed game-theoretical route navigation for vehicular crowdsensing[C/OL]//Proc of the 50th Int Conf on Parallel Processing. New York: ACM, (2021-10-05)[2023-01-15].https://doi.org/10.1145/3472456.3472498
[23] Fan Guiyun, Jin Haiming, Liu Qihong, et al. Joint scheduling and incentive mechanism for spatio-temporal vehicular crowd sensing[J]. IEEE Transactions on Mobile Computing, 2019, 20(4): 1449−1464
[24] Gao Guoju, Xiao Mingjun, Wu Jie, et al. Truthful incentive mechanism for nondeterministic crowdsensing with vehicles[J]. IEEE Transactions on Mobile Computing, 2018, 17(12): 2982−2997 doi: 10.1109/TMC.2018.2829506
[25] Chen Xianhao, Zhang Lan, Pang Yawei, et al. Timeliness-aware incentive mechanism for vehicular crowdsourcing in smart cities[J]. IEEE Transactions on Mobile Computing, 2021, 21(9): 3373−3387
[26] Zhao Yinuo, Liu C. Social-aware incentive mechanism for vehicular crowdsensing by deep reinforcement learning[J]. IEEE Transactions on Intelligent Transportation Systems, 2020, 22(4): 2314−2325
[27] Xu Chenghao, Song Wei. Intelligent task allocation for mobile crowdsensing with graph attention network and deep reinforcement learning[J]. IEEE Transactions on Network Science and Engineering, 2023, 10(2): 1032−1048 doi: 10.1109/TNSE.2022.3226422
[28] Ding Rong, Yang Zhaoxing, Wei Yifei, et al. Multi-agent reinforcement learning for urban crowd sensing with for-hire vehicles[C/OL]//Proc of the 40th IEEE Conf on Computer Communications. Piscataway, NJ: IEEE, (2021-07-26)[2023-10-04].https://doi.org/10.1109/INFOCOM42981.2021.9488713
[29] Liu C, Dai Zipeng, Zhao Yinuo, et al. Distributed and energy-efficient mobile crowdsensing with charging stations by deep reinforcement learning[J]. IEEE Transactions on Mobile Computing, 2019, 20(1): 130−146
[30] Ding Lige, Zhao Dong, Cao Mingzhe, et al. When crowdsourcing meets unmanned vehicles: Toward cost-effective collaborative urban sensing via deep reinforcement learning[J]. IEEE Internet of Things Journal, 2021, 8(15): 12150−12162 doi: 10.1109/JIOT.2021.3062569
[31] Liu C, Chen Zheyu, Zhan Yufeng. Energy-efficient distributed mobile crowd sensing: A deep learning approach[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(6): 1262−1276 doi: 10.1109/JSAC.2019.2904353
[32] Zhou Huan, Wang Zhenning, Zheng Hantong, et al. Cost minimization-oriented computation offloading and service caching in mobile cloud-edge computing: An A3C-based approach[J]. IEEE Transactions on Network Science and Engineering, 2023, 10(3): 1326−1338 doi: 10.1109/TNSE.2023.3255544
[33] Zhou Huan, Zhang Zhenyu, Wu Yuan, et al. Energy efficient joint computation offloading and service caching for mobile edge computing: A deep reinforcement learning approach[J]. IEEE Transactions on Green Communications and Networking, 2023, 7(2): 950−961 doi: 10.1109/TGCN.2022.3186403
[34] Cao Xiaofeng, Yang Peng, Lyu Feng, et al. Trajectory penetration characterization for efficient vehicle selection in HD map crowdsourcing[J]. IEEE Internet of Things Journal, 2020, 8(6): 4526−4539
[35] Wang Xiaojie, Ning Zhaolong, Hu Xiping, et al. A city-wide real-time traffic management system: Enabling crowdsensing in social internet of vehicles[J]. IEEE Communications Magazine, 2018, 56(9): 19−25 doi: 10.1109/MCOM.2018.1701065
-
期刊类型引用(6)
1. 齐锐，彭依明，万静. 基于边缘计算的异构集群混合式资源调度方法. 电气技术与经济. 2025(01): 57-59 . 
百度学术
2. 任晓旭，仇超，邓辉，戴子明，刘泽军，王晓飞. 边缘智能融合区块链：研究现状、应用及挑战. 信息与控制. 2024(01): 1-16 . 百度学术
3. 王斌，马重阳，彭博，牛莹. 基于区块链的分布式算力资源调度机制. 中国宽带. 2024(05): 139-141 . 百度学术
4. 崔佳怡，谢人超，唐琴琴. 基于生成式人工智能的算力网络自智优化研究综述. 中兴通讯技术. 2024(06): 54-62 . 百度学术
5. 夏景旋 ，申国伟 ，郭春 ，崔允贺 . USPS:面向算力资源高效协同的用户态跨协议代理系统. 计算机科学. 2023(11): 348-355 . 百度学术
6. 周旭，李琢. 面向算力网络的云边端协同调度技术. 中兴通讯技术. 2023(04): 32-37 . 百度学术
其他类型引用(3)
计量
- 文章访问数: 220
- HTML全文浏览量: 37
- PDF下载量: 70
- 被引次数: 9
