SBS: 基于固态盘内部并行性的R-树高效查询算法

由于闪存固态盘逐渐取代机械硬盘成为主流存储,与此同时,随着闪存固态盘技术的进步,越来越多的存储芯片和硬件资源被植入,使得它拥有丰富的内部并行性,而传统的外存算法和数据结构优化工作往往没有考虑固态盘的内部并行性. 范围查询作为R-树索引的基础操作,它的性能对于地理信息系统非常重要. 但是由于R-树索引父子结点之间加载的依赖问题,使得它很难能够有效地去利用固态盘内部并行性去加速. 因此,为了克服该困难,提出一种基于栈结构的范围查询算法SBS(stack batch search). 它能在有效地利用固态盘内部并行性的同时,最多只需要O(B log N)内存空间. 最后,通过真实数据实验来验证SBS算法的性能. 实验结果表明,SBS在可接受的内存消耗情况下,在2款不同的固态盘上,范围查询的性能加速比可达3.4和4.5.     

移动无线传感网恶意数据包传播随机模型

该文基于随机元胞自动机理论研究移动无线传感器网络中恶意数据包的传播行为.依据移动无线传感器网络的信息扩散机制,设计节点移动模型、无线信道分配算法、信号干扰模型和恶意数据包传播模型,定义移动传感器网络环境下的元胞空间、元胞邻域、元胞状态以及状态转换规则,提出移动无线传感器网络中恶意数据包传播的随机元胞自动机模型,研究在不确定环境下恶意数据包传播的时空特征.研究结果表明该模型能够有效预测恶意数据包传播的趋势和空间分布状态,有效克服基于马尔科夫随机场理论、常微分方程或差分方程建立的恶意数据包传播模型而无法描述恶意数据包传播的空间分布状态的不足.