论文研究-均衡满意度的并行单色连通分支频谱分配算法.pdf

所需积分/C币:5 2019-09-10 09:41:26 589KB .PDF

针对各类图论着色频谱分配算法的时间开销过大的问题,提出了一种并行单色连通分支处理拓扑图的方法。该方法结合连通分量理论和单色子图分解法,可应用于目前所有的图论着色模型的拓扑图分解中。并且根据认知用户的需求来调整分配使满意的用户比例增大,从而解决了分配结果存在的用户满意度不均衡情况。仿真结果表明,提出的算法是一种快速且能够使更多用户满足需求的有效方法。
郑艳,徐国军,覃锡忠,等:均衡满意度的并行单色连通分支频谱分配算法 2014,50(18)199 看出,≥1指用户需求得到满足,反之是指用户需求未 将n从K中删除且 得到满足。 由图G生成M个邻接 24可调整颜色的计算 矩阵,得到对应的简单 Sn21? 标号图 假设对满足需求的顶点n*和未满足需求的顶点n 将r从A和Q屮删除 作分配调整。本文算法定义的顶点n的可调整颜色集 利用连通分量求解算法计算 将r存入An并计算S将 合计算式如下: G的W个连通分支G,并将 Un=Ln∩An,∩CA (4) 所含顶点存入集合 其中n的可用颜色集合L由可用频谱矩阵L得到,A 取各Q第一个元素n除 指顶点m*分配到的颜色集合,CMAn指该网络的所有 由式(1)或(2)并行计算各 个连遥分支G的顶点 频谱集合Ms中未分配给顶点n的颜色集合。 标号 label Q为空 考虑到取消某颜色的分配后满足需求的顶点可能 会变成不满足需求的顶点,所以顶点n*和所有未满足 选择最大标号的n分配颜 需求的顶点都可以调整的颜色矩阵如下 色m,并将m存入集合An 把集合Vn,改为Vnm r从0开始自加1 {Pp,p,∈0,1} (5 其中,r和n3分别指取消分配后顶点n*的需求依然满 由上述分配结果用式(3) 矩阵P的每列得各可调 颜色的可调顶点集合 足的颜色集合R的元素和元素个数,n和n1分别指未 计算各个用户的用户满 Q(∈[1,n3l) 意度S,n=V 满足需求顶点集合K的元素和元素个数。若r∈U 由式(5)得到可调整的 则pn=1。所以pn=1指r是顶点n和n*都可以调 小于1的满意度从小到大将 颜色矩阵P 整的颜色 对应顶点存入集合K,大于 1的满意度从大到小将对 将所有R中元素按所 应顶点存入集合F并分别 对应的权值bn,从 3算法步骤 计数为n1,n2 小到大排序 本文分为两个阶段进行频谱分配:一是根据信道效 将n从 中堋除且 益情况对用户标号来完成初次频谱分配;二是考虑用户 需求,调整某些频谱的分配得到最终的分配结果。在文 mCM,将满足S 0或 2-0? 献[11-12]中具体给出了对拓扑图的分块方法,文中不再 nn N bndn>1的m存 入集合R,并计数 过多讲解,而用户潢意度均衡的调整分配算法在下面 的流程图介绍中将详细给出。 取F的第一个儿素n*,由 结束 式(4)计算K中所有元素 根据本文的算法思想,具体的流程如图1所示。 的可调整颜色集合Un 该算法对系统拓扑图进行处理后,最终分解成了W 图1算法流程图 个单色连通分量子图。为了表现出矩阵和集合的意义方 的各颜色下的未满足需求顶点集合Q,由于上面的排序 便人家理解,由频谱特点分解成的子图命名为GG依次存入集合的是对顶点n的需求影响小的颜色r下 下标表示该子图是此颜色下的所有顶点的千扰关系。再 的满意度最低的顶点n。由上面的命名方式能快而直 由连通分量分解法分解成的单色连通分支Gm(≤W)接地找到分配颜色r给n*的单色连通分支的顶点集合 下标的首位和第一位指该连通分支顶点是关于m色的v,并判断n是否也是该连通分支的顶点,如果是,就 干扰关系并是第w个连通分支。同理,顶点集合的名能取消给n分凰r面将r分给n。每次调整分配成功, 称也随着算法在改变,完成预分配后顶点存入的集合为和n本的满意度都会变化。如果顶点n满足了需求,就 vnn,是指将颜色m分配给了顶点n的单色连通分支从K中删除n,否则重新计算满足Sn一 b,* m/dn+>1的 的顶点集合 颜色集合R,继续n*和n的颜色调整。如果最大满意 完成第一阶段的预分配后要对各顶点的分配作词度顶点n*取消了所有能调整分配的颜色后仍不能使未 整。先将满意度最大的满足需求的顶点n*与所有未满满足需求顶点满足需求,就从F中删除n*,直到F集 足需求的顶点根据式(4)计算各自的可调整颜色集合合或者K集合中没有可调整分配的满足需求顶点或未 Un。再计算取消分配仍能使n*满足需求的颜色集合满足需求顶点为止。 R,为了不使满足需求顶点取消分配的颜色对它的需求 影响太大,本文将集合内的元素按对n*的效益权值从4仿真结果与分析 小到大排序。由式(5)得到n*和K屮元素都可以调整 下面对PASA算法和CBSA算法以及本文的PCU 2002014,50(18) Computer Engineering and Applications计算机工程与应用 表1仿真参数 参数名 参数取值 认知用户数 6或 可用频带数 M从1到30依次取值 空矩阵L 0,1二元随机矩阵 效益矩阵B 接照IEEE802.22的6个等级均匀分布(3025,45375,6050,9075,12100,13600)(单位 bit. pcriod) 干扰矩阵C 为随机生成的0,1二元对称稀疏矩阵 需求矩阵D按照IL802.22的业务源参数均匀分布(186,3800,3986,38000,38186,1800,41986)(单位 bit period-) 仿真次数 1000 循环执行时间 T=I ms 算法进行 MATLAB仿真。仿真参数如表1所示,本文的分配循环执行次数随频谱数目的增加近似呈线性增加: 用户效益权值和需求参考IEEE80222的设定,同时为PASA算法循环执行次数与待分配的频谱数H无关,循 了保证算法的准确性,仿真结果取多次随机的拓扑图G环执行次数几乎不变;CBSA算法循环执行次数略小于 仿真结果的均值。 PASA算法m;而PCU算法执行次便能完成分配无 41时间开销 需循环。所以这三种算法的曲线近似于反比例函数图, 不考虑用户满意度的均衡,通过原理可以得到这三但鉴于实际拓扑图的不同会出现一些突变点。 种算法频谱分配的时间取决丁分解成的各小块所需要4,2满意用户比例 的分配时间的最大值,所以在相同系统拓扑图下,由于 根据式(3)很容易便能计算出用户满意度人于等于 PCU算法进行着色的子图比PASA算法、CBSA算法的1的满足需求用户数占总用户数的比例。如图4是用户 还要简单,所以新算法的运算量少,相应的时间开销更数N取12时这三种算法的满意用广占总用广数的比例 少。本文的比较釆取文献[12]的方法,假设每次分配的随着频谱数H的增加,三种算法的满足需求用户比例都 循环执行时间为T,时间开销:=h×T,其中h是总的有提高。这是由于在分配周期内用户需求不变化的情 执行分配次数。如图2和图3是用户数N取6时PASA况下,随着频谱数目的增加,频谱复用的程度有所增加 算法、CBSA算法及PCU算法在协作准则和非协作准则用户获得的信道效益增多,满足需求的用户也随之增 下分别占CSGC算法的时间开销比例随频谱数目增加加。还可以看出PASA算法和CBSA算法的满意用户所 而变化的曲线。从图中可以看出,随着频谱数目M的增占比例完全相同,PCU算法满意用户比例最高并且随着 加,时间开销比例呈下降趋势。这是因为CSGC算法的频谱数山的增加所有用户最先达到全部满足需求的情 况。这与PASA算法利CBSA算法的频谱分配相同,PCU 0.9 0.8 CBSA 算法根据用户需求调整分配使更多用户满足需求有关。 0.7 PCU 再者,随机生成的拓扑图不同导致分配结果也有所不 50.6 同,所以当频谱资源少的时侯偶尔会出现满意用户,即 0.5 0.4 满意用户的比例没有从0开始。 1.0 …5“ 0. 510 30 07 频谱数M 图2协作式下频谱分配时间开销 三0 0).8 PASA - CBSA . CBSA 三0.7 - PCU * PCU 0.6 频谱数 0.4 图4满意用户所占比例 0.3 5结论 0.1 本文研究了认知无线电网络中各类基于图论着色 202530 频谱数M 模型的频谱分配算法,在详细分析了CSGC算法的各种 图3非协作式下的频谱分配时间开销 改进算法后,提出一种用户满意度均衡的并行单色连通 郑艳,徐国军,覃锡忠,等:均衡满意度的并行单色连通分支频谱分配算法 2014,50(18)201 分支频谱分配算法。该算法适用于所有基亍图论的算 infrastructure-based cognitive radio networks J.IEEE Trans 法处理系统拓扑图,其特点是:将复杂的系统拓扑图分 actions on Mobile Computing, 2011. 10(6): 853-867 解成较多的可以并行计算的无干扰单色连通分量子图,[7] Rahwan, Jahedpari F, abdallah. The dynamics of two 兀需循环更新拓扑图就能一次性完成分配,大大降低了 cognitive heuristics for coordination on networks[C]//2010 时间开销。考虑到实际应用,又采取了均衡用户满意度 IEEE Second International Conference on Social Com 的方法来调整频谱分配结果,使更多用户满足效益需 puting,2010:473-479 求。并且与并行算法和连通分支算法在时间开销和满 8 Zheny HaiLao, Peny Chunyi Collaboration and fairness opportunistic spectrum access[C]/IEEE 2005 International 意用广比例方面进行比较,仿真表明:新的改进CSGC Conference on Communications, Washington DC, 2005 算法分配时间与频谱数无关,提高了可扩展性和有效地 3132-3136 减少了时间开销,也更适于实际应用 9 Wang Wei, Liu Xin List-coloring based channel allocation eless networksICy/Proceedings 参考文献 IEEE the 62nd Vehicular Technology Conference, Wash [1] Stotas S, Nallanathan A On the throughput and spectrum ington do,2005:690-694 sensing enhancement of opportunistic spectrum access [10] Cao Lili, Zheng Haitao Distributed spectrum allocation cognitive radio networks[JIEL Transactions on Wire via local bargaining[c]/Second Annual IEEE Communi less Communications, 2012,11(1):97-10% cations Society Conference, 2005: 475-486 [2] Leshem a, Zehavi e, Yaffe y. Multichannel opportunistic[l]l廖楚林,陈劼,唐友善,等认知无线电中的并行频谱分配 carrier sensing for stable channel access control in cog 算法[电子信息学报,2007,29(7):1608-161 nitive radio systems[J].IEEE Journal on Selected Areas[12]覃玉荣,胡虹梅动态频谱分配的连通分支并行处理[电 in Communications, 2012.30(1):82-95 波科学学报,2012,27(1):152-156 [3] Janssen J, Kilakos K, Marcotte O Fixed preference chan- [131 Wang Jiao, Huang Yuqing, Jiang Hong.Improved algorithm nel assignment for cellular telephone systemsJ. IEEE Trans of spectrum allocation based on graph coloring model actions on Vehicular Technology, 1999, 48(2): 533-541 in cognitive radio[c]i2009 WrI International Conferences [4 Akyildiz I F, Lee Won-Yeol, Vuran M C, et al. A survey on Communications and Mobile Computing, Washington on spectrum management in cognitive radio networks[J DC,2009:353-35 IEEE Journal on Communications Magazine. 2008. 46(4): [14]Gozupek D, Eraslan B, Alagoz. FThroughput satisfac 40-48. tion based scheduling for cognitive radio networks[J] [5] MacKenzie A B, Reed J H, Athanas p, et al. Cognitive IEEE Trans on Vehicular Technology, 2012,61(9): 1-16 radio and networking research at Virginia tech[J]. Proceed- [15] Stolas S, Nallanathan A Enhancing the capacity of spec ings of the IEEE, 2009, 97(4): 660-688 trum sharing cognitive radio networks.IEEE Trans on [6] Nguyen M V, Lee Hwang Soo. Effective scheduling in Vehicular Technology, 2011, 60(8): 3768-3779 (上接177页) 4 Chan T F, Vese L AActive contours without edges[J I 置有一定限制,如何解决对不同图像的初始轮廓不敏感 IEEE Trans on Image Processing. 2001.10(2): 266-277 问题,还有待于进一步深入研究。 15 Li Chunming, Kao chiuyen, Gore J C, et al. Minimization of region-scalable fitting energy for image segmentation[J] 参考文献: IEEE Trans on Image Processing, 2008, 17(10): 1940-1949 Caselles y. catte f coll e et ala geometric model for [6] Zhang K, Song H, Zhang L. Active contours driven by active cotours[J]. Numerishe Mathematik, 1993, 66(1):1-31 local image fiLling energy[J]. Pallern Recognition, 2010 [2] Li Chunming, Xu Chenyang, Konwar K M, et al. Fast dis- 43(4):1199-1206 tance image segmentation(Cli Proc of the Int'1 Conf on [7 Caselles v, Kimmel R, Sapiro G Geodesic active contours!JI Control, Automation, Robotics and Vision. Singapore: [s.n. International Journal of Computer Vision, 1997, 22(1) 2006:1-7 61-79 13]何传江,李梦,詹毅用于图像分割的自适应距离保持水平8林亚忠,顾金库郝刚.一种新的自适应水平集算法小计算 集演化[软件学报,2008,19(12):3161-3169 机工程.2011,13(7):216-218

...展开详情
试读 5P 论文研究-均衡满意度的并行单色连通分支频谱分配算法.pdf
img
  • 至尊王者

    成功上传501个资源即可获取

关注 私信 TA的资源

上传资源赚积分,得勋章
    最新推荐
    论文研究-均衡满意度的并行单色连通分支频谱分配算法.pdf 5积分/C币 立即下载
    1/5
    论文研究-均衡满意度的并行单色连通分支频谱分配算法.pdf第1页
    论文研究-均衡满意度的并行单色连通分支频谱分配算法.pdf第2页

    试读已结束,剩余3页未读...

    5积分/C币 立即下载 >