摘要：基于权重最大一最小公平准则提出正规化余额扩展（ Normalized Residual Scaling，NRS）资源分配方法，适用于无线网络节点分布式数据传输调度，以实现上行带宽分配等相关应用。通过控制平均传输周期长度及调适个别节点的带宽用量，显著提升网络带宽使用率、降低节点处理控制信息的负担、保障各节点传输数据的最长潜伏期，并且通过正规化资源位准的概念改进算法，降低系统资源分配的计算复杂度。通过系统仿真与效能分析，该方法在轮询频率及带宽使用率皆有良好的效能。

关键词：权重最大一最小公平;水挹注程序;无线令牌环通讯协议

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2020）22-0069-02

开放科学（资源服务）标识码（OSID）：

1 前言

随着互联网的高速发展，使用移动设备通过无线网络进行各项应用与娱乐已成为很多人日常生活的一部分[1]。因物联网[2]及传感网络的应用不断增加，这些传感设备与轻量化终端设备必须通过各式的无线网络，将其数据传输至后端的服务系统。因此，无线网络已是现今与未来各项应用与服务的重要基础，学者们持续投入研究以提升无线网络的各项效能[3]。在无线传感网络中，如何有效节省与管理电量以延长整体网络的存活时间是一项重要的议题[4]。一般而言，传感节点传送与接收数据的无线通信动作为最主要的电量消耗来源，因此必须有良好的传感节点部署架构以及有效且公平的节点媒体访问控制与资源分配调度方式。

本论文提出一应用于无线网络中的分布式权重最大一最小公平准则的资源分配方法，本方法通过控制平均传输周期及调适个别节点的带宽用量，将各节点让出的系统资源按照权重比例实时地分配给网络中的全部节点，使系统整体资源的分配方式达成权重最大一最小公平准则。本方法具有以下优点：（1河弹性调整服务周期，有效提升资源使用率。（2）能保障各网络节点对于最小带宽的质量要求。（3）资源使用时间计算复杂度低。（4）可简化资源管理，避免控制信息过长而造成额外的成本。

2 相关技术

2.1 最大一最小公平资源分配

最大一最小公平（ Max-Min Faimess）是分时多任务系统中被广泛采用的资源分配模型，其定义如下：

依据此定义：在固定有限资源的条件下，假设N维实数序列x满足最大一最小公平资源分配，则对于其他任何分配方式y，任一使用者如果能在y中获得较多的资源，必定牺牲其他使用者t，使得y.< xt;且在原来的分配方式x中，使用者t获得的资源比s还要少。

2.2 无线令牌环通讯协议

无线令牌环通讯协议（Wireless Token Ring Protocol，WTRP）是支持分布式无线网络带宽分配的通讯协议之一，借由令牌传递来同步各节点的带宽使用时间。其作法系将系统节点在逻辑上组成一环状结构，所有节点于此结构单向传递一令牌，持有令牌的节点拥有带宽使用权，且必须在MTRT（ Maxi-mum Token Rotation Time）到期之前将令牌传递给下一节点。令牌环封包和数据的传输区间需保留一传递时间。此通讯协议实施一有限状态机，用以处理网络运作过程中可能发生的各种事件，包括：节点加入、节点离开、环修复、环重建、令牌同步。

3 分布式无线网络带宽分配

3.1 分布式无线网络传输架构

以下先说明一般分布式无线网络的传输架构，假设一无线网络包括N个节点，依序为n1，n2 ，...，nN，轮流使用网络带宽，每一节点ni对应一权重wi，当节点接收控制信息获得带宽使用权时，计算本次允许的带宽使用时间，利用这段时间进行数据传输;当使用权到期时，发送控制信息将使用权传递给下一节点。其中，带宽使用权的传递方式可为WTRP，或任何支持网络节点协同运作的传输协议。轮询规则容许在一个周期内多次拜访同一实体节点，依节点对于数据延迟的敏感度和传输量而弹性设计，但在带宽资源分配过程是将一周期内的每一节点在逻辑上视为不同节点。

3.2 带宽分配规则原型设计

此法通过轮流调度确保每个节点可得到一定的传输时间，并借由缩短传输周期回收剩余带宽再重新分配给未满足的节点，以改善带宽资源的使用率;但缩短周期使系统花费过高的时间比例在切换节点的带宽使用权，导致真正用于传输数据的带宽效能不佳，且过量的控制信息将增加无线网络的维护负担以及收发器的耗电量。

假设每一节点n.对应权重给定一基本传输时间‘（简称基本量），在节点轮流使用带宽的过程中，若节点传输数据所需时间q1（简称需求量）低于基本量，除将资源配额冻结之外，可将剩余资源（简称剩余量）依權重比例累加至其他未冻结的节点，因而需求量较低节点所节省的传输时间可公平转移至需求量较高的节点，避免传输周期缩减导致带宽使用率下降。

依据上述计算，节点ni在第k周期获得的带宽使用量si（k）是由需求量qi（k）和分配量di（k）决定，而分配量为基本量ti与优惠量pi（k）的总和，优惠量则是节点在此次使用带宽的前一周期内，所有节点释放的剩余量依权重比例平均分配的累加值，其中，剩余量ei（k）是分配量与使用量的差值。

3.3 带宽分配算法设计

本文目标为发展实用的无线网络带宽资源分配方法，满足权重最大一最小公平分配准则，且同时解决带宽使用率、计算复杂度等效能问题。为了克服上述缺点，我们采用了“资源位准”的构想，提出正规化余额扩展（ Normalized Residual Scaling，NRS）资源分配方法。除沿用前述定义，本方法另外基于正规化位准的概念引入下列变量：

B（x）系统带宽在第x次被使用前的系统优惠位准

bi（k）节点ni在第k轮使用带宽前的个体优惠基准

NRS方法将各节点让出的剩余量经过正规化后累加至系统优惠位准。并且定义传输节点获得的优惠量等于系统优惠位准在一周期内的增量、乘以该节点的权重。其中，系统优惠位准在一周期内的增量为节点本次传输和上次传输时的系统优惠位准的差额，本次传输时的系统优惠位准B（x）可通过控制信息传递，而上次的系统优惠位准即个体优惠基准bi（k），则借由节点在上一周期所储存的当时的系统优惠位准得来。

经由前面实例可知本论文所提的NRS方法与原型方法计算所得的分配结果完全相同，下面更通过数学证明来加以验证。由前述计算步骤可知，两者的主要差异在于优惠量pi（k）的定义。若将系统带宽在第x次被使用后的剩余量标示为e（x），则ei（k）=e（N×（k一1）+i）。

NRS方法借由傳输节点协同维护系统优惠位准以及活化节点权重总和，可将节点让出的带宽剩余量按权重比例实时地分配给所有的需求节点，相较于前述所提的带宽分配原型，节点在单一周期内计算带宽使用量的复杂度由O（N）降为0（1）。且因两者的带宽分配结果完全相同，故NRS方法可保证网络节点的带宽用量满足权重最大一最小公平准则，相较于WRR方法则提升了系统带宽使用率。

从带宽分配规则的原型设计可知，NRS带宽分配时序在一个传输周期内可由原本超前时间L转为对齐标准时序，在此情况下，节点等待数据传输的最长潜伏期为一个标准周期长度+L。为了保障节点的传输潜伏期，NRS方法可额外维护L（x），代表系统带宽在第x次被使用前的传输进度超前量，并且限制此超前量不高于Lmax。依据此限制，NRS方法的带宽使用量更改为：

当带宽使用期满时，则将更新后的进度超前量连同系统优惠位准与活化节点权重总和传递至下一节点。

由计算公式可知，进度超前量是各节点使用量低于基本量的差额累计值，因此，当节点评估本次带宽让予将使得进度超前量高于Lmax时，则依据超前量的限制来决定使用量。借此机制，NRS可调整传输周期弹性伸缩的最大范围，并且仍确保平均周期与标准周期长度相等。

4 系统仿真与效能分析

我们使用C++仿真WTRP网络传输系统，实验WRR与NRS带宽分配算法。系统仿真参数如表l所示。

假设全部节点的权重皆为1。其中n个负载节点持续要求最大带宽，另外（20-n）个沉默节点的带宽需求量为0。改变负载节点数量从2，4，6，…，至20，模拟分析下列各项效能指标：

（1）轮询频率：节点平均每秒获得带宽使用权的次数。

（2）带宽使用率：系统传送数据所使用的带宽占总带宽的比例。

（3）最长潜伏期：数据进入空队列到开始传送的最长时间间隔。

依据模拟结果可知，NRS方法借由保持传输周期平均长度而大幅降低节点轮询频率，以节省收发器耗电量及网络维护的负担;并且借由弹性调适个别节点的带宽用量，保障系统维持稳定的带宽使用率，因而有效提升负载节点的数据传输量。本方法付出的代价是稍微地增加了节点等待传输的最长潜伏期，但理论上潜伏期达到此最大值的发生概率非常微小。

5 结论

本论文基于水挹注程序概念提出NRS权重最大一最小资源分配方法，依据节点需求而弹性调整传输周期的长度，并且基于公用资源位准的概念提出正规化余额的加权运算方法，将计算节点带宽使用量的复杂度由O（N）降为0（1）。借由网络传输节点协同维护公用变量，可实时回收剩余的带宽资源并按照权重比例分配给所有的需求节点。经由实验模拟验证，NRS方法可显著提升网络系统带宽使用率及降低节点轮询频率，在多节点间歇性实时数据传输的应用情境下，可大幅改善系统效能。

参考文献：

[1]贺伟，梁潘.移动无线传感网络的分布式协作定位的研究[J].计算机应用与软件，2019，36（4）：161-165.

[2]任广鹏，杨志恒，申宇豪.分布式无线传感器网络通信协议分析[J].中国新技术新产品，2019（7）：37-38.

[3]刘文军，王喜，林政宽.无线传感器网络延迟约束的MDC分布式轨道规划算法[J].传感技术学报，2018，31（8）：1270-1276.

[4]陈倩，骆骏，乐婷婷.无线网络中分布式机会协作的信道接入算法研究[J].电子科技，2018，31（11）：6-10.

【通联编辑：代影】

作者简介：肖坚（1982-），男，湖南益阳人，湖南外贸职业学院讲师，硕士，研究方向：无线传感器网络、计算机应用、网络安全。