接入算法

接入算法（共7篇）

接入算法 篇1

摘要：多网融合是当今无线通信网络发展的必然趋势,垂直切换是网络融合的关键技术之一。对现有3G网络的终端接入信令流程进行分析,提出了一种基于分段式PPP协商的快速接入算法。通过在现网环境中测试,证明该算法有效地缩短了切换执行时延,对垂直切换过程中“切换执行”阶段的研究做出了贡献。

关键词：异构网络,垂直切换,快速接入,分段式PPP协商

0 引言

随着通信技术的日新月异,各种基于不同射频接入技术的无线网络应运而生,将这些网络进行融合,对所有通信终端形成一个分布式的通信系统,这就是异构网络。未来的4G网络将不再由单一的接入方式构成,而是采用不同无线接入技术的多种网络的融合[1]。

垂直切换技术是多网融合的基础。垂直切换的过程一般分为三个步骤:网络监测与评价;切换决策;切换执行[2]。目前对垂直切换的研究主要集中在切换决策算法上,对切换执行过程的研究非常有限。在实际的网络环境中,接入一个网络所花费的时间受到信号质量、当前用户数量、网络拥塞状况、所用协议等各种因素的影响,是一个在较大范围内变化的值。现有的切换决策算法一般不把切换执行时间考虑在内,而是理想的认为只要根据决策算法判断出需要切换,切换就能立即完成。在算法的研究过程中,这样的假设是必须的,但在工程实现时,如果不考率切换执行时间,再优秀的决策算法也会失效。本文从分析现网环境中移动终端的接入流程入手,提出了一种基于分段式PPP协商的快速接入算法,有效地缩短了切换执行时间。

1 现有终端接入流程分析

在现有的EVDO、WCDMA等3G网络环境中,终端都采用PPP协议[3,4]与网络侧建立连接。根据网络状况的优劣,该过程一般持续几秒至几十秒的时间不等,形成较长的切换时延。合理的简化或者分解PPP协商过程是缩短切换执行时间的有效途径。图1是EVDO网络中移动终端与网络侧的PDSN建立PPP协商的信令流程图,其它网络的PPP协商过程与之基本一致。

图1中BSC,PCF,PDSN,AAA都是EVDO网络的网元,移动终端的接入过程就是与PDSN建立PPP协商的过程。图1中移动终端直接参与的信令交互如下。

建立空口:移动终端向基站拨号,与网络侧建立起一条实际的物理连接。

LCP协商:终端与网络侧协商最大接收单元(MRU)等基本的通信参数,确定使用的鉴权协议以及通信中使用的协议压缩算法。

CHAP鉴权:网络侧发起鉴权过程,终端向网络侧提供用户名和密码以表明身份。

CCP协商:确定PPP压缩控制协议的具体参数。

IPCP协商:PDSN给移动终端分配IP地址。至此,终端接入网络,可以与连接在Internet中的其它终端通信。

连接计费开始:网络运营商开始对终端计费。

经过反复实验发现:PPP协商建立过程中空口建立和鉴权所花费的时间较短且稳定;LCP协商时间最长,往往引入较大时延。

2 基于分段式PPP协商的快速接入算法

根据上文所总结的现有PPP协商的特点,本文提出了基于分段式PPP协商的快速接入算法。该算法将PPP协商建立过程分解成两个阶段。

如图2所示,初始时移动终端通过WLAN接入Internet,并与某种3G网络完成PPP协商建立的第一阶段,该阶段包括空口建立、LCP协商和鉴权,然后维持IPCP协商,这一阶段耗时较大,因此在切换决策算法决定切换之前完成;在切换决策算法决定从WLAN切换到3G后,移动终端与3G网络完成PPP协商建立的第二阶段,该阶段仅包含IPCP协商,时间较短,从而缩短了切换执行时延。将PPP协商分成两段执行的具体方法是在正常的PPP协商程序中安装“协议过滤器”。所谓“协议过滤器”就是捕捉所有网络侧发来的IPCP协商的数据包并将它们丢弃的一段代码,同时移动终端不断地向网络侧发送IPCP请求以保证网络侧不会因为超时而中断协商,使得PPP协商建立过程停留在IPCP协商阶段。当切换决策算法决定要接入该网络时,向“协议过滤器”发送触发命令,令其放行IPCP协商数据包,使得移动终端最终完成IPCP协商与网络侧建立起PPP协商。各网络运营商都是在IPCP协商完成之后才开始对移动终端计费,所以当PPP协商完成第一阶段后停留在IPCP协商阶段时不会对用户造成费用的损耗。

基于分段式PPP协商的快速接入算法,一方面缩短了切换执行时间,另一方面由于预先完成了PPP协商过程中时间较长且不稳定的部分,因此一定程度上减小了切换执行时间的不确定性对整个切换过程的影响。

3 现网环境测试与分析

使用i386硬件系统结合WLAN、EVDO、WCDMA无线数据卡构成异构网络终端,软件系统采用Linux2.6内核的RHEL5.1,通过修改该系统原有的PPP协商程序pppd实现了基于分段式PPP协商的快速接入算法。将该终端置于具有WLAN, EVDO和WCDMA等多种网络的真实异构网络环境中进行测试。测试内容是在切换决策算法决定接入某个目标网络后,移动终端接入该网络所花费的时间,即切换执行时延。测试结果如表1-2所示。

表1给出了当切换决策算法决定切换到EVDO时原PPP协商建立过程和基于分段式PPP协商的快速接入过程分别花费的时间,表2是切换的目标网络为WCDMA时的情况。将表1和表2中的测试结果画成柱状图可以更清晰地展示使用基于分段式PPP协商的快速接入算法前后切换执行时延的差异,如图3所示。

测试结果表明:使用基于分段式PPP协商的快速接入算法后,切换执行时延与原过程相比有大幅下降。对于所测试的两种网络,平均时延分别缩短69%和70%。虽然在现实环境中的测试结果与当时当地的网络状况有关,每次测试结果的具体数值都不会完全一致,但基于分段式PPP协商的快速接入算法能够缩短切换执行时延的结论是显而易见的。

4 结束语

本文对现有3G网络的终端接入信令流程进行分析,提出了一种基于分段式PPP协商的快速接入算法。通过在现网环境中测试,证明了基于分段式PPP协商的快速接入算法有效地降低了切换执行时间。

参考文献

[1]刘敏,李忠诚,过晓冰,等.异构无线网络中垂直切换算法的评测与改进[J].软件学报,2007,18(7):1652-1659.

[2]BALASUBRAMANIAM,INDULSKA J.Vertical Handover Support-ing Pervasive Computing in Future Wireless Networks[J].ComputerCommunication Journal,Special Issue on 4G/Future Wireless net-works.2004,27(8):708-719.

[3]IETF RFC 1661.The Point-to-Point Protocol[S].

[4]IETF RFC 1332.The PPP Internet Protocol Control Protocol[S].

基于业务的光接入网路由选择算法 篇2

接入网(Access Network,AN)是指从端局到用户之间的所有机线设备,在整个电信网中有重要的基础性作用。随着光纤技术的发展,光纤接入方式将会逐渐取代传统的铜线接入方式,成为有线接入的主流技术之一[1,2,3]。目前的光传输路由选择算法大多针对光骨干网(Optical Backbone Network,OBN),对于光接入网(Optical Access Network,OAN)的路由选择算法研究不多。OAN有着不同于OBN的特点和问题,因此OBN的路由选择算法不能直接适用于OAN,开展OAN路由选择算法研究十分必要。

1光骨干网的路由选择算法

光传输网的路由选择问题实际是路由和波长分配(Routing and Wavelength Assignment,RWA)问题[4,5,6],在数学上抽象为带权图来研究。OBN中,工程应用较多的算法是最短路径法、最少网元法和负载均衡法。

1.1 最短路径法

最短路径法又称为Dijkstra算法。将OBN抽象为带权图G=(V,E),其中顶点V={1,2,…,n},边G的邻接矩阵用cost二维数组表示。若顶点i至j存在直接的边,则用cost[i][j]表示其权值;若不存在直接的边,则其权值为∞。设S表示一个顶点集合,顶点v0为源点,初始时,集合S只包含顶点v0,数组dist记录从源点到其他各顶点当前的最短距离,其初值为dist[i]=cost[v0][i],i=1,2,…,n。数组path记录从源点到顶点i之间的最短路径的前驱顶点,其初始值为v0。从S之外的顶点集合V-S中选出一个dist[w]值最小的顶点w。于是从源点到达w只通过S中的定点,把w加入集合S中,调整dist中记录的从源点到V-S中每个顶点v的距离:将原来的dist[v]和dist[w]+cost[w][v]进行比较,选择较小的值作为新的dist[v],同时令path[v]=w。重复以上过程,直到S中包含V中其余各顶点的最短距离。如果求到目标顶点的最短距离,找到对应的dist数组的值即可,通过遍历path数组即可找到目标顶点的路径踪迹[7]。

算法步骤如下:

(1) 初始化:S={v0},dist[i]=cost[v0][i],path[i]=v0;

(2) 从V-S中选出w,使dist[w]的值最小;

(3) S←w,从V-S中删除w;

(4) 调整dist[v]:dist[v]=min{dist[v],dist[w]+cost[w][v]}, path[v]=w;

(5) 判断V-S中是否为空,为空则算法结束,否则转步骤(2)。

1.2 最少网元法

该算法原理与最短路径法一致,将每一条边的权值均设置为1即可。这里不再赘述。

1.3 负载均衡法

上述二种算法没有考虑网络的均衡度,使得业务集中分布在几条最短的路径上,从而导致某些链路过于拥挤,而另外链路则较少被使用的现象。负载均衡算法[8]以网络整体流量的均衡性为优化目标,能有效地平衡负载,降低阻塞。

定义网络负载方差,对于有L条链路的网络,分别编号为0～L-1,第i条链路上负载为li,由此构成一个1×L的链路负载矩阵[l0,l1,…,lL-1],0≤i≤L-1。lave表示网络中所有链路上的负载平均值,以公式表示为:

$l{}_{\text{a}\text{v}\text{e}}=\frac{1}{L}{\displaystyle \sum _{i=0}^{L-1}l}{}_i(1)$

由此得到负载分布方差的定义如下:

$V{}_{\text{L}\text{A}}=\frac{1}{L}{\displaystyle \sum _{i=0}^{L-1}(}l{}_i-l{}_{\text{a}\text{v}\text{e}}){}^2(2)$

算法步骤如下:首先利用Dijkstra算法选择多条路径较短的光通道,并要求这些光通道在物理上是分离的,即遵守链路分离或边分离机制。然后按照式(1)、式(2)计算各条光通道在业务引入后,整个网络的负载分布方差。最后选取其中负载分布方差最小的光通道作为工作路由[9]。

2基于业务的光接入网路由选择算法

2.1 算法思想

以上三种路由选择算法有一个共同特点,它们都对网络进行了理想化的抽象和简化,没有考虑实际中的种种复杂因素。这对于OBN是可行的,因为OBN设备和线路质量较好,各种业务复用到一起,都能稳定可靠地传输。而OAN是直接面对用户的,由于环境、设备和线路等各种复杂原因,其稳定性和可靠性不如OBN,所以必须根据实际中的诸多因素合理分配链路资源,建立针对OAN的路由选择算法。

本文提了一种基于业务的OAN路由选择算法,其思想是根据业务类型和重要性构建不同的带权图模型,每一种模型采用相应的子算法,使整体资源得到合理配置。

2.2 算法步骤

算法的具体步骤如下:

(1) 对于用户接入业务进行分类。将较为重要的业务作为第一类业务。将传输质量要求较高的业务,如会议室视频会议业务等作为第二类业务。不属于第一类、第二类的业务作为第三类业务。

(2) 对于第一类业务建立基于稳定性的带权图模型。节点i,j之间的边权值cost[i][j]=pij,其中pij表示i,j之间链路出现故障的概率。首先按照最少网元法计算出多条网元较少的路由,再按照式(3)衡量路由的稳定性。

$p=1-{\displaystyle \prod _{k=0}^{m-1}(}1-\text{c}\text{o}\text{s}\text{t}[k][k+1])(3)$

式中:m表示所选路由途经网元的总数;cost[k][k+1]表示路由中第k个与第k+1个网元之间发生故障的概率;p即为该路由出现故障的概率。选择p值最小的路由作为业务路由,此时的路由是一种最稳定的路由。

(3) 对于第二类业务建立基于传输质量的带权图模型。节点i,j之间的边权值cost[i][j]=-10lg(Aij),其中Aij表示节点i,j上的光衰减[10]。按照最短路由法计算业务路由,将获得光网络中衰减最少的路径,可以最大程度地满足传输质量要求高的业务。

(4) 对于第三类业务建立基于负载的带权图模型。节点i,j之间的边权值cost[i][j]为链路负载。按照负载均衡法计算业务路由,此时在满足第一、二类业务需求的情况下达到整网负载均衡的目的。

2.3 算法的工程应用实例

某OAN网络拓扑图如图1所示。

该网络为双纤SDH光接入网,每一条链路均为一个STM-1,即包含了63个2M时隙。网络拓扑综合了星型、链型和环型结构,传输性能对算法比较敏感。在以往的运营维护中,所有业务均采用最少网元法配置,出现了以下问题:一是部分干线上负载过重,如J-JN-P,R-JY。在光缆线路意外中断时,会造成很大损失;二是一些重要业务被分配到一些故障概率较高的路由上,如从J站点至R站点的某单位程控用户小交换机的中继业务,被分配到J-JZ-P3-R路由上。该路由途经的两个站点均为二级站点,可靠性不如J-JN-P-R;三是需要高传输质量的业务得不到保证。如J-P的视频会议业务,被分配在J-JG3-JQC-JT-P路由上,用户反映会议质量不好,图像有时会有马赛克出现。

为了使用本文的算法改善网络的传输质量,首先对网络的各项参数进行了评估。从统计学角度出发,计算网络中相邻站点间链路的故障概率pij。

$p{}_{ij}=\text{链}\text{路}\text{中}\text{断}\text{总}\text{时}\text{长}/\text{链}\text{路}\text{运}\text{行}\text{总}\text{时}\text{长}(4)$

用光功率计测量并计算网络中相邻站点间的光衰减Aij:

$A{}_{ij}=(\text{发}\text{送}\text{端}\text{光}\text{功}\text{率}-\text{接}\text{收}\text{端}\text{光}\text{功}\text{率})/\text{发}\text{送}\text{端}\text{光}\text{功}\text{率}(5)$

由于网络为双纤网络,因此链路两端都要测量计算光衰减,并取平均值。采用本文提出的算法,对所有运营业务重新分配了路由,并统计了此后二年内网络的传输状况。从表1中可以看出,虽然业务配置时间有所增加,但是整个网络的传输质量得以改善。

3结语

本文对光接入网的路由选择算法进行了研究,考虑到光接入网的稳定性和可靠性不如光骨干网的现状,提出了一种基于业务的光接入网的路由选择算法。该算法根据业务类型和重要性构建不同的带权图模型,每一种模型采用相应的子算法,使整体资源得到合理配置。实践证明,虽然该算法计算量较大,但是能够使整网的资源得到优化配置,改善了网络的传输质量。

摘要：光接入网有着不同于光骨干网的特点和问题,不能直接套用光骨干网的路由选择算法。提出了一种基于业务的光接入网的路由选择算法。其思想是根据业务类型和重要性构建不同的带权图模型,每一种模型采用相应的子算法,使整体资源得到合理配置。实践证明,该算法能够改善网络的传输质量。

关键词：电信网,光网络,接入网,选路和波长分配

参考文献

[1]孙强,周虚.光接入网技术及其应用[M].北京:清华大学出版社,2005.

[2]蒋青泉.接入网技术[M].北京:人民邮电出版社,2005.

[3]雷维礼.接入网技术[M].北京:清华大学出版社,2011.

[4]顾碗仪,张杰.全光通信网[M].北京:北京邮电大学出版社,1999.

[5]纪越峰.光波分复用系统[M].北京:北京邮电大学出版社,1999.

[6]GORALSKI Walter.光网络与波分复用[M].胡先志,译.北京:人民邮电出版社,2003.

[7]龚倩倩.基于SDH的网管系统设计及其关键技术的研究[D].武汉:武汉理工大学,2010.

[8]乐孜纯,付明磊.IP over WDM网络中一种新型虚拓扑构造算法[J].通信学报,2007,28(6):96-101.

[9]蒋树嵩,王辉.基于负载均衡的矿井光纤通信传输网的研究[J].煤炭技术,2010,29(1):46-48.

接入算法 篇3

EPON (Ethernet Passive Optical Network, 以太无源光网络) 是光接入网的一种重要技术, 以其高带宽、易维护和廉价等优势成为接入技术的一个发展趋势[1]。为了适应不同用户的各种业务需求, EPON必须能够支持业务QoS需求, 并且利用动态带宽分配提高上行带宽的利用率, 为用户提供更好的服务, 介质访问控制 (Medium access control, MAC) 是以太网无源光学网络设计中的一个关键问题。EPON由三部分组成:OLT (Optical Line Terminator) 、ONU (Optical Network Unit) 以及ODN (Optical Distribution Network) 。EPON采用多点到点上行链路模式, 多个ONU共用一个信道, 主要数据传输方式为TDMA[2]。OLT集中控制各个ONU的上行数据传输, 主要利用Gate和Report机制来动态地分配带宽。现在的MAC机制有:停等机制 (图1) , 交叉询问机制 (图2) 。

如图1所示:在停等机制中, OLT向某一ONU发送GATE帧, 在此ONU回复OLT之前, OLT是不接受其他ONU的任何数据和报告的。当受到此ONU的数据报告后, 再向下一个ONU发送GATE帧。由此可见, 在OLT等待某一ONU的报告的这段时间内上下行信道都是空闲的, 没有任何数据的传输, 这是对带宽的极大浪费。对此进行改进就有了交叉询问机制。

如图2 所示, 在交叉询问机制中, OLT连续发送GATE帧给所有在线的ONU, 然后ONU顺序发送自己的报告。由此可见, 上下行信道得到了充分利用。但是, 因为信道的带宽是有限的, 因此, 又引发了一个问题, 当前面几个ONU的带宽报告把全部的带宽给占据后, 那么报告的ONU将不可能分配的带宽, 这严重违反了公平性的原则。

为了进一步改善上述两种MAC机制, 针对上述两种机制的问题, 提出了停等交叉询问机制, 如图3所示, 首先, 它与交叉询问机制一样顺序发送GATE帧给所有在线的ONU, 然后, 停止计算所有ONU的报告, 然后再分配给ONU带宽。

1 改进的带宽分配算法

现有的EPON带宽分配算法大多是基于MPCP协议的, 如IPACT[3]算法;BGP[4]算法; CBR算法等。但现有的算法都存在着问题, 如QoS实时业务的保证问题, 公平性问题, 带宽利用率问题, 轻负荷恶化问题等;结合了APON (ATM Passive Optical Network) 的最小分配法和最少业务量损失法[5], 提出改进的动态带宽分配算法, 并构建了基于OPNET的系统仿真模型, 仿真结果表明该算法有效地解决了, 轻负荷恶化问题, 低EF等级时延抖动等问题。

改进的算法中采用了支持服务等级协议 (SLA) [6], 将业务划分为:EF业务实时性比较强, 对时延非常敏感, 必须保证带宽按时送达, 优先级最高;AF:对时延有一定的要求, 带宽必须保证, 优先级次之;BE:对时延和带宽没有要求, 尽量传送, 优先级最低。

其中, 对高优先级的EF业务采用固定带宽分配, 对中低优先级的AF、BE业务采用根据负载情况分配的原则。在Report帧中只有中、低优先级队列大小, 高优先级业务占非常小的带宽。

高优先级的业务分配的带宽为G${}_i^{{\rm H}}$为:G${}_i^{{\rm H}}$=R${}_i^{{\rm H}}$, 中优先级的业务分配的带宽G${}_i^{{\rm M}}$为:

$G{}_i^{{\rm M}}=\min \left(R{}_i^{{\rm M}}‚\left(B{}_{\text{t}\text{o}\text{t}\text{a}\text{l}}-{\displaystyle \sum _{r=1}^{n}G}{}_i^{{\rm H}}\right)\frac{R{}_i^{{\rm M}}}{{\displaystyle \sum _{i=1}^{n}R}{}_i^{{\rm M}}}\right)$

低优先级的业务分配的带宽G${}_i^L$为:

$G{}_i^L=\left(B{}_{\text{t}\text{o}\text{t}\text{a}\text{l}}-{\displaystyle \sum _{r=1}^n(}G{}_i^{{\rm H}}+G{}_i^{{\rm M}})\right)\frac{R{}_i^L}{{\displaystyle \sum _{i=1}^{n}R}{}_i^L}$

每个ONU的参考授权带宽为:

$B{}_i=\frac{({\rm T}{}_{\text{c}\text{y}\text{c}\text{l}\text{e}}-{\rm N}*G{}^{{\rm H}})*W{}_i*R{}_u}{8*{\displaystyle \sum _{i=1}^{{\rm N}}W}{}_i}$

实际的授权带宽:

$B{}_i=\{\begin{array}{l}R{}_i=(R{}_i^{{\rm H}}+R{}_i^{{\rm M}}+R{}_i^L)\text{i}\text{f}(R{}_i＜B{}_i)\\ B{}_i\text{i}\text{f}(R{}_i\ge B{}_i)\end{array}$

其中, B${}_i^{{\rm H}}$是第i个ONU高优先级业务请求的带宽, R${}_i^{{\rm M}}$是第i个ONU中优先级业务请求的带宽, Ri是第i个ONU低优先级业务请求的带宽, Wi为各个ONU的授权因子, 因为在整个网络中各个ONU的等级不一定相同, 有些要用作专线。

为了公平性, 方针业务量大的ONU长期占据网络资源, 在OLT端对ONU设置的传输窗口, 其最大值为W${}_i^{\text{Μ}\text{A}\text{X}}$, 则最大轮询周期TCmax就是:

${\rm T}{}^{C\text{m}\text{a}\text{x}}={\displaystyle \sum _{i=1}^{n}W}{}_i^{\text{Μ}\text{A}\text{X}}/R{}_U+({\rm N}-1)*t{}_g$

同时, 在OLT端对EF业务的带宽并不是一直固定不变的, 而是通过设定一个查询周期, 这个周期比固定的轮询周期要大的多, 可以是几个过十几个轮询周期。

2 仿真与结果分析

为了能体现改进的算法的性能, 在OPNET下分别对现有的动态带宽分配算法和改进的算法分别作了仿真并对仿真结果作了相关分析。网络模型是由一个OLT、两个ODN以及10个ONU组成。主要仿真参数如下:下行数据链路传输速率RL=1000Mbps, 各个模拟数据源的速率为:RU=100Mbps, 仿真中1∶N光分路器中的N设定为8, 上行数据帧长2ms, ONU上行数据之间的保护时隙tg=5μs, 最大传出窗口W${}_i^{\text{Μ}\text{A}\text{X}}$=15000bytes, 设定所有ONU占用W${}_i^{\text{Μ}\text{A}\text{X}}$进行上传输数据, 网络负载取用户实际得到上行速率Ri与RU的比值。

当有效的网络装载是低时, 所有包的延时很少, 不管ONU装载情况如何。这是改进的带宽分配算法的明显优势:当网络装载是低的, 低优先业务将得到更多带宽, 这就解决了轻负载恶化问题。相反, 在ONU的低负载网络装载量高时, 网络整体延时很高。 导致此现象的原因是网络突发业务。这时, 轮询周期Tcycle将增加, 以便接受大于WMAXi得突发业务量。结果可能导致低等级的业务延时增加甚至超过一个轮询周期。网络负载量小于80%时, 包的丢失率为零或者很小可以忽略, 但是当网络负载量超过90%ONU的负载量超过50%时, 包的丢失率超过50%, 这同样是因为突发业务。此时, 可以适当的调小ONU的W${}_i^{\text{Μ}\text{A}\text{X}}$, 以降低包的丢失率。

从图4-6可以看出, 在轻负载时, 两种算法的平均帧延时非常接近, 但随着负载越来越大, 改进算法的优势就越来越明显, 而且高优先级的优势先开始呈现。图4中EF从网络负载0.3开始, 改进算法的时延开始低于现有动态带宽分配算法, 随着网络负载的越来越重时延差距越来越大, 图5中现有动态带宽分配的AF业务时延从网络负载0.45左右开始逐渐超过改进的算法, 图6是BE业务的时延比较图, 从网络负载0.55左右开始, 两种算法的时延曲线开始分叉, 改进的算法也明显优于现有的动态带宽分配算法。

3 结束语

EPON是解决接入网瓶颈问题的最佳解决方案, 因此动态分配算法就显得尤其重要。文中提出了一种改进的动态带宽分配算法, 首先, 针对现有的MAC机制的问题, 提出了一种改进的机制, 同时, 进行了方针, 从方针结果上看, 有效地保证整个EPON网络的QoS以及带宽分配公平性。在网络负载时, 在没有影响AF、BE业务的前提下, 使得EF业务的延时得到了改善。在网络负载超过50%时, 不论是EF业务, 还是AF、BE业务都有明显的改善。由此可见, 改进算法有效提高了上行信道的带宽利用率, 减小了EF等级业务的时延抖动, 具有较好的时延特性。

参考文献

[1]MCGARRY MP, MAIER M, REISSLEIN M.Ethernet PONs:A Sur-vey of Dynamic Bandwidth Allocation (DBA) Algorithms[J].IEEEOptical Communications, 2004 (8) :8-15.

[2]王亚民, 郭俊娜.一种改进的EPON动态带宽分配算法[J].光通信技术, 2007 (11) .

[3]KRAMER G, MUKHERJEE B, DIXITS, et al.Supporting differenti-ated classes of service in Ethernet passive optical networks[J].Opt.Networks.2002:280-298.

[4]MA M, ZHU Y, CHENG T H.A bandwidth guaranteed pollingMACprotocol for Ethernet passive optical networks[C].San Francis-co//Proc.IEEE INFOCOM, 2003:22-31.

[5]曾清海, 邱昆, 唐明光.一种APON上行带宽分配方案[J].通信学报, 2001, 22:86-91.

接入算法 篇4

随着无线通信技术的发展, 人们对频谱的需求越来越大, 预测到2010年对频带需求量将变为2002年的200%至300%[1], 然而由于目前的频谱资源的静态的分配策略导致了某些授权频段的频谱资源并没有得到充分的利用, 形成了频谱资源在时间空间频谱三个维度下的频谱空穴。以美国的为例, FCC在2003年提供的从时空二维的统计数据来看已经分配频谱的资源利用率为15%～85%[2];而另外一份2003年的调查指出, 授权频段在大多数的时候使用率只有6%[3]。

在这样的情况下, Mitola在1999提出了认知无线电的概念[4], 用来解决频谱资源紧张和大量频谱空穴存在的矛盾, 其基本思想是让无线电设备具有认知能力, 能感知外界的频谱环境, 利用频谱空穴进行通信。动态频谱接入是认知无线电系统中的关键技术之一。目前关于动态频谱接入的算法主要有合作和非合作的方式。文献[5]中合作方式的动态接入的方法需要认知无线电系统有一个专用信道来交换系统中的各个认知设备获得的信道信息, 但是在实际的认知系统很难保证随时都存在这个专有信道。非合作方式的动态接入算法, 只需要研究单个的认知设备, 但是要在规定的时间内检测所有频谱解释难以实现的。例如基于OFDM的动态频谱接算法, 实际的设备一个时隙内要检测所有子载波是难以实现的。因此提出了基于部分课观察马尔科夫决策过程的动态频谱接入算法, 该算法只检测部分信道就可以使得认知设备充分的利用外界的频谱资源。

1系统模型

动态频谱接入算法主要包括两个部分:感知和接入。感知部分就是决策是否要感知频谱, 以及感知哪个频段或者频道的频谱;接入部分就是根据感知的结果决策决定是是否接入相应的频谱当中去算法目的是在一定的时间内, 在硬件有限的限制下获得最多的空闲频谱资源并接入。

2系统建模

在模型中假设各个信道采用时分复用的方式 (如TD-SCDMA系统) , 且认知系统已经跟踪上了信道的复用时钟。假设系统中有N个信道, 每个信道带宽为Bi (i=1, 2, …N) 。每个信道的工作过程可以看作一个Markov过程, 其状态转移图如图1所示, 即每个信道都有两个工作状态{1 (Idle) , 0 (Busy) }。特别的我们假设在一定的时间间隔内 (T个时隙) , 各个信道统计特性都是不变的, 即图中的α, β保持不变。由于每个信道在一个时隙中有2个状态, 那么由N个信道组成的系统就有2N个系统状态, 那么在系统某个时隙t的状态可以用这个向量来表示[S1 (t) , …, SN (t) ], 其中Si (t) 表示第i个信道的状态, Si (t) ∈{1 (Idle) , 0 (Busy) }。引入变量信息向量π, 其表示当前系统在2N个系统状态上的概率分布, 显然∑πi=1。

算法的目的就是优化感知和接入的策略使得在一定时隙内认知设备可以获得最多的频谱资源。各个认知无线电设备在工作时没有中央控制器或者专有信道来协调他们工作, 所以在MAC层会采用一个分布式的接入协议, 但在此并不考虑此具体协议, 其对下面的讨论影响不大。

3 接入算法

由于受到硬件和时分系统同步的限制, 认知无线电设备不可能一次检测所有N个信道的状态, 只能选择一部分信道 (M1个信道) 来进行检测。检测完成之后, 根据检测的结果选择刚才的那部分的信道的一个子集用来进行接入, 这部分信道数量为M2, 显然M2≤M1。在本文只考虑M2=M1=1。那么我们算法就是决定每个时隙下的检测的信道和根据相应检测结果, 决定是否接入。由于系统可以建模为一个马尔科夫过程, 而认知无线电设备每个时隙只能观察到系统中有限的信道并且考虑信道检测的虚警和漏检概率, 因此采用部分可观察马尔科夫决策过程来求解算法。

算法的具体工作的过程如图2所示:在t时隙, 认知无线点设备根据之前设备工作的历史π向量估计系统所处的状态, 决定检测的信道a1 (a1∈{1, 2, …, N}) , 同时根据检测的信道结果θa1 (θ∈{Idle, Busy}) 决定接入动作a2, 获得相应的收益。在此时系统立即可以得到的收益的期望可以表示为:

$V{}^t={\displaystyle \sum _i{\displaystyle \sum _j{\displaystyle \sum _{\theta }\pi }}}{}_i^t{\rm P}{}_{ij}^{a{}_1}R{}_{j,\theta }^{a{}_1}W{}_{j,\theta }^{a{}_2}$ (1)

(1) 式中P${}_{ij}^a$表示在动作a下的系统转移概率;R${}_{{}^{j,\theta }}^a$表示在动作a下, 系统处于j状态观察

到θ结果的概率;W${}_{j,\theta }^a$表示系统在j状态下采用动作a观察到θ时认知无线电设备的收益。

因为一次检测相当于观察了一次系统, 那么可以根据观察结果获得了系统所处状态的最新信息;根据Bayes公式更新π向量到π′。

$\pi {}_j^{t+1}=\frac{{\displaystyle \sum _i\pi }{}_i^t{\rm P}{}_{ij}^{a}R{}_{j,\theta }^a}{{\displaystyle \sum _n{\displaystyle \sum _k\pi }}{}_n^t{\rm P}{}_{nk}^a}R{}_{k,\theta }^a$ (2)

(2) 式中π${}_j^t$表示在时隙t系统处于j状态的概率。

下一阶段的决策就要根据信息向量π′来确定当前的收益。根据算法的目的:认知无线电设备T个时隙内获在能得尽量多的空闲频谱资源, 可得到如下目标函数:

$\max ({\displaystyle \sum _{t=1}^{{\rm T}}V}{}^t)$ (3)

但是由于π的更新受前一阶段的动作a和观察结果θ的影响 (见公式 (2) ) , 所以时隙t作决策时不仅仅要考虑当前的收益Vt, 还要综合考虑该决策下造成的信息向量跟新对下一时隙的收益的影响。为了简化目标函数 (3) , 引入值函数

$V(n,\pi )=\max ({\displaystyle \sum _{t={\rm T}-n+1}^{{\rm T}}V}{}^t)$ (4)

其意义为在剩下n个决策时隙时、当前的信息向量为π时, 所能获得的最大收益。对于值函数V (n, π) 在最后一个阶段明显有:

$V(0,\pi {}^{{\rm T}})=\underset{a{}_1,a{}_2}{{\displaystyle \max }}({\displaystyle \sum _i{\displaystyle \sum _j{\displaystyle \sum _{\theta }\pi }}}{}_i^{{\rm T}}{\rm P}{}_{ij}^{a{}_1}R{}_{j,\theta }^{a{}_1}W{}_{j,\theta }^{a{}_2})$。

那么目标函数 (3) 式就可以改写为:

$\begin{array}{l}V({\rm T},\pi {}^1)=\max ({\displaystyle \sum _i{\displaystyle \sum _j{\displaystyle \sum _{\theta }(}}}\pi {}_i^t{\rm P}{}_{ij}^{a{}_1}R{}_{j,\theta }^{a{}_1}W{}_{j,\theta }^{a{}_2}+\\ V({\rm T}-1,{\rm T}(\pi {}^1|a{}_1,\theta ))))(5)\end{array}$

这样的迭代式。其中函数公式T (π|a1, θ) 是根据公式 (2) 更新信息向量的函数。

再考虑信道检测的工作参数 (虚警和漏检概率) 和实际系统所能忍受的碰撞概率。根据Neyman-Pearson准则, 漏检概率σ和虚警概率ε满足一定的函数关系。在这一限制条件下只考虑ε来确定信道检测的工作点。那么动态频谱接入算法求解就是以下优化问题的优化过程。

{a*1 (k) , a*2 (k) , ε*}=argmax (V (T, π1) )

s.t.

Pr (access channel i|Si (t) =0) ≤ξ (6)

(6) 式中a*1 (k) 、a*2 (k) 分别表示最优检测动作序列和相应的最优接入动作序列;ε*为认知无线电信道检测的最佳工作点;ξ表示系统所能忍受的认知设备与主用户碰撞的最大概率。

优化问题 (6) 式, 需要同时优化a1 (k) 、a2 (k) 和ε。似乎求解比较困难, 幸运的是文献[6]证明了ε的优化可以和a1 (k) , a2 (k) 分离开优化并不影响结果, 同时指出当ε*=ξ是检测器最佳工作点, 此时对应的a1 (k) , a2 (k) 关系为:

$a{}_2(k)=\{\begin{array}{l}\text{接}\text{入}\text{信}\text{道}a{}_1(k)‚\text{若}\theta {}_{a{}_1(k)}=1\\ \text{不}\text{接}\text{入}‚\text{若}\theta {}_{a{}_1(k)}=0\end{array}(7)$

(7) 式中θa1 (k) 表示检测信道a1 (k) 得到的检测结果, 如果检测到信道a1 (k) 空闲, a2 (k) 则选择接入到信道a1 (k) , 反之则不接入。通过公式 (7) , 优化问题 (6) 就只剩下了一个优化变量, 它的求解就变为了公式 (5) 的一个无约束的POMDP问题。该问题可以转化为一个动态规划的问题来求解;在每个阶段根据问题解的特性, 首先计算信息空间上的一个随机点的最优策略, 再从这个最优策略的适用的信息空间区域的边界搜索其他的策略的区域, 直到搜索完当前阶段的所有最优策略的区域。但是无约束POMDP问题的求解的复杂度会随着系统中信道数的增加成指数速度增长, 若要在移动设备上实现实时的计算非常的困难, 因此我们提出采用贪心法求解上述问题。将优化目标函数 (5) 后半部分V (T-1, T (π1|a1, θ) ) 略去不考合适的折中, 这样之后的仿真结果也可以看出, 即每个阶段只考虑当前阶段期望收益最大化忽略对下一阶段收益的影响, 如公式 (3) 所示。贪心法无法达到问题的最优解, 但是在解的优化程度和计算复杂度是一个合适的折衷。

4 仿真结果

在信道数为N=3, 各个信道的归一化带宽分别为0.9、1和0.8时, 各信道的统计特性α分别为0.1、0.5和0.8, β为0.5、0.4和0.3时, 通过仿真得到在相同的信息空间上的不同阶段数的累积期望收益。

从仿真结果可以看出, 基于POMDP最优解的接入策略任何情况下都能比其他方法获得更多的收益, 特别是随着总阶段T增大时, 这种优势更加的明显, 原因就在于本算法综合考虑了当前和未来的收益。为了降低算法的复杂度而提出的贪心算法, 在阶段数较小时 (见图3阶段数1～10处) , 其性能和最优解十分的接近, 但是随着阶段数的增加性能降低。至于随机检测接入的算法从实际应用来看它是一种“盲目”的算法, 所以它的性能是最差的。

5 结论

本文在分析当前认知无线电动态频谱接入的两类算法后, 提出了符合实际应用的情况使用的非合作式基于POMDP的动态频谱接入算法;鉴于POMDP问题求解的复杂度较高使用贪心法求解上述问题得到接入算法的次优解。通过仿真发现最优解和次优解在应用分别比随机检测接入算法多获得约25%和22%的带宽。

本文研究的接入算法检测接入信道数都为1的, 但当硬件条件提高时检测和接入信道增加时, 该算法需要做适当的改进才能应用;此外该算法还可以引进协作方式, 各个认知设备共享检测结果, 使得认知设备对外界频谱环境得到更加准确的估计。这些都是本课题后继可以研究的方向。

摘要：针对当前认知无线电动态频谱接入算法实现复杂度高的缺点, 提出了在硬件受限制的情况下, 基于部分可观察马尔科夫决策过程的动态频谱接入算法。该算法利用多次对外界信道的检测得到对外界环境的估计, 然后根据此估计以当前和未来收益总和最大化为目标, 实频谱接入, 并实现了最优解和贪心法次优解。该算法比随机检测接入算法多获得约25%的带宽, 贪心法的次优解在阶段数较少时与最优解性能非常接近。

关键词：认知无线电,动态频谱接入,部分可观察马尔科夫决策过程,动态规划

参考文献

[1]Reed D P.Howwireless networks scale:the illusion of spectrum scar-city.FCC Technological Advisory Coucil April2002and International Symposium on Advanced Radio Technologies (ISART2002) , March2002

[2]FCC, ETDocknet NO.03-103Notice of proposed rule making and or-der, December2003

[3]McHenry M.Spectrumwhite space measurements.NewAmerica Foun-dation Broadband Forum, June2003

[4] Mitola III J, Maguire Jr G Q.Cognitive radio: making software radios more personal.IEEE Personal Communications, 1999;6 (4) : 13—18

[5] Su Hang, Zhang Xi.Opportunistic MAC protocols for cognitive radio based wireless networks.Proc 41st Conference on Information Sciences and Systems (CISS 2007) , John Hopkings University, USA, March 2007:363—368

接入算法 篇5

协同多点传输/接收 (Coordinated Multi-point Transmission and Reception, Co MP) 对提升小区边缘用户的数据传输性能具有十分重要的作用。3GPP在Co MP R11项目中正式启动了针对Co MP技术在Het Net中应用的研究[1,2]。目前已有的研究工作[3,4,5]主要关注的是如何利用Co MP机制来改善Het Net中小区边缘用户的下行传输性能, 而怎样采用Co MP机制来提高小区边缘用户的上行传输性能, 还少有研究者关注。

在非异构LTE网络中, 研究表明采用Co MP机制能有效地改善小区边缘用户的上行传输性能[6,7,8]。但在Het Net中, 低功率小型基站的引入, 使得网络环境变得十分复杂, 网络中存在多个重叠覆盖的区域, 产生了多个新的小区边缘区域。小区边缘用户在采取Co MP机制进行上行传输时, 可选的协作基站数量和类型也大大增多。同时, 由于产生了多个新的微小区, 移动用户在不同小区间的切换也更加频繁。因此, 在Het Net中, 移动用户如何在复杂多变的网络环境下, 合理地选择合适的基站参与协作, 采用Co MP机制来提高上行数据传输的性能, 是一个值得深入研究的问题。

1 系统模型及问题描述

1.1 系统模型

一个典型的Het Net场景如图1所示, 一个宏小区中存在多个小型基站。Het Net中的小型基站类型有多种, 包括微基站 (Micro) 、微微基站 (Pico) 、家庭基站 (Femto) 和RRH (Remote Radio Head) 等。不失一般性, 本文用RRH来表示Het Net中的低功率小型站点。RRH通过光纤与宏基站相连, 拥有自己的物理小区ID, 并且发送自己的同步信号和参考信号等, 接入该RRH小区的用户直接从RRH处接收到调度信令和反馈信息, 并且发送上行控制信息和反馈信息给RRH。在上行链路中, 当采用Co MP机制来支持用户的数据传输时, 一个用户能够同时被一个主服务小区和多个协作小区服务。

1.2 边缘用户定义

一般情况下, 有2种方法来定义边缘用户, 一种是根据用户接收到的信号功率, 这种方法被大家广泛接受, 并在很多提案中使用[9];另一种是根据用户所在的地理位置来决定[10]。但在异构环境中, RRH的引入实际上对原来的LTE网络起到了小区分裂的作用, 提供了新的小区覆盖区域, 地理位置上就增加了新的小区边缘, 而且RRH的加入也会影响到用户的接收信号功率, 原有的边缘用户判定方法将不再适用[4]。综合考虑用户所处位置的实际链路衰落和环境噪声两方面对用户接收信号的影响, 选取用户接收的信干噪比 (Signal to Interference plus Noise Ratio, SINR) 来判定是否为边缘用户, 当用户接收到主服务小区的SINR小于某一门限值SINRth时, 被认为是小区边缘用户。

根据文献[4], 在实际的移动通信网络中, 小区边缘的用户约占用户总数的10%。通过仿真发现, 如果用户随机均匀分布在小区中, 当宏小区SINRth=0 d B, RRH小区SINRth=-15 d B时满足这一条件。因此在本文的研究中, 分别将宏小区和RRH小区的SINRth设置为0 d B和-15 d B。

2 上行Co MP的动态多小区接入算法

针对Co MP协作小区选择的研究, 目前在3GPP RAN1中主要有动态、静态以及半静态3种选择策略[11,12]。在Het Net中, 低功率基站的部署将导致网络拓扑变得更加复杂, 移动用户面临更加复杂的动态网络环境。因此, 考虑采用动态的Co MP协作小区选择策略, 根据用户所处环境的实际信道条件动态地选择协作小区参与上行Co MP传输, 提出了基于上行Co MP的动态多小区接入算法 (Uplink Co MP Dynamic cell Selection, UCDS) 。

对某一用户来说, 该用户到基站i的上行链路信干噪比用SINRi表示, 如果满足条件SINRi>SINRcomp_th, 则选择该基站作为协作基站, 其中SINRcomp_th为协作门限。在LTE标准中规定传输的BLER (Block Error Ratio, 误块率) 不得低于0.1, SINRcomp_th是保证用户到基站的上行传输链路满足最低BLER的最小SINR。根据链路级仿真结果得到满足BLER限制条件的最小SINR值约为-7 d B, 因此, 选择SINRcomp_th的值为-7 d B。

在一个时隙中UCDS算法步骤为:

对每个UE,

If UE∈Macro e NB

If SINRr<0 d B%接收SINR小于设定门限值, 为边缘用户

For b=1:Nb%计算用户到周边基站的上行传输SINR

仅列出宏小区用户的情况, RRH小区用户的算法步骤与宏小区类似。其中, SINRr表示用户接收的信干噪比;PN表示用户接收到的所有基站和RRH的功率总和;Pn表示热噪声功率;Pr表示用户接收到的主服务小区功率。SINR为LTE-A中上行传输信干噪比[14], 其中M为基站的接收天线数目。R为基站分配给用户的上行传输PRB集合, 由基站对用户的调度信息决定;NPRB为一个PRB上的噪声功率;Sm (r) 为用户接入的基站b在PRB r上对用户的接收信号功率。

3 基于二次判决的Co MP小区选择算法

在Het Net中, 采用Co MP机制来支持上行数据传输, 每个参与协作的基站都需要为用户的上行传输保留需要的资源, 并进行必要的控制信息交互。如果参与协作的基站数越多, 则Co MP传输消耗的系统资源越多, 算法实现的复杂度越高。

因此, 为了减少系统中的资源消耗, 降低算法实现的复杂度, 考虑在协作小区动态选择策略的基础上, 进一步加入二次判决机制, 提出了基于二次判决的Co MP协作小区选择算法 (Double Judgement based Co MP cell Selection, DJCS) 。当协作小区集中某个基站接收到的参考信号接收功率 (Reference Signal Received Power, RSRP) 远低于其它RSRP时, 该基站就不再参与到对边缘用户的协作处理, 从而在尽量保证用户传输性能的条件下, 减少参与协作的基站数量。

通过仿真发现, 当2条链路的RSRP相差10倍以上时, 采用Co MP传输机制和直接选取质量较好的链路进行传输, 获得的数据传输性能相近。因此, 在文中如果协作小区集中某个基站的RSRP低于其他基站10倍以上, 则该基站退出协作小区集。

根据上述分析, DJCS算法在一个时隙中的具体工作步骤如下:

①根据用户所在位置接收的SINR判定是否为边缘用户, 如果是, 则进行②, 否则用户进行非Co MP上行数据传输;

②计算边缘用户到周边基站的上行传输SINR;

③根据计算出的上行传输SINR是否大于Co MP判决门限SINRcomp_th来确定边缘用户的协作小区集;

④比较协作小区集中各基站接收到的RSRP, 当其中某个基站的低于其他基站10倍时, 该基站退出协作小区集;

⑤更新后的协作小区集中的基站对边缘用户上行数据进行联合处理。

4 仿真结果

考虑在一个由7个宏小区组成的Het Net场景中进行仿真验证, 其中每个宏小区分为3个扇区, 在每个扇区中部署一个RRH, 网络场景如图1所示。研究证明在LTE-A网络中将小型站点均匀放置在宏小区半径的2/3处, 将能防止过强的相邻小区干扰[15]。因此, 仿真中将RRH均匀地部署到宏小区半径的2/3处, 宏基站和RRH的发射功率分别为46 d Bm和30 d Bm, 宏小区和RRH小区的用户数分别为10和5, 仿真初始时刻用户随机分布在小区中, 并在仿真开始后, 在小区内以3 km/h的速度随机移动。

4.1 UCDS和DJCS的边缘用户吞吐率评估

为了验证Het Net中边缘用户采用UCDS和DJCS算法对数据传输性能的影响, 比较了这2种算法与不采用Co MP的传输机制带来的边缘用户平均吞吐率差异, 如图2所示。

从图2中可以看到, 在相同的用户发送功率下, 通过小区协作, 边缘用户的平均吞吐率获得了较大的提升。DJCS与UCDS相比, 边缘用户平均吞吐率差距并不明显, 这表明, DJCS算法在减少参与协作基站数量的同时, 能有效地保障用户的数据传输性能。

4.2 UCDS算法下的边缘用户能效评估

上行Co MP传输使边缘用户以较低的发射功率获得了较好的传输性能, 这说明用户在获得较高吞吐率的同时还获得一定的能效增益。定义边缘用户的能量效率为用户消耗单位能量所传输的数据量, 可以表示为:

式中, R表示边缘用户的平均吞吐率, Pe表示终端能耗。在上行传输中, 终端发射功率Ptx占了终端上行能耗的大部分, 它与Pe之间的关系为:Pe=η×Ptx, η表示终端上行能耗与上行发射功率的比值。η是一个固定值, 与功率放大器的放大系数等硬件因素有关系。

不同的用户发送功率下, 使用UCDS算法和非Co MP传输机制对用户能效的影响如图3所示。可以看到, UCDS算法能够有效提升终端用户的传输能效。

4.3 DJCS算法下的系统能耗评估

为了验证DJCS算法在系统资源消耗方面对UCDS算法的改进, 我们通过仿真比较了2种算法下, 小区边缘用户的平均吞吐率差异和基站端能耗差异。

定义DJCS算法在基站端的能耗为:

式中, Etotal_RB为基站进行数据处理时分配给所有用户的RB总和, Ucomp_RB为基站参与边缘用户的协作处理时, 分配给边缘用户的RB数。当不参与协作时, 基站被调度的RB数减少, 能耗降低。

DJCS与UCDS相比, 小区边缘用户平均吞吐率损失的比例和基站端能耗节约的比例如图4所示。从图4中可以发现, DJCS算法以较小的用户传输性能损失, 获得了较高的基站端能耗节约。

5 结束语

接入算法 篇6

随着无线技术的发展,无线局域网正走向大众化,并逐步融入人们的日常工作和生活中。目前,中国WLAN[1,2,3]市场逐步显现出强烈发展的势头,各运营商已开始大力铺设WLAN网络,并极力推广其应用。在WLAN体系结构方面,集中式WLAN体系结构由于能满足大规模组网需求,已成为发展趋势。在该体系结构中增加了接入控制器AC,对系统内的无线接入点(WTP)进行集中管理。AC通过WTP的定期报告,很容易知道全网的无线资源情况,然后根据当前情况,在系统内执行全局的无线资源管理策略。CAPWAP[4]是IETF正在标准化的协议,用于WTP与AC通信交互,基于集中式WLAN体系结构。

在WLAN系统中,由于无线终端(STA)的移动性和数据流的波动性较强,如何有效地平衡WLAN中各节点的负载差异,保持网络稳定和较高的服务质量是WLAN中的重要问题。负载均衡技术就是为了解决这一问题孕育而生的。WLAN负载均衡技术按照其解决方式分类[5]可以分为:接入式负载均衡和切换式负载均衡。接入式负载均衡就是通过控制STA的接入实现负载均衡,当AP的负载情况超过阈值后AP就会拒绝新的终端的接入,这时新终端需选择负载较轻的AP进行接入。而实现负载均衡的三个关键点在于:负载信息判定、负载信息更新策略和调度算法。

1 接入式负载均衡设计与实现

1.1 负载信息判定与收集

在WLAN中,采用以下三个指标来衡量一个WTP负载:

(1) WTP中接入STA的数量

接入STA的数量是衡量一个AP负载的一个基础指标,通常一个AP接入STA的数量越大,该AP的负载较重。

(2) RSSI值

接收信号强度指示RSSI(Received Signal Strength Indication),表示接收到的帧的信号强度。这也是衡量AP负载的一个基础指标,RSSI值越大,信号强度越高,其AP承受负载能力越强。

(3) 丢包率

丢包率是衡量无线局域网性能的重要参数之一,而当丢包率较大时候,发送一个数据帧的时间也就不断的延长,STA能获得的吞吐量也就越小,信道质量也相对较差。而丢包率可以用成功发送一个MAC帧的平均时间[6]来衡量。

在CAPWAP协议中,WTP和AC之间的通信交互,实现了对于AC关联的所有WTP的控制管理和数据转发。WTP定期扫描所有信道的无线资源信息,然后向AC发送扫描报告,这样AC可以计算出当前的WLAN网络拓扑图,也即收集了WTP的负载均衡信息。通过以下两种方法,AC从WTP获取需要的无线资源信息:

(1) 利用Wireless Specific Information选项

第一种方式是利用CAPWAP首部的Wireless Specific Information选项,把IEEE802.11标准定义的PHY信息包含在CAPWAP首部中进行传送,CAPWAP定义了如图1所示的IEEE802.11帧信息,其中包含了RSSI、信噪比、帧的接收速率等。

(2) 利用控制报文

第二种方式是利用CAPWAP定义的控制消息元素,WTP通过控制报文将无线资源信息传递给AC,可以传送的信息包括SSID、MAC地址、工作信道、工作功率、QOS参数和SNR信息等。

1.2 负载信息更新策略

按信息更新的驱动动机,节点状态更新方法[7]可以分为按需驱动、状态变化驱动和周期性驱动这三类:

按需驱动 当节点需要某些状态信息时,才通过向其他节点发送请求或命令收集状态信息。

状态变化驱动 当节点状态改变或改变到某种程度时发布其状态信息。

周期性驱动 节点定期交换或收集负载信息。

在CAPWAP结构中,采用周期驱动与状态变化驱动相结合的方式对负载信息进行更新,可以很好地完成负载信息收集,从而为调度算法打下基础。

1.3 算法设计与实现

接入式负载均衡的关键问题[8]在于STA如何选择最优WTP进行关联。该算法的基本思想是通过比较WTP中接入STA的数量和RSSI值筛选出候选WTP,然后从候选中选择具有发送MAC数据帧的平均时间最小的WTP进行接入。

算法整体上分成四个步骤:

Step1 在STA加入某个WTP之前,STA先给AC发送一个加入请求帧。

Step2 AC根据各WTP接入STA数量和RSSI值返回候选WTP1 ～WTPn。若n=1,即候选WTP数量为1,则STA即可与该WTP关联,否则,转Step3。

Step3 STA向每个候选WTP发送K个探测请求帧,并记录发送时间,S1～Sk,之后STA会收到WTP的探测响应帧,记录STA收到探测响应帧的时间R1～Rk。计算STA探测响应帧的平均时间T为:${\rm T}=\frac{{\displaystyle {\sum }_{i=1}^{{\rm K}}(}R{}_i-S{}_i)}{{\rm K}}$ (1)

Step4 STA向T最小的WTP发送关联请求帧,并通知AC,AC建立STA与该WTP的关联关系。

2 仿真实验及分析

利用仿真工具验证文中提出的基于CAPWAP的WLAN接入式负载均衡技术的有效性。实验中共有3个WTP形成三个基本架构服务子集,即BSS1、BSS2和BSS3,整个网络仿真模型构成了一个扩展服务子集。三个WTP的覆盖区域之间都存在着重叠区域,分别工作在不同的信道之上,互相之间的干扰较小,其余配置参数如表1所示。

图2所示是传统的接入式算法[9],即基于STA数量和RSSI值筛选WTP的算法,可以看出,各WTP业务量随着STA的加入不断上升,WTP的吞吐量也在不断提升,在STA全部加入到WLAN之后(720s),各个WTP的吞吐量也趋于平衡。但是传统算法只考虑STA数量和RSSI值,由于STA的业务量不同,使得WTP的负载出现较大差异,WTP2关联的STA业务量较小,其吞吐量也较小,还有很多闲置的资源未经利用。

图3所示是本文算法,综合考虑了STA数量、RSSI值以及探测请求帧的平均探测时间等指标,三个WTP的吞吐量曲线比较接近,即吞吐量差不多大小。说明该算法能很好地衡量WTP的负载情况,使WLAN中各WTP的负载也基本达到均衡。

3 结 语

负载均衡的关键技术在于如何有效地衡量负载和如何正确地决策。在CAPWAP结构中的AC充当了负载信息源的角色,本文算法综合考虑STA数量、RSSI值以及探测请求帧的平均探测时间等指标来衡量WTP的负载量,通过仿真实验表明该算法能够平衡各WTP的负载,从而提升网络性能。

参考文献

[1]IEEE802.11a[S].USA:IEEE,1999.

[2]IEEE802.11b[S].USA:IEEE,1999.

[3]IEEE802.11g[S].USA:IEEE,2003.

[4]Calhoun P,Montemurro M,Stanley D.Control And Provisioning of Wire-less Access Points(CAPWAP)Protocol Specification[EB/OL].2009-3.http://www.rfc-editor.org/rfc/rfc5415.txt.

[5]向望.基于CAPWAP的无线资源管理技术研究与优化[D].上海:复旦大学计算机科学技术学院,2009.

[6]邢光璞.无线局域网负载均衡优化研究[D].合肥:中国科学技术大学.2009.

[7]陈侃,李华,潘春建,等.集中式WLAN网络无线资源管理研究[J].计算机工程,2007,33(8):124-129.

[8]Velayos H,Aleo V,Karlsson G.Load balancing in overlapping wirelessLAN cells[C]//Communications,2004 IEEE International Conferenceon.USA:IEEE,2004,7:3833-3836.

接入算法 篇7

关键词：异构无线网络,移动终端,QoS,网络选择

目前无线环境是由众多具有不同性能的异构接入网络形成,用户对互联网的访问服务,是由不同服务质量和成本的网络提供。此外,随着移动终端( Mobile Terminal, MT) 的普及,多模终端在各种网络重叠覆盖的区域可以有多种无线接入网络供选择,异构网络环境的存在需要移动终端总是选择最好的网络( Always Best Connected, ABC) 。为了成功地实现ABC,移动终端应该具备面向多个无线接入系统的网络接口,每个MT将至少有3个或更多的网络接口,支持如WLAN,GPRS,Wi MAX,HSPA,EV- DO等无线接入,所有这些服务都可以允许MT用户自由地从一个接入网络切换到另一个网络。理想的情况是, MT用户可以在会话连接不断开的情况下从一个无线网络漫游到另一个无线网络,并使得移动终端总是选择一个最好的网络。因此,只有必要的同步机制和网络选择方法才能保证MT无线异构环境中网络的无缝切换。

垂直切换决策( Vertical Handover Decision,VHD) 可以使用成本函数[1]、模糊逻辑方法[2],或其他更复杂的算法。最后,MT经过选择连接到新的网络接入点( AP) 和改变它之前的网络连接方式。然而,接口的选择是一个问题( 包括接口的功能、用户偏好和应用要求等) 。在用于切换决策和接口选择的方法中,多属性决策法( Multiple At- tribute Decision Making,MADM) 是最有前途的方法。

切换判决是由MT和无线接入网络的性能共同决定的,不同的接入技术和无线网络的不同行为使得切换变得困难。本文提出,一种新型的垂直切换方法Rafo Q( Rank- ing for Qo S)[3]。通过考虑用户的喜好和应用程序Qo S来仿真比较Rafo Q与其他多属性决策算法,使用现有的网络性能参数来对改进的Rafo Q算法和其他的多属性决策算法进行评估。通过仿真验证,证明了改进算法Rafo Q的有效性。

1相关的工作

由于垂直切换判决能够评估所述无线网络的性能。 因此,越来越多的研究工作致力于理解新的切换解决方案。经典的切换解决方案是根据接收信号强度( RSS)[4]来进行网络选择。虽然这种切换方法具有很长的切换时延,可以达到2 s,但是能够使越区切换失败概率最小化, 并能提高可用带宽。

还有一些以成本代价为基础的垂直切换方法,它们通过研究几个参数,选择最佳的网络。这些参数定义为4组: 访问网络信息、用户偏好、终端能力和服务类型。文献[5]提出的跨层成本函数,收集不同层的决策标准。最后,基于应用程序和用户的喜好,MT选择具有最高分数的无线接入网络。

除了RSS和基于代价函数的切换算法,还设计了其他更复杂的算法。多属性决策( MADM) 实现了多个备选方案和属性,选择适当的计算方法。最经典MADM算法, 如SAW( 简单加权)[6]中的总得分是由候选接入网络的所有属性值的加权和。灰色关联度分析( GRA)[7]通过计算灰色关联系数为每个终端选择理想的无线接入网络。 TOPSIS法[6]通过评价对象与最优解、最劣解的距离来进行排序,选择一个最接近理想的解决方案,最好的选择应该具有最短的欧氏距离,负理想解是设计一个最远的距离,即最差的解决方案。多元指数加权( MEW)[8]可以表示为矩阵形式,其中行对应于候选网络,列对应其属性,最后计算接入网络的加权属性得分。一个多属性决策问题, 制定如下: A = { Ai,i = 1,2,…,n } 是一组代表移动终端支持的接口数目,B = { Bj,j = 1,2,…,m } 是一组属性, 如界面特性、应用需求和用户偏好( 例如接收到的信号强度、功耗、成本、覆盖范围、延时、安全等) 。权重向量W = [W1,W2,… ,Wm]表示这些Qo S参数的相对重要性,W是权重的决定因素,一种MADM问题可以由矩阵来表示,即

式中: N是相对矩阵; qij是相应的Qo S因子的值。

大多数早期的研究,特别是考虑到TOPSIS法在网络中多Qo S的冲突问题,而且如何处理这些问题并没有被明确提及。事实上,一些先前的研究提出,通过使用多目标优化的机制,而不是使用一个单一的目标函数来达到目的。目前研究的Qo S问题,在其有效性、无线接入网络负载均衡、企业节约成本以及顾客体验等方面,一致性被广泛重视。因此,选择多属性网络是非常重要的。

2Rafo Q算法

本文提出一种将层次分析法( Analytical Hierarchy Process,AHP) 和Rafo Q技术相结合的网络选择算法,以便找到一个权衡用户喜好、业务应用和网络条件的方案。算法机制分为以下功能块,即网络代理模块、MT请求模块和决策模块。网络代理模块和MT请求模块收集用户的喜好和网络条件; 决策模块是由AHP和Rafo Q对用户的数据进行处理和将网络数据标准化,也是本文关注的重点。

Rafo Q基于多目标优化的Qo S参数和监督在异构环境中的接入网络排名。该排名采用了多目标优化方法AMOSA[9],在排名函数的基础上评估最佳Qo S的接入网络。在这里,所提供的接入网络的集合作为输入,并返回一组输出的行列。算法步骤如下:

输入为一组k接入网络N={N1,N2,…,Nk}。

输出为集合N中的排名R={R1,R2,…,Rk}。

1) 在异构网络环境中模拟不同的接入网络,并计算其Qo S参数。

2) Ni采用多目标优化算法AMOSA,并选择最佳Qo S矢量的网络为特定网络。

3) 采用排名函数比较Qo S矢量,对Ni进行排名。

3仿真结果

3. 1仿真环境

在本节中,将Rafo Q算法与4种不同的垂直切换决策算法进行比较,即SAW,TOPSIS,GRA和MEW。在场景中,模拟2个WLAN、UMTS和GPRS共4个网络,这些网络覆盖相同的面积。使用NS-2和NIST流动性模块来模拟所描述的配置,接入网络性能,如表1所示。

网络覆盖区域可以容纳几百个手机终端,并将3GPP定义的几类应用程序分布在不同的终端运行( 即会话类、 流类、交互类和背景类) ,这几类应用程序主要特征通过时延、抖动和丢包率这几个Qo S参数表示( 见表2) 。对于不同类别,为每个参数分配不同的权重。虽然关于多属性的垂直切换决策是一个复杂的问题,但层次分析法( AHP) 可以把它分解成更简单、更易于管理的子问题,这些子问题可以是决定因素或权重。决定因素可以是解决方案,层次分析法通过比较权重选择解决方案、收集用户偏好数据来构造AHP矩阵,所有Qo S因子的权重参数如表2所示。在仿真环境中,设置终端的平均连接时间在1 ~ 10 s之间变化,来观察各个算法的网络性能。

3. 2模拟结果

在同一网络覆盖范围内,移动终端每次使用不同的切换判决算法,分别为Rafo Q,SAW,TOPSIS,GRA和MEW,并对这些算法仿真结果进行比较。在这些算法中,每个网络的瞬时容量并没有反映在切换判决中。因此,最好的网络应该具有最低的丢包率、最低的端到端时延和抖动。

由于切换判决算法GRA,SAW和TOPSIS选择同一网络的MT,所以在仿真图中显示这几类算法的图形叠加。

图1 ~ 图4表示每个业务类的每个越区切换决定算法的平均时延。它代表了从MT将数据包传送到接收终端的时延。仿真结果表明Rafo Q提供最低的终端到终端延时。事实上,Rafo Q能不断评估网络性能,并给终端分配最好的瞬时网络。

图5 ~ 图8描绘了每个业务类的平均抖动变化,它被定义为数据包到达时间之间的偏差。它取决于接入网络本身,以及网络负载。从图中可以看出Rafo Q的抖动性能是最好的,然后是TOPSIS,SAW和GRA。从图中可以看出除了会话类业务,MEW优于SAW,TOPSIS和GRA外, 其他类业务MEW的性能是最差的。

图9 ~ 图12描述的丢包率,定义为丢失数据包的数目与发送总数据包的比例。相对其他算法,Rafo Q算法具有最低的丢包率。TOPSIS法、GRA和SAW在背景类和流类业务方面比MEW具有更好的性能。然而,MEW在会话类却有较低的丢包率。

4结论