用户分配网络

2024-08-12

用户分配网络（共8篇）

用户分配网络篇1

随着广大人民群众物质生活水平的提高和精神文化生活需求的增加, 对有线数字电视的要求越来越高。互联网视频节目的极大丰富, 网络机顶盒及IPTV的发展对传统有线数字电视的冲击越来越大。面对文化产业市场经济的发展要求, 数字高清电视、VOD点播业务、互动电视业务已经成为各地有线电视传输部门在保障传统有线电视用户不流失前提下, 应对市场竞争不可或缺的重要组成部分。居民住宅小区有线数字电视网络的施工质量作为有线数字电视网络的重要组成部分, 是保证有线数字电视信号传输不可忽视的环节。

一、有线数字电视分配网络设计方案的确定

随着数字电视的广泛普及, 广播电视技术及其附属多功能业务的发展越来越快, 对双向网络及带宽的要求越来越高, 对小区有线数字电视分配网络进行设计要兼顾当前流行的施工建设方案, 制定科学、可行的设计方案。

(一) 户外分配网络

目前, 随着通讯光缆价格的持续降低, 光缆成为线路传输中重要的传输介质。越来越多的网络运营商在建设有线数字电视网络时, 选择让光接收机尽量接近用户端, 光传输比重的增加不但提高了网络的传输质量, 同时也降低了网络维护成本。目前较为广泛使用的设计方案是光纤到楼和光纤到户两种模式。

光纤到楼型:如图1所示, 有线数字电视运营商网络进入各住宅小区后使用无源光分路器将光信号采用星型连接方式将光纤引入各个住宅楼, 在每个楼内主单元有线数字电视箱体内安装光接收机, 每个光接收机可以覆盖100户左右, 采用EPON+LAN方式实现同轴电缆和五类线同时入户。由于相对过去同轴电缆分配网和光纤进小区的组网模式, 具有可靠性高, 调试方便, 便于维护等特点。

光纤到户型:如图2所示, 有线数字电视运营商网络进入各住宅小区后使用无源光分路器将光信号采用星型连接方式将两芯皮线光缆引入各个居民家中。由于光纤链路中连接设备少, 这种光网络建设方案具有系统可靠性高, 调试方便, 便于维护等优点。由于用户与有线电视前端机房链路中没有有源设备, 用户可以得到更好的带宽体验。这种网络建设方式具有投资相对较高, 线路维护量大幅降低, 用户可以更好地体验网络带宽增大所提供的各种电视增值业务。

(二) 楼内分配网络

有线数字电视信号进入各住宅楼后, 使用光接收机将光信号转换为能够在同轴电缆中传输的射频信号是目前有线数字电视网络技术发展的常规技术。目前针对户外分配网络采用光纤到楼的组网模式, 各运营商采用较多的楼内分配方式包括分支分配型和集中分配型两种。由于链路中间存在线路对接头及同轴电缆, 分支、分配器材, 用户信号质量差别较大, 维护相对困难。而采用光纤到户的组网模式就实现了有线数字电视前端机房到住宅小区用户家中的无源全光网络, 具有施工简单, 维护方便, 用户信号均衡等特点。

(三) 分光设计

光缆到达小区室外交接箱 (或机房) 后进行一次分光, 出局的光缆到达楼栋各单元时进行二次分光后入户。由于光纤入户将占用大量的PON口, 所以应科学计算分光方式, 确保数据信号分光后达到或接近1:64的分光比, 避免造成不必要的端口资源浪费。

1. 广播信号分光原则。

广播信号在小区室外交接箱 (或机房) 可进行一次或多次分光, 出局的光缆到达楼栋各单元时再次分光。

2. 数据信号分光原则。

数据信号在小区室外交接箱 (或机房) 进行一次分光, 出局的光缆到达楼栋各单元时二次分光。以低层、多层楼栋为例。4芯光缆到达单元配线箱后, 在熔配盘内成端2芯 (1芯数据信号, 1芯广播信号) , 成端应选用SC/UPC型连接器 (数据信号为蓝色, 广播信号为绿色) , 并预留两芯在熔纤盘内。

3. 单元分光。

每个单元分光点处配置2台插片式PLC光分路器, 通过单元配线箱熔纤盘成端的2芯分别连接对应的插片式PLC光分路器的IN口, 数据信号为蓝色连接器及接头, 广播信号为绿色连接器及接头。入户采用2芯单侧带头皮线光缆敷设 (1芯数据信号, 1芯广播信号) , 带头一端在单元箱侧。数据信号为蓝色SC/UPC型连接器, 连接数据信号PLC光分路器出口, 外护套印有光缆信息, 广播信号为绿色SC/UPC型连接器, 连接广播信号PLC光分路器出口, 外护套不印光缆信息。皮线不带头一端去往用户端光纤插座盒。

二、指标及测试

(一) 指标的选取

针对住宅小区内的有线数字电视分配网络的质量进行整体测试, 需要关注完工后的整体网络指标和施工工艺质量两方面内容。指标直接关系到用户的信号接收质量, 施工工艺质量则对网络的使用寿命和后期维护有重要影响。对有线数字电视分配网络指标和施工工艺进行整体测试, 可对整个施工建设工程给出具有明确意义和完整充分的测试评估意见。

如表1所示, 对网络进行的指标测试主要包括系统输出口电平、任意频道间电平差、相邻频道间电平差、调整误差率、误码率、数字射频信号与噪声功率比, 采用光纤入户方式后还要考虑光纤机顶盒的输入光功率。

1. 频道间电平差。

有线数字电视信号进入机顶盒后, 首先进行信号放大, 通常使用小信号放大器, 动态范围很小, 当频道间信号电平差超过10d B时, 可能使放大器进入非线性区而引起失真。另外, 信号电平差超过10d B, 也可能超过接收机的选择 (性) 能力而直接导致锁频失败, 丢失频道。对频道间电平差进行测试使用有线数字电视测试标准场强仪或频谱仪, 使用阻抗匹配的线缆和接头连接被测系统的输出口, 读取各频道电平测试数值并进行计算。

2. 调制误差率 (Moulation Error Ration) 。

调制误差率是标称矢量幅度的平方和与误差矢量幅度的平方和之比, 用d B表示。数字系统中的误差率类似于模拟系统中的信号噪声比, 是衡量数字系统信号传输最重要的指标之一。

误码是数字系统最致命的损伤, 直接导致接收质量下降, 出现马赛克甚至不能接收, 对调制误差率测试使用有线数字电视测试标准场强仪, 使用阻抗匹配的线缆和接头连接被测系统的输出口, 直接读取调制误差率和误码率测试数值。

3. 比特误码率 (Bit Error Rate) 。

比特误码率是数字系统信号传输中接收端接收到的正确的数字数据比特与总传输的数字数据比特的比值, 是一个小于1或者等于1的数值。产生的原因主要有:传输网络中的有源设备, 如:光发射机、光接收机、光放大器、电放大器、有源分配器、机顶盒等, 输出的电平过高或过低引起的失真导致误码产生;因电缆接头老化, 接触不良致使阻抗不匹配造成严重反射导致数字信号误码产生。当接收端信号误码率处于临界状态时, 性能较差的机顶盒或其他接收设备会产生不同程度的马赛克, 影响收视质量甚至接收信号失败。对比特误码率测试使用有线数字电视测试标准场强仪, 使用阻抗匹配的线缆和接头连接被测系统的输出口, 通过一定时间的测试直接读取误码率测试数值。

4. 数字射频信号与噪声功率比 (SNR) 。

与模拟电视相比, 数字电视具有清晰度高, 声音和图像效果好的特点。为了保证信号质量, 要求系统能够提供较高的信噪比。有线数字电视分配网络信号经过多级放大电路, 噪声已经经过多级叠加, 信噪比随之逐级下降。所以, 数字射频信号与噪声功率比是工程建设中需要关注的主要技术指标, 数字射频信号与噪声功率比进行测试使用有线数字电视测试标准场强仪或具有有线数字电视分析功能的频谱分析仪, 使用阻抗匹配的线缆和接头连接被测系统的输出口, 直接读取信噪比测试数值。

因为有线数字电视的元器件可能存在线性失真问题, 在高中低频率、在每个测试点要至少针对网络频段内不同范围选择频点进行测试, 对有线数字电视网络1000MHz以下的网络一般选取203MHz、482MHz、826MHz频点分别进行信号指标的测试。

(二) 施工工艺质量主要评估内容选取

根据住宅小区规模的不同, 有线数字电视分配网络可能会比较复杂, 工程建设中会使用不同的设备组合, 不同的线缆、器件、安装方式, 施工工艺质量的好坏直接关系到有线数字电视分配网络的使用寿命和用户接收信号的质量。如有源器件接地质量差可能造成系统引入瞬间干扰, 严重情况可能造成系统不能正常工作。方式措施质量差会影响网络寿命, 增加驻波、增加误码、降低用户端接收质量。

因此施工工艺也是工程质量的重要组成部分, 施工工艺质量差不光为系统维护检修带来困难, 也直接降低整个有线数字电视网络的指标和信号质量。对网络施工工艺质量的评估主要包括以下内容。

1. 传输设备。

包括有源设备的接地、壳体固定、空余输出端终接、安装牢固度、防水、馈线的布线、穿管保护、接点牢固等。

2. 用户设备。包括无源设备安装高度、设备连接、接点牢固、外壳接地、馈线连接牢固、标记等。

3. 电缆和接插件。包括电缆布线、弯曲、间隙、接插件安装牢固、防水防蚀等。

(三) 测试点选取

根据住宅小区的建设规模和网络布线的具体情况, 要选择多个测试点分别对网络指标和施工工艺进行测试和评估。如根据光接收机距离的不同、根据分支分配器的距离的不同、设备器件品牌规格的不同选取不同的测试点, 根据数字信号传输及占用带宽的特性, 一般分别选取远中近3个测试点。

三、结束语

随着有线数字电视技术的飞速发展, 住宅小区有线数字电视分配网络在设计、施工方面要做到高质量、高可用性, 以应对不断发展的有线数字电视业务, 给用户带来更多、更好的视觉享受。

摘要：住宅小区有线数字电视网络的施工质量是保证其信号传输不可忽视的环节。工程技术人员要设计完成有线电视系统, 需要更好地完成用户分配网络的设计, 因为这直接关系到用户能否正常接收数字电视信号。

关键词：有线数字电视,用户分配网络,设计,测试

未来“网络帝国”的权力分配篇2

权力向网络转移

如果把权力理解为对他人的影响力和支配力的话，那么，网络公司正在朝这个方向迈进。数百万人同时在线玩网络游戏，已在网络公司那里魂不附体了。但网络并非游戏或娱乐，它更从现实世界中攫取了实质性的权力。

今后，我们或许会看到阿里巴巴控制虚拟世界的经济，新浪控制资讯和娱乐，当当控制出版业，而百度决定着对每一个意义的解释——这并非科幻。

考虑到技术的发展，网络帝国权力的膨胀将是飞快的。比如，语义互联网的出现，将使互联网更加智能，而后，人与电脑之间将相互影响。人工智能的发展，将有可能通过神经网络和细胞自动控制建立一个全新的、类人脑的网络世界，从而大大提高网络权力的分量。

值得注意的是虚拟世界的发展。Hipihi（3D虚拟世界平台）的老总许晖甚至说，3D虚拟世界的创造体系，将发挥瓦特蒸汽机之于工业革命的引擎作用。

另外，移动网络的发展，將促使通过移动设备实现的诸多定位服务不断出现，现实中的很多服务业务可能转入网络公司。注意力经济也许会在构建网络世界中扮演更重要的角色，未来网络帝国的权力分配，将取决于注意力的分配——消费者选择把注意力“花”在哪里。

而随着越来越多的网络再混合，整个系统正在变成一个平台和数据库的混合体，服务面将会更大。尤其是在线视频和网络电视的普及，给CCTV等传统媒体提出了如何适应未来发展的问题。

结合了声音、视频和实时对话的综合通信技术，使“丰富因特网应用程序”（RIA）为网上用户带来了前所未有的体验，同时也大大增加了用户对网络的人身和精神依附性。

更加数字化的真实生活

虚拟世界的出现可以帮助我们更好地理解未来网络帝国的权力模式。

根据美国科幻小说《雪崩》设计的网络虚拟国度“第二人生”，目前已拥有400万注册居民。他们在网络上工作和生活，日均交易额过百万美元，还造就了钟安舍这样的百万富翁。世界五百强纷纷入驻“第二人生”，一些国家还在“第二人生”中设立了大使馆，哈佛大学在里面开学，路透社也设立了“第二人生”分社，还有一些国家的总统候选人在里面设立了竞选分部。

所以，虚拟世界不仅仅只是关于数字的生活，它也使我们的真实生活更加数字化。类似“第二人生”这样的虚拟世界，使现实社会中的政治、经济和文化权力有了新的落脚点。

有人甚至预计，未来人类的整个权力都有可能移交给人工智能和网络。比如特里·比森在名为《亲爱的艾比》的科幻小说中预言，未来人类将由一个被称作ARD的地球智能来照料，它就是从一个监测网络发展而来的。另一种东西叫RVR，作为人类无所不知的“大管家”，它可以看作是移动网络进一步发展的结果。今天，如果我们可以通过Google得到导航地图，在商场购物时随时可以从Yahoo那里得到出价建议，那么今后，我们生活中的一切，难道不是都可以由一个随时跟在身边的“幽灵”来进行综合解决吗？

再比如把人类的意识数字化后上传到计算机系统的问题，有科学家已经在做这项工作。作家拉拉在《掉线》一书中描述了这样的未来：世界将分为“基底世界” （即现实世界）和“网球”（虚拟世界）两部分。全人类都把意识上传到“网球”，脱离“基底世界”的生活，因为网络才是真正的桃花源。而“基底世界”再也没有一个人，只由自动机器接管。那么谁来掌控这个未来的“网球”人类世界呢？不太可能是现实世界的政府。那么可能是Yahoo吗？可能是微软吗？可能是林登实验室吗？如此大权在握的网络帝国很可能首先产生于西方。目前我们还很难设想一家发展中国家的网络公司能达到帝国型规模。

网络帝国的冲突与战争

网络帝国不仅仅是“人头经济”的问题。它涉及信用、安全、语言，还有技术及文化价值观。 25个流量最高的美国网站中的14个在美国之外吸引的访问者比国内多。美国科学家预测说，人类从现实世界向虚拟世界“移民”，是一个不可扭转的趋势。到 2011年，80%的网民将加入虚拟世界。而这种前往异质文化、异国背景的虚拟世界的人口流动，不需要办理任何海关手续，又怎么控制呢？这里面也有权力多极化的问题。

比如“第二人生”的开发，现在有林登实验室的版本，有中国人开发的版本。谁更能吸引居民入住呢？中文虚拟世界的一位开发者查卫江说，美国“第二人生”里面更多的是欧美用户，中国的版本中更多的是国内用户。不仅文化不同，虚拟世界的经济体发展程度也不同。那么，相同文化、语言和经济背景的虚拟世界，将来会否联合在一起呢？比如就汉语文化圈的“第二人生”而言，国内的，新加坡的，北美华人社区的，欧洲华人社区的用户，有可能统一成一个大的网络联合体吗？它与英语的虚拟世界会是既对话又对抗的关系吗？这些都会打破传统的国家主权概念。如果一个国家的半数居民都跑到外国的虚拟世界去了，现实世界中的国家权力又如何去管理和影响他们？由此，我们可以做更进一步的设想：如果一些问题解决不了，网络帝国之间会爆发军事冲突吗？如果某大国用黑客手段“误炸”了另一国设在虚拟世界中的一座大使馆，那么，这在现实世界中会引起外交纠纷吗？在网络战争中，大量的民用网络公司将被临时征用。那些控制着巨大网络资源的帝国型公司将如何利用这样的机会发“军火财”呢？现在，已有人在“第二人生”中组建虚拟军队了。战争是政治的延续，网络世界中五花八门的民主或专制政治体制不会不考虑战争手段的。

科幻小说家刘慈欣设想中的微软公司的和平视窗计划，就是用一种网络虚拟战争来解决现实战争问题的，而且得到了联合国安理会的授权。因此将来有可能是，谁控制了网络，谁就赢得了主动，谁就能不战而屈人之兵。

建立网络权力学

十余年前，很多国人还不会上网。十余年后，中国已成了世界第二大网络国家，印度等国也在纷纷赶上来。对一些人来说，网络对价值观、世界观的影响很大，对生活方式的影响也很大。今后这种趋势还会进一步发展。未来虚拟世界和现实世界的关系会越来越紧密，权力的重组是必然的。但我们对网络未来的理解和认识还很肤浅，这主要在于人们还把它理解为一种技术形态而不是权力形态。实际上，对政府来讲，网络不仅仅是信息公开那样简单。网络对世界的改变是实质性的。网络权力学，包括虚拟政治、外交、军事和法律等的研究，应该是大学的一门新课程。

用户分配网络篇3

关键词：交通分配,容量约束,变分不等式,仿真算法

交通分配可分为均衡分配与随机均衡分配两类,Beckman最早研究了离散网络路段无容量约束的交通分配问题,提出了满足Wardrop用户均衡的分配模型,Frank-Wolfe算法是求解这个模型的最有效方法。但这个模型常使很多路段的流量异常高,这不符合实际情形,当对每条路段加一个容量约束时,又会导致Frank-Wolfe算法的优势丧失。许多学者采用内罚函数法、外罚函数法或广义拉格朗日乘子法将路段容量约束问题转化为一系列无容量约束子问题[1,2,3],通过对惩罚因子的不断调节,反复采用Frank-Wolfe算法求解,由于Frank-Wolfe算法收敛速度慢,妨碍了容量约束模型在大型路网上的应用。随后Dagazno和Sheffi给出了随机用户均衡(SUE)概念[4],此后许多学者对随机用户均衡问题也进行了深入研究[5,6,7,8],在随机均衡交通分配模型中,Logit分配模型是最重要的模型之一,但该分配模型需要首先对各O-D对之间的所有路径进行枚举,这同样导致了其在复杂大型路网上应用的困难。文献[9]提出一种拟Frank-Wolfe迭代算法,提高了分配效率。以上算法主要针对离散网络,而对于非对称网络中的交通分配问题,对应算法却比较少见[8]。

首先通过图表分析了实际路段行驶时间与无路段容量约束的函数近似行驶时间的差异,指出后者低估了实际路段行驶时间,从而可以通过不断校正排队延误因子和误差因子来模拟实际路段行驶时间。基于仿真思想,对非对称网络,提出了一种带路段容易约束的用户均衡交通分配仿真算法,它基于O-D对间最短路的动态生成,不需要路径枚举,在每轮迭代中,将按全有全无方法进行流量分配,并与前一轮迭代所得到的流量进行加权得到新一轮的路径流量,而各O-D对的加权系数则依据Logit模型来确定,通过不断自适应调节排队延误因子和误差因子,使路段流量逐步低于路段容量,最终达到广义用户均衡。一方面该算法不需要在每轮迭代中求解无约束交通分配模型,另一方面,它又避免了随机均衡分配法在各O-D对之间进行路径枚举。随后证明了算法的收敛性。通过一个交通分配问题算例,说明了算法的可行性。

1容量约束交通均衡分配问题

给定一个交通网络G=(N,A),N为节点集,A为路段集,R为起点集,S为终点集,R与S可以有公共元素;网络中共有|A|条路段;(r,s)是以r为起点,s为终点的O-D对;Prs为O-D对(r,s)间所有路径集合。容量约束交通均衡问题考虑了路段的容量,使该问题更加符合实际路网情形,在非对称网络,容量约束交通均衡模型具有如下变分不等式形式:

t(x*)T(x-x*)≥0; ∀x∈Ω (1)

式(1)中:

式(2)中:x*为均衡路段流量解;f $_{p}^{r s}$ 是O-D对(r,s)间路径p上的流量,组成的向量为f=(…,f,…)T;xa为路段a的流量,组成的向量为x=(…,xa,…)T;ta(x)为路段a的行驶时间函数,t(x)=(…,ta(x),…)T为路段行驶时间函数向量,假定是严格单调可微且雅克比矩阵∇t(x)是严格对角占优的;Ca为路段a的容量,C=(…,Ca,…)T;qrs是O-D对(r,s)间的需求量;如果O-D对(r,s)间路径p经过路段a则δ=1,否则为0。上述模型式(1)—式(2)当可行域Ω非空(Ω≠∅)时,具有唯一路段流量解[10]。

模型式(1)—式(2)的均衡条件为:

${\begin{cases} \sum_{a \in A} \tilde{t}_{a} (x^{*}) δ_{a p}^{r s} - u_{r s}) f_{p}^{r s}^{*} = 0, \\ \sum_{a \in A} \tilde{t}_{a} (x^{*}) δ_{a p}^{r s} - u_{r s} \geq 0, f_{p}^{r s}^{*} \geq 0 \\ d_{a} (x_{a}^{*} - C_{a}) = 0 ； x_{a}^{*} \leq C_{a}, d_{a} \geq 0 \end{cases} (3)$

式(3)中: $\tilde{t}_{a} (x) = t_{a} (x) + d_{a}$ 称为广义路段行驶时间,Lagrange乘子urs,da分别代表O-D对(r,s)间的最小行驶时间与路段a的排队延误时间,因此上述条件经常称为广义用户均衡条件。由于在拥挤网络中,da并不是可以忽略的[10],如图1(a)所示,在容量Ca附近时间函数近似曲线与实际时间曲线误差较大;从图1(b)可以看出,在无路段容量约束模型中,由于t(x)是严格对角占优的,当xa>Ca时,实际延误da要高于函数近似延误d′a,其误差因子Δda=da-d′a>0,因此仅用t(x)并不能模拟路段的实际行驶时间。需要注意的是,虽然在实际路网均衡条件下,排队延误是唯一的,但Lagrange乘子da并不唯一。

2路段容量约束用户均衡交通分配仿真算法

模型式(1)—式(2)是一个约束变分不等式问题,因具有容量约束,相应算法比较少见,因此现设计仿真算法来求解该模型。

2.1算法的迭代步骤

STEP0:输入O-D表及网络信息;设O-D对个数为N,令i表示第i 个O-D对;置各路段初始流量为0,置迭代次数k=1,第i个O-D对最短路径集Ai=∅;取允许误差ε>0,在0流下求各O-D对最短路p,(i=1,2,…,N),按全有全无分配各O-D对流量并计算路段行驶时间tk,令,随机产生Δd>0,∀a∈A;将产生的最短路归入各O-D对的最短路径集A(i=1,2,…,N)中,置mpki=1。

STEP1:确定各路段行驶时间t $_{a}^{k + 1}$ =t $_{a}^{k}$ +d $_{a}^{k}$ ,计算各个O-D对最短路p $_{i}^{k + 1}$ ,(i=1,2,…,N)。如果p∉Ai,置Ai:=Ai∪p $_{i}^{k + 1}$ ,路径p的出现次数mpk+1i=1;否则Ai中路径不发生变化,置mpk+1i=mpki+1。将每个O-D对的需求量按全有全无分配法全部分配到这批新产生的路径上,记所得到的各路径上的流量向量为。按一定规则选取流量加权组合系数α(0≤α≤1),对第i个O-D对,在其最短路径集Ai中分配流量为:。

STEP2:计算输出路段流量xk+1及路行驶时间t $_{a}^{k + 1}$ ,如果 $\max_{a \in A} | x_{a}^{k + 1} - x_{a}^{k} | + \max_{a \in A} {0, x_{a}^{k + 1} - C_{a}} \leq ε$ ,停止;否则转STEP3。

STEP3:令延误因子:

;误差因子:,置k:=k+1,转STEP1。

2.2α $_{i}^{k}$ 的选取方法

由于现实路网中各个O-D对的路径集和交通需求都存在一定差异,不同于Frank-Wolfe算法中各O-D对共用一个加权系数,本算法在迭代过程中各O-D对可选取不同的加权系数。选取方式如下:

计算第k次迭代时新产生的路径p $_{i}^{k}$ 的初始行驶时间tpki及A $_{i}^{k}$ 中各条路径的初始行驶时间,取:

$α_{i}^{k} = \max {\frac{\exp (- θ t_{p_{i}^{k}})}{\sum_{q_{i} \in A_{i}^{k}} m_{q_{i}} \exp (- θ t_{q_{i}})}, ζ_{i}} (4)$

式(4)中,θ>0为Logit模型中的分布参数;A为第k次迭代后,已经求出的第i个O-D对的最短路集合;tqi是路径qi的初始行驶时间;mqi表示到目前为止,路径qi作为最短路而被重复选中的次数。式(4)中ζi是一个与算法迭代误差ε有关的充分小的正数,其作用是既要保证算法能够收敛,又要使每一步迭代路径流量都有适当的调整。

2.3算法的收敛性

定理:当Ω≠∅且qi<∞(i=1,2,…,N)时,则对任意给定的迭代误差ε>0,适当选取ζi(i=1,2,…,N),上述迭代算法是有限终止的。

证明:由于路网中只有有限条路段,要证明上述定理,只需证明对路网中任意一条路段a,有

$| x_{a}^{k} - x_{a}^{k - 1} | \leq \frac{ε}{2}, \max {0, x_{a}^{k} - C_{a}} \leq \frac{ε}{2}, k \to \infty$ 即可。

先证。

考察第i个O-D对,取:

及

其中P为各O-D对所有可能路径的集合。有:

$\frac{\exp (- θ t_{p_{i}^{k}})}{\sum_{q_{i} \in A_{i}} m_{q_{i}} \exp (- θ t_{q_{i}})} \leq \frac{Μ_{i}^{k}}{\sum_{q_{i} \in A_{i}} m_{q_{i}} m_{i}^{k}} = \frac{Μ_{i}^{k}}{m_{i}^{k}} \frac{1}{k} \leq \frac{Μ}{m} \frac{1}{k} \to 0, k \to \infty 。$ 可以看出,若取 $ζ_{i} = \frac{ε}{2 Ν | A_{i} | q_{i}}$ ,那么当k充分大时,总有α $_{i}^{k}$ =ζi,因此对A $_{i}^{}$ 中任一条路径pi,由

知 $| f_{p_{i}}^{k} - f_{p_{i}}^{k - 1} | = | α_{i}^{k} | | \tilde{f}_{p_{i}}^{k} - f_{p_{i}}^{k - 1} | \leq q_{i} α_{i}^{k} = q_{i} ζ_{i}, k \to \infty 。$

其中:qi第i个O-D对的交通需求量。由于交通网络中每个O-D对路径是有限的,即当k→∞时Ai中路径不再产生变化,从而对路网中任意一条路段a,其路段流量为 $x_{a}^{k} = \sum_{i = 1, 2, \dots Ν} \sum_{p \in A_{i}} δ_{a p} f_{p}^{k}$ ,即有

$\begin{array}{l} | x_{a}^{k} - x_{a}^{k - 1} | \leq \sum_{i = 1, 2, \dots Ν} \sum_{p \in A_{i}} δ_{a p} | f_{p}^{k} - f_{p}^{k - 1} | \leq \\ \sum_{i = 1, 2, \dots Ν} | A_{i} | q_{i} ζ_{i} \leq \frac{ε}{2}; k \to \infty 。 \end{array}$

再证。

$\begin{array}{l} f_{p}^{k} = α_{i}^{k} \tilde{f}_{p}^{k} + (1 - α_{i}^{k}) f_{p}^{k - 1} = (1 - α_{i}^{k}) f_{p}^{k - 1} = \\ (1 - ζ_{i}) f_{p}^{k - 1} \to 0, k \to \infty 。 \end{array}$

既有 $x_{a}^{k} = \sum_{p \in Ρ} δ_{a p} f_{p}^{k} \to 0 ‚ k \to \infty$ 。与 $x_{a}^{k} - C_{a} > \frac{ε}{2} > 0$ , 矛盾。

本算法是通过最短路算法来产生新路径,且总是在最短路上进行流量分配,而一些较差路径不能被选择或分配交通流量,这符合用户均衡交通分配的原则。随着迭代次数的增加,算法将不会产生新路径,并且通过流量的不断调节,最终达到广义的用户均衡。在STEP1与STEP3中,路段行驶时间采用仿真形式得到,因此该算法为仿真算法。在STEP3中,误差因子更新方式和Lagrange乘子更新方式相似,但算法不需要在每次迭代中进行无约束交通分配运算,并且每次迭代都更新已产生的所有路径流量,更重要的是算法可以求解非对称网络。由于算法虽然不能直接得到准确延误因子,但却是非对称网络交通分配的快速算法。由均衡条件式(3)可知延误因子可在多面体式(5)中得到。

${\begin{matrix} f_{p}^{r s}^{*} \sum_{a \in A} t_{a} (x^{*}) δ_{a p}^{r s} + f_{p}^{r s}^{*} \sum_{a \in A} d_{a} δ_{a p}^{r s} = \\ u_{r s} f_{p}^{r s}^{*}, & \forall r, s, p \\ \sum_{a \in A} t_{a} (x^{*}) δ_{a p}^{r s} + \sum_{a \in A} d_{a} δ_{a p}^{r s} \geq u_{r s}, & \forall r, s, p \\ d_{a} (x_{a}^{*} - C_{a}) = 0, & \forall a \\ d_{a} \geq 0, & \forall a \end{matrix} (5)$

虽然多面体式(5)中只含有一组变量da,∀a,但da并不唯一,这与Lagrange乘子的不唯一性是一致的。

3计算实例

下面通过一个实例来检验本文提出的分配算法,采用文献[12]的初始数据和道路交通网络:

在如图2所示的网络中有4个O-D对:1-12、 9-4、12-1、4-9,O-D需求量分别为q1,12=460、q9,4=400、q12,1=440、q4,9=420,网络共有34条路段; 路段旁数字表示路段流量为0时的行驶时间, 设每条路段的容量均为300,采用非对称路段行驶时间函数: $t_{a} (x) = t_{a} (0) [1 + 0.5 (\frac{x_{a} + 0.2 x_{\hat{a}}}{1.2 C_{a}})^{4}]$ 。 Ca为路段a的容量, $x_{\hat{a}}$ 为路段a的反向路段 $\hat{a}$ 的流量。

x $_{a}^{C}$ 表示算法所得到的路段流量, 表1给出了相应的分配结果(取ε=1, 保留小数点后两位)。

从表1可以发现,算法所得的结果中,最高路段流量仅为300.06,是允许范围内的误差,意味着该路段达到饱和。图3给出了算法的收敛曲线,可以看出本算法收敛的速度非常快;

图4、图5分别给出了路段(3,2)与路段(7,6)在算法迭代过程中流量的变化趋势,在100次迭代以后趋于稳定。

4结论

对非对称网络,提出了一种带路段容量约束的用户均衡交通分配仿真迭代算法,通过不断修正排队延误因子和误差因子来模拟实际路段行驶时间,再利用最短路算法产生有效路径,在当前迭代过程中,将全有全无分配法得到的各路径流量与上一轮迭代后各路径分配流量进行加权组合,得到新的路径分配流量,各O-D对加权组合系数通过Logit模型得到,随后给出了算法的基本思想与迭代步骤,并证明了算法的收敛性。计算实例还显示:该算法所得分配结果在误差范围内均不超过路段容量,收敛速度非常快,各路段流量在有限次迭代后便趋于稳定。由于分配流量的路径均是各O-D当前迭代下的最优路径,而未被选中的路径(相对较差的路径)不分配流量,这恰好符合用户均衡交通分

配原则,因此算法收敛时可达到广义用户均衡。本算法不需要路径枚举,而比求解容量约束下均衡交通分配模型计算量又小得多。因而它是一个有效的容量约束交通分配算法,适合在非对称道路交通网络中应用。

参考文献

[1] Larsson T,Patriksson M.An augmented lagrangian dual algorithm forlink capacity side constrained traffic assignment problems.Transpor-tation Research,1995;29:433—455

[2] Nie Y,Zhang H M.Models and algorithms for the traffic assignmentProblem with link capacity constraints.Transportation Research,2004;38:285—312

[3] Xu Y D,Li S J,Teo K L.Vector network equilibrium problems withcapacity constraints of arcs.Transportation Research Part E,2012;48:567—577

[4] Sheffi Y.Urban transportation networks:Equilibrium analysis withmathematical program methods.New Jersey,Prentice-Hall,INC,En-glewood Cliffs,1985

[5] Chiou Suh-wen.A novel algorithm for area traffic capacity control withelastic travel demands.Applied Mathematical Model,2011;35:650—666

[6] Meng Qiang,Khoo Hooiling.A computational model for the probit-based dynamic stochastic user optimal traffic assignment problem.JAdv Transp,2012;46:80—94

[7] Szeto W Y,Solayappan M,Yu Jiang.Reliability-Based transit as-signment for congested stochastic transit networks.Computer-AidedCivil and Infrastructure Engineering,2011;26:311—326

[8] D’Acierno L,Gallo M,Montella B.An ant colony optimisation algo-rithm for solving the asymmetric traffic assignment problem.EuropeanJournal of Operational Research,2012;217:459—469

[9]黄崇超,刘炳全.非平衡交通分配的Frank-Wolfe迭代算法.数学的实践与认识,2009;39(8):19—26

用户分配网络篇4

认知无线电技术通过允许一组次要用户动态接入已经分配给主要用户的频谱, 可以有效解决频谱使用效率低下的问题, 通过引入协作中继技术, 认知无线电系统的性能和频谱利用率可以得到更进一步提升, 且可以带来系统的空间分集增益。因具有很好的对抗无线传输环境中的频率选择性衰落以及高频谱利用率的特点, OFDM技术非常适用于无线宽带信道下的高速传输。作为实现个人未来通信系统目标的有效方法 (OFDM技术与协作中继技术已经被多个多个无线宽带系统标准如802.16e标准[1]和3GPP LTE-Advanced方案[2]作为关键技术采用) , 这几种技术的有效融合, 将大力提升无线频谱资源的利用率, 提高无线通信链路的可靠性和网络连通性。

对任何无线通信系统来说, 资源分配问题始终都是研究的热点问题。不考虑认知无线电和协作通信技术的多用户OFDMA系统中的资源分配问题已经得到了较多的研究 (如Cioffi等人的专著[3]) , 特别是基于不同优化目标对载波、比特和功率等的分配方案研究的热点, 如[4,5,6,7]以及对应的参考文献。参考文献[8,9,10,11]研究了蜂窝网络中基于OFDM的多用户协作场景下的中继选择与载波分配问题。我们在前期工作[12,13]中研究了协作无线通信网络中的联合单中继选择与频谱分配问题。针对多信源- 多信宿- 多中继场景下的最优中继选择与子载波分配问题, [14]以中断概率最小化为目标, 设计了基于随机二部图最大匹配 (random bipartite graph based maximum matching, RBG matching) 的算法。参考文献[15]考虑了基于OFDMA的认知无线电网络中的载波和功率分配问题, 在次用户系统中考虑了一个次用户中继节点帮助次用户信源向多个次用户信宿节点广播数据, 且主用户系统只考虑了一个信源- 信宿收发对。[16]在基于OFDMA的认知协作无线网络中, 基于对偶分解技术设计了子载波匹配、中继选择和功率分配的渐近最优算法, 但是该文章只考虑了一个主用户信宿、一对次用户收发对的情况, 而没有考虑多用户情况。[17]研究了认知协作Ad Hoc网络中路由、中继选择和频谱分配问题, 采用跨层设计的方法提出了分布式算法, 但是考虑的是overlay频谱接入方式, 即只有某一子载波的授权用户不占用该频段的时候, 次要用户才可以接入。

1 多用户认知协作网络模型

本文所研究的多用户认知协作无线网络的系统模型如图1 所示。该系统有一个主要用户网络和一个次要用户网络组成。其中, 主要用户网络有M个主要用户信源端 (Primary Transmitter, PT) 以及对应的主要用户信宿端 (Primary Destination, PD) 组建的M个主用户对组成, 分别用PT1, ..., PTm, ..., PTM和PD1, ..., PDm, ..., PDM来表示, 这M个主用户对分别从W个子载波中占用一个完成通信。次要用户网络里面包含N个次要用户发送端 (Secondary Transmitter, 记作ST1, ..., STn, ..., STN) 以及对应的N个次要用户接收端 (Secondary Destination, 记作SD1, ..., SDn, ..., SDN) 。假定这些次用户收发对 (包含次要用户发送端以及对应的次要用户接收端) 采用两跳传输的方式以降低发送功率从而减少对主用户可能造成的干扰, 即需要借助K个次要用记作户中继节点 (记作SR1, ..., SRk, ..., SRK) 的帮助完成通信。同时为了降低信令交互的复杂度, 我们假定每个次用户收发对只能选择一个次要用户中继节点, 并将次用户收发对以及选中的次用户中继节点称作一个次要用户组合。次要用户组合也从W个子载波中选择通信使用的载波。在某一个次要用户组合里面, 次要用户对之间进行两跳通信的时候, 我们假定次要用户发送端在第一个时隙选用的载波与第二个时隙里次要用户中继节点选用的载波相同, 当然, 如果在每个时隙中都运行载波分配算法, 相关的工作即可以扩展到两个时隙中次用户发送端和次用户中继节点选用不同载波的情况。次要用户网络在主要用户网络的传输区域之内工作, 当采用underlay的频谱接入方式时, 每个主用户对在每个信道上的干扰温度限制必须得到保证。

假定多用户认知协作无线网络中的每个节点都只配备一根半双工全向天线。用表示从次用户发送端STn到次用户中继节点SRk和主用户接收端PDm在第w个信道上的信道增益;用和分别代表从次用户中继节点SRk到次用户接收端SDn和主用户接收端PDm在第w个信道上的信道增益;用分别表示从主用户发送端PTm到主用户接收端PDm、次用户中继节点SRk和次用户接收端SDn在第w个信道上的信道增益。分别用和分别表示第m个主用户发送端、第n个次用户发送端和第k个次用户中继节点在第w个子载波上的发送功率, 其中。

2 问题建模

在本文研究的工作中, 我们对系统进行如下假设:

● 在每次通信过程中, 每个主用户对最多只能占用一个载波, 且每个载波只能被一个主用户对唯一占用。

● 在每次通信过程中, 每个次用户对至多只能选中一个次用户中继节点, 且每个次用户中继节点每次只能被一个次用户对唯一选中。

● 在主用户完成载波分配的基础之上, 每个次用户组合只能占用一个载波进行通信。如果该载波已经被某一主用户对占用, 则在一个通信周期的两个时隙内, 在需要满足该主用户对的干扰温度限制条件下, 次用户组合中的次用户发送端和次用户中继节点占用同一载波进行传输。

2.1 本中问继题选中择, 模使型用一个N行K列的矩阵A=来表示N个次用户发送端选择K个中继节点的情况, 也就是说:当A (n, k) =1的时候, 次用户中继节点SRk被次用户对STn和SDn选中用于帮助完成通信。

考虑到在每次通信过程中, 每个次用户对至多只能选中一个次用户中继节点, 且每个次用户中继节点每次只能被一个次用户对唯一选中。我们可以得到关于中继选择矩阵A的如下约束:

其中, 约束条件 (2) 和 (3) 表示在该矩阵中, 任何一行或者任何一列里面最多只能有一个1。

2.2 载波分配模型

在我们的问题当中, 主用户网络和次用户网络之间共享载波资源, 当次要用户组合选用的载波已经被主用户对占用的时候, 需要满足占用该载波的主用户对的干扰温度限制;当主用户没有占用该载波的时候, 则不受干扰温度的限制。从实际的角度出发, 在一个主次用户同时存在的网络里面, 主用户享有对子载波分配的优先权。换言之, 主用户网络的用户对可以根据某种原则首先进行子载波的分配。我们假定这一主用户载波分配的结果可以通过某种方式被次用户网络的用户知道。次用户网络的用户可以根据某种规则进行子载波分配, 次用户可以独占空闲的子载波或者在满足主用户干扰门限的条件下与某一主用户对共享该子载波。

我们用一个M行W列的载波分配矩阵BPU来表示M个主用户对占用W个子载波的情况。这里, 我们用BPU ( m, w) =1 , ∀m ∈{1, …, M}, w ∈{1, …, W} 表示主用户发送端PTm选择占用子载波w进行数据传输, 否则表示不占用该载波。

考虑在每次通信过程中, 每个主用户对最多只能占用一个载波, 且每个载波只能被一个主用户对唯一占用的限制, 可以得到如下主用户子载波分配矩阵BPU的相关约束:

其中约束条件 (5) 和 (6) 分别表示在该矩阵中任何一行或者任何一列里面最多只能有一个1。

同样, 我们用一个N行W列的矩阵BSU来表示N个次用户组合对W个子载波的占用情况。这里, 我们用BSU ( n, w) =1 , ∀n ∈{1, …, N}, w ∈{1, …, W} 表示次用户发送端STn及选定的次用户中继节点选择占用子载波w , 否则, 表示不占用该子载波。可以得到如下次用户子载波分配矩阵BSU的相关约束:

其中, 约束条件 (8) 和 (9) 表示在该矩阵中, 任何一行或者任何一列里面最多只能有一个1。

2.3 多用户系统容量

当次用户网络中的中继节点采用译码转发 (DF) 的中继策略时, 对次用户网络中的任意一个次用户收发对STn-SDn来说, 其链路容量表达式如下:

代表第一个时隙中中继节点SRk收到的信干噪比, 代表第二个时隙中次用户接收端SDn收到的信干噪比。下面, 我们首先给出以上信干噪比的通用表达式。用和代表被次用户发送节点STn和次用户中继节点SRk占用的子载波集合。那么我们可以得到和的通用表达式如下:

以上公式中的分子部分表示接收端在占用的所有子载波上接收的有用信号功率之和;分母中的1 为接收端收到的AWGN噪声的归一化功率, 后面的两个表达式分别代表占用相同子载波的主用户和其他次用户造成的干扰。这些干扰的通用表达式如下:

在我们的问题中, 当限定每个子载波只能分配给一个次用户组合使用时, 其他次用户将不会产生干扰, 即。

用一个M行W列的矩阵Qth来表示M个主用户接收端在W个子载波上的干扰温度限制。用和分别表示第一个时隙中所有工作在子载波w上的次用户发送端和第二个时隙中所有工作在子载波w上的次用户中继节点对主用户接收端PDm造成的干扰, 其中:

2.4 问题数学模型

本问题的求解目标是在满足主用户干扰温度限制的条件下, 联合考虑中继选择和子载波分配策略以最大化次用户对的链路容量之和。公式表示如下:

公式 (1) - (9) 的限制条件

其中, 公式 (22) 和 (23) 中的Qth ( m, w) 表示主用户PDm在子载波w上的干扰温度限制值。和则分别表示工作在子载波w上的所有次用户发送端和次用户中继节点在两个时隙对主用户接收端PDm造成的干扰。

3 中心式全局最优算法

在2.4 节中描述的问题是一个0-1 非线性整数规划问题, 通常来说都是NP-hard问题。为了对问题进行求解, 我们首先将对该问题进行等价变换使其转变为带约束条件的0-1 线性整数规划问题, 然后设计全局最优的中继选择与子载波分配算法。

3.1 问题等价转换

为了进一步求解优化问题的最优解, 我们定义如下几个新的变量:

● N* K*W的三维变量, 其中代表STn占用第w个子载波与SRk通信时, SRk接收到的信干噪比。

● N* K*W的三维变量, 其中代表SRk占用第w个子载波与SDn通信时, SDn接收到的信干噪比。

● N* K*W的三维变量, 其中代表STn占用第w个子载波选择SRk作为中继节点与SDn通信时, STn与SDn之间的有效信干噪比。

● N* K*W的三维变量, 其中代表STn占用第w个子载波选择SRk作为中继节点与SDn通信时, 他们之间的信道容量。

经过分析, 公式 (10) 等价于如下公式所示:

其中,

公式 (25) 中的和可直接将变量带入公式 (13) 和 (14) 中求得。这里需要说明的是当 (22) 或 (23) 两者中的任何一个限制条件无法满足时, 即主用户接收端在某个子载波上的干扰温度限制无法满足的时候, 此时不允许STn选择SRk作为中继节点占用第w个子载波与SDn构建通链路, 意味着。

经过以上的转化之后, 我们的问题等价成为设计一个N*K*W的三维0-1 系数矩阵X , 其约束条件如下:

其中, 当X (n, k, w) =1时, 表示STn选择SRk作为中继节点占用第w个子载波与SDn建立通信链路。公式 (27) - (29) 表示的限制条件对应于在该三维系数矩阵中, 任何一个二维平面上最多只能有一个1, 其物理意义为任何一个次用户发送端最多只能选用一个次用户中继节点, 同时最多只能占用一个子载波进行通信。此时原来的优化问题可以等效表示为:

公式 (26) - (29) 的限制条件

3.2 算法设计

3.1 节中 (26) - (32) 描述的问题是一个0-1 线性整数规划问题, 是一个NP-hard问题, 采用穷举方法肯定可以得到此问题的最优解, 但是当节点规模较大时, 穷举法带来的复杂度将非常大。为了解决此问题, 我们在本节基于分支定界算法框架, 设计了可快速取到全局最优性能的算法。分支定界算法被认为是寻求非凸优化问题全局最优解的一种有效工具[18,19,20,21], 该算法框架的收敛性和全局最优性的理论证明可以参考[21]。针对本研究问题, 分支定界算法框架的关键步骤包括:对原问题的优化函数或者限制条件进行放松, 以得到一个便于求解的原问题上界;以放松后的解为出发点, 通过设计本地搜索算法, 得到一个原问题的可行下界;通过子问题选择和变量选择分割算法, 将选定的子问题分割为两个子问题进行迭代求解。具体来说, 就是首先将待求解变量从离散取值范围放松成为连续取值区间, 求得原问题的一个放松解。本地搜索算法则是将待求解变量重新收敛到离散值。

下面, 我们将对这几个步骤详细说明。

3.2.1 放松问题及上界求解

本问题中的变量是三维系数矩阵中的每个0-1 离散变量X (n, k, w) , 为便于求解原问题的上界, 首先将待求解变量从离散变量放松为连续区间变量, 后面会再通过本地搜索算法再将变量收敛到0 或者1, 从而经过有限的迭代过程, 最终得到最优性能解。将所有的优化变量X (n, k, w) 从离散的{0, 1}放松到连续区间[0, 1]之后, 我们可以得到放松之后的优化问题如下:

3.2.2 本地搜索算法

上面经过放松之后的优化问题, 可以使用内点法[22]等传统凸优化方法进行求解, 得到一组最优解和对应的最优值。为了得到原优化问题的一组可行解以及对应的可行值, 我们在本小节介绍的本地搜索算法中主要是在的基础上, 将放松后的变量重新收敛到0 或者1。

此处, 采用对通过求解放松问题得到的解进行四舍五入取整运算, 即:

经过以上处理之后, 在极个别情况下, 会出现某一个二维平面上存在两个1 的情况, 这与本问题的限制条件不符。为了解决这个问题, 我们采取如下措施:取整运算完成之后, 当某一个平面上有两个1 存在时, 比较这两个1 所在位置对应值的大小, 保留值较大的为1, 将另一个置0。更新所有变量值之后, 代入目标函数可以求得原优化问题的一个函数值, 作为原优化问题的可行下界。

本地搜索算法的详细描述如下:

本地搜索算法

3.2.3 变量选择和分割策略

在基于分支定界算法的每个迭代过程中, 若当前最大可行下界与最大上界仍无法满足迭代停止条件时, 需要继续选定一个子问题, 并选定该子问题中的一个未确定变量进行分割, 从而生成两个新的子问题, 进一步迭代求解。在我们的问题当中, 我们选择具有最大上界的子问题进行分割。子问题选定之后, 对分割变量的选择方法采用“不确定最大的值首先被分割”的原则。在我们的问题当中, 由于需把待求解的变量X (n, k, w) 确定为1 或者0, 因此, 我们选定距离不确定性最大的0.5 最近的变量首先进行分割, 即

算法整体描述如下所示:

算法I:全局最优中继选择与载波分配算法

输入变量:

主用户干扰温度矩阵Qth;

求解精度ε;

初始化:

迭代次数变量t=0 ;

子问题集合, 初始子问题;

原优化问题全局初始上界;

原优化问题全局初始下界;

迭代:

输出:

LBt为满足原优化问题求解精度要求的最终函数值。

在全局最优中继选择与载波分配算法中, Φub{Q}表示按照3.2.1 节中所描述的方法对子问题Q进行问题放松和求解的过程;Φlb{Q}表示按照3.2.2 节中所描述的本地搜索算法求解子问题Q上可行解的过程。

4 仿真结果与复杂度分析

4.1 仿真结果

本节将通过仿真实验来验证3.2节中所设计算法的性能。仿真参数如下:

●所有的信道都是单位方差、独立同分部 (i.i.d.) 的瑞利衰落信道;

●所有主次用户的发送节点最多只能占用一个子载波且有相同的发送功率, 即;

●所有主用户接收端在每个载波上的干扰温度限制值都为 Qth=5dB;

● 求解精度 ε=0.99 ;

● 所有仿真结果均是10000 次Monte Carlo信道仿真后的平均值。

需要说明的是, 在仿真中, 主用户之间的载波分配算法不是我们研究的重点, 此处我们采用以所有主用户对链路容量和最大化为目标的载波分配方法。

图2 分别给出了主用户对数量M=5, 次用户对数量N=5, 次用户中继节点数量K=10 情况下本文所设计中继选择与载波分配算法 (图中用“proposed”表示) 与通过穷举法 (图中用“exhaustive”表示) 取得所有次用户对链路容量和随子载波数量w变化的性能比较和本文所设计算法的平均迭代次数。从图中可以看出, 本文所设计中继选择与载波分配算法可以取到全局最优性能且平均迭代次数在1 到1.9 之间。运行以上仿真过程所有的台式PC机配置如下:Windows XP操作系统, Intel Pentium DualE2200 @2.2 GHz CPU和2 GB的内存。运行以上仿真时, “exhaustive” (“proposed”) 算法所用平均时间依次为:35秒 (少于1 秒) , 3 分2 秒 (少于1 秒) , 12 分45 秒34 分44 秒 (少于1 秒) , 1 小时20 分25 秒 (1 秒) , 2 小时43 分50 秒 (少于3 秒) 。

为进一步验证所提算法性能, 我们考虑在次用户中继节点数量K=8 情况下, 主次用户对以及整体系统的容量和随主用户对数量M和次用户对数量N、载波数量W变化时的三维性能曲线。需要说明的是, 因为仿真过程中本文所设计算法始终可以取到全局性能, 故没有再用proposed和exhaustive区分。图3分别从不同角度给出了主用户对容量和 (图中用“PUs”表示) 、次用户对容量和 (图中用“SUs”表示) 以及整个认知协作无线网络中所有主次用户对容量和 (图中用“PUs+SUs”表示) 。图4 从不同角度展示了本文所设计算法的平均迭代次数, 从图中可以看出我们的算法经过简单的几步迭代即可取到最优值。

4.2 复杂度分析

为进一步比较本文所设计算法与穷举法的性能, 我们将对这两种算法的计算复杂度进行定量分析。

由3.2 节中对本文所设计算法的描述可以得出, 本算法的计算复杂度主要体现在对N* K*W的三维变量中的每个元素的计算上, 因此其算法复杂度为ο (N* K*W) 。而当采用穷举方法时, 其计算复杂度为

上式中, 表示在K个中任选N个的所有排列数。上式中U1, U2, ..., UN分别代表第一个次用户对, 第二个次用户对, 第N个用户对进行中继选择和载波分配时的选择组合数。

综合以上仿真结果以及算法复杂度分析可知, 在多用户认知协作无线网络场景中, 本文所设计的中继选择与载波分配联合算法可取得全局最优性能且其运算复杂度远远低于穷举法。

5 结论

用户分配网络篇5

随着互联网( Internet) 发展的日趋成熟,人类进入一个前所未有的学习化社会,人际交往、工作、学习中的社会化的特性不断显露,在这个背景下,知识社区也获得了长足发展。知识社区作为一种交流、分享、互动知识的平台,为社区用户带来了更为方便快捷的获取知识的途径。随之产生的网上问答类社区 ( Online Q&A Communities) ,诸如Yahoo! Answers、百度知道[1]等,由于能够很好地满足网民的需求,开始吸引更多网民的关注和使用,在当今社会非常受欢迎。

新一代的问答服务,即基于Web. 2. 0平台的知识问答系统[2],也因此成为现代问答服务的主要形式。这是因为这些问答社区不仅可以给用户提供一个交流和共享知识的平台[3],而且给社区中的专家带来了很多显著的好处。在知识社区中,用户提出问题,由专家回答,而不是普通的用户回答,这样提高了问题回答的可靠性和正确率,同时也通过专家回答问题的数量及被采纳率和用户满意度,提高了专家的声誉,也使专家的个人价值得到了体现。但基于用户提出的问题五花八门,而且数据资源庞大, 专家需要花费更多的时间寻找自己感兴趣的问题, 由此提问用户需要等待较长的时间得到答案。此外,系统中还存在大量问题未被回答,问题所获得答案数目较少,回答答案质量差、用户无法获得最有效的答案等问题。因此,如何将大量闲置未被回答的问题及用户新提出来的问题进行合理分配,加速专家寻找问题及用户获得最佳答案的过程,从而增进知识社区信息传递、知识分享成为当务之急。

本文在对用户提出的问题进行深层次语义分析[4]的基础上,首先,引入概率潜在语义分析技术, 针对专家兴趣主题建模,通过专家对问题的感兴趣程度及问句之间的相似度计算[5],获得备选相关领域专家集。其次,构建专家与用户的链接结构[6], 使用PageRank算法估计专家的权威度,并结合专家回答问题及其答案的匹配度,最终获得最优专家集, 从而实现用户问题的合理分配。

1用户问题的语义分析

用户提出的每一个问题都有其特殊的组成单元,每个单元具有特殊的语义功能。本文使用块标记法分析用户提出的问句信息。该方法首先定义了用户问题的五项基本元素: 1问题主题T; 2问题关键词F; 3问题疑问词W*; 4辅助信息S; 5其他标记I。通过对问句语义基本元素的分析识别,可以将问句从普通的文字空间映射到一个具有特殊结构的语义空间中,使得问句的结构更清晰,便于研究与提取其中的块元素。五项基本元素的定义如表1所示。其中“问题主题”是问句的主体,它反应用户的信息需求。“问题关键词”,是对问句主题的进一步补充说明。“辅助信息”,是对问题主题的补充或者限制,一般包括时间、地点、场景等的限制。“其他标记”,在问句中没有实质性的语义,可以是敬语或者常用的网络词汇( 例如跪求、亲等) 。

“问题疑问词”,是疑问词及与疑问词有关的具体搭配。“问题疑问词”包含12个子类,包括选择、对比、描述、数量、原因、时间等,这个分类是一个粗粒度的问句分类体系。

由此定义一个五元组来表示问句的语义:

其中,W( q) 是疑问词信息代表问句的类型,T( q) 、 F( q) 、S( q) 、I( q) 分别表示问句的主题、关键词、辅助信息及其他信息。

2领域问答专家发现

2.1问题推荐定义

推荐系统最早可以追溯到信息检索、文本分类等不同领域。其一般由3个重要的模块组成: 用户建模模块、推荐对象建模模块、推荐算法模块。推荐系统把用户模型中兴趣需求信息和推荐对象模型中的特征信息匹配,同时使用相应的推荐算法进行计算筛选,找到用户可能感兴趣的推荐对象,然后推荐给用户。根据推荐机制[7]的不同可以将推荐系统分为: 基于内容的推荐、协同过滤推荐[8]和混合推荐等。

本文中问题推荐旨在将待解决的问题推荐分配给对该问题感兴趣的相关领域的专家[9],从而缩短用户等待答案的时间并获得有效的答案,增进知识社区中信息传播与知识共享。

问题推荐定义:

给定专家集E = { e1,e2,…,en} 和问题集Q = { q1,q2,…,qm} ,系统根据用户问题及专家的兴趣和所属专长,将相应问题qe∈ Q推荐给专家e ∈ E , 推荐问题满足:

其中,Degreeq,e表示专家e对问题q的感兴趣程度, 其取值范围为( 0,1) ,Degreeq,e的值越大,说明专家e对问题的感兴趣程度及擅长程度越高,回答问题的可能性越大。

2.2基于问题主题的用户兴趣建模

2.2.1概率潜在语义分析技术

概率潜在语义分析( PLSA) 应用于信息检索,过滤,自然语言处理,文本的机器学习或者其他相关领域。概率潜在语义分析与标准潜在语义分析的不同是,标准潜在语义分析是以共现表( 就是共现的矩阵) 的奇异值分解的形式表现的,而概率潜在语义分析却是基于派生自LCM的混合矩阵分解。

2.2.2模型构建

概率潜在语义分析模型( PLSA)[10]将自动挖掘文档类集中的潜在主题,同时能全面描述专家兴趣。在对专家e进行建模时,以概率潜在语义分析模型中的潜在变量z ∈ { z1,z2,…,zk} 表示专家e所回答的问题集的潜在主题。专家e回答问题q的过程是先选择主题z,再根据主题选择问题q,因此,专家e回答问题q的概率计算公式表示为:

其中,专家e ∈ { e1,e2,…,en} 和问题集q ∈ { q1, q2,…,qm} 。

利用 < 专家,词语 > 对的共现信息,得到专家与词语、问题的联合概率表示为:

其中,w表示词语,V表示所有词语的字典集合。 Pr( w | q) 表示为词语w和问题q之间的相关性。

2.3备选领域专家集获得

本文将结合专家e对选择问题q的可能性和专家e已回答问题集中的问题与用户等待回答问题的相似度,最终给出衡量专家对用户问题感兴趣程度即专长程度的Degreeq,e的计算方法。

1专家e对选择问题q的可能性用后验概率Pr( qu| e) 表示,根据贝叶斯定律( Beyesian Law) ,

针对同一个专家,概率值可以通过问题q中的词语概率的乘积,并经过问题长度的规格化计算得到:

2结合对问句的深层次语义分析过程,专家e已回答问题集中的问题qe与用户等待回答问题qu的相似度计算如下:

其中包含信息主体的相似度和问句类型的相似度[11]。问题信息主体包括T( q) ,F( q) ,S( q) ,I( q) 四类信息。而问题类型的相似度是用来度量两个不同问句类型之间的相似关系,W( X) 表示问句X的类型,Sim T( t1,t2) 表示两个问句类型的相似度。

由此得出,专家e对用户问题qu的感兴趣程度Degreeq,e计算公式为:

于是,针对专家e得到一个根据Degreeq,e排序的用户问题列表,从而可以选择其中前N个问题分配给专家回答。根据专家对同一问题的感兴趣程度, 得到领域专家列表,从而选择其中前M个专家,构成备选领域专家集。

3最优问答专家发现

在第2节中本文已经提出了获得回答用户问题的相关领域专家集的方法,但是根据专家对用户提出问题的感兴趣程度,以及结合专家历史回答问题集中的问题与用户提出问题的相似程度,得到的领域专家并不能保证能给现有用户最有效的回答,即有可能存在答案质量差、专业水准不够的问题。因而,本节在领域专家集的基础上,对这些专家进行进一步研究,通过研究专家历史回答问题集中问题与答案的匹配度即相似度,并结合专家的权威度,对领域专家集重新排序,最终筛选出更具权威更适合回答用户相关问题的专家列表,从而获得最优专家集, 使用户问题得到最合理的分配。

3.1专家权威度评价

本文提出根据问答社区中的链接结构来评估用户的权威度。通过给定专家已回答问题集合中用户提问与专家回答的关系,构建专家与用户的交互图。本文认为,权威度高的专家向用户提供的答案质量就越高,答案的质量高也就意味着专家提供的答案被用户选为最佳答案的几率越大,从而根据专家与用户的交互图计算出被选为最佳答案的用户到专家的边的权值,根据得分的高低进行用户权威度的排序。

当专家ej回答了一个用户ui提出的问题时,ej在一定程度上给用户ui提供了一些有用的信息。可将这种信息的传递看作是ui到ej的一条链接。举例说明,在图1中,有三个问题,u1、u4、u3分别为问题1、问题2 、问题3的提问用户,问题下面是各个专家分别给的答案,其中答案包括最佳答案和备选答案。

针对一个专家,本文将其回答用户提出的问题及相应的的答案看作是一对一的链接。考虑到专家回答过的问题以后,有的答案会被用户采纳选择为最佳答案,有的答案只作为该用户问题下的答案之一,并不作为最佳答案。由此,以图1中的专家e4为例,其分别回答了问题1、2、3这三个问题,且问题3的提问用户u3将专家e4的回答选择为最佳答案,而问题1、2的提问用户并没有将专家e4的答案选为最佳答案。

由此,将图1中的用户与专家的交互关系以专家e4为例,用链接结构来表示,如图2所示,其中节点分别表示专家与其提供答案的用户,有向边表示专家与用户之间的链接。其中粗边表示该专家的答案被用户选为最佳答案。

所以给定专家已回答问题用户的集合Ue和专家ej,Ue到专家ej的边的权值Wij定义为:

其中,Qi,jbest为专家回答并被用户采纳为最佳答案的问题集合,Qi,j为专家回答但未被用户作为最佳答案的问题集合,λ 为权重系数,λ ∈[0. 5,1],表示最佳答案比其他答案更突出。受PageRank算法[12]的启发,将用户的集合Ue和专家ej的链接网络关系看作是有向图G = ( Ue,B) ,Ue表示专家已回答问题用户的集合,B表示用户与专家之间ej有向边的集合,则对于一个专家ej,其权威度authej可表示为:

其中,authej为用户的Weight PageRank[13]值,Ue为所有指向专家ej的用户集,Wij为专家j到用户有向边的权重,∑wj为专家j到所有用户的有向边的权重之和。利用公式( 9) 计算出的Weight PageRank值即为专家得分。依据得分的高低进行用户权威度的排序。

3.2问题与答案的关联性特征计算

本文采用基于关键词的匹配数来计算专家回答问题集中,问题与答案的匹配度。给定问题的关键词集合为Fq( x1,x2,…,xn) ,答案的关键词集合为Aq( x1,x2,…,xm) ,根据集合Fq和集合Aq的关键词匹配数来计算问题与答案的关联度。

其中, C ( Fq ) 表示集合Fq中关键词的个数, C ( Aq ) 表示集合Aq中关键词的个数, C ( Fq ∩ Aq ) 表示集合Fq与集合Aq匹配的关键词的个数, Sim ( Fq , Aq ) 就是问题与答案的关联度。

根据问题与答案对的关联度Sim( Fq,Aq) ,可以计算出专家回答用户的问题集中,问题与答案的关联度的平均值Sim'( Fq,Aq) ,即平均关联度,平均关联度越高,证明专家回答的答案质量[14]越高, 用户获得的答案信息更有价值。

3.3最优问答专家集获得

研究相关领域专家集中的每个专家,将其回答用户问题集中问题与答案的平均匹配度Sim'( Fq, Aq) 与其权威度authej结合,从而将相关领域专家集中的专家重新排序,获得最优专家集合。将系统中用户提出的新问题及未被回答的问题推荐给每个问题对应的最优专家集,从而最终实现用户问题的合理分配。

4实验验证

本文通过收集到的百度知道[15]用户访问日志数据,从百度知道上抽取了真实的标注数据集。根据问题与答案的质量经过挑选,选取了哲学、心理疾病、教育三个类别的问题集中的部分问答结果,包括33520个问题和对应的171864个与之相对应的答案,并从中获取了一组用户数据,数据集具体信息如表2所示。

对于领域专家集的推荐,实验分别在哲学、心理疾病、教育三个方面的数据集上进行测试,对每个数据集分别使用余弦相似度计算方法Cosine和基于概率潜在语义分析的推荐方法。通过对比观察发现, 基于概率潜在语义分析模型的问题推荐方法比余弦相似度方法准确率分别高出4. 7% 、5. 2% 、7. 1% 。

对于最优专家集的推荐,本文对数据集进行了如表3的比较,其中Cos为计算问题内容与专家答案的余弦相似度、Sim为将问题的内容和答案的相似度和提问用户和回答专家的相似度线性加权,权重系数 α = 0. 2、Sim Auth为本文提出的将相似度与专家权威度融合,α = 0. 2,λ = 1。实验结果发现,引入专家权威度的相似度计算,可进一步提升系统的性能,体现了专家权威度在获得最优专家集中的有效性。

5结束语

用户分配网络篇6

随着无线通信的发展, 对频谱资源的需求越来越大, 传统的频谱分配方式受到了极大的挑战。传统的频谱分配方式主要是以固定分配方式为主, 即频谱固定分配给授权用户使用, 其他用户无权进入该频谱段。这样的方式有利于提高系统的服务质量 (QoS) , 但由于使用某频段的授权用户在不同的位置不同时间段对频谱的使用情况是不一样的, 这样, 在授权用户不使用该频段的时候, 其他用户又不能进入该频段, 造成了频谱资源的浪费, 导致了频谱的利用率偏低。解决这个问题的一种可行的方法就是采用认知无线电技术]1[。在认知无线电网络中用户分为授权用户 (也叫主用户, Primary User, PU) , 非授权用户 (也叫次用户, Secondary User, SU) , PU可以在任何时间无限制地进入它的授权信道, SU则通过不断对频谱的监测发现频谱空穴, 然后把所发现的频谱空穴放入频谱池共享。

本文主要是讨论频谱池的资源在SU之间的分配问题。现在关于认知无线电网络的频谱分配问题已经有了不少的文献, 文献[2,3]提出了一种基于图论着色理论的频谱接入算法——CSGC (Color Sensitive Graph Coloring) 算法, 在避免用户间干扰的前提上能获得最大化的带宽效益, 并分析了该算法中频谱利用率和公平性的问题。文献[4]提出了一种并行频谱分配算法, 有效地降低了频谱分配的时间开销。文献[5]在重新定义了频谱利用率的基础上提出了一种标签着色-删除算法 (以下简称删除算法) , 在新的定义下频谱利用率比CSGC算法了有较大的提高。但这些算法都没有考虑到用户的等待时间问题, 也就是每一轮的分配只和本轮的参数有关, 不考虑之前的因素。这样, 在频谱资源比较紧张的时候就会导致部分用户, 特别是弱势用户 (该用户使用同样频谱的时候带来的系统效益较小) 的等待时间过长。本文提出了一种基于用户等待时间的频谱分配改进算法, 既考虑到了系统效益, 又能在频谱资源比较紧张的时候有效地避免用户特别是弱势用户出现等待时间过长的问题, 使系统效益和用户的等待时间得到很好的平衡。

2 频谱分配数学模型

本文的频谱分配数学模型[2]由可用频谱矩阵、效益矩阵、干扰矩阵和分配矩阵, 以及本算法所特有的用户等待时间矩阵来描述的。假设分配时间相对于环境变化时间是很短的, 各矩阵在每轮分配中保持不变。各矩阵具体定义如下:

(1) 可用频谱矩阵。用L={l n, m|ln, m∈0{1, }N×M来表示可用矩阵。其中N为用户标号 (下标从0到N-1) , M为频谱标号 (下标从0到M-1) 。当ln, m=1是表示频带m对于用户n是可用的, 反之, 当ln, m=0表示频带m对于用户n是不可用的。

(2) 效益矩阵。用B={nb, m}N×M表示效益矩阵。bn, m表示用户n使用信道m带来的效益。把可用频谱矩阵L和效益矩阵B结合, 将得到可用的效益矩阵LB={l n.m.bn, m}N×M。

(3) 干扰矩阵。用C={c n, k, m|ln, k, m∈0{1, }N×N×M来表示用户间的干扰矩阵。cn, k, m=1表示用户n与用户k同时使用信道m的话将会导致干扰, 当n=k时, cn, k, m=ln, m。

(4) 用户等待时间矩阵。这是本算法独有的矩阵。由于相邻两轮分配的时间间隔是一样的, 并假设用户的发射请求未得到满足前会在每轮分配时都提出发射申请, 所以我们可以用用户发射请求被满足时的总申请次数或经过的等待次数来表示用户等待时间。则用户等待时间矩阵可以表示为G={g n|gn∈N}N×1, gn称为用户n的等级系数。初始化时, G为全零矩阵, 当用户n提出发射请求时gn=1, 每当用户的发射请求未满足时, gn递增1;当用户的发射请求得到满足时, gn变为0。也称为用户级别矩阵。

(5) 无干扰分配矩阵。用A={a n, m|an, m∈0{1, }N×M表示满足无干扰的分配矩阵。如果an, m=1表示信道分配给用户n。明显地, 无干扰分配矩阵必须满足:

a n, m.ak, m=0, 当

这样认知无线电网络的频谱分配问题就抽象成为一个图G= (U, EC, LB) 的着色问题。其中U是图G的顶点集, 表示无线电网络中共享频谱的次用户, LB表示顶点可选频谱的集合和权重, EC是边集, 由干扰矩阵决定, 当且仅当cn, k, m=1时, 两个不同的顶点 (用户) u, v∈U之间有一条颜色为m (对应频带m) 的边。这样, 满足 (1) 式的无干扰分配的条件可以描述为:当两个不同的顶点存在着m色边的时候, 两个顶点不能同时着m色。

3 基于用户等待时间的频谱分配改进算法

3.1 频谱利用率的定义

文献[2]、[3]都是用频谱利用率作为系统的效益的, 并把频谱利用率定义为:

如文献[5]分析, 这样定义的频谱利用率并没有太大的现实意义。因为现实的终端用户大多都是一个频率的通信接口, 无法享用多个频率信道的好处。在这样的定义下, 如果最大化频谱利用率, 将会驱使一个用户被分配到多个信道 (频段) 。如果一个用户只使用其中的一个信道, 其他的信道将作为其备用信道, 这样必然会导致贫困用户的出现。所以文献[5]把频谱利用率重新定义为:

在如 (3) 式的定义下, 最大化频谱利用率的话, 每个用户只会分配到一个信道, 这样, 在频谱资源比较紧张的时候能避免一个强势用户分配到多个信道导致浪费的问题, 提高了信道利用率。但文献[5]提出的删除算法仍然没解决频谱紧张的时候部分用户等待时间过长的问题。

本文的频谱利用率采用式 (3) 的定义。

3.2 基于用户等待时间的频谱分配改进算法

CSGC算法和删除标签算法都只考虑到了用户的带宽效益, 并未考虑到在频谱资源比较紧张的时候用户的等待时间, 这样必然会导致部分用户特别是弱势用户的等待时间过场的问题。

3.2.1 分配目标

本算法的分配目标是平衡系统效益和用户等待时间的矛盾问题, 既要使用户的等待时间不至于很长, 又考虑到系统的效益。即如果用户的等待时间不同, 优先分配给等待时间长的用户, 如果用户的等待时间一样, 优先分配给系统效益大的用户。

3.2.2 基于用户等待时间的频谱分配改进算法

本算法将结合用户等待时间进行频谱分配。其基本思想是在频谱资源比较紧张的时候, 部分用户要等待一段时间才可以使用信道, 分配时考虑用户的等待时间, 对等待时间较长的, 优先分配。而对于等待时间一样的, 再采用经典频谱分配的某个准则 (如CMSB, CollaborativeMax-Sum-Bandwidth, 协作最大化带宽准则;NMSB, Non-collaborative-Max-Sum-Bandwidth, 非协作最大化带宽准则等) 计算标签值后再进行分配, 标签值大的优先分配。在CMSB准则下, 标签值, 其中nD, m表示与该次用户干扰的其他次用户数, 也叫邻居数;在NMSB准则下, 标签值。当一个用户n已分配到一个信道时, 退出本轮分配, 并把n的等级系数gn置0;当用户n没分配到信道时, n的等级系数递增1。这样, 用户随着等待时间变化, 能自适应地调整其优先级, 保证每个用户在不是很长的等待时间内就能分配到信道。

本算法考虑到了用户的等待时间, 避免用户出现很长的等待时间, 体现公平性。在等待时间相同的时候, 考虑到了系统效益。如果在频谱资源不紧张的时候, 即每个用户都不用等待就能使用频谱时, 用户等级矩阵一直为全0矩阵, 本算法就和删除算法一样了。

算法步骤如下:

(1) 搜寻图的用户级别矩阵, 找出级别最高的那些顶点 (用户名单) 。

(2) 选择某分配准则 (如CMSB或者NMSB) , 对本级别顶点计算标签值, 然后根据该准则分配颜色 (频谱) 。

(3) 更新顶点 (用户) 表单和颜色 (频谱) 表单, 若该级别顶点已全部分配完或该级别顶点已无可用颜色, 则进入下一级别分配, 否则返回 (1) 。该级别中分配到信道的用户级别数值置0, 否则递增1。

(4) 下一级别分配, 重复 (1) 到 (3) 的步骤。

(5) 当最低级别分配完毕, 本轮分配结束。

具体算法流程图如图1所示:

4 仿真结果分析

下面将本文算法、CSGC算法和删除算法分别在CMSB准则下进行比较, 比较频谱分配对用户等待时间的满足情况。

为简便起见, 假设每个用户如果在某轮分配到频谱, 到下一轮分配时候刚好结束使用, 该用户重新回到申请队列。为了看出不同算法在频谱资源比较紧张的时候对普通用户和弱势用户等待时间的影响, 我们让两种用户分别成功申请1 000次, 并计算每成功申请一次需要等待的次数的概率分布。具体参数如表1所示:

在CMSB准则下, 并采用 (3) 式来计算系统吞吐量 (频谱利用率) , 让某个弱势用户和一般用户成功申请1 000次, 每成功申请一次需要等待次数的概率分布如图2, 图3所示:

如图2所示, 而在删除算法中, 弱势用户的等待次数在4次内的只有80%, 而且出现长达20次等待次数, 不过概率比较小, 弱势用户等待次数大于6次的有10%左右的机会出现;在CSGC算法中, 等待次数在4次内的概率不到70%, 大于6次的概率大于20%。本算法中的弱势用户等待次数最多只有4次, 而集中在2次内的概率达到了97%左右。很明显, 本文所提算法对用户等待时间有明显的改善, 弱势用户不会出现很长的时间。

图3中, 删除算法中的一般用户一次就申请成功 (对应等待次数0次) 的概率比本算法大, 但是一般用户仍有可能出现长时间的等待, 甚至可能出现长达10次的等待次数。CSGC算法的一般用户的等待时间比删除算法的一般用户的等待时间更长。而在本算法中, 一般用户的等待时间最多只有3次, 而且2次内的概率就已经接近100%。所以对于一般用户而言, 本算法对用户的等待时间也有改善。

总的来说, 本算法对用户的等待时间有明显的改善作用, 能通过用户的等待时间自适应地改变用户的优先级, 使用户不会陷入长时间的等待, 用户有趋于均衡的机会使用频谱, 提高了系统的公平性。

下面比较3种算法的系统吞吐量, 让系统运行1 000次, 并 (3) 式定义下计算吞吐量的概率分布, 结果如图3所示:

从图4中可以看出, 本算法比CSGC算法的吞吐量要大, 比删除算法的吞吐量要小。本算法在牺牲了部分带宽效益的同时获得了满足用户等待时间的性能提高。

5 结束语

认知无线电的频谱池是给次用户实行资源共享的, 每个次用户都有权使用频谱。如果一个次用户使用频谱的等待时间过长, 甚至把一个次用户排除在系统外, 这明显造成了不公平。本算法第一次把用户的等待时间引入基于图论的频谱分配的数学模型中, 把等待时间和CMSB准则结合一起, 自适应地调整用户的优先级别, 使用户在频谱紧张的时候不会陷入长时间的等待, 用户有趋于均衡的机会使用频谱, 保证了系统的公平性。仿真结果分析证明了本文结论。

造成了不公平。本算法第一次把用户的等待时间引入基于图论的频谱分配的数学模型中, 把等待时间和CMSB准则结合一起, 自适应地调整用户的优先级别, 使用户在频谱紧张的时候不会陷入长时间的等待, 用户有趋于均衡的机会使用频谱, 保证了系统的公平性。仿真结果分析证明了本文结论。

参考文献

[1]Joseph MitolaⅢand Maguire G Q.Cognitive Radio:Making software radios more personal, IEEE Personal Communications, 1999, 6 (4) :13-18

[2]Zheng H and Peng C.Collaboration and fairness in opportunistic access.In Proc.40th annual IEEE International Conference on Communications (ICC) , Seoul Korea, 2005, 5:3132-3136

[3]Peng C, Zheng H, Zhao B Y.Utilization and fairness in spectrum assignment for opportunistic spectrum access[J].ACM Mobile Networks and Applications (MONET) , 2006, 11 (4) :555-576.

[4]廖楚林, 陈劼, 唐友喜等.认知无线电中的并行频谱分配算法.电子与信息学报, 2007, 29 (7) :1608-1611

用户分配网络篇7

关键词：交通分配,Wardrop准则,基于终点模型,仿射尺度算法

交通分配就是把各种出行方式的空间OD量分配到具体的交通路网上,它是城市交通规划的一个重要环节。依据Wardrop第一、第二准则,通常把交通分配划分为均衡分配与非均衡分配。Beckman最早提出了满足Wardrop第一准则的用户均衡交通分配模型,常采用Frank-wolfe算法进行求解[1,2,3]。由于该模型以各OD对之间的路径流量为变量,需要枚举OD对间的所有路径,因此对大型路网,模型求解相对比较困难。

近年来,许多学者对这类问题进行了多方面研究[4,5,6],提出许多新的模型与算法,如基于路段模型与算法[7],基于起点和终点的模型与算法[8,9]等。这些模型与算法都是以路段流量为变量,并发现基于路段的交通分配模型同样满足Wardrop第一准则。选择路段流量为变量,避免路径枚举,减少计算的复杂程度。

基于终点的用户均衡交通分配模型可以归结为一个具有线性约束的非线性规划问题,本文采用简单实用的仿射尺度算法[10]求解这类问题。首先给出基于终点的用户均衡交通分配模型,指出该模型与基于路径均衡配流模型是等价的,当选择适当路阻函数后,模型可以归结为带线性约束的非线性规划问题,并转化为仿射尺度算法的处理形式;最后采用该算法求解一个小型路网的交通配流问题,仿真结果显示,该算法是有效的,可用于大型路网的配流计算.

1 交通分配模型

1.1 用户均衡交通分配模型

用户均衡分配模型是更接近实际交通状态的分配模型。在均衡状态时,在同一OD对间所有被使用的路径上,其路径行驶时间相等且该行驶时间小于或等于未被使用路径上的行驶时间,此时网络处于平衡状态,任何出行者均无法通过变更选择路径达到减少出行时间的目的。对于一个给定交通网络G=(N,A),N为节点集,A为边集,R为起点集,S为终点集,R与S可以有公共元素;A(i)为以i为起点的有向路段集合;B(i)为以i为终点的有向路段集合;(r,s)为以r为起点,s为终点的OD对;x $_{a}^{s}$ 表示路段a上到终点s,(s∈S)的流量;Prs为OD对(r,s)间所有路径集合。对应于Wardrop第一准则的用户均衡交通分配模型(1):

$\begin{array}{l} \min z (x) = \sum_{a \in A} \int_{0}^{x_{a}} t_{a} (ω) d ω (1) \\ s . t . \sum_{p \in Ρ_{r s}} f_{p}^{r s} = q_{r s}, \forall r, s (2) \\ f_{p}^{r s} \geq 0, \forall p, r, s (3) \\ x_{a} = \sum_{r \in R} \sum_{s \in S} \sum_{p \in Ρ_{r s}} δ_{a p}^{r s} \cdot f_{p}^{r s}, \forall a (4) \end{array}$

式中:f $_{p}^{r s}$ 是O-D对(r,s)间路径p上的交通量;qrs是OD对(r,s)间的交通需求量;

$δ_{a p}^{r s} = {\begin{matrix} 1 ‚ & Ο D 对 (r, s) 间路径 p 经过路段 a \\ 0 ‚ & 否则 \end{matrix}$

上面模型是基于路径用户均衡交通分配模型,求解该模型需要枚举OD对间的所有路径,因此在大型路网上应用比较困难。下面给出的基于终点的用户均衡交通分配模型(2):

$\begin{array}{l} \min z (x) = \sum_{a \in A} \int_{0}^{x_{a}} t_{a} (ω) d ω (5) \\ s . t . \sum_{a \in A (i)} x_{a}^{s} - \sum_{b \in B (i)} x_{b}^{s} = q_{i s}, \forall i \in R, s \in S, i \neq s (6) \\ \sum_{a \in A (i)} x_{a}^{s} - \sum_{b \in B (i)} x_{b}^{s} = 0, \forall i \notin R, s \in S, i \neq s (7) \\ x_{a}^{s} \geq 0 (8) \\ x_{a} = \sum_{s \in S} x_{a}^{s} (9) \end{array}$

该优化模型以路段到终点的流量x $_{a}^{s}$ 为变量,避免了路径枚举,从而适用于大型路网的配流计算。

1.2 模型分析

模型(1) 中目标函数是路段行驶时间函数积分之和,该目标函数在交通上的含义并不直观,但它的K-K-T条件却正好与Wardrop第一准则一致。并且可以证明,模型(2)与模型(1)是等价的。事实上,令x $_{a}^{r s}$ 为路段a从起点r到终点s的流量,则有 $x_{a}^{r s} = \sum_{p \in Ρ_{r s}} f_{p}^{r s} \cdot δ_{p a}^{r s}$ ,对∀i≠r,i≠s,有 $\sum_{a \in A (i)} \sum_{p \in Ρ_{r s}} f_{p}^{r s} \cdot δ_{a p}^{r s} - \sum_{b \in B (i)} \sum_{p \in Ρ_{r s}} f_{p}^{r s} \cdot δ_{b p}^{r s} = 0$ ,即OD对(r,s)中,当节点i为中间点时进入i的流量等于流出流量。从而有:

$\begin{array}{l} \sum_{a \in A (i)} x_{a}^{s} - \sum_{b \in B (i)} x_{b}^{s} = \sum_{a \in A (i)} \sum_{r \in R} x_{a}^{r s} - \sum_{b \in B (i)} \sum_{r \in R} x_{b}^{r s} \\ = \sum_{a \in A (i)} \sum_{r \in R} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{a p}^{r s} - \sum_{b \in B (i)} \sum_{r \in R} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{b p}^{r s} \\ = \sum_{r \in R} (\sum_{a \in A (i)} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{a p}^{r s} - \sum_{b \in B (i)} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{b p}^{r s}) = 0 \end{array}$

即为式(7)。同样对∀i∈R,i≠s时有:

$\begin{array}{l} \sum_{a \in A (i)} x_{a}^{s} - \sum_{b \in B (i)} x_{b}^{s} \\ = \sum_{a \in A (i)} \sum_{r \in R} \sum_{p \in Ρ^{o s}} f_{p}^{r s} \cdot δ_{a p}^{r s} - \sum_{b \in B (i)} \sum_{r \in R} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{b p}^{r s} \\ = \sum_{a \in A (i)} \sum_{p \in Ρ^{i s}} f_{p}^{i s} \cdot δ_{a p}^{i s} + \sum_{a \in A (e)} \sum_{r \in R {i}} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{a p}^{r s} - \\ \sum_{b \in B (i)} \sum_{p \in Ρ^{i s}} f_{p}^{i s} \cdot δ_{b p}^{i s} - \sum_{b \in B (i)} \sum_{r \in R {i}} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{b p}^{r s} \\ = \sum_{a \in A (i)} \sum_{p \in Ρ^{i s}} f_{p}^{i s} \cdot δ_{a p}^{i s} + \sum_{r \in R {i}} (\sum_{a \in A (i)} \sum_{p \in Ρ^{r s}} f_{p}^{r s} \cdot δ_{a p}^{r s} - \\ \sum_{b \in B (i)} \sum_{p \in Ρ^{i s}} f_{p}^{i s} \cdot δ_{b p}^{i s}) \\ = \sum_{a \in A (i)} \sum_{p \in Ρ^{i s}} f_{p}^{i s} \cdot δ_{a p}^{i s} = \sum_{p \in Ρ^{i s}} f_{p}^{i s} = q_{i s} \end{array}$

与式(2)一致,所以模型(1)与(2)是等价的。

1.3 模型的矩阵表示

令x=(…,x $_{a}^{1}$ …x $_{a}^{| S |}$ ,…)T(|A|×|S|)×1表示路网中各路段基于终点的流量向量;ei(s)=(…,eia(s),…)1×|A|表示s为OD对终点时节点i的点弧关联向量;其中:

$e_{i a} (s) = {\begin{matrix} 1 ‚ & s 为 Ο D 终点时, i 为 a 的起点 \\ - 1 ‚ & s 为 Ο D 终点时, i 为 a 的终点 \\ 0 ‚ & 否则 \end{matrix}$

设:

$\begin{array}{l} E (s) = [\begin{array}{l} e_{1} (s) \\ e_{2} (s) \\ \dots \\ e_{| Ν |} (s) \end{array}]_{| Ν | \times | A |} \\ E = [\begin{matrix} E (1) & 0 & \dots & 0 \\ 0 & E (2) & \dots & 0 \\ \dots & \dots & \dots & \dots \\ 0 & 0 & \dots & E (| S |) \end{matrix}]_{(| Ν | \times | S |) \times (| A | \times | S |)} \\ b = (\dots, b_{i}^{s}, \dots)_{(| Ν | \times | S |) \times 1}^{Τ}, \\ b_{i}^{s} = {\begin{matrix} q_{i s}, & i \in R, s \in S 且 i \neq s \\ 0, & 否则 \end{matrix} \end{array}$

采用矩阵表示模型(2)转化为式(10):

$\begin{array}{l} \min z (x) = \sum_{a \in A} \int_{0}^{x_{a}} t_{a} (ω) d ω \\ s . t . E x = b \\ x \geq 0 (10) \end{array}$

2 仿射尺度算法

2.1 算法的基本思想

设模型(3)的内可行域Q+={x|Ex=b,x>0},当前迭代点为xk=(x $_{1}^{k}$ ,…,x $_{| A | \times | S |}^{k}$ )T,xk∈Q+,构造对角阵Dk=diag(x $_{1}^{k}$ ,x $_{2}^{k}$ ,…,x $_{| A | \times | S |}^{k}$ ),做仿射尺度变换Tk:g=D-1kx,在此变换下,式(10)变为:

$\begin{array}{l} \min G_{k} (g) \\ s . t \bar{E_{k}} g = b ‚ g \geq 0 (11) \end{array}$

其中, $\bar{E_{k}} = E D_{k}$ ,并且xk被变换到式(11)约束区域的中心e=(1,1,…,1) $_{(| A | \times | S |) \times 1}^{Τ}$ 。从e出发沿式(11)的目标函数在gk=e处的负梯度在矩阵 $\bar{E_{k}}$ 的核空间的投影方向: $q_{k} = - (\nabla G_{k} (e) - \bar{E_{k}} ´ (\bar{E_{k}} \bar{E_{k}} ´)^{- 1} \bar{E_{k}} \nabla G_{k} (e))$ 做一维搜索,这里ᐁGk(e)=Dkᐁz(xk)。若qk=0,则可证xk是式(11)一个K-T点;若qk≠0,则记 $p_{k} = \frac{q_{k}}{∥ q_{k} ∥}$ ,做一维搜索 $\min_{0 \leq λ \leq θ} F (x^{k} + λ D_{k} p_{k}) ‚ (0 < θ < 1)$ 。

2.2 算法的迭代步骤

Step 1: 给定初始点x0∈Q+,x0=(x $_{1}^{0}$ ,x $_{2}^{0}$ ,…,x $_{| A | \times | S |}^{0}$ )T,允许误差ε,σ>0,置k =1;

Step 2: 令Dk=diag(x $_{1}^{k}$ ,x $_{2}^{k}$ ,…,x $_{| A | \times | S |}^{k}$ ),计算 $q_{k} = - (\nabla G_{k} (e) - \bar{E_{k}} ´ (\bar{E_{k}} \bar{E_{k}} ´)^{- 1} \bar{E_{k}} \nabla G_{k} (e))$ ,其中 $\nabla G_{k} (e) = D_{k} \nabla z (x^{k}), \bar{A_{k}} = A D_{k}$ ;

Step 3: 若‖qk‖<ε,则令xmin=xk,停止;否则,转Step 4;

Step 4: 计算 $p_{k} = \frac{q_{k}}{∥ q_{k} ∥}$ ,进行一维搜索

$\min_{0 \leq λ \leq θ} z (x^{k} + λ D_{k} p_{k}) ‚ θ \in (0 ‚ 1)$ ;

Step 5: 设λk是Step4中最优解,若‖λkDkpk‖<σ,则令xmin=xk,停止;否则,转Step 6;

Step 6: 令xk+1=xk+λkDkpk,置k=k+1,转Step2;

3 仿真实验

考虑如图1所示的交通路网,有14条路段,变量x $_{a}^{s}$ 有28个;有2个OD对1-9和3-7,OD需求量分别为q1,9=q3,7=55;路阻函数采用美国公路局1964年提出的BPR函数,具体可取 $t_{a} (x_{a}) = t_{a} (0) (1 + 0.15 (\frac{x_{a}}{c_{a}})^{4}), t_{a} (0)$ 为路段自由流行驶时间,设每条路段饱和容量为40;路段自由流行驶时间见表1。

采用仿射尺度算法,使用Matlab软件编程对这个实例进行求解。求解中所取允许误为ε=0.01,σ=0.1时,各路段分配流量见表2。表3给出分配流量路径的行驶时间,可以看到,同一OD对路径行驶时间基本相同,从而满足Wardrop 第一准则。图2给出了仿射尺度算法的收敛曲线图,可以发现,本算法收敛速度快,算法迭代528步后误差降为0.01。

4 结语

本文给出了基于终点的用户平衡交通分配模型的仿射尺度算法,模型以基于OD对终点的路段流量作为变量,避免了路径枚举,减少计算量。仿真计算结果显示,本文采用的仿射尺度算法是有效的,分配到各路段的流量满足Wardrop 第一准则。

参考文献

[1]Lee Der-Horng,Nie Yu.Accelerating Strategies and Compu-tational Studies of the Frank-Wolfe Algorithm for theTraffic Assignment Problem[J].Trans.Research Record,2001,1 771:97-105.

[2]Gao Ziyou,Lam W H K,Wong S C.The Convergence of E-quilibrium Algorithms with Non-monotone Line SearchTechnique[J].Applied Mathematic and Computation,2004,148:1-13.

[3]Michael Patriksson.Algorithm for Comuting Traffic Equilib-ria[J].Network and Spatial Economics,2004,4:242-250.

[4]Yu Nie,Zhang H M.Models and Algorithms for the TrafficAssignment Problem with Link Capacity Constraints[J].Transportation Research Part B,2004,38:285-312.

[5]Lee Der-Horng,Nie Yu,Chen Anthony.A Conjugate GradientProjection Algorithm for Traffic Assignment Problem[J].Mathematical and Computer Modeling,2003,37:863-878.

[6]芦群,刘灿齐.城市公共交通网络均衡分配模型与算法[J].交通与计算机,2004,22(4):3-6.

[7]肖海燕.基于路段流量的交通分配模型的算法[J].武汉科技大学学报:自然科学版,2007,30(3):274-277.

[8]Bar-Gera H.Origin-based Algorithm for the TrafficAssignemnt Problem[J].Trans.Science,2002,36:398-417.

[9]李峰,王书宁.基于终点的路径交通量求解算法[J].清华大学学报:自然科学版,2006,46(1):149-152.

用户分配网络篇8

为了满足更多用户、更高速率的业务传输以及更高的频率利用效率的要求,第三代合作伙伴计划(3GPP)于2004年底正式启动了长期演进(Long Term Evolution,LTE)项目。LTE的主要性能需求为:上行链路不低于50Mbit/s、下行链路不低于100Mbit/s的高系统吞吐量;用户面单向时延<5ms、控制面时延<10ms的更低传输时间延迟;三倍高速分组接入(HSPA)的高频谱效率;支持可变带宽、离散频谱资源分配等更灵活的频谱利用方式。

3GPP R8版本中指出LTE物理层的关键技术包括:正交频分复用(OFDM)技术;自适应调制和编码(AMC)技术、快速混合自动重传(HARQ)技术、多输入多输出(MIMO)技术以及动态资源分配技术等。其中,动态资源分配主要是研究如何利用有限的时间、子载波及功率等资源实现LTE系统性能最优化,因此备受运营商关注。本文首先对业务模型及资源分配模型进行简要介绍,然后介绍了经典的分组调度算法及现代分组调度算法,最后根据LTE的业务特征对资源分配技术提出改进。

2 LTE业务特性及资源分配系统概述

不同种类业务应用于不同的场景,可以具备不同的服务质量(QoS)性能特征。在3GPP协议中规定了4种业务类型,分别为:会话类(Conversational Class)、流媒体类(Streaming Class)、交互类(Interactive Class)和背景类(Background Class)。每种业务类型的性能特征如表1所示。

语音电话是最常见的会话类业务,目前可视电话和视频会议逐渐成为新的会话类业务。作为一种实时业务,会话类业务最主要的特征就是严格的低传输延时和信息流前后时序关系的保证。流媒体类业务是非会话类的实时业务,以单向传输的音频或视频为主。这类业务最主要的特征就是虽对传输时延没有严格的要求,但是要保证信息流前后的时序关系,同时对该类业务的端到端时延抖动也有所限制。交互类业务面向数据应用,该类业务的主要特征包括终端对往返传输时延的要求以及对误码率的要求。背景类业务与交互类业务都是面向数据应用的业务类型,背景类业务对传输时延并没有特殊要求,但对传输信息的可靠性要求很高,也即是对误码率要求很高。

与3G系统的三层网络架构不同,LTE系统采用扁平化全IP网络架构,由E-UTRAU基站(eNodeB)和接入网关(AGW)组成,其中eNodeB主要功能包括选择接入网关、寻呼信息、广播消息、设置和测量eNodeB及无线资源管理(RMM)等。LTE系统采用的动态资源分配技术作为无线资源管理的一部分在eNodeB中实现。

无线资源分配主要是指对时间、信道及功率等受限资源进行分配,LTE无线资源具体包括时间、子载波和功率。3GPP中规定,在LTE系统中12个子载波被称为一个资源块(RB),是LTE资源分配的最小单位。目前,对LTE资源分配算法的主流研究是在一个最小时间单位内,即一个调度周期内,分配RB和功率资源。通过在不同调度周期内,对不同用户、不同业务动态分配RB和功率资源来实现最佳的LTE系统性能。

3 经典资源分配技术

经典资源分配技术,只考虑小区吞吐量和用户之间的公平性这两个因素,分配算法也就是这两个因素之间的折中,经典资源调度算法主要包括:轮询(Round Robin,RR)调度、最大载干比(Max C/I)调度和正比公平(Proportional Fair,PF)调度三种分配算法

3.1 轮询(Round Robin,RR)算法

轮询调度只考虑用户的公平性,其基本思想是:小区内的用户按照某种确定顺序循环占用等时间的无线资源进行通信。目标就是保障用户之间的公平性,即保证每个用户都能得到一定的服务时间。但它并没有考虑到无线信道的时变特点,也没有利用无线信道条件,因而会造成较大的系统资源浪费,不能达到较高的系统容量。另外该算法只考虑用户间的公平性,没有优先级计算公式,也不需要对用户进行排序,所以实现比较简单。该算法调度规则如下:

(1)每个用户对应一个传输队列,用来存放需要传送的数据;

(2)在每个调度时隙内,非空队列采用轮询的方式依次接受服务;

(3)在一个队列再次接收数据传输服务之前,其他所有的非空队列都必须已经接受过一次服务;

(4)只有系统存在且只存在一个非空队列时,才有可能连续接受服务;

(5)该调度算法允许一次传送多个数据包。

轮询算法不仅能够保证用户之间长时间的公平性,也能保证用户间短时间的公平性,且算法实现较为简单。但轮询算法并没有考虑到不同用户无线信道的具体情况,因此系统吞吐量也往往是很低的。通常轮询算法被认为是最公平的,同时算法性能也是最差的,也就是说,轮询算法可以作为分组调度算法公平性的上界和系统容量的下界。

3.2 最大载干比(Max C/I)算法

最大载干比(Max C/I)算法只考虑吞吐量,完全不考虑用户之间的公平性。该算法的基本思想是:在每个调度周期内,对所有用户依据其接收信号的载干比(C/I)进行排序,按照载干比从大到小的顺序依次选择用户进行调度。也就是每一个调度时隙内,系统总是选择信道条件最好的用户进行服务。

最大载干比算法的目标是获得最大限度的系统吞吐量和最高的频谱利用率,而并不考虑用户的公平性。因此在实际的通信系统中,可能会出现距离基站近(信道条件较好)的用户一直接受服务,处在小区边缘(信道条件较差)的用户会由于C/I较低而一直得不到服务的情况,因而就无法保证用户的QoS要求。在算法复杂度上,最大载干比算法由于要对用户的载干比进行排序,所以与轮询调度算法相比要复杂,但它只考虑载干比这一个参数,所以实现起来还是比较简单的。其公式为:

最大载干比算法可以最大限度的提高系统吞吐量,而且实现起来还是比较简单的。但是,在无线移动环境中,信道的时变特性会导致信道条件较差的用户长期得不到服务,而一些信道条件好的用户会一直得到数据传输,因而该算法无法保证用户之间的公平性,更不能满足不同业务的QoS要求。

3.3 正比公平(Proportional Fair,PF)算法

在实际的通信系统中,调度算法不能单一的选择小区的吞吐量或者是用户的公平性作为调度原则,而是应该在这两者之间做一个折中,正比公平算法就是通过吞吐量和公平性进行折中而产生的。其目的是在保证小区吞吐量的同时,兼顾到不同用户之间的公平性。传统的正比公平算法优先级计算公式为:

其中(C//)k(t)表示第k个用户在t时刻的载干比,λk(t)表示用户k在时隙t内的平均数据传输速率。正比公平算法按照用户优先级从高到低的顺序依次选择用户进行服务的。在一个多用户的小区中,当信道条件好的用户被连续服务时,其平均数据传输速率就会增大,从而降低其优先级:同时,信道条件不好的用户由于长期得不到服务,导致其平均传输速率变小,从而提高了其优先级。因而正比公平算法实现了最大化系统吞吐量和保证用户公平性之间的折中。然而,与轮询调度算法和最大载干比算法相比,正比公平算法不仅需要考虑每个用户的载干比,还需要计算每个用户在一段时隙内的平均数据传输速率,因而实现较复杂。

4 现代资源分配技术

从以上的分析可以看出,在无线通信系统中,只有正比公平(PF)算法能够提供一定的QoS保证,但在多业务环境中,PF算法并不能提供多业务的QoS保证。为了满足多业务环境中不同业务的QoS要求,产生了现代资源分配技术,其中以自适应比例公平(Adaptive Proportional Fair,APF)和修正的最大权重时延优先(Modified Largest Weighted Delay First,M-LWDF)算法最具代表性。

4.1 自适应公平(APF)算法

自适应公平(Adaptive Proportional Fair,APF)算法采用瞬时数据传输速率的指数形式代替PF算法中的载干比,并在此基础上进行改进。主要分为尽力而为(Best-effort)和带QoS要求这两种模式。

尽力而为(Best-effort)模式优先级计算公式为:

其中ri表示用户i在该调度时隙内,可以达到的数据传输速率,Ri表示用户i在一段时隙t内的平均传输速率,而c则是控制参数。在该算法中要对两部分参数进行更新,一部分是短时更新,也就是每个资源分配周期内都要对Ri进行更新,另外一部分是长时更新,也就是可以每隔一段时间更新一次控制参数ci。

带服务质量(QoS)要求模式的优先级计算公式为:

与尽力而为模式相比,带QoS要求模式下的APF算法增加了用户要求的传输速率RT1,从而实现对不同用户不同传输速率的控制。同样带QoS要求模式的APF算法也需要短时更新Ri和长时更新ci。

APF算法提高了系统吞吐量、同时在一定程度上保证了不同用户对数据传输速率的不同要求,但是由于APF算法要更新2个参数,计算量比较庞大,因而该算法实现起来非常复杂。

4.2 修正的最大权重时延优先(M-LWDF)算法

修正的最大权重时延优先(Modified Largest Weighted Delay First,M-LWDF)算法是针对高速率业务流而提出的,该算法的主要思想是将分组数据包的时延和如何有效利用信道信息平衡考虑,其用户优先级的计算不仅和用户当前的信道质量有关,还和包的队列时延有关。其优先级计算公式为:

其中,P(Di>Ti)≤δi,Di表示用户i的HOL分组延时,Ti表示该用户允许的最大分组延迟,δi表示该用户允许的丢包率。优先级计算公式中的与PF算法相同。

由其优先级计算公式可知,在PF算法的基础上,用户i的时间延迟越大,该用户的优先级也就越高。同时优先级还受限于该用户所要求的时间延迟,时间延迟要求越低,在同样情况下,用户的优先级就会越低;相反,如果用户对分组延迟要求较为严格,用户的优先级就会越高。

由于M-LWDF考虑到了不同用户对时间延时的不同要求,因而能够更好的满足用户的QoS要求。然而M-LWDF算法会降低小区吞吐量,并且由于该算法并没有考虑到用户当前的QoS水平,所以会导致用户出现较高的分组丢失率,也即是会严重降低业务的QoS性能。

5 LTE系统多用户动态资源分配技术的改进

考虑到LTE业务特征及系统自身特点,为了实现资源分配技术在保证系统吞吐量和业务QoS要求的前提下,改善用户的分组丢失率等QoS性能,本文对现有的多用户动态资源分配技术进行改进,提出一种新的资源分配技术。

其主要实现流程包括:首先根据信道模型估算出LTE系统中所有用户的瞬时信道质量反馈信息CQI,并计算出用户在一段时间内平均CQI。然后,根据用户CQI的瞬时值和平均值以及业务的QoS要求和当前该业务的QoS水平,计算得出每个用户在当前资源分配周期内的优先级,按照优先级从高到底的顺序对用户依次分配资源。其优先级计算公式为:

其中:为用户i在当前时隙的信道质量CQI;MeanCQIi(t)表示用户i五个时隙内的平均CQI;QCIj为第j类业务的QoS等级标识,是LTE系统新增的重要的QoS参数之一,LTE系统中定义的标准QCI一共分9个等级;reqRbi(t)表示用户i当前调度时刻可以实现的数据传输速率;avRbi(t)是用户i在最近特定长度的资源分配周期内平均数据传输速率;delayi,j(t)是用户i的j类业务的传输延时;reqdelayj表示第j类业务要求的分组延时。

6 结束语

本文在对经典资源分配技术和现代资源分配技术分析的基础上,根据LTE业务特性及资源分配系统自身特点,提出了一种基于信道质量、业务QCI等级、传输速率及时延要求的新型资源分配技术。与以往的资源分配算法相比,本算法选择瞬时信道质量和平均信道质量作为一个参考标准,有效地降低由于信道急剧变坏导致的分组丢失率,改善业务的QoS水平。本优先级计算函数还考虑到了用户当前资源分配周期内可以实现的数据传输速率,以及用户在一段时间内的平均传输速率、能够在保证用户公平性的同时,最大限度的实现较高速率传输。本算法同时利用业务当前的分组延时及该类业务要求分组延时等参数来控制不同业务对时延的要求。同时,QCI等级参数为多用户多业务模式下,LTE动态资源分配提供了更为具体的QoS的约束,能在保证用户公平性及系统吞吐量的基础上,最大限度满足用户对LTE业务的服务质量的要求。

摘要：文章简要介绍了3GPP长期演进(Long Term Evolution,LTE)系统主要业务特性及资源分配系统,分析评估了经典资源分配技术及现代资源分配技术。由于LTE系统中多用户多业务具备不同的服务质量(QoS)要求,因此本文提出一种新的资源分配技术,该技术在考虑用户公平性和系统吞吐量的同时,能够最大限度的满足用户的QoS要求。

关键词：LTE业务特性,动态资源分配,调度算法

参考文献

[1]胡宏林,徐景.3GPP LTE无线链路关键技术[M].北京:电子工业出版社.2008

[2]张新程,田韬,周晓津等.LTE空中接口技术与性能[M].北京:人民邮电出版社,2009

[3] 3GPP.TR25.913 V 8.7.0.Requirements for evolved Universal Terrestrial Radio Access(UTRA) and Universal Terrestrial Radio Access Network(UTRAN),2009

[4] 3GPP.QoS Concept and Architecture(Release 5).TS 23.107 V 5.13.0.2004

[5] H.Chao,Z.C.Liang,Y.G.Wang,L.N.Gui.A dynamic resource allocation method for HSDPA in WCDMA system. 3G Mobile Communication Technologies,2004,Page(s): 569-573

[6] Matthias Malkowski,Andreas Kemper,Xiaohua Wang. Performance of Scheduling Algorithms for HSDPA. Communications and Networking in China,2007,22-24 Aug.2007 Page(s):1052-1056

[7] M.Boaretto,D.Angelini,M.Zorzi.Fast Scheduling Policies using WCDMA High Speed Downlink Packet Access. Vehicular Technology Conference,6-9 Oct.2003,VTC 2003-Fall.2003 IEEE 56th Volume 4:2650-2654

[8] Ghassane Aniba,Sonia Aissa.Adaptive Proportional Fairness for Packet Scheduling in HSDPA.IEEE Communications Society GlobeCOM 2004 IEEE,29 Nov.- 3 Dec.2004,Volume 6:4033-4037

【用户分配网络】推荐阅读：

用户分配网06-26

网络资源分配05-10

用户偏好05-10

用户数据05-28

基于用户06-01

用户基础06-15

>> 查看更多相关文档