Random walk search in unstructured P2P

Unstructured P2P has power-law link distribution, and the random walk in power-law networks is analyzed. The analysis results show that the probability that a random walker walks through the high degree nodes is high in the power-law network, and the information on the high degree nodes can be easily found through random walk. Random walk spread and random walk search method （RWSS） is proposed based on the analysis result. Simulation results show that RWSS achieves high success rates at low cost and is robust to high degree node failure.

HDNBS: An approach for search in decentralized and unstructured P2P

Decentralized and unstructured peer-to-peer applications such as Gnutella are attractive because they require no centralized directories and no precise control over network topology or data placement. Search algorithm is the major component of the distributed system and its efficiency also does influence the systems performance. However the flooding-based query algorithm used in Gnutella produces huge traffic and does not scale well. Gnutella-like P2P topology has power-law characteristic, so a search algorithm was proposed based on high degree nodes of power-law network, High Degree Nodes-Based Search （HDNBS）. Extensive simulation results show that this algorithm performs on power-law networks very well, achieves almost 100% success rates, produces O（logN） messages per query and can locate target file within O（lagN） hops.

An Efficient Multi-Keyword Query Processing Strategy on P2P Based Web Search

The paper presents a novel benefit based query processing strategy for efficient query routing. Based on DHT as the overlay network, it first applies Nash equilibrium to construct the optimal peer group based on the correlations of keywords and coverage and overlap of the peers to decrease the time cost, and then presents a two-layered architecture for query processing that utilizes Bloom filter as compact representation to reduce the bandwidth consumption. Extensive experiments conducted on a real world dataset have demonstrated that our approach obviously decreases the processing time, while improves the precision and recall as well.

Analytical Comparison of Resource Search Algorithms in Non-DHT Mobile Peer-to-Peer Networks

One of the key challenges in ad-hoc networks is the resource discovery problem.How efciently&quickly the queried resource/object can be resolved in such a highly dynamic self-evolving network is the underlying question?Broadcasting is a basic technique in the Mobile Ad-hoc Networks(MANETs),and it refers to sending a packet from one node to every other node within the transmission range.Flooding is a type of broadcast where the received packet is retransmitted once by every node.The naive ooding technique oods the network with query messages,while the random walk scheme operates by contacting subsets of each node’s neighbors at every step,thereby restricting the search space.Many earlier works have mainly focused on the simulation-based analysis of ooding technique,and its variants,in a wired network scenario.Although,there have been some empirical studies in peer-to-peer(P2P)networks,the analytical results are still lacking,especially in the context of mobile P2P networks.In this article,we mathematically model different widely used existing search techniques,and compare with the proposed improved random walk method,a simple lightweight approach suitable for the non-DHT architecture.We provide analytical expressions to measure the performance of the different ooding-based search techniques,and our proposed technique.We analytically derive 3 relevant key performance measures,i.e.,the avg.number of steps needed to nd a resource,the probability of locating a resource,and the avg.number of messages generated during the entire search process.

Hybrid ants-like search algorithms for P2P media streaming distribution in ad hoc networks

Media streaming delivery in wireless ad hoc networks is challenging due to the stringent resource restrictions,po-tential high loss rate and the decentralized architecture. To support long and high-quality streams,one viable approach is that a media stream is partitioned into segments,and then the segments are replicated in a network and served in a peer-to-peer(P2P) fashion. However,the searching strategy for segments is one key problem with the approach. This paper proposes a hybrid ants-like search algorithm(HASA) for P2P media streaming distribution in ad hoc networks. It takes the advantages of random walks and ants-like algorithms for searching in unstructured P2P networks,such as low transmitting latency,less jitter times,and low unnecessary traffic. We quantify the performance of our scheme in terms of response time,jitter times,and network messages for media streaming distribution. Simulation results showed that it can effectively improve the search efficiency for P2P media streaming distribution in ad hoc networks.

A P2P Platform for Collaborative Aggregated Multimedia Sharing

Peer-to-peer technologies have emerged as a powerful and scalable communication model for large scale content shar-ing. However, they are not yet provided with optimized heterogeneous aggregated content management functionality since they lack rich semantic specifications. To overcome these shortcomings, we elaborated a reference model of P2P architecture for a dynamic aggregation, sharing and retrieval of heterogeneous multimedia contents (simple or aggre-gated). This architecture was mainly developed under the CAM4Home European research project and is fully based on the CAM4Home semantic metadata model. This semantic model relies on RDF (Resource Description Framework) and is rich (but simple enough), extensible and dedicated for the description of any kind of multimedia content.In this paper, we detail and evaluate an original semantic-based community network architecture for heterogeneous multimedia con-tent sharing and retrieval. Within the presentedarchitecture, multimedia contents are managed according to their asso-ciated CAM4Home semantic metadata through a structured P2P topology. This topology relies on a semantically en-hanced DHT (Distributed Hash Table) and is also provided with an additional indexing system for offering semantic storage and search facilities and overcoming the problem of exact match keywords in DHTs.

Mathematical Model Validation of Search Protocols in MP2P Networks

Broadcasting is a basic technique in Mobile ad-hoc network(MANET),and it refers to sending a packet from one node to every other node within the transmission range.Flooding is a type of broadcast where the received packet is retransmitted once by every node.The naive flooding technique,floods the network with query messages,while the random walk technique operates by contacting the subsets of every node’s neighbors at each step,thereby restricting the search space.One of the key challenges in an ad-hoc network is the resource or content discovery problem which is about locating the queried resource.Many earlier works have mainly focused on the simulation-based analysis of flooding,and its variants under a wired network.Although,there have been some empirical studies in peer-to-peer(P2P)networks,the analytical results are still lacking,especially in the context of P2P systems running over MANET.In this paper,we describe how P2P resource discovery protocols perform badly over MANETs.To address the limitations,we propose a new protocol named ABRW(Address Broadcast Random Walk),which is a lightweight search approach,designed considering the underlay topology aimed to better suit the unstructured architecture.We provide the mathematical model,measuring the performance of our proposed search scheme with different widely popular benchmarked search techniques.Further,we also derive three relevant search performance metrics,i.e.,mean no.of steps needed to find a resource,the probability of finding a resource,and the mean no.of message overhead.We validated the analytical expressions through simulations.The simulation results closely matched with our analyticalmodel,justifying our findings.Our proposed search algorithm under such highly dynamic self-evolving networks performed better,as it reduced the search latency,decreased the overall message overhead,and still equally had a good success rate.

A Semantic Searching Scheme in Heterogeneous Unstructured P2P Networks

Semantic-based searching in peer-to-peer （P2P） networks has drawn significant attention recently. A number of semantic searching schemes, such as GES proposed by Zhu Y et al., employ search models in Information Retrieval （IR）. All these IR-based schemes use one vector to summarize semantic contents of all documents on a single node. For example, GES derives a node vector based on the IR model： VSM （Vector Space Model）. A topology adaptation algorithm and a search protocol are then designed according to the similarity between node vectors of different nodes. Although the single semantic vector is suitable when the distribution of documents in each node is uniform, it may not be efficient when the distribution is diverse. When there are many categories of documents at each node, the node vector representation may be inaccurate. We extend the idea of GES and present a new class-based semantic searching scheme （CSS） specifically designed for unstructured P2P networks with heterogeneous single-node document collection. It makes use of a state-of-the-art data clustering algorithm, online spherical k-means clustering （OSKM）, to cluster all documents on a node into several classes. Each class can be viewed as a virtual node. Virtual nodes are connected through virtual links. As a result, the class vector replaces the node vector and plays an important role in the class-based topology adaptation and search process. This makes CSS very efficient. Our simulation using the IR benchmark TREC collection demonstrates that CSS outperforms GES in terms of higher recall, higher precision, and lower search cost.

HAPS:Supporting Effective and Effcient Full-Text P2P Search with Peer Dynamics

Recently, peer-to-peer （P2P） search technique has become popular in the Web as an alternative to centralized search due to its high scalability and low deployment-cost. However, P2P search systems are known to suffer from the problem of peer dynamics, such as frequent node join/leave and document changes, which cause serious performance degradation. This paper presents the architecture of a P2P search system that supports full-text search in an overlay network with peer dynamics. This architecture, namely HAPS, consists of two layers of peers. The upper layer is a DHT （distributed hash table） network interconnected by some super peers （which we refer to as hubs）. Each hub maintains distributed data structures called search directories, which could be used to guide the query and to control the search cost. The bottom layer consists of clusters of ordinary peers （called providers）, which can receive queries and return relevant results. Extensive experimental results indicate that HAPS can perform searches effectively and efficiently. In addition, the performance comparison illustrates that HAPS outperforms a fiat structured system and a hierarchical unstructured system in the environment with peer dynamics.

基于P2P的制造资源搜索引擎的研究与实现

资源共享是网格技术追求的目标之一。基于中心服务器的集中式系统虽然具有易控制、维护方便等优点,但同时带来了很多问题,如中心服务器会成为整个系统的瓶颈、通信效率较低、检索资源的范围仅仅局限于资源的提供者等。P2P中对等点(Peer)之间通过直接互连,实现动态共享资源。本文结合P2P的网络特点,构建了一个面向制造业的资源共享平台——制造资源搜索引擎(Manufacturing Resource Search Engine,MRSE),对其中的关键技术进行了研究,提出了基于XML的资源搜索策略,给出了XML的两种同步机制,并且在快速原型制造网格中实现了制造资源搜索引擎。

Semantic overlay network for searching taxonomy-based data sources

Distributed data sources which employ taxonomy hierarchy to describe the contents of their objects are considered, and a super-peer-based semantic overlay network （SSON） is proposed for sharing and searching their data objects. In SSON, peers are dynamically clustered into many semantic clusters based on the semantics of their data objects and organized in the semantic clusters into a semantic overlay network. Each semantic cluster consists of a super-peer and more peers, and is only responsible for answering queries in its semantic subspace. A query is first routed to the appropriate semantic clusters by an efficient searching algorithm, and then it is forwarded to the specific peers that hold the relevant data objects. Experimental results indicate that SSON has good scalability and achieves a competitive trade-off between search efficiency and costs.

Study on semantic-oriented hybrid indexing strategy of resource metadata in peer-to-peer network

Applying ontology to describe resource metadata richly in the peer-to-peer environment has become current research trend. In this semantic peer-to-peer environment, indexing semantic element of resource description to support efficient resource location is a difficult and challenging problem. This paper provided a hybrid indexing architecture, which combines local indexing and global indexing. It uses community strategy and semantic routing strategy to organize key layer metadata element and uses DHT (distributed hash table) to index extensional layer metadata element. Compared with related system, this approach is more efficient in resource location and more scalable.

KRBKSS: a keyword relationship based keyword-set search system for peer-to-peer networks

may incur significant bandwidth for executing more com- plicated search queries such as multiple-attribute queries. In order to reduce query overhead, KSS (keyword-set search) by Gnawali partitions the index by a set of keywords. However, a KSS index is considerably larger than a standard inverted index, since there are more word sets than there are individual words. And the insert overhead and storage overhead are obviously un- acceptable for full-text search on a collection of documents even if KSS uses the distance window technology. In this paper, we extract the relationship information between query keywords from websites’ queries logs to improve performance of KSS system. Experiments results clearly demonstrated that the improved keyword-set search system based on keywords relationship (KRBKSS) is more efficient than KSS index in insert overhead and storage overhead, and a standard inverted index in terms of communication costs for query.

PChord:a distributed hash table for P2P network

As a solution for data storage and information sharing for peer-to-peer(P2P)networks,a novel distributed hash table(DHT)structure called PChord is presented in this paper.PChord adopts a bi-directional searching mechanism superior to Chord and enhances the structure of the finger table.Based on Hilbert space filling curve,PChord realizes the mapping mechanism for multikeyword approximate searching.Compared with the Chord and Kademlia protocols,PChord evidently increases speed on resource searching and message spreading via theoretic proof and simulation results,while maintaining satisfactory load balance.

A Chord-based resource scheduling approach in drug discovery grid

This paper presents a resource scheduling approach in grid computing environment. Using P2P technology, this novel approach can schedule dynamic grid computing resources efficiently. Grid computing resources in different domains are organized into a structured P2P overlay network. Available resource information is published in type of grid services. Task requests for computational resources are also presented as grid services. Problem of resources scheduling is translated into services discovery. Different from central scheduling approaches that collect available resources information, this Chord-based approach forwards task requests in the overlay network and discovers satisfied resources for these tasks. Using this approach, the computational resources of a grid system can be scheduled dynamically according to the real- time workload on each peer. Furthermore, the application of this approach is introduced into DDG, a grid system for drug discovery and design, to evaluate the performance. Experimental results show that computational resources of a grid system can be managed efficiently, and the system can hold a perfect load balance state and robustness.

带投资约束p-中位问题的混合蚁群算法

将投资限制引入经典约束p-中位问题,提出带投资的约束p-中位问题,该问题更适用于交通、物流等领域的设施选址。在深入分析带投资约束p-中位问题的数学模型的基础上,首先提出了适用于该问题求解的局部搜索策略;其次,将局部搜索策略与拉格朗日启发式算法和蚁群算法相结合,设计了求解该问题的拉格朗日混合蚁群算法。实验结果表明,带投资的约束p-中位问题能够根据投资金额规划不同的投资方案;且提出的混合蚁群算法较大程度上提高了蚁群算法和拉格朗日启发式算法的求解精度,具有较好的收敛性。

汇聚组播:新型MPLS服务质量组播体系结构

为支持新兴网络应用,IP组播(multicast)和MPLS(multi-protocol label switching)技术分别从不同方向扩展了当前的IP路由和交换模式.MPLS和IP组播的结合是当前研究的一个热点,MPLS网络中的服务质量组播面临着标签资源匮乏、组播路由状态的可扩展性以及具体实现上的困难.针对这些问题,提出了基于汇聚方法的新型MPLS服务质量组播体系结构,提出在现有的路由控制平面上叠加一层面向IP组播服务的控制平面,取代组播路由协议并支持组播聚集,形成2层控制平面结构.定义了两平面之间的协作和交互方式,并通过扩展RSVP-TE(resourcereservation protocol-traffic engineering)P2MP(point to multi-point)协议,在新的体系结构中融合了服务质量控制能力.另外,还探讨了汇聚组播中基于距离约束选择汇聚路由器的算法,实现了基于Linux的MPLS组播路由器和IP组播服务控制系统,并组建了实验平台.实验和模拟结果表明,基于汇聚组播的双平面网络控制结构能够适应组播用户和网络拓扑的动态变化,能够有效节省MPLS标签资源,平衡网络中组播流量的分布.

P码直接捕获算法的设计及资源优化

针对P码直接捕获消耗资源较多的问题,提出了一种资源优化的方法。该方法在检测概率、虚警概率和捕获时间满足系统要求的约束下,对存储资源、乘法器资源与逻辑资源进行多目标的优化,并通过兼容FFT快速捕获法与延迟相乘法的特点,能够自由地分配时域与频率搜索的并行度,因此该方法能够适用于各种形状的二维不确定域搜索任务,更有效地对资源消耗进行优化。

准噶尔盆地莫索湾地区油源分析

在对准噶尔盆地莫索湾地区地化特征的研究和大量地化参数处理的基础上,利用原油δ13C,Pr/Ph和(Pr+nC17)/(Ph+nC18)以及饱和烃轻重比∑C21-/∑C22+和(C21+C22)/(C28+C29)等参数对原油进行了对比分析,并结合原油运移分析及其他地质特征的研究,最终确定了莫索湾地区的油源:盆参2、芳2井区油源主要为昌吉凹陷二叠系;盆5、盆6井区油源主要为盆1井西凹陷二叠系;两井区交汇地带的盆4井和莫5井一带原油是混源的.

一种求解厌恶型p-中位问题的混合进化算法

厌恶型p-中位问题是一个NP-困难问题.提出了一种求解厌恶型p-中位问题的混合进化算法.首先,通过贪心随机自适应搜索方法和随机构造方法产生初始种群.然后,利用搜索过程中收集到的全局信息和局部信息构造新解,期间注意提高搜索的多样性,避免早熟.最后,针对厌恶型p-中位问题的特点,构造基于约束交换邻域的局部搜索算法,提高了算法的局部搜索能力.通过求解72个标准测试例子以检验算法的性能,发现该算法在较短时间内得到了高质量解,优于现有算法.