无线Mesh网络中基于奖励机制的均衡传输方案

何 健

(罗定职业技术学院 电子信息系，广东 罗定 527200)

0 引言

无线Mesh网络即“无线网格网络”，它是多跳(multi-hop)网络，是解决“最后一公里”问题的关键技术之一[1]。在多跳无线Mesh网络中，从移动用户到有限网络的流量是经由网关通过多无线传输访问点(Transit Access Points，TAPs)进行处理。然而，在现有MAC操作中，对于一些距离网关几跳距离的用户，其可能会遭受较低的吞吐量[2]。甚至会由于多跳中继、流聚合和底层MAC层机制而导致吞吐量饥饿情况。为此，需要可以确保无线Mesh网络中公平资源共享的解决方案[3]。无线Mesh网络系统模型见图1。

图1 无线Mesh网络系统模型

由于无线Mesh网络中的下行流量不能通过逐跳传输进行聚合，因此当前的研究[4-6]集中于上行流量。事实上，下行流量通过扩散方式从网关传输到各个目标TAP，因此，由流量聚合和TAP之间的竞争而导致下行流量出现问题的概率较小。然而，下行流量的量常常要大于上行流量，这是因为移动用户常常从有线网络中下载数据。如果无线Mesh网络中的节点(TAPs和网关)为独立实体，那么去往不同TAPs的下行网络将会严重受到传输不均衡问题的影响[7-9]。迄今为止，极少有学者尝试解决这一点上的均衡问题。文献[10]提出了一种针对包含了自私TAPs的多跳无线Mesh网络的基于激励的传输机制，但是仅考虑了上行流量。由于上行流量和下行流量的均衡机制的关键设计问题不同，所以现有机制不能适用于解决具有自私节点的无线网格网络下行和双向流量的均衡传输问题。基于此，提出了一种基于奖励的传输机制，该方法主要创新点如下：

1)研究了自私TAPs和自私网关在无线Mesh网络中如何影响双向流量的均衡传输问题。

2)推导出了每个传输访问点(TAP)的双向目标吞吐量，并提出了一种基于奖励的均衡传输机制，通过信用币和代币支付策略来鼓励闲置TAP转发数据，同时使网关尽可能均衡地向TAP传输下行数据。

1 公平参考模型和虚拟信用币

1.1 公平参考模型

很多研究已经提出各种解决方案来解决无线Mesh网络中双向传输的均衡问题。然而，这些方案并没有考虑公平访问问题。要验证提出的基于奖励的均衡传输机制能否解决双向传输的公平问题，首先应该建立一套公平参考模型，为提出的机制提供理想基准，推导出理想状态下TAPs的客观吞吐量。要建立这样一个理想基准，则要做到以下几点。第一，公平的间隔尺寸为一个TAP-聚合流量，这是因为提出的机制是从服务提供者而非移动用户的角度而设计的。第二，使用广播时间取代吞吐量作为网络中的资源从而避免IEEE 802.11无线网络中的性能异常。一个TAP的目标吞吐量与其链路容量成比例，为TAPs支付更多的操作者理应拥有更高的链接容量，这对现实世界的商业模式也合理。第三，在不考虑TAPs到网关距离的情况下，所有TAPs都应当分配到相同的时间。这在多跳无线Mesh网络中是必要性能，因为不同位置上的TAPs不应该由于其到网关的距离受到处罚，必须最大化空间复用从而保证链接得到充分利用。

1.2 虚拟币假设

本文定义了两种虚拟货币：信用币和代币。信用币在多跳无线Mesh网络中没有实际的货币价值。当TAP向前一跳TAPs转发数据时可获得信用币，当其与局部移动用户进行数据包传输时使用信用币。该策略有助于鼓励TAP参加数据转发，以此增加其信用币的存量。对于TAP发送一个单位局部数据包所能获得的确切信用币数量，其是根据网络中每个TAP-聚合流量的目标吞吐量来确定的。与信用币不同，代币拥有实际货币价值。移动用户向处理其数据的相关TAP支付代币，TAP向网关支付代币来促使其尽可能多地传输数据。另外，TAP和网关在负责交易代币的中央银行兑现各自的代币。节点(即，用户、网关和TAP)可通过可用链路与中央银行进行交流，中央银行利用代币不同的卖出和买入价格来从中获利。其中，中央银行通常属于网络运营者或设备提供者。

总之，该策略鼓励TAP通过为其他TAP转发数据来增加信用币存量，并通过发送数据到其局部移动用户来赚取代币。本文假设每个TAP具备一个基于信任计算的防篡改模块，该模型是通过转发数据来获得信用币，通过发送局部数据来消耗信用币。因此，在提出的机制中，每个TAP 信用币的生成和消耗均可以防篡改。

2 基于奖励的双向均衡传输机制

2.1 奖励机制

无线Mesh网络中因自私节点导致的均衡传输问题已得到广泛认知，并且已经提出一些支持节点间合作的机制[11-13]。这些机制大体可分为两类：1)基于信誉的机制，其监控每个节点的行为并惩罚非合作节点；2)基于支付的机制，其引进了一些虚拟货币来支持向其他节点发送数据包。然而在无线Mesh网络中，收益主要来自于移动用户，而不是现有研究假设的TAPs或有线网络的终点。因此，上述基于信誉和基于支付的机制不能扩展用于解决包含自私节点的无线Mesh网络中的均衡传输问题。为此，本文提出的基于奖励的均衡传输机制兼顾了这些问题。

2.2 下行流量的均衡传输机制

先前的研究主要集中于无线Mesh网络中上行流量的均衡传输问题，上行流量在中间TAPs丢弃数据包，然而几乎所有的下行流量都在网关进行丢弃。因此，当网络节点为自私时，用于上行和下行流量的均衡传输机制的也存在不同。对于上行流量，关键角色为中间TAPs，设计的传输机制必须鼓励TAPs转发所有传输数据并向其移动用户提供真实的数据速率。然而对于下行流量，网关才是机制设计中最重要的一环，这是因为所有数据流量都必须从网关向无线Mesh网络发送。如果网关为自私的，就会造成中间TAPs的转发问题，显然，这种自私行为会造成下行流量的传输不均衡问题，因为网关控制了下行流量的整体性能[14]。因此，提出的新方法需要处理中间TAPs的转发问题，并且促进网关均衡地向不同TAPs传输数据。使每个TAP对其他TAPs的最优策略为转发所有传输数据，而对网关的最优策略，则是根据不同TAPs到最近TAPs的吞吐量，来确定下行数据传输到哪些TAPs。在提出的均衡传输机制中，每个TAP通过向邻近TAP转发一个单位传输数据获得一个信用币。为了赚取真实收益，TAPs必须收集足够的信用币来向其移动用户发送数据。向移动用户发送一个单位数据所需的信用币数量并不固定为一个。此外，根据TAPs接收的吞吐量，其向网关支付代币来确保网关会尽全力向无线Mesh网络传输下行数据。TAPs向网关支付的接收一个单位数据所需的代币数量也不固定，其是根据所有TAPs吞吐量的均衡指数来确定的。

TAPs也向通向网关的路由通道中的闲置TAPs支付代币，当TAPs和网关与银行有较好的链路链接时，其可以在中央银行兑现代币。因此，在提出的均衡传输机制下，这种消耗信用币和代币的支付设计，是鼓励自私TAPs转发所有的传输数据，而网关必须尽力向网络均衡地传输下行数据。

设计的策略具体如下：

1)通过控制每个时期自动产生的信用币数量和TAPs向网关支付的代币数量，并根据TAPs的目标吞吐量，使网关尽可能均衡地向TAPs传输下行数据。

2)调整每个TAP发送一个单位数据到其移动用户所需的信用币数量。用来确保每个TAP将会向其他TAPs转发所有的传输数据。

3)向路由通道中闲置的TAPs支付代币来鼓励其参与到数据转发中。

2.3 双向流量的目标吞吐量

首先，使每个TAP的下行和上行流量共享的时间一致，从而推导出多速率多权值Mesh网络中双向流量状况下的TAPs共享的目标时间。然后证明了当TAPs可以控制下行和上行流量之间的比率时，下行和上行流量的目标吞吐量的可行性(即，所有TAPs传输所有局部和传输数据所需时间为1，并且所有TAPs都有充足时间来传输所有传输数据)。

(1)

其中:WTAPi为网络中TAPi的权重。还需保证每个TAP有足够时间来转发来自前面TAPs的所有传输数据因此有：

∀i,j∈Rf

(2)

然后，必须满足下列方程式来获得最大聚合吞吐量。

(3)

这里为了描述简单，先假设无线Mesh网络中所有链接都有着相同的干扰范围(即，只有一个链接可以在网络中传输)。对于可以空间复用的网络，必须找到干扰范围内具有最多流量的瓶颈链接。ht为链接l上运行的流量数，CLl表示链接l的干扰范围内链接的集合。然后瓶颈链接定义为具有最大∑l∈CLlhl值的链接。由于希望所有上行和下行流量都可以充分利用网络资源，所以用等式∑fF∑l∈CLktlf= 1表示瓶颈链接的时间份额。

根据公式(1)～(3)，可以将每个流量x的第一个链接的时间份额计算如下：

belong to TAPk(TAPm)

(4)

由于每个链接可能具有不同链路容量，所以确定每个链接上的每个流量的目标时间份额如下：

is belong to TAPk(TAPm)

(5)

因此，具有双向流量的无线Mesh网络中每个TAP的目标时间份额为下行和上行流量时间份额的总和：

flowx(f) is belong toTAPm

(6)

然而，在真实无线Mesh网络中，TAPs应该有权控制上行和下行流量的比率。定义TAPi的上行和下行流量的时间份额如下：

(7)

(8)

(9)

根据公式(2)可以得出中间TAPs在考虑链路容量之后从TAPi转发传输数据所需传输时间，如公式(10)和(11)所示：

(10)

(11)

然后，TAPi的上行和下行流量的目标吞吐量为：

*Ci

(12)

(13)

2.4 提出的均衡双向传输机制

(14)

其中:STi为流量穿过TAPi的TAPs的集合。

*(1±δ),thenω=ω,

otherwiseω=ωL,whereωL>ωL

(15)

为了从有限网络向无线Mesh网络传输下行数据，网关从网络中所有TAPs处挣得代币。对于双向流量，公式如下：

*CTAPi*WTAPi/

CTAPi*WTAPi/(AdTAPi+AuTAPl)))2)

(16)

根据公式(16)，当网关根据TAPs目标吞吐量传输下行流量时，AT_FI的值为1。结果，网关转发一个单位数据就从TAPs接收ζ*AT_FI个代币。与前文描述的基于奖励的下行流量机制类似，TAPi向路由通路中闲置TAPs支付λ代币来传输一个单位下行或上行数据。值得注意的是参数ω、λ和ζ之间的关系为ω>λ+ζ。

3 仿真评估

3.1 实验环境

本章利用NS-2网络仿真器评估了提出的双向流量的均衡传输机制。重点关注双向流量的机制是因为空间限制以及双向流量包括下行流量。图2仿真模型是一个具有3个双向流量的TAPs的无线Mesh网络，在该网络结构中，处于两个跳跃之外的TAPs位于载波检测范围内。无线链接速率均设置为11 Mbps。这些仿真中使用的MAC协议是不具有RTS/CTS的IEEE 802.11 DCF。在接下来的仿真中假设TAPs可以通过交换信息学习移动用户的聚合流量负载。根据前面提到的设计原则，ω、ζ和λ的值分别为10、2和0.1/字节数据。提出的机制设定δ的值为5%。测量周期为1s。仿真中的所有TAPs都运行双向流量并且数据流量是数据大小为1000字节的UDP CBR流量。首先，所有TAPs饱和(即，总是有流量传输到移动用户或从移动用户传出)，并且TAPs的上行和下行流量的比率为：AuTAP1:AdTAP1=2:3，AuTAP2:AdTAP2=3:7，AuTAP3:AdTAP3=1:4。

图2 具有3个双向流量TAPs的无线Mesh网络

3.2 仿真结果

仿真结果如表1显示，初始条件下每个TAPs的上行流量和下行流量的平均吞吐量分别为：583和460、433和390、85和405，均衡机制条件下分别为：302和446、225和520、154和592。基于原始802.11 MAC协议，双向流量的平均吞吐量明显不公平。相反，均衡传输机制下的仿真结果与系统设置则十分接近。值得注意的是这里使用广播时间替代吞吐量作为网络中的资源从而避免IEEE 802.11无线网络的性能异常。表2

表1 TAPs上行和下行流量的平均吞吐量

表2 每个流量的平均吞吐量

显示了每个流量的平均吞吐量，每个TAP的目标吞吐量大约为742字节，这与仿真结果十分接近。上行和下行流量间的比率也确认了提出方法的配置。此外，仿真结果的平均吞吐量与公平参考模型下的目标吞吐量也十分接近。

接下来本文讨论了自私TAPs的不正当行为，即其宣布处于忙碌状态的错误信息。表3分别显示了TAP2在真实闲置和谎称非闲置时，在真实非闲置和谎称闲置时，其获得的代币。可以看出，当TAP2为闲置时，在宣布闲置时TAP3将会支付其114.24个代币来转发其上行和下行流量。然而，如果其行为不当或错误宣布其忙碌，则TAP3和TAP2的移动用户将不会向TAP2支付代币，这是因为TAP2忙碌，没有数据从移动用户传出或传向移动用户。同样，当TAP2真实忙碌(即，其有来自于移动用户的局部数据要发送)，它将无法谎称空闲。这是因为当其谎称空闲时，其他TAPs的支付要远少于移动用户(即，ω>λ)的支付。

表3 TAP2在闲置和非闲置情况下获得的代币

4 总结

对于无线Mesh网络中存在的自私节点问题，提出基于奖励的均衡传输机制来解决。再构建公平参考模型，并推导出理想状态下，每个TAP的客观吞吐量并证明了每个TAP上行和下行流量目标吞吐量的可行性。然后建立基于奖励的传输机制，最后，将均衡机制下的仿真结果与推导出的每个TAP的客观吞吐量进行比较，验证了基于奖励的均衡传输机制的可行性。此外，该网络中没有自私行为出现。

未来将会考虑复杂的网络环境，例如多网关、多信道分配、负载平衡以及资源分配问题。

[1] 冯琳函, 钱志鸿, 金冬成. 增强型的无线mesh网络信道分配方法[J]. 通信学报, 2012, 33(10): 44-50.

[2] 陈星晨, 张丽萍. 基于无线传输的车载温湿度测量系统设计[J]. 计算机测量与控制, 2017, 25(5): 42-44.

[3]NarlikarG,WilfongG,ZhangL.Designingmultihopwirelessbackhaulnetworkswithdelayguarantees.[J].WirelessNetw,2010,16(1):23-54.

[4]AvokhA,MirjalilyG.Load-balancedMulticastTreeRoutinginMultiChannelMultiRadioWirelessMeshNetworksUsingaNewCostFunction[J].WirelessPersonalCommunications, 2013, 69(1):75-106.

[5] 樊秀梅, 李晓辉, 何 骞. 无线Mesh网络中的组播机会路由研究[J]. 电子学报, 2010:38(1):32-36.

[6]JunJ,SichitiuML.FairnessandQoSinmultihopwirelessnetworks. [J].IEEEVTC, 2003,5(5):2936-2940.

[7]LiuT,LiaoW.Location-dependentthroughputanddelayinwirelessmeshnetworks[J].IEEETransVehTechnol2008,57(2):88-98.

[8] 符 琦, 陈志刚, 蒋云霞. 集中式无线Mesh网络信道分配策略研究[J]. 计算机应用研究, 2012, 29(8): 2821-2825.

[9] 夏汉铸, 刘辉元. 无线Mesh网络中基于信道状态的动态信道分配算法研究[J]. 重庆邮电大学学报: 自然科学版, 2014, 26(3): 362-366.

[10]LeeJ,LiaoW,ChenM.Anincentive-basedfairnessmechanismformulti-hopwirelessbackhaulnetworkswithselfishnodes[J].IEEETransWirelCommun. ,2008,7(2):697-704.

[11] 许世文. 基于SDN的信息中心网络的技术研究[D]. 北京:北京邮电大学, 2013.22-24.

[12] 王 坚, 李玉柏, 蒋勇男. 片上网络通信性能分析建模与缓存分配优化算法[J]. 电子与信息学报, 2009, 31(5): 1059-1062.

[13]ErnstJB,DenkoMK.Thedesignandevaluationoffairschedulinginwirelessmeshnetworks. [J].AcademicPress,Inc, 2011 , 77 (4) :652-664.

[14]KabbaniA,SalonidisT,KnightlyE.Adistributedlow-complexitymaximum-throughputschedulingforwirelessbackhaulnetworks.[J].IEEEINFOCOM, 2007, 20(3): 63-71.