共查询到19条相似文献,搜索用时 140 毫秒
1.
提出了一种新颖的分布环境中的序敏感轮廓查询算法(即找出不被别的对象所"支配"的且聚集值较高的对象)。现有的算法在节点数m较大时会消耗大量的网络带宽。提出了一种新的分布式序敏感轮廓查询处理算法(Distributed Rank-aware Skylining,DRS)。DRS算法在任意数据集上只需要4次交互就能完成,并且通过剪除不必要的对象来减少通讯代价。通过模拟数据验证了DRS算法的效率。实验表明,当节点数m大于4时,DRS算法性能优于现有算法的性能。 相似文献
2.
无线传感器网络中Skyline节点连续查询算法 总被引:2,自引:0,他引:2
作为多目标决策的重要手段之一,Skyline节点查询在传感器网络应用中发挥着非常重要的作用.文中深入地分析了Skyline节点查询的性质,提出了基于过滤的Skyline节点连续查询算法(FIlter based Skyline moniToringalgorithm,FIST).FIST算法共包括自底向上、自顶向下和混合3种过滤方式,均通过在传感器节点设置本地或全局过滤器来避免不必要的数据传输,进而节约传感器节点的能量.自底向上过滤方式通过缓存先前Skyline结果作为本地过滤器来避免数据重复传输,而自顶向下过滤则通过设置超立方体作为全局过滤器来避免数据反复更新.由于两者各有利弊,因而提出了混合过滤方式,通过为节点选择合适的过滤器来扬长避短.大量仿真实验的结果表明,FIST算法能有效地减少Skyline节点连续查询过程中传感器节点的通信代价,进而降低传感器网络的能量消耗. 相似文献
3.
为解决海量RDF数据的Skyline查询问题,通过分析现有Skyline查询算法的优缺点,提出一种针对海量RDF数据的查询机制。对RDF数据的存储结构进行分析,根据RDF数据垂直存储结构,设计一种候选Skyline点筛选策略,提前修剪部分非Skyline元组,减少Skyline支配点计算的数据量;在筛选的基础上,给出基于MapReduce的Skyline并行化查询算法。实验结果表明,提前筛选能有效减小查询的数据集,并行化算法能够有效提高查询的效率。 相似文献
4.
5.
云计算为分布并行Skyline查询提供强大存储能力和计算能力的同时,其大规模数据中心固有的故障频发特性给可靠Skyline查询处理带来极大挑战。现有研究致力于提高Skyline算法的响应时间、渐进性、负载均衡等各项性能,不能保证故障情况下查询继续正确执行。为此,提出一种容错并行Skyline查询算法(fault-tolerant parallel Skyline,FTPS)。该算法通过故障监测和任务迁移,使得能够在查询过程中及时发现故障,并将故障节点的计算任务迁移到副本节点,保证查询的正确执行。理论分析和实验证明,FTPS算法能够在不影响正常Skyline查询处理性能的情况下获取较好的容错处理性能。 相似文献
6.
7.
现有基于MapReduce的算法不能高效地解决大数据的Skyline查询问题。针对这种情况,提出一种高效的预处理Skyline查询算法MRFS(MapReduce based Filter Skyline),对大数据集进行预处理,提取支配能力较强的小点集组成比较点集,在算法开始前用比较点集对原始数据集进行过滤,排除掉一大部分不能成为Skyline结果集的数据对象;再对过滤后的数据集在Map阶段并行计算出局部Skyline集;最后合并到一个Reduce任务,得到最终的Skyline结果集。在不同数据分布下对该算法进行系统实验,结果表明算法比现有的算法在时间效率上提高了20%~30%。 相似文献
8.
现有的基于单服务器的Skyline查询算法已经不能很好地应用于无线传感器网络这类分布式多跳自组织网络中。基于聚簇结构的Skyline查询算法就是针对 这类特定的网络结构而提出的。该算法采用基于聚簇的路由结构,为了减少Skyline查询处理过程中传感器节点的通信开销,挑选具有最大支配力的数据元组作为全局过滤元组来过滤不满足Skyline条件的数据。同时,在Skyline查询处理过程中引入滑动窗口机制,该机制也能有效地降低通信开销。大量的仿真实验结果显示,所提Skyline查询算法在确保能耗的基础上仍然具有很好的性能。 相似文献
9.
10.
由于无线传感器网络的能源有限,且在许多应用中Skyline查询的部分结果即可满足用户需求,提出了一种近似Skyline查询处理算法,在满足用户查询需求的前提下最大化地节省能量.该算法仅需无线传感器网络中的部分传感器节点回传其感知数据即可计算出Skyline查询的一个近似结果集.由于该算法在处理查询时,每个传感器节点只需考察自身数据信息即可决定是否回传其感知数据,而无须与其他传感器节点的感知数据进行比较,因此可以避免大量的网内通信开销,从而节省网络能源.模拟环境下的大量实验结果表明,该算法可以根据用户的应用需求,节能地处理传感器网络中的近似skyline查询. 相似文献
11.
一种基于调度簇树的周期性分布实时任务调度算法 总被引:1,自引:1,他引:1
本文针对现有的基于任务复制的静态调度算法在调度周期性分布实时任务时存在的缺点,提出了一种称之为调度簇树(SCT)的新的结构并研究了其特性,在此基础上给出了一种基于SCT树的周期性分布实时任务调度算法(SAS)。通过与OSA算法进行比较的实验结果表明,SAS算法可实现调度长度向上最接近分布实时任务周期,最大程度减少所需顸留处理器数目,大大提高分布实时系统的处理器利用率,同时并不增加调度算法的复杂度。 相似文献
12.
针对无线传感器网络(WSN)故障节点率高于50%时故障检测率降低的问题,提出一种基于邻居节点预状态及邻居节点数据的无线传感器节点故障诊断算法。首先利用节点自身历史数据对节点状态进行初步预判断;然后结合节点间相似性和邻居节点的预状态对节点状态进行最终的判断;最后利用移动传感器节点将故障节点信息通过最优路径发送给基站,有效地减少了通信次数。仿真实验在100 m×100 m的方形区域内模拟WSN。实验结果表明,与传统的分布式故障诊断(DFD)算法相比,诊断精度提升了9.84个百分点,并且当节点故障率高达50%时,该算法仍能达到95%的诊断精度。在实际应用中,所提算法在提高故障诊断精度的同时,能有效地减少能量消耗、延长网络寿命。 相似文献
13.
在深入分析MANET组通信安全需求和已有工作的基础上,基于门限秘密分享机制和门限RSA方案,提出了分布式安全组通信协议DSGCP(Distributed Secure Group Communication Protocol)。该协议避免了组密钥管理的单点失效问题,降低了节点移动性和链路可靠性对于组密钥管理的影响,适应网络拓扑变化的特点,抗毁性强。描述了协议的组通信密钥更新算法、组控制密钥更新算法和合作解密算法,刻画了协议报文格式和主要协议过程,并基于实际Ad-hoc网络进行了协议实现和协议性能测试。 相似文献
14.
Communication-Efficient Distributed Mining of Association Rules 总被引:3,自引:0,他引:3
Mining for associations between items in large transactional databases is a central problem in the field of knowledge discovery. When the database is partitioned among several share-nothing machines, the problem can be addressed using distributed data mining algorithms. One such algorithm, called CD, was proposed by Agrawal and Shafer and was later enhanced by the FDM algorithm of Cheung, Han et al. The main problem with these algorithms is that they do not scale well with the number of partitions. They are thus impractical for use in modern distributed environments such as peer-to-peer systems, in which hundreds or thousands of computers may interact.In this paper we present a set of new algorithms that solve the Distributed Association Rule Mining problem using far less communication. In addition to being very efficient, the new algorithms are also extremely robust. Unlike existing algorithms, they continue to be efficient even when the data is skewed or the partition sizes are imbalanced. We present both experimental and theoretical results concerning the behavior of these algorithms and explain how they can be implemented in different settings. 相似文献
15.
针对如何对分布式网络采集的数据进行在线学习的问题,提出了一种基于交替方向乘子法(ADMM)的分布式在线学习优化算法--分布式在线交替方向乘子法(DOM)。首先,针对分布式在线学习需要各节点根据新采集的数据来更新本地估计,同时保持网络中所有节点的估计趋于一致这一问题,建立了数学模型并设计DOM算法对其进行求解。其次,针对分布式在线学习问题定义了Regret 界,用以表征在线估计的性能;证明了当本地即时损失函数是凸函数时,DOM算法是收敛的,并给出了其收敛速度。最后,通过数值仿真实验结果表明,相比现有的分布式在线梯度下降法(DOGD)和分布式在线自主学习算法(DAOL),所提出的DOM算法具有更快的收敛性能。 相似文献
16.
Distributed query processing algorithms usually perform data reduction by using a semijoin program, but the problem with these approaches is that they still require an explicit join of the reduced relations in the final phase. We introduce an efficient algorithm for join processing in distributed database systems that makes use of bipartite graphs in order to reduce data communication costs and local processing costs. The bipartite graphs represent the tuples that can be joined in two relations taking also into account the reduction state of the relations. This algorithm fully reduces the relations at each site. We then present an adaptive algorithm for response time optimization that takes into account the system configuration, i.e., the additional resources available and the data characteristics, in order to select the best strategy for response time minimization. We also report on the results of a set of experiments which show that our algorithms outperform a number of the recently proposed methods for total processing time and response time minimization. 相似文献
17.
This paper presents new efficient shortest path algorithms to solve single origin shortest path problems (SOSP problems) and multiple origins shortest path problems (MOSP problems) for hierarchically clustered data networks. To solve an SOSP problem for a network with n nodes, the distributed version of our algorithm reaches the time complexity of O(log(n)), which is less than the time complexity of O(log 2 (n)) achieved by the best existing algorithm. To solve an MOSP problem, our algorithm minimizes the needed computation resources, including computation processors and communication links for the computation of each shortest path so that we can achieve massive parallelization. The time complexity of our algorithm for an MOSP problem is O(m log(n)), which is much less than the time complexity of O(M log2 (0)) of the best previous algorithm. Here, M is the number of the shortest paths to be computed and m is a positive number related to the network topology and the distribution of the nodes incurring communications, m is usually much smaller than M. Our experiment shows that m is almost a constant when the network size increases. Accordingly, our algorithm is significantly faster than the best previous algorithms to solve MOSP problems for large data networks 相似文献
18.
Xiaopeng FanAuthor Vitae Weigang WuAuthor Vitae 《Journal of Parallel and Distributed Computing》2011,71(4):603-614
This paper studies a challenging problem of cache placement in wireless multi-hop ad hoc networks. More specifically, we study how to achieve an optimal tradeoff between total access delay and caching overheads, by properly selecting a subset of wireless nodes as cache nodes when the network topology changes. We assume a data source updates a data item to be accessed by other client nodes. Most of the existing cache placement algorithms use hop counts to measure the total cost of a caching system, but hop delay in wireless networks varies much due to the contentions among these nodes and the traffic load on each link. Therefore, we evaluate the per-hop delay for each link according to the contentions detected by a wireless node from the MAC layer. We propose two heuristic cache placement algorithms, named Centralized Contention-aware Caching Algorithm (CCCA) and Distributed Contention-aware Caching Algorithm (DCCA), both of which detect the variation of contentions and the change of the traffic flows, in order to evaluate the benefit of selecting a node as a cache node. We also apply a TTL-based cache consistency strategy to maintain the delta consistency among all the cache nodes. Simulation results show that the proposed algorithms achieve better performance than other alternative ones in terms of average query delay, caching overheads, and query success ratio. 相似文献
19.
为解决现有无线传感器网络(WSN)分簇算法难以同时兼顾其异构性和移动性,从而引发网络寿命较短、网络数据吞吐量较低等问题,提出了基于节点等级的自适应分簇算法。该算法按轮运行,每轮分为自适应分簇、簇建立、数据传输三个阶段。为解决节点移动性引发的簇首数目和成簇规模不合理的问题,在自适应分簇阶段,根据子区域内节点数目变化对相应子区域进行细化或就近合并,以确保每个子区域内节点数目在合理范围内。在簇建立阶段,选举簇内等级最高的节点为簇首,解决异构性引发的部分节点能耗过快、网络寿命缩短的问题;节点等级除考虑节点剩余能量外,还结合WSN实际应用,由节点剩余能量、能量消耗速率、到基站的距离、到簇内其他节点的距离综合决定。基于OMNeT++和Matlab的仿真实验结果表明,在节点移动速度为0~0.6 m/s的能量异构WSN环境下,较移动低功耗自适应集簇分层(LEACH-Mobile)算法和分布式能量有效分簇(DEEC)算法,运用所提算法分簇的WSN寿命延长了30.9%以上,网络数据吞吐量是其他两种算法分簇的网络的1.15倍以上。 相似文献