非结构P2P网络受限搜索机制

降低搜索过程中产生的大量网络开销,是非结构P2P 网络重点研究内容之一.泛洪算法和随机查找算法简单且易于实现,但其在搜索过程中产生的大量冗余消息是造成大量网络开销的主要原因.针对这一问题,提出一种受限搜索机制(restricted forward search algorithm,简称RFSA),定义了搜索路径和冗余搜索路径,引入本地消息索引缓存机制,通过节点对消息的受限接收,消除节点对消息的重复接收与转发;利用搜索过程中携带的实时搜索路径信息,选择未出现在搜索路径中的邻居节点对消息进行转发,消除冗余搜索路径的产生.从理论上分析了RFSA 所产生的消息数目和网络开销.模拟实验分别从网络开销、查询点击率、搜索覆盖率和产生的冗余消息数目等方面对受限机制下和非受限机制下的泛洪算法和随机查找算法进行了对比分析,结果表明,在搜索覆盖率和查询点击率基本相同的情况下,受限机制下的泛洪算法和随机查找算法能够减少大量冗余消息的产生,降低了网络开销.     

Reducing query overhead through route learning in unstructured peer-to-peer network

In unstructured peer-to-peer networks, such as Gnutella, peers propagate query messages towards the resource holders by flooding them through the network. This is, however, a costly operation since it consumes node and link resources excessively and often unnecessarily. There is no reason, for example, for a peer to receive a query message if the peer has no matching resource or is not on the path to a peer holding a matching resource. In this paper, we present a solution to this problem, which we call Route Learning, aiming to reduce query traffic in unstructured peer-to-peer networks. In Route Learning, peers try to identify the most likely neighbors through which replies can be obtained to submitted queries. In this way, a query is forwarded only to a subset of the neighbors of a peer, or it is dropped if no neighbor, likely to reply, is found. The scheme also has mechanisms to cope with variations in user submitted queries, like changes in the keywords. The scheme can also evaluate the route for a query for which it is not trained. We show through simulation results that when compared to a pure flooding based querying approach, our scheme reduces bandwidth overhead significantly without sacrificing user satisfaction.     

基于拥塞控制的非结构化P2P网络的路由负载均衡策略

非结构化P2P(unstructured peer-to-peer network)对等网络中的节点资源定位的路由查询是对等网络研究中的一个主要难题,特别是当网络中客户端节点由于其频繁加入、离开导致网络结构动态变化所带来的资源查询难题.提出了一种新的基于拥塞控制的路由查询方法来实现动态网络下的资源查询.该方法分两部分实现:首先是网络资源的分组与节点重连策略.该策略使得具有同等资源的节点相互连接,并周期性地调整节点上的节点连接数量以减少同组资源节点上的负载.通过以上策略,使得网络的拓扑结构自动地从随机网络结构进化到以资源组为单位的聚类网络,从而使得网络中形成网络资源组间的查询负载均衡.另一方面,组内的节点之间的路由负载均衡是通过节点间协同学习实现的.采用协同Q-学习方法,所研究的方法不仅从节点上学习其处理能力、连接数和资源的个数等参数,还将节点的拥塞状态作为协同Q-学习的重要参数,并建立模型.通过这种技术,同一组节点上的资源查询被有目的地引导,以避开那些组内拥塞的节点,从而最终实现资源组内节点之间的查询均衡.仿真实验结果表明,相比常用的random walk资源查找方法,该研究所实现的资源定位方法能够更迅速地实现网络的资源查询.仿真结果还表明,相比random walk方法,所提出的方法在网络高强度查询和网络节点动态加入和退出的情况下进行查询具有更高的鲁棒性和适应性.     

Multi-constraint multi-objective QoS aware routing heuristics for query driven sensor networks using fuzzy soft sets

In this paper, a fuzzy based distributed power aware routing scheme considering both energy and bandwidth constraints, especially for query driven applications in the asynchronous duty-cycled wireless sensor networks are devised. The proposed multi-constraint, multi-objective routing optimization approach under strict resource constraints guarantees reliability and fast data delivery along with efficient power management in spite of unreliable wireless links and limited power supply. In query driven applications, the request from the sink to the individual sensor node will be a broadcast message, whereas the individual sensor nodes replies back to sink as unicast messages. In the proposed work, the fuzzy approach and “A Star” algorithm are utilized for satisfying energy and bandwidth constraints to route the broadcast messages of the sink while querying all the sensor nodes in the network. Every node will be provided with a guidance list, which is used to decide the next best neighbor node with good route quality for forwarding the received multi-hop broadcast messages. The route quality of the every node is estimated with fuzzy rules based on the network parameters such as maximum remaining energy, minimum traffic load and better link quality to increase the network lifetime. The provision of overhearing the broadcast messages and acknowledgements within the transmission range minimizes the effort to search for the active time of nodes while routing the broadcast messages with asynchronous scheduling. Further, in the proposed work only the time slot of its nearest neighbor relay node (to which packets are to be forwarded) is learnt to reduce the number of message transmissions in the network. For the unicast message replies, the fuzzy membership function is modified and devised based on the routing metrics such as higher residual energy, minimum traffic loads and minimum hop count under energy and bandwidth constraints. Also, the multi-hop heuristic routing algorithm called Nearest Neighbor Tree is effectively used to reduce the number of neighbors in the guidance list that are elected for forwarding. This helps to increase the individual sensor node’s lifetime, thereby maximizes the network lifetime and guarantees increased network throughput. The simulation results show that the proposed technique reduces repeated transmissions, decreases the number of transmissions, shortens the active time of the sensor nodes and increases the network lifetime for query driven sensor network applications invariant to total the number of sensor nodes and sinks in the network. The proposed algorithm is tested in a small test bed of sensor network with ten nodes that monitors the room temperature.     

Web search results caching service for structured P2P networks

This paper proposes a two-level P2P caching strategy for Web search queries. The design is suitable for a fully distributed service platform based on managed peer boxes (set-top-box or DSL/cable modem) located at the edge of the network, where both boxes and access bandwidth to those boxes are controlled and managed by an ISP provider. Our solution significantly reduces user query traffic going outside of the ISP provider to get query results from the respective Web search engine. Web users are usually very reactive to worldwide events which cause highly dynamic query traffic patterns leading to load imbalance across peers. Our solution contains a strategy to quickly ease imbalance on peers and spread communication flow among participating peers. Each peer maintains a local result cache used to keep the answers for queries originated in the peer itself and queries for which the peer is responsible for by contacting the Web search engine on-demand. When query traffic is predominantly routed to a few responsible peers our strategy replicates the role of “being responsible for” to neighboring peers so that they can absorb query traffic. This is a fairly slow and adaptive process that we call mid-term load balancing. To achieve a short-term fair distribution of queries we introduce a location cache in each peer which keeps pointers to peers that have already requested the same queries in the recent past. This lets these peers share their query answers with newly requesting peers. This process is fast as these popular queries are usually cached in the first DHT hop of a requesting peer which quickly tends to redistribute load among more and more peers.     

Dynamic Search Algorithm in Unstructured Peer-to-Peer Networks

Designing efficient search algorithms is a key challenge in unstructured peer-to-peer networks. Flooding and random walk (RW) are two typical search algorithms. Flooding searches aggressively and covers the most nodes. However, it generates a large amount of query messages and, thus, does not scale. On the contrary, RW searches conservatively. It only generates a fixed amount of query messages at each hop but would take longer search time. We propose the dynamic search (DS) algorithm, which is a generalization of flooding and RW. DS takes advantage of various contexts under which each previous search algorithm performs well. It resembles flooding for short-term search and RW for long-term search. Moreover, DS could be further combined with knowledge-based search mechanisms to improve the search performance. We analyze the performance of DS based on some performance metrics including the success rate, search time, query hits, query messages, query efficiency, and search efficiency. Numerical results show that DS provides a good tradeoff between search performance and cost. On average, DS performs about 25 times better than flooding and 58 times better than RW in power-law graphs, and about 186 times better than flooding and 120 times better than RW in bimodal topologies.     

Scalable and fair forwarding of elephant and mice traffic in software defined networks

A software defined network decouples the control and data planes of the networking devices and places the control plane of all the switches in a central server. These flow based networks do not scale well because of the increased number of switch to controller communications, limited size of flow tables and increased size of flow table entries in the switches. In our work we use labels to convey control information of path and policy in the packet. This makes the core of the network simple and all routing and policy decisions are taken at the edge. The routing algorithm splits the elephant traffic into mice and distributes them across multiple paths, thus ensuring latency sensitive mice traffic is not adversely affected by elephant traffic. We observed that label based forwarding and traffic splitting work well together to enable scalable and fair forwarding. Our approach is topology independent. We present here a few preliminary simulation results obtained by running our routing algorithm on random network topologies.     

Scalable Retrieval and Mining With Optimal Peer-to-Peer Configuration

We proposed to utilize the scalable peer-to-peer network to perform the content-based image retrieval and mining, i.e, P2P-CBIRM. The decentralized unstructured P2P model with certain overheads, i.e., peer clustering and update procedures, is adopted to compromise with the structured one while still reserving flexible routing control when peers join/leave or network fails. The peer CBIRM engine is designed to utilize multi-instance query with multi-feature types to effectively reduce network traffic while maintaining high retrieval accuracy. It helps to enhance the knowledge discovery and image data mining capability. The proposed P2P-CBIRM system provides the scalable retrieval and mining function that the query scope and retrieval accuracy can be adaptively and progressively controlled. To improve the query efficiency (recall-rate/query-scope), it effectively utilizes both: 1) forwarding query message (forward phase) to reduce the query scope and 2) transmitting retrieval results (backward phase) such that activated peers keep filtering high similarity images on the link-path toward the query peer. Experiments show that the query efficiency of the scalable retrieval approach is better than previous methods, i.e., firework query model and breadth-first search. It provides a scalable knowledge discovery platform for efficient image data mining applications. We also proposed to optimally configure the P2P-CBIRM system such that, under a certain number of online users, it would yield the highest recall rate. Simulations demonstrate that, with the optimal configuration, recall rates can be improved to 2.5 to 3 times larger while the network traffic of each peer is reduced to 30% of the original, under the same number of on-line users.     

无线传感器网络能量有效的实时查询处理方法

实时性和能量有效性是战争、抢险救灾等无线传感器网络系统应用的重要指标,因而提出了在查询截止期内,访问节点数目最大化,同时尽可能减少能量消耗的方法.此方法提出了松弛时间和数据传递模式的概念,并利用松弛时间计算跳步数的门限值,对比节点的不同路由方式的跳步数和门限值的关系,从而确定节点的数据传递模式,制定有效的实时查询计划的查询处理方法.仿真实验证明,利用这种查询处理方法能够有效的提高在截止期内查询的准确度和减少查询所需能量.     

Cross-layer routing for peer database querying over mobile ad hoc networks

The widespread of mobile ad hoc networking calls for a careful design of network functions in order to meet the application requirements and economize on the limited resources. In this paper we address the problem of distributing query messages among peers in mobile ad hoc networks. We assume that peers are organized in classes. Each peer possesses a local database and can answer queries posed by other peers. Each peer can also pose queries to all the peers belonging to a certain class or classes. Contrary to traditional p2p lookup queries, we are interested in collecting answers from as many peers as possible. We propose a query routing protocol, called CL-QF, which is based on a novel cross-layer design. The purpose of this design is to incorporate application layer specifics (e.g., class information) into the network layer in order to reduce transmissions therefore economize on resources. CL-QF coexists with traditional routing. This synergy minimizes the complexity and signaling of CL-QF while the network is able to seamlessly provide legacy unicast communication. CL-QF manages a reduction of up to ～78% compared to non-cross-layer approaches, such as probabilistic forwarding, without compromising the ability to effectively collect replies.     

基于查询的无线传感器网络多源单汇路由算法

针对定向扩散巨大的能量开销以及在路径加强时存在的链路冗余等问题,提出了一种基于查询的无线传感器网络多源单汇路由算法。该算法通过网络分簇来减少平面泛洪所带来的能量消耗,根据邻居节点的优先级来选择下一跳节点,建立多条源节点到Sink节点的路径,并在路径交叉处进行数据融合。仿真结果表明,该算法在节点能耗均衡性、能量有效性、数据包的传输量等方面具有明显的优势,有效地延长了网络生命周期。     

A path-traceable query routing mechanism for search in unstructured peer-to-peer networks

Unstructured Peer-to-Peer (P2P) networks have become a very popular architecture for content distribution in large-scale and dynamic environments. Searching for content in unstructured P2P networks is a challenging task because the distribution of objects has no association with the organization of peers. Proposed methods in recent years either depend too much on objects replication rate or suffer from a sharp decline in performance when objects stored in peers change rapidly, although their performance is better than flooding or random walk algorithms to some extent. In this paper, we propose a novel query routing mechanism for improving query performance in unstructured P2P networks. We design a data structure called traceable gain matrix (TGM) that records every query's gain at each peer along the query hit path, and allows for optimizing query routing decision effectively. Experimental results show that our query routing mechanism achieves relatively high query hit rate with low bandwidth consumption in different types of network topologies under static and dynamic network conditions.     

基于随机漫步的信任路径搜索算法

传统的局部信任模型采用简单洪泛的方法获得信任信息,针对该方法效率较低且对网络资源消耗较大的问题,提出一种基于随机漫步的搜索信任路径的算法。通过以往遗留的路径信息改进搜索,可有效减少多余信息的数日和信任回路的出现。该算法适用于对网络资源占用比较敏感的环境。     

Hierarchical Cellular-Based management for mobile hosts in Ad-Hoc wireless networks

This study proposes a hierarchical Cellular-Based management model for Mobile Ad-Hoc Networks. The proposed management model allows the mobile host to establish a stable communication path with fewer flooding messages and smaller hop count. In the single-level management, a host is selected to act as manager, constructing a communication path and managing the mobile hosts in a specific cellular region to significantly reduce the number of flooding packets. Two-level management is also proposed, to reduce the hop count and enhance the efficiency of constructing the QoS routing path. The Cellular-Based management model is compared with Triangular- and Zone-based management models. Performance evaluation shows that hierarchical Cellular-Based management more efficiently reduces the number of flooding messages and the hop count of the routing paths.     

Optimizing in-network aggregate queries in wireless sensor networks for energy saving

This study proposes a method of in-network aggregate query processing to reduce the number of messages incurred in a wireless sensor network. When aggregate queries are issued to the resource-constrained wireless sensor network, it is important to efficiently perform these queries. Given a set of multiple aggregate queries, the proposed approach shares intermediate results among queries to reduce the number of messages. When the sink receives multiple queries, it should be propagated these queries to a wireless sensor network via existing routing protocols. The sink could obtain the corresponding topology of queries and views each query as a query tree. With a set of query trees collected at the sink, it is necessary to determine a set of backbones that share intermediate results with other query trees (called non-backbones). First, it is necessary to formulate the objective cost function for backbones and non-backbones. Using this objective cost function, it is possible to derive a reduction graph that reveals possible cases of sharing intermediate results among query trees. Using the reduction graph, this study first proposes a heuristic algorithm BM (standing for Backbone Mapping). This study also develops algorithm OOB (standing for Obtaining Optimal Backbones) that exploits a branch-and-bound strategy to obtain the optimal solution efficiently. This study tests the performance of these algorithms on both synthesis and real datasets. Experimental results show that by sharing the intermediate results, the BM and OOB algorithms significantly reduce the total number of messages incurred by multiple aggregate queries, thereby extending the lifetime of sensor networks.     

On random routing in wireless sensor grids: A mathematical model for rendezvous probability and performance optimization

Random routing protocols in Wireless Sensor Networks (WSNs) forward packets to randomly selected neighbors. These packets are ‘agents’ carrying information about events or ‘queries’ seeking such information. A novel mathematical framework is proposed for analyzing random routing protocols. Exact probability of a packet visiting a given node within a given hop count as well as the rendezvous probability of agents and queries meeting at a given node in a 2-D grid-based WSN are derived. The basic relationship needed for extending the models to a 3-D grid topology is provided. Exact probabilities of agents meeting queries are derived while ignoring physical boundary effects and packet losses, under two different strategies for forwarding the packet to a neighbor: (a) with equal probability, and (b) self-avoiding forwarding. We then extend the model to account for packet losses by considering the case where a packet is forwarded to a neighbor with equal probability. Also provided is the extension of the analysis for a network with rectangular boundaries. The exact solutions presented, unlike existing models relying on asymptotic behavior, are also applicable to small and medium scale networks. They can be used to set parameters and optimize performance of several classes of random routing protocols. All the models are validated using Monte Carlo simulations. Simulation results indicate that the model is also a good approximation for sparse arrays with 75% or higher node density. Finally, the utility of the model is demonstrated by determining the protocol parameters to optimize the performance of rumor routing protocol under a fixed energy budget.     

?无结构P2P网络中的混合式搜索方法

针对轻洪泛冗余查询消息数多、对稀有资源搜索延迟大的问题,提出一种结合无结构P2P搜索技术和双向Chord环的混合式搜索方法。该方法利用节点的异构性,在k-walker随机走的基础上,根据邻居节点的查询能力,对查询请求的转发方式进行改进,在双向Chord环中对无结构P2P未搜索到的资源进行结构化P2P搜索。仿真结果证明,与轻洪泛相比,混合式搜索方法的冗余查询消息数较少,对稀有资源的搜索延迟较小。     

Efficient semantic search on DHT overlays

Distributed hash tables (DHTs) excel at exact-match lookups, but they do not directly support complex queries such as semantic search that is based on content. In this paper, we propose a novel approach to efficient semantic search on DHT overlays. The basic idea is to place indexes of semantically close files into same peer nodes with high probability by exploiting information retrieval algorithms and locality sensitive hashing. A query for retrieving semantically close files is answered with high recall by consulting only a small number (e.g., 10–20) of nodes that stores the indexes of the files semantically close to the query. Our approach adds only index information to peer nodes, imposing only a small storage overhead. Via detailed simulations, we show that our approach achieves high recall for queries at very low cost, i.e., the number of nodes visited for a query is about 10–20, independent of the overlay size.     

Ant colony optimization inspired resource discovery in P2P Grid systems

It is a challenge for the traditional centralized or hierarchical Grid architecture to manage the large-scale and dynamic resources, while providing scalability. The Peer-to-Peer (P2P) model offers a prospect of dynamicity, scalability, and availability of a large pool of resources. By integrating the P2P philosophy and techniques into a Grid architecture, P2P Grid system is emerging as a promising platform for executing large-scale, resource intensive applications. There are two typical resource discovery approaches for a large-scale P2P system. The first one is an unstructured approach which propagates the query messages to all nodes to locate the required resources. The method does not scale well because each individual query generates a large amount of traffic and the network quickly becomes overwhelmed by the messages. The second one is a structured approach which places resources at specified locations to make subsequent queries easier to satisfy. However, the method does not support multi-attribute range queries and may not work well in the network which has an extremely transient population. This paper proposes and designs a large-scale P2P Grid system which employs an Ant Colony Optimization (ACO) algorithm to locate the required resources. The ACO method avoids a large-scale flat flooding and supports multi-attribute range query. Multiple ants can be employed to improve the parallelism of the method. A simulator is developed to evaluate the proposed resource discovery mechanism. Comprehensive simulation results validate the effectiveness of the proposed method compared with the traditional unstructured and structured approaches.

基于紧缩状态表的高效数据定位方法

数据定位是松散式P2P系统面临的挑战性难题。本文提出了一种新的数据定位方法--紧缩状态表方法（CSTM）。在CSTM中,每个结点上维护一个状态表,保存了丁跳（Hop）内全部邻居上数据的关键字信息,各个结点按照状态表来转发数据定位消息。CSTM方法采用Bloom Filter技术来压缩表示状态表,采用查询Cache建立与最近访问的结点之间的快捷连接。模拟结果表明,与广播泛洪和二路随机转发方法相比,CSTM方法大大减低了P2P网络中数据定位的消息开销,并能够获得较短的查询路径长度。