自调整混合树RFID多标签防碰撞算法

在RFID系统中,阅读器读取标签的效率与解决标签发生碰撞的方法密切相关.目前采用多叉树查询是一种较好的多标签防碰撞方法.它能减少碰撞时隙,再通过额外的查询来减少空闲时隙.但额外的查询也增加了新的开销.本文提出了一个自调整混合树RFID多标签防碰撞算法,该算法根据最高两个碰撞位的特征,在不增加额外查询的条件下,自调整搜索树的叉数,从而避免了一些碰撞时隙和空闲时隙.通过对算法的性能分析和仿真结果可以看到,自调整混合树RFID多标签防碰撞算法具有较少的时间复杂度和通信复杂度,识别效率也明显高于其他多叉树算法.     

第k小元素范围查询算法

范围查询是进行数据分析的有效方法,预计算技术可以提高查询的速度,从而实现快速的用户响应.提出了一个新的范围查询问题:第k小元素范围查询,迄今未见有文献报导.在决策支持系统中,了解第k小元素比仅仅依靠最大值要关键得多.在线段树、扩展红黑树及预计算的基础上,给出了查询第k小元素的算法,其空间复杂度为0(nlogn),查询的时间复杂度为0(log3n).     

HFC网络MAC协议的三叉树冲突化解算法分析

对HFC网络中普遍采用的三叉树冲突化解算法进行分析，介绍树冲突化解算法的两种栈管理模式：FIFO(先进先出)模式和LIFO(后进先出)模式，并举例说明FIFO和LIFPO的冲突化解过程。     

标签防冲突算法的研究

与传统通信系统一样,RFID系统也存在信道争用问题——标签冲突问题,标签防冲突性能是决定RFID系统性能的关键参数之一。对解决标签冲突的常用方法Aloha和二进制树防冲突算法做了详细的研究,并给出了标签防冲突算法进一步研究的方向。     

递归建立HS-树计算最小碰集

在基于模型的诊断中，广泛地使用冲突集来计算最小碰集的算法诊断。现有的HS－树，HST－树，BHS－树等算法普遍存在实现的困难。文章提出用递归算法建立平衡的二叉HS－树（Recursive hitting set-树，简记为RHS－树）计算最小碰集的方法，在空间复杂性与时间复杂性上能够满足大多数诊断系统中的要求。     

基于随机分布的多比特Trie树IP数据包分类算法研究

在无冲突散列算法和多比特Trie树算法的基础上,提出了一种基于随机分布的IP分类算法,该算法的核心有3点:一是基于目的,源端口和协议域构造无冲突散列,由于该三域的组合数目非常少,避免了空间爆炸;二是将目的/源IP连成比特串后分为4块,每块16bit,并将其中一块映射到一随机空间,将随机数和其余3块进行异或,获得分类索引值,并用此值生成多比特Trie树,一般情况下减小了空间和时间复杂度;三是在Trie树终点存放最终分类规则的索引值,为了保证查找到的规则的正确性,对每一个索引值的源,目的IP地址均匹配一次.通过以上3点改进一般要降低算法的时间复杂度和空间复杂度,通过仿真,当对10 000条分类规则进行包分类时,该算法的包分类速度可以达到2Mpaekut/s,所消耗的最大内存为1MB.     

基于查询树的防碰撞算法性能分析与研究

多标签碰撞问题严重影响射频识别系统的性能.基于查询树的防碰撞算法作为一种确定性算法被广泛的应用于各类射频识别场景中.本文分析了主流查询树防碰撞算法的性能与不足,并基于查询树方法提出了一种时间有效的防碰撞算法.该算法基于传统查询树识别模型,实施了一种双查询前缀匹配方法,可以消除传统查询树方法中的空闲时隙.此外,提出的算法可以充分利用碰撞时隙来提高识别效率.理论分析和仿真结果表明该算法优于现有的查询树防碰撞算法.     

基于关系树的知识查询算法研究

在关系模型基础上,进一步深入研究,将关系模型转换成关系树。基于此关系树模型,作者提出一般直接知识的正向,逆向知识查询算法,对不能直接查询的知识,进一步提出隐含知识查询算法。论文提出的查询算法有效地解决了基于知识库知识查询的相关问题。     

改进的二进制搜索防冲突算法

射频识别(Radio Frequency Identification,RFID)系统中的多标签冲突问题是不可避免的,防冲突算法是RFID系统中实现标签快速识别的关键.在一些相关的二进制搜索防冲突算法的基础上,提出了一种改进的二进制搜索防冲突算法.该算法利用冲突位构建四叉搜索树,使读写器的搜索次数和发送的信息量大大减少,提高了标签识别效率.实验结果表明该算法明显优于已有的二进制搜索防冲突算法.     

资源定位服务的分布式生成树模型及算法研究

针对云计算中资源定位索引的瓶颈问题,基于分布式生成树DST提出了一种自适应的资源定位服务DST-RLS模犁以及搜索半径限制的资源定位算法SRL.通过给出代表元选取规则,使代表元均衡分布在DST-RLS模型中,提高了资源定位服务的负载均衡性.SRL算法支持复杂查询和灵活的搜索策略,算法的时间复杂度为常数阶.数学分析和仿真...     

Novel RFID anti-collision algorithm based on the Monte–Carlo query tree search

Tag collision is a pressing issue in radio frequency identification systems which significantly lowers the system performance if not mitigated carefully. This paper presents the Monte–Carlo Query Tree Search (MCQTS) method as a novel and fast anti-collision algorithm. This method combines the capabilities of the conventional Monte–Carlo Tree Search and Query Tree by applying a few heuristics on the tree traversal to raise the chance of facing the most promising states. The collision mitigation based on the MCQTS is presented and its performance in terms of time, and space (memory) complexity is analytically verified. Simulations are performed, and the effects of tree size, number of tags, and tag ID length on the performance of the proposed method are investigated. The results are compared to the previously presented tree-based algorithms, and it is shown that for typical tag lengths, the MCQTS method performs between 3.89% and 62.06% (in average) faster than the conventional methods for multi-tag identification.

     

一种基于碰撞位指示的射频识别标签防碰撞算法

多标签碰撞是射频识别(RFID)技术在推广应用中必须克服的一个问题。针对目前RFID标签防碰撞算法存在识别效率低的不足,该文提出一种基于碰撞位指示的RFID标签防碰撞的碰撞位指示算法(CBIA)。通过跟踪待识别标签的碰撞位,采用碰撞位编解码技术,对待识别标签进行重复分组,直到所有标签都被正确识别。算法通过确定性分组,避免了空闲时隙的产生。仿真结果表明,采用CBIA算法的多标签识别系统,吞吐率可以达到每时隙0.7个标签,CBIA算法识别效率优于优化查询跟踪树算法(OQTT)和碰撞跟踪树算法(CTTA)算法。     

Tree pruning for MIMO sphere detection based on MMSE detection

Tree pruning is an effective algorithm to reduce the complexity of sphere detection(SD) for multiple-input multiple-output(MIMO) communication systems.How to determine the tree pruning rule,as well as by what the tradeoff between the performance and the complexity can be achieved,is still an open problem.In this paper,a tree pruning algorithm is proposed based on minimum mean square error(MMSE) detection.The proposed algorithm first preforms MMSE detection since the complexity of MMSE detection is very low.Then the pruning constraints will be set according to the scaled path metrics of the MMSE solution.The choice of the scale factors and their influences on the complexity and performance are also discussed.Through analysis and simulations,it is shown that the complexity is reduced significantly with negligible performance degradation and additional computations.     

C4.5决策树改进算法研究

决策树是数据挖掘分类算法中非常重要的一个算法分支。文章介绍了决策树算法中应用最广泛的典型算法-ID3和C4.5算法,并基于四个通用的数据集,针对这两个算法进行定量分析对比,研究两个算法的性能优劣。文章对C4.5算法中的连续属性离散化方法提出一些优化改进,并通过实际数据实验证实了优化的可行性。     

一种基于NNIA多目标优化的代价敏感决策树构建方法

本文提出了一种基于非支配邻域免疫算法(NNIA,Nondominated Neighbor Immune Algorithm)多目标优化的代价敏感决策树构建方法.将平均误分类代价和平均测试代价作为两个优化目标,然后利用NNIA对决策树进行优化,最终获取了一组Pareto最优的决策树.对多个测试集的测试结果表明,与C4....     

数字电视传输网络中的LDPC码译码算法研究

对目前应用在数字电视传输网络中的LDPC码译码算法进行归纳与总结,分别应用对数似然比测度和积译码算法及其简化算法在高斯信道上仿真,通过误码性能和译码复杂度两方面的比较表明对数似然比测度和积译码算法性能更优越,但最小和算法的复杂度相对来说有大幅下降.     

动态贝叶斯网精确推理中联合树算法的改进

基于动态贝叶斯网络处理动态不确定性问题的过程中推理是非常重要的，而椎理算法的优劣决定推理的执行效率。在分析联合树性质的基础上提出一种较简单的1 1/2片联合树算法，该算法不需要限制消去顺序且只做一次扩展。讨论了算法的复杂度、并做了试验比较。     

数据挖掘在通信行业精确营销中的应用

针对传统通信行业数据业务营销模式中存在的普遍撒网的缺点,提出利用数据挖掘中的决策树算法对数据业务的潜在客户进行分类,预测什么类型的人可能开通数据业务、什么类型的人开通数据业务的可能性低,并且在实际的环境中进行追踪检验。实际的实验以数据业务中的彩铃业务为例,结果表明,数据挖掘中的决策树算法能将预测准确率保持在较高的自然准确率,反映出其在真实的环境中运行是可行的、有效的,提高了通信行业数据业务精确营销的客户响应率,在实际的营销环境中具有积极的意义。     

加权的基于多播节点的多播路由算法

在许多多播应用中,降低多播树网络费用非常重要.本文提出了加权的基于多播节点的多播路由算法（WDDMC算法）.由于改变了DDMC（Destination-Driven routing for low-cost Multicast ）算法中的指示函数,适当降低了多播节点作为中间节点的优先级,提高非多播节点作为中间节点的优先级,从而使得多播树更接近最小Steiner树.在随机网络上的仿真结果表明,WDDMC算法的多播树网络费用优于DDMC算法.该算法的复杂度与DDMC算法完全相同.     

WDM网络中确定波长变换器位置与数目的启发式算法

该文首次研究了波分复用(Wavelength Division Multiplex,WDM)网络中如何在最佳节点中确定波长变换器数目的算法,设计了3种启发式算法,通过在NSFNET(the U.S.NationalScience Foundation backbone NETwork,美国科学基金会骨干网络),ARPANBT(the AdvancedResearch Projects Agency NETwork,美国高级研究规划局网络),CERNET(China Educationand Research NETwork,中国教育科研网络)上的仿真,比较了3种算法的性能差异,得出算法1的性能最优,且复杂度最低。另外,通过比较在部分节点以及全部节点中运用算法1确定波长变换器的数目,得出:在WDM网络中,在部分节点中装配有限的波长变换器也可以达到全部节点中装备波长变换器的性能,并且还可以降低光交叉连接设备(Optical Cross-Connects,OXC)的成本,减少复杂的控制。