【摘 要】
：
针对Multi-Radio Multi-Channel传感器网络中链路服务质量和信道冲突等问题，提出并证明了基于缓存和信道切换的数据查询问题是一个NP完全问题。根据数据流守恒和链路-信道等约束条件，建立线性规划方程，得到该问题的最优解模型，并提出了一个多项式时间的近似算法——贪心新覆盖数据算法。该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延，再贪心选择其具有最小路径
【机 构】
：
School of Computer Science and Technology, Heilongjiang University, Harbin 150080
论文部分内容阅读
针对Multi-Radio Multi-Channel传感器网络中链路服务质量和信道冲突等问题，提出并证明了基于缓存和信道切换的数据查询问题是一个NP完全问题。根据数据流守恒和链路-信道等约束条件，建立线性规划方程，得到该问题的最优解模型，并提出了一个多项式时间的近似算法——贪心新覆盖数据算法。该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延，再贪心选择其具有最小路径时延的缓存节点，收集其新覆盖数据。理论分析和实验结果表明，提出的方案能有效地减少数据收集时延，提高数据查询效率。
其他文献
子序列的相似性查询是时间序列数据集中的一种重要操作，包括范围查询和k近邻查询。现有的大多算法是基于欧几里德距离或者DTW距离的，缺点在于查询效率低下。文中提出了一种新的基于LSH的距离度量方法，可以在保证查询结果质量的前提下，极大提高相似性查询的效率；在此基础上，给出一种DS-Index索引结构，利用距离下界进行剪枝，进而还提出了两种优化的OLSH-Range和OLSH-kNN算法。实验是在真实的
当前，在OLTP数据库的应用场景中，事务通常由一些简单的查询构成，尤其是大量存在的基于主键的读写事务。在这种应用场景下，逻辑锁能够避免复杂的逻辑判定，通过基于简单比较的语义封锁来防止不可重复读、幻象读等问题，从而实现事务的串行化调度。为了提高事务读写的并发能力，针对当前OLTP应用的特点，在谓词锁的基础上进一步细分锁粒度，提出属性谓词锁的理论，并在给定的复杂度内讨论了该理论在上述应用场景下的可行性
作者研究了时间依赖图下，具有时间限制的费用代价最优路径的查询问题。目前有关时间依赖图上的最短路径查询的研究工作解决的是最短旅行时间问题( TDSP)，这些工作都利用了以下性质：到达某个顶点的最早时刻可以通过到达其邻居的最早时刻计算得出。然而，在计算具有时间限制的费用代价最优路径时，该性质并不成立。因此，目前解决TDSP问题的方法均不能解决文中面对的问题。对此作者提出一个新的算法用于计算时间依赖图模
紧密子图发现在许多现实世界网络应用中具有重要的研究意义.提出一种新的紧密子图发现问题——Top-k属性差异q-clique查询,找出图中k个节点间属性具有最大差异的q-clique.属性差异q-clique是一种结合图的结构特征和节点属性的紧密子图,在作者合作关系图数据中,该查询可以发现属性(如研究领域或所属单位)上不同的具有紧密合作关系的团队.给出了q-clique的属性差异度量,证明了该问题为
面向挖掘应用的隐私保护数据发布要求对数据集进行隐藏的同时维持数据的挖掘可用性，数据扰动是解决该问题的有效方法。现有的面向聚类的数据扰动方法难以兼顾原始数据个体隐私和维持数据聚类可用性，对此提出了一种基于对数螺线的隐私保护数据干扰方法。通过构建面向聚类的隐私保护数据扰动模型，利用对数螺线对原始数据进行扰动隐藏，维持原始数据的邻域关系稳定，实现数据集聚类可用性的有效维护；进一步提出多重对数螺线扰动的策
基于闪存的固态硬盘(Solid State Driver,SSD)已成为目前广泛使用的一种持久存储设备.但是由于闪存不对称的I/O特性以及价格因素,SSD还不能完全取代传统硬盘(Hard Disk Driver,HDD).因此,由SSD和HDD组成的混合存储系统逐步成为目前研究的重点.文中针对SSD和HDD混合存储问题,提出了一个时间敏感的混合存储模型用来有效地利用SSD.该模型把SSD和HDD作
云计算技术的快速发展为海量数据的存储和管理提供了可能。然而，由于存储模型的根本改变，传统关系数据库管理系统中成熟的索引技术既不能直接应用于海量数据的处理，也无法被简单地迁移到云计算环境中。通过分析对比辅助索引在云环境中的两种截然不同的基本逻辑结构，即集中式方案与分布式方案，在吸收两者的优势并规避其弱点的基础上，提出了具有良好可扩展性的分片位图索引机制，从而对云环境中海量数据的检索任务提供高效的支持
随着基于闪存的固态硬盘在个人计算机和企业服务器上的广泛应用,固态硬盘受到学术界和工业界越来越多的关注。除了具有闪存存储器的优良特性之外,固态硬盘内部还具有丰富的并行特性。传统数据库系统的物理操作表扫描和上层聚集操作是针对磁盘的机械特性和对称读写特性而设计的,并不能发挥固态硬盘内部并行特性的优势。文中首先将固态硬盘作为一个黑盒进行探测以了解其内部的并行特性。在此基础上,对传统数据库表扫描操作进行相应
聚类热度时间序列是揭示和建模网络热点话题形成与发展的重要过程.Leskovec等人在2010年提出面向话题时间序列的K_SC聚类算法,其精确度较高且能较好地刻画话题内在发展趋势特征.但K_SC算法具有对初始类矩阵中心高度敏感、高时间复杂度等特性,使其难以在实际高维大数据集上应用.文中结合小波变换技术,提出一个新的迭代式聚类算法WKSC,主要提出两个创新：(1)用Haar小波变换将原始时间序列进行压
随着移动互联网、地理定位技术和智能终端设备的迅速普及,产生了大量的位置信息和其对应的标签(tag)描述信息。路线搜索是人们出行时经常进行的活动,但面临多个任务需求时,寻找最佳路线是一项极为耗时的工作。此外空间对象本身的访问权限和用户指定的限制一定程度上制约了对象的访问次序。针对上述情况,文中提出了一种路网环境下访问序列受限的多标签路线(MTROC)查询,该查询的目标是找出一条从源点到目标点、经由与