论文研究-一种基于分层云对等网络的多属性云资源区间查找算法.pdf

所需积分/C币:9 2019-07-22 18:45:57 1.45MB .PDF
0
收藏 收藏
举报

为了研究多维属性云资源在云对等网络中快速定位问题,结合云对等网络的优势,提出一种基于云对等网络的多属性云资源的查找算法。在分层云对等网络的基础上,分别利用云资源的类型和属性值建立多维索引。首先根据类型索引将相关的数据聚集在同一个资源簇内;然后将属性值的值域划分为多个区段,并将相应资源存储其中。同时建立资源簇融合、区间邻居维护等机制使算法更具效率和扩展性。仿真实验表明,该算法实现了多属性云资源的快速定位,它不会随着网络节点和类型维度增加而产生较大查询迟延,具有很好的扩展性。
1824 计算机应用研究 第33卷 层有多份相同的索引并不会增加系统的存储负担,反而给系统 B 提供更好的容错性。正因为资源维度都较低,所以容易形成如 0l01 1010 图2(a)所小的情形:节点的索引很多,但索引中包含的资源类 型都较少,这既占用存储空间,又表示系统中有太多的小型资源 簇。如果将资源簇m、mr都融合到資源簇bc中(图2(b)),则 能减少索引所占空间和资源簇数量,也能提髙簇的热度和降低 簇间杳找概率,提高杳找效率(详见后面的效能分析)。 0000 图3二维资源空间 ab IP Nodea IP(Nodc) 然后将笛卡尔坐标值转换为相应的HSFC码,组成一个 IP(Noded IP(Nodea)Hilbert,以实现多维键值向单维键值的转换。具体的转换规 则可参考文献[15],依据N维 Hilbert单元和基因,可以有效实 (a)类型a的索引表(融合前 (b)类型a的索引表(融合后) 现笛卡尔坐标和SFC码的相互转换。如图3所示, 图2融合前后类型a的索引表 (0000)b=(000)src,(1100)D=(1111)1s。面内的粗曲 b)当资源簇的代理节点发生变化时,会引发相应节点更线即是将一维笛卡尔坐标转换为HsC值所形成的一维Hil 新索引。由于可以并发更新索引,所以更新的时间复杂度约为hert线,实现了降维的目的。再将 Hilbert曲线首尾相接,覆 0(logm),其中m是索引层的节点数。而民山于本文是基于盖在Chrd环上,组成一个 Hilbert -Chord环。节点的加入和离 云对等网络,索引层节点稳定性好,索引更新对整个系统的影开还是依照 Chord的规则,而资源的检索则结合了HSFC码和 响可以忽略不计。在 CHord系统运行的初期,由于可能存在 Chord的相关规则 许多类型维度较低的资源簇,在资源簇的融合过程中会引起2.5区间邻居节点 CHord系统的波动,但也不会太大地增加查询廷迟。资源簇 如2.4节中所说,一个n维的资源簇空间会被划分成d 的类型维度增长到一定程度就会趋于稳定,这时整个系统的资个多维区间。除了在空间边界上的多维区间,其他的多维区间 源簇融合也就很少发生」 在任意维度上都有两个相邻的区间,这些区间便是邻居区间。 )一节点查询负荷太重或者节点发生故障如果没有存储邻居区间资源的节点被称为区间邻居节点。每个资源节 其他备份节点,就会导致查询失败,甚至是索引与资源信息丢点都会存储其区间邻居节点的索引信息,空间复杂度约为O 失。因此,为了保证整个系统的稳定,为所有节点增加一定数(k),k为类型维度。根据局部性原理区间邻居节点所存储的 量的备份节点时,并采用镜像技术,在原节点负荷过重或故障资源往往与原节点是相关的。对丁查询末命中或某些复杂查 时提供相应服务。 找,这些索引信息能为査询操作提供更多的选择。如图3所 2.4HsFC编码 示,阴影多维区间(1101)的邻居区间有(100)b、(1001)D 通过建立资源类型索引可以方便定位资源簇,然后再建立和(1110)。于在空间边界十,在A1维度上少了一个邻居 资源属性值索引,便可定位资源节点。由于资源属性值可能是区间 整数、小数或者是字符类的,如果以云资源属性值向量直接哈2.6匹配权重 希冇储,会增加检索的复杂性,同时也会破坏原有数据的一些 当冇多个资源簇满足查询时,来自不同资源簇的查询结果 相关性,降低检索效率。所以本文先将毎个类型的属性值分的匹配权重可能不同。那些满足查洵且类型维度史低的资源 段,在逻辑上形成一个多维资源空间;然后利用空间填充曲线簇具有更高的匹配杈重。类似地,资源簇内的资源节点提供的 将多维资源降维,使之映射到单维资源环上。由于在空间曲线资源也比其Ⅸ间邻居节点所提供的更准确,匹配权重也就更 族中 Hilbert曲线具有最好数据聚集特性,所以本文采用了高。具体的公式如下 Filbert空间填充曲线( Hilbert space-filling curve,ISFC)编码, 假设某资源簇的类型维度为C,杳询语句的类型维度为 将多维资源空间映射为单维 Hilbert坏,既降低了数据维度,×Cn,则类型的匹配权重为W1=C,/C。假设资源簇内的某资源 能较好地保持原有资源的相对位置。为了方便,本文采用原始节点的邻居跳数为X(当资源来自节点木身,为0;来自直接 的 Hilbert曲线填充的方式进行编码 邻居,X为1,以此类推),则属性值的匹配权重为W2=1/(1+ 首先,将每个特定的属性值向量转换为相应立的资源空间笛x)。最终的匹配权重为W=aW1+BW2。其中c为类型匹配 卡尔坐标。每个资源簇就是一个资源空间,资源簇内每一类型因子B为属性值匹配因子,可由人工配置 就是资源空间的一个维度,n维类型就形成一个n维笛卡尔坐 当W越大,匹配程度越高。而当资源簇的类型维度与査 标系。每个类型的属性值以其值域被划分为d个区间,这样便询的类型维度相差越大,或者查询结果来源于原资源节点的邻 形成了d个多维区间。每个多维区间的属性值向量都可以用居节点,则W越小,匹配程度也就越低。 这个多维区间的笛卡尔坐标值D(x1,x2,…,xn)来表示。由于 类型个数和区间划分情况都可能是变动的,所以每个资游簇保3资源查找 存一张区间划分表。依据区间划分表,属性值向量能转换为相 本文采用 H Chord模型,主要是为了利用这种双层结构对 应的笛卡尔坐标。如图3所示,资源簇包含A和B两个类型,每资源索引信息进行分层存储。粗略的资源类型信息由索引层节 个类型划为四个区间,其中属于阴影部分的属性值向量都可以点提供,而具休的资源属性值信息由资源层的节点负责。可认 D(11,01)表示(或写为(1101)),其中坐标值用二进制表示 为该模型是采用全局索引和局部索引的双层索引机制,首先在 第6期 胡凯,等:一种基于分层云对等网络的多属性云资源区间查找算法 1825 索引层建立全局索引,然后在实际资源所在的资源层上建立局情况下,这样能够快速地进行容灾处理,不会因资源簇索引信 部索引,通过双层的索引机制快速实现资源存储和查询定位。 息丢失而对查询带来干扰,保证系统的稳定性和可靠性。同时 3.1查找算法 为系统中的节点增加历史节点缓冲区,保存过去一段时问内所 资源的杳找步骤如下 访问过的节点信息,这在一定程度上提高系统查询效率。 )节点N收到查询请求QA(QA包含类型和属性值信4模拟与仿真 息).如果N不是资源簇代理节点D,则将QA的类型信息发送 给D。节点D解析QA:首先与木节点提供的资源类型作比较 本文仿真实验的机器配置Dual-Coe2 GHz CPU,4GB内 如果匹配执行资源簇内查找否则采用资源簇定位算法,然后存Imx系统。采用JDK版本16,Pesm版本1.0.5,编写 将QA发送给满足该类型的资源簇代理节点(可能不止一个 Jaa模坎程序实现仿真。实验参数设计如下:设n为网络节点 当有多个时,查找是并行的),以执行资源簇内查找。而当资数,m为资源簇个数,为簇间查找概率,是类型维度(属性个 源簇定位算汏也找不到代理节点时,向用户返回査找失败。 数),d是每个类型的属性值划分个数。在进行实验时将所有节 b)资源簇内查找。首先依据QA的类型及属性值信息查点均分为m个资源簇,每次仿真的循环次数为50次,设定实验 询区间划分表,确定查询资源的笛卡尔坐标,并转换为HSFC中网络的最大延迟为10ms、最小延迟为2ms,资源的数量为 编码;然后依据Chor规则定位到提供资源的节点;最后将资2000个,每次实验结果数据是统计多次仿真结果的平均值。 源及节点的P发送给用户,用户可以直接与该节点通信。 实验1验证 HChoru模型对资源查洵延迟的影响。本文 c)如果资源节点提供的资源不足或无此资源,资源节点将对 IChor、分层rche原始(ho模型进行仿真实验。 间邻居节点返回给用户。如果区间邻居节点也没有资源,那设定相同的p=0.2,m=10,选取维度为3的多维查找为例: 么可再提供邻居的区间邻居节点,否则向用户返回查找失败。 d=3,h=3,网络节点数分别为1000、1500、2000、2500 d)用户集合资源节点提供的资源信息。当资源来自多个3003500。所得实验结果数据如图4所示。 资源簇时,按匹配权重排序并提供给用户。 实验结果分析:图4数据显示,当网络节点数相同时 虽然保持区问邻居节点信息会增加节点的存储开销,但该 CHord与 HTC-Chord. Chord模型相比,产生的查询延迟最小 系统建立在云服务器上,存储容量已不再是主要限制囚素,却随着网络节点数增加, HTC-Chord、 Chord模型产生的查询延迟 能带来简化査询、提高査找效率等便利。考虑到存在节点加明显地随着节点数的增多而增大,而 ICHord模型产生的查询 入、退出等情况,资源首次登记时,节点的区间邻居信息只存储延迟波动较小,趋于平稳。所以分层H(hord模型在进行资源 HSFC码,而在第次查找和固定维护期间,节点才会维护自查询时,不会随着网终节点数的增加而产生较大的查询延迟, 己的邻居,存储每个HSFC码对应的节点P;而当节点需要将适合大规模云计算网络中资源的快速杳询。 数据转移时,会主动通知邻居节点更新邻居节点IP。 实验2验证资源类型维度对资源查询延迟的影响。对 3.2效能分析 CHord和原始(hord模型进行仿真实验,设定=0.2,m=10 n=2000,d=3;改变k。所得实验结果数据如图5所示。 该算法是将资源信息进行分层冇储.分别建立资源类型和 HTC- Cher -HHCherdl▲ Chord ●HCh 属性值的索引。查询发起时,首先在索引层査找资源簇,然后 在较小网络范围的资源簇内进行资源查找。定义网络节点数 为n资源簇为m。索引层与资源层都是基于传统Clol网络。m 55 Chord在节点为n的刚络上的半均查找长度为l0=0(gn)。1s,数0m8x 将有n个节点的网络平均划分为m个簇,假设每个节点的查 类型维度 询穊率相同。由于簇内节点需要转发查询给资源簇代理节点 图4网络节点数与 图5类刑维度与 查询延迟的关系 查询延迟的关系 以奁洵分区表,所以簇内的平均杳找长度为 实验结果分析:图5数据显示,在 CHord模型中,多属性 Li =o(log)+1 资源与单属性的资源查询相比,多属性资源的查询产生略大的 当需要跨簇查找时,首先定位资源簇,然后执行簇内查找。查询延迟;但是随着属性个数的增加,产生的查询延迟波动较 虽然可能同时定位多个资源簇,但都是并行处珥这些查询,故小,趋于平稳。而原始Chm算法的查询延迟会随着属性个数 平均查询长度大致相同,即 的增加而不断増大。因此,与原始(hor算法相比,本文算法支 L,=1 +o(log m)+O(log 持多维属性云资源的查找是可行高效的,并且本文算法以凶段 划分属性值,能支持范围查找等复杂查询,具有良好的扩展性。 假设簇间査找概峯为p,那么整个系统的平均查找长度为 5结束语 L=pL +(1-p)l=p(l+o( log m)+O(log))+ 本文利用分层网络的思想将云资源的类型和属性值分别 (1-p)(O(log"-)+1)=p0(gm)+O(log")+1 存储和索引。资源簇的合并能够有效地将相关資源聚集在 由上式可知,随着p减小,会提高本文算法的查询效率。起,当资源簇的类型达到一定规模时,其类型维度的交化将会很 当某一类资源过热或者代理节点失效吋,势必影响整个资少,有很好的收敛性。在资源层利用 Hilbert幽线将多维属性降 源簇资源的存储和査询故为勾个资源簇代理节点都设置多个为单维 Hilbert环,同时增加对区间邻居的索引存储,既提高了 备份节点。当资源簇代理节点的路由和区间划分表等信息更云资源定位的查找效率,也减少了冗余查找降低网络开销。 新时,同时备份节点也作出相应更新。在代理节点意外失效的模拟实验证明了该算法具有很好的扩展性,(下转第1838页) 1838 计算机应用研究 第33卷 的性能。 [5 Pan Mengshiuan, Yeh Lunwu, Chen Yenann, et al. A WSN-based intelligent light control system considering user activities and profiles 5结束语 [J].| EEE Sensors journa,2008,8(10):1710-172 智能灯光控是无线传感器执行器网络的重要应用领域,[61 Yeh lunyu, Lu Cheye, Kou Chiwan,ota. Autonomous light con- 针对系统模型变化而带来的控制问题,本文设计∫一种基于单 rol by wireless sensor and actuator networks[J. IEEE Sensors 神经元自适应PSD的分布式控制算法。当外界自然光照变化 Journal,2010,10(6):1029-1041. 或因控制目标点改变而造成系统模型变化时,该分布式控制算[7 Caicedo D, Pandharipande A, Leus G. Occupancy-based illumination 法可以根据系统误差,在线调整控訇器的参数,最终达到满意 control of LED lighting systems[ J]. Lighting Research and Tech 的控制效果。通过基于无线传感器执行器网络的智能灯光控 nology,2011,43(2):217234 制实验平台的模型进行了仿真实验研究,实验结果验证了控制「81 Van de Meugheuvel N, Pandharipande A, Caicedo d,atal.Dtmi 算法的有效性。与已有的PD分布式控制算法相比,本文提出 buted lighting control with daylight and occupancy adaptation J].Ene 的方法鲁棒性更强.更适合于实际应用,有很好的应用前景。 rgy and Buildings, 2014, 75: 321-329 9 Mo Lei, Xu Bugong, You Xiaoping, et al. Distributed lighting system 0987 PD分布式控制 based on wireless sensor and actuator networks[ J. Ad hoc& Sen sor Wireless Networks, 2014. 20(1-2): 21-40 [10 Liu Longqing, Xu bugong, Yang Jiawei. Distributed light control u- 321 sing wireless sensor and actuator networks[ C]//Proc of the 11th World Congress on Intelligent Control and Automation. [S1.]: IEEE 10152025303540455 Press.2014:340l-3406 图7两种方法目标函数比较 l1]刘龙庆.基于无线传感器/执行器网络的智能灯光控制系统的硏 参考文献: 究LD」.广州:华南理工大学,2014. [ 1] Iwayemi A, Yi Peizhong, Zhou Chi. Intelligent wireless lighting con- L 12 Akyildiz I F, Kasimoglu I IL. Wireless sensor and actor networks: re trol using wireless sensor and actuator networks: a survey[ J]. Elee search challenges[ J]. Ad hoc Networks, 2004, 2(4): 351-367 tronic Journal of Structural Engineering, 2010: 67-77 L13 Vukosavic SN, Stojic M R. On-line tuning of the rotor time constant [2 Kelso J. Buildings energy data book[R]. [S1.I: U.S. Department for veclor-controlled induction molor in position control applications f eue 2012 [JJ. IEEE Trans on Industrial Electronics, 1993, 40(1): 130- [3 Pandharipande A, Caicedo D. Daylight integrated illumination control 138 of LED systems based on enhanced presence sensing[ J. Energy and Buildings,2011,43(4):)44-9 [14]易继锴,侯谖彬.智能控制技术[M].北京:北京工业大学出版社, [4 Tran D, Tan Y K. Sensorless illumination control of a networked 2007:120-125 LED-lighting system using feedforward neural network[J.EEE[15]龚菲,王水骥.基于神经网络的PD参数自整定与实时控制[冂 Trans on Industrial Electronics, 2014, 61(4): 2113-2121 华中科技大学学报:自然科学版,2002,30(10):69-71 (上接第1825页)适应大规模云对等恻络。但在资源簇内计算[8』邵一川,中德泶,赵宏伟. Hilbert chord:一种网格资源管理的PP HSC码时会耗費一定量的节点计算资源,找到一种更效率更 框架[J.微计算机信息,2009,25(5-3):105-106,81 均衡的划分机制來交排资源存储将是未來的主要硏究方向。 [9 Yang Xiaoyu, Hu Yiming. A scalable index architecture for supporting 参考文献 multi-dimensional range queries in peer-to peer networks[C 1//Pro of International Conference on Collaborative Computing Networking [1 Stoica 1, Morris R, Karger D, et a/ Chord: a scalable peer-to-peer loo- Applications and Worksharing. 2006: 1-10 kup service for Internet applications Cl//Proc of ACM SICCOMM [ 1U] Shu Yanfeng, Ooi B C, Tan K L, et al. Supporting multi-dimensional Conference. 2001. 149-160 range queries in peer-to-peer systems[ C]//Proc of the 5th IEEE In [2〗肖永刚. Chord网络模型的硏究与改进[)].北京:北京邮电大学, 2010. ernational Conference on Peer-to-Peer Computing. 2005: 173-180 [3 Jagadish H V, Ooi bC. vI BATO\: a balanced tree structure fo LI]」傲英,周敏奇,线卫,等.大规模分布式系统中的多属性查询 peer-lo-peer networks[ C// Proe of the 31 st VLDB 2005: 661-67 处理[J.计算机学报,2008,31(9):1563-1572. 14」 Bharambe A R, Agrawal M, Seshan S. Mercur:s甲 porting scalabl12陈字中,陈世平,方芳,构建白组织的云资源共享对等网络[J multi-attribute range queries[J]. ACM Sigcomm Computer Co 型微型计算机系统,2014,35(5):1051-1054 mmunication Review, 2004, 34(4): 353-366 [13]陆丹.基亍PP云存储备份系统设计及日志恢复实现[D].关 「5李钊伟、陈世平.支持多查找的资源共亭设计「J].计算机应用 春:吉林大学,2013 研究,2013,30(7):2156-2159,2184 14 Moon B, Jagadish H V, Faloutsos C, et al. Analysis of the clustering 6]余星,胡德敏.棊于ⅣP网络的云资源多维查询算法[冂.计算杌 propert ies of the: Hilbert space-filling curve[J.IEEE Trans an 应用研究,2014,31(10):3061-3064 Knowledge and Data Engineering, 2001, 13(1): 124-141 [7]方启明,杨广文 E-SkipNet:一种文持多属性范國查询的DIT网[15]李晨阳,张扬,冯玉才N维 Hilbert编码的计算[J].计算辅助 络[J].小型微型计算机系统,2014,35(10):2308-2312 设计与图形学学报,2006,18(7):1032-1038

...展开详情
试读 5P 论文研究-一种基于分层云对等网络的多属性云资源区间查找算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_39841365 你的留言是对我莫大的支持
2019-07-22
上传资源赚积分or赚钱
    最新推荐
    论文研究-一种基于分层云对等网络的多属性云资源区间查找算法.pdf 9积分/C币 立即下载
    1/5
    论文研究-一种基于分层云对等网络的多属性云资源区间查找算法.pdf第1页

    试读结束, 可继续读1页

    9积分/C币 立即下载 >