Searching Methods of MP2P Based on Diffusion Strategy of Resources Index

Published Online April 2011 in MECS

The P2P network has had great success in the Internet, while the wireless communication technologies have rapidly develop. P2P technology and wireless communication technology combined with each other in the academic and industrial field. Thus organically combining the advantages of both to better meet customer demands of accessing the information anytime and anywhere is becoming a hot research. MP2P as the integration of mobile technology and P2P network model is an important development in the application of the future wireless networks. The combination of P2P and wireless communication is the mobile peer to peer network (referred to as the MP2P network, also known as mobile P2P network). MP2P is network layer above the session layer overlay network (Overlay), which superimposed on the mobile network environment. Directly achieving resource sharing between mobile devices and service coordination is its main function. Currently, MP2P network can be divided into two types: one is based on Ad Hoc, and the other one is based on cellular networks. Researching on the MP2P network and its industry has important practical significance. It not only can enhance the coordination capacity in the field of military battle and the task of disaster relief, but also accelerate the free flow of information between mobile users sharing of their resources. [1, 2]

MP2P based on P2P fully distributed network technology and mobile network, has good scalability, robustness, cost-effective, flow balancing, and low cost of self-organization, and also adapt to the user’s request of connection to the network at any time. However, due to the inherent mobility of MP2P nodes, it leads to a lot of technologies, which are relatively mature in p2p, can’t be directly applied in MP2P, such as: topology changes frequently, no unified network layer routing algorithms, long delay and so on. The situations lead to MP2P Research and Exploration facing some serious challenges in the resource location:

• A.    Lack of Effective Mechanisms for Resource Discovery

The mobility of MP2P peers is unpredictable, and network topology is prone to changes.However, the traditional classic search methods in P2P network, without mobility handling mechanism. So, in the wireless environment, traditional P2P protocol can’t carry out effective searching resources. One of the most important challenges to face is to promote the accuracy and the effect of the resource location.

• B.    The Difficulty in Maintenance of Locate Route

MP2P network was characterized by its peers with mobility. The peers frequently mobility directly leads to overlay network topology (the logical topology) are fluctuation. MP2P cannot be timely and accurately reflect the actual connection status information (physical topology). In addition, electromagnetic wave is the main transmission medium of theMP2P Network. It has the defects of limited scope and vulnerable to interference. The defects increase the randomness of mobile nodes joining and leaving the network. That increases the difficulty of the system in timely manner getting location information, accurately reflecting the status of nodes.

• C.    Itself Limits of the Network and Mobile device

Except for many problems caused by mobility of nodes, limited bandwidth of individual nodes and the volatility of MP2P network caused by the network signal attenuation are the other characters of MP2P.In addition to the mobile device battery life is shorter, less computing power, storage space for smaller, which lead to the connectivity of network nodes as being difficult to maintain management. Therefore, in the premise of handling mobile nodes, how to avoid too much redundant data into the network increased the network load, to reduce the processing tasks of the mobile nodes, rational design of lightweight resources search for construction MP2P model is the key to success.

Today an important basic research is designed on a method for the resource location of MP2P. But researchers pay most attention to design a search algorithm on specific model, failed to solve the movement and accurate fast positioning. The diffusion index of resources in the direction of resource providers is proposed, so as to increase the efficiency of resource location.

• II.    R ELEATION W ORK

Search for resources concentrated in the resource representation and resource search algorithm. Common methods of resources that mainly include the index method of using of resources, compress the bulk of the resource data, which reduces the amount of data transfer information. Small amount of index data resources, light query algorithm, is a good carrier of the resource request algorithm. Researchers study the index of resources focused on the index data structure, indexes the contents of the organization and manner of publication of the index three. One index the order of the index data structure often is divided into: inverted index [3], the index tree [4, 5] and distributed indexing [6].The order of the index search algorithm is simple but a longer delay, inverted index and the index tree data structure using a hierarchical index find the index of the time reduction, subject to the introduction of buffer space. Distributed index be satisfied with reducing the time and space requirements, but the network structure is fit for distributed. The article used the distributed index structure in conjunction with the tree-index method.

Most resource search algorithm is fit for a particular MP2P architecture. Reference [7] investigates finding and sharing of resources of the social network of the cell phone. The proposed query mechanism allows mobile users communicate with each other for resource located on three criteria: the limited depth of inquiry; avoid redundancy query; known path query. Although to some extent its mobile customers to solve the transfer request message, but the drawback is an increase in the request packet path information query mechanisms to put the network will increase the amount of data, limited bandwidth, large-scale mobile communication networks. It is availability to be studied further. JiuJun Cheng in Beijing posts and telecommunications university put forward a simple and effective search mechanism for the index server [8].The results showed that, comparing searching method with the index server proposed and flooding search mechanism for mobile P2P systems, it reduces the energy cost to make up for the lack of mobile terminals. But when the resource request nodes and destination nodes are in different cellular networks, the repeated requests for the same resources go through the index server every time that will bring great delay and unnecessary bandwidth overhead. Researchers at the University of Sydney proposed the diffusion mechanisms based on the epidemic algorithm in mobile Ad hoc network. The method is on the structure of intermittent network connectivity of MANETs (ICMANs). It uses infectious disease model to search resource content. And it uses the cache to speed up the positioning speed. When the user terminal to download the free content of interest to the content identifier information, it uses flooding request to locate the relevant keywords in the network. The researchers also compared the different cache update method. While it only spread resource keywords in infectious diseases model. Even if it can find resources key, it can’t accurately locate the place that the resources are stored.

A feedback spread algorithm is proposed for MANET based on the infectious diseases model in [10]. This algorithm is used in mobile networks, adapt to the dynamic requirements of mobile networks, and achieve the purpose of proliferation. Researchers study disconnected epidemic routing process of building in mobile Ad Hoc network, which is based on the waveform model of mobile networks. The routing model is built by broadcast or unicast in the epidemic ： When the node contained the information and non-information node are in the same communication domain, the nodes contained information "infect" nodes non- messages contained. The proposed method completes diffusion resources in the MANET. But it is lack of consideration of MP2P peer node mobility and file-sharing, it cannot adapt to the transmission mode in MP2P.

Integrated all of the above results, resources Index information has the unique advantage in the resource identifier. It can give a comprehensive characterization of resources, but also has a low amount of information. Existing MP2P resource location methods cannot solve resource location process mobility and randomness of nodes. Location methods are proposed for a specific model, and the adaption failure to meet user requirements. In such cases, resources location is combined with node orientation. Directly meeting users’ resource application, resource location method is designed in both sides of resource providers and requesters. So as to achieve efficient, rapid and low positioning purposes.

• III.    R ESOURCES I NDEX R ELEASE

The model that researching on is fully distributed architecture model without control services, which is accepted by mainly researchers. [11] Ordinary nodes are distributed network and registered to the neighbor nodes, and the states of nodes are defined in the epidemic model. The structure of resource index is divided into different parts. The contents of resource are the keyword of it and the necessary information that will be used in the progress of resource location.

• A.    The Contents of the Index of Resources

Resource index is the data structure to show the content of the resource. If includes resources for key (RKEY), resource identifier and resource location information stored. To better finishing this purpose, the contents of index is organization in different parts. The key of the resource is calculated by Hash (RHash). The resource ID (RID) and the file ID (FID) are used to distinguish different resources. The content of FID can be getting with the release time of the file "and" random numbers got from progress. It means that FID=Time of Releasing(s) +Random. Storage locations of resources is representation of sub-ID, MAD = IP + MAC. MAD is multi-level address. IP is the IP assigned to the mobile terminal and variable. The fixed MAC address for the mobile terminal is not moving with the position change. The contents about the index of resources are shown in Fig 1.

Time of Register File + Random

RKEY

IP of Node

MAC of Node

Figure 1. The content of index

• B.    Organization of Resource Index

Resource index is stored in different nodes. When positioning of resources, resource index is queried. The contents of index will be able to designate the nodes that storage the targeting resource to complete the process. Index in the general nodes is storage of order structure. The index is reverse order by retrieved times.

• IV.    T HE D IFFUSION O F RESOURCE INDEX

The fundamental characteristics of MP2P are fully distributed network model without central control, and the dynamic change is strong. Release its index to the network is an effective means to reduced energy consumption and improves the positioning effects. Diffusion is an important way to increase the amount of information resources in network. By the diffusion of resources, resource requests can effectively improve the corresponding speed and reduce the search delay. Taking into the large amount of information resources and data, spreading all the data to the network is not realistic and will generate a lot of redundant data, leading to the collapse of the network, so take use of releasing index of resources. Resource index is a microcosm of resource data. It can effectively identify the resource information and reducing the amount of information. To spread the resources index to the network can achieve the purpose of increasing the amount of information, without a tremendous burden of network channel.

• A.    Diffusion Index

Epidemic model as a mathematical research model is a good application prospects in this unstructured distributed P2P network. Epidemic model has three categories nodes: S class (Susceptible), refers to the nodes who are not infected, but are infection source of the objects; I class (Infective), refers to the objects with infectious disease. It can spread diseases to the S class members; R class (Removal), refers to the objects those are isolated or not infected objects. There are many epidemic models. Typical ones include SIR (susceptible infected removed) [12, 13] and the SIS (susceptible Infected susceptible) [14, 15]. SIS model mainly considers the objective state of the infected objects, emphasizing the infectious process. But transmission node statues maintenances are ill-considered. SIR takes into all possible statues of nodes in the transmission process, but is poor ability in the maintenance of the network link. The behavior on the proliferation of P2P resources is analyzed in paper [16]. Diffusion of resources plays an important role in the network resource management, which mathematically verify. To effectively manage P2P network, according to epidemic model of complex networks (SIR), A MP2P resource diffusion model is established. The mathematical expression of abstracted resources diffusion capacity and resources successfully location rate is got by mathematical derivation and discusses the diffusion resources of P2P under certain conditions. The results analysis the feasibility of diffusion to be used in the application of the P2P network in mathematical theory, but doesn’t give specific methods in practice. Consideration to the advantages and disadvantages between the two network models, the article decides to use the SIRS model (short-term immunity removed susceptible) [17].Consideration to the advantages and disadvantages between the two network models, the article decides to use the SIRS model (short-term immunity removed susceptible) [14]. It is able to control proliferation, and ensure the connectivity of the network path.

As the disease spread in complex networks is equal probability distribution, the transition between three states as shown in Fig 2, we get:

SN(t)+IN(t)+RN(t)=1 (1)

SIRS, in combination with the advantages of the SIS and the SIR, uses short-term immunity, making the removal nodes in the secondary infection to ensure the effectiveness and continuity of resources diffusion path. Network nodes are in 3 categories: susceptible node (SN), the infected nodes (IN), recovered node (RN). SN: refers to the nodes in the transmission path which are not infected but infective. It can diffuse resource index.

Figure 2. State transition

• •    IN: refers to the nodes that received spread of the index. It can diffuse index to the SN class members;

• •    RN: refers to the nodes that have received the contents of spread index. This class is now only forwards the message, not backed up and diffusion.

SN (t), IN (t), RN (t) mean the probability of node in three different states at time t. α, β, γ, δ1, δ2 mean the probability of conversion between the three states.

• B.    Implementation of Diffusion

In the SIRS model, each node in the process of joining the network is in the state of SN, in order to complete the network of the communication path establishing, maintaining the continuity of the network channel. When the ordinary nodes push its own resource index into the network, it initialized its concentration of resource request (CRR), download diffusion function of epidemic, and the initialize trigger threshold (TT) of epidemic function.

• •    CRR = times of resources visited / times of node visited.

• •    EDF: diffusion algorithm designed from epidemic algorithm, mainly about diffusion direction and definition the extent .

• •    TT: the threshold of trigger diffusion function, controlling the amount of diffusion data.

With the node activities, the amount of request increasing, then ultimately is up to TT of EDF to begin the diffusion of resources. Write the resource indexes that reach the TT to the proliferation table. EDF is used to spread the information to other nodes in the SN status. The algorithm uses the spread hops are 7. Diffusion algorithm is shown in Fig 3. TT can avoid too much amount of proliferation data so as to waste of network bandwidth resources, increase network load and lead to network collapse.

• Figure 3. Diffusion Process

• C. Maintain the Proliferation Resource Index

The network will appear a lot of resource index back up after diffusion. It can undoubtedly increase positioning speed and reduce the positioning time delay. However, it will bring a lot of redundant data to the network, and network load increase exponentially. After the diffusion index information resources, the nodes use the time decay function to process the receiving information. By the analysis of network traffic, the indexes that decay to 20% CRS following resources index information exist too long in the network and its access rate is not high. So they are removed to long information index table, the high-speed cache can be reasonable used, and reduce the amount of information indexed. In addition, the source information nodes circularly release resources index information in a time interval to refresh the resource index information content and CRS value in destination nodes. The purpose of that is to announcement of the source nodes’ survival and to ensure the credibility of the index information that the source nodes provided. The specific process can be expressed as:

• •    Records received index information resources index information recorded into the table of local resources;

• •    Initialize CRS =15;

• •    Receives the request, refresh CRS in accordance with the results;

• •    If CRS <20% initial value, remove it into the old information index table, otherwise continue to previous step.

In epidemic model, the node in the state of RN can’t continue to disseminate information. To ensure the channel connectivity, the article uses short immune status to keep the contradiction balance between the Characteristics of MP2P and an epidemic model. When the mobility of nodes damaged stability of network link the node is set to state set R, enable short-term immunization (SI), thus avoiding the instantaneous topology changes frequently. It is used to maintain the network connectivity and channel stability.

• V.    R ESOURCES L OCATION M ETHODS B ASED ON THE SIRS AND THE N UMBER OF I NDEX

In the previous section, the design methods achieve the resource provider spreading their own resources information, importing a large number of resources index information to the network. This information combines nodes and resources. It can directly search resource to overcome the shortcomings resulting in traditional resources search method fragmentizing resources and nodes.

• A.    Search route construction method Footnotes

Construction of the route search is the first step. All resources should have to be launched on this basis. The diffusion resources are used to establish the direct links

Index between resources and nodes, and locate resource based on such information.

The establishment of searching route is based on the above model about diffusion index information. The resource requests are send to the nodes in the IN set. The nodes in IN are the sender of the resources index information, which are resources index information provider. Meanwhile, the three states of SIR is probability distribution. The sizes of resource index and nodes status information are introduced to trade-off locating. The right of node is defined:

CT_rpp = ( δ × Status_N + ε × Total_Nr ) * φ β

^δ , ε and φ are the rights; a us ^N are the status of node, setting IN=2,SN=1,RN=0; o a ^Nr is the size of resource index. Combining the above two parameters the node weights are defined. Node transfers resource request to the nodes whose weight is the largest. Thus completing the establishment of heuristic search route is based on node status and the size of resource index. Request process is as follows:

• •    Node gets together the received index information these get TT , index r;

• •    Ask for the state of all adjacent points, get Status            Total

N , as well as Nr .

• •    According to the formula 2, calculate and record the node N next with maximum CT_rpp ;

• •    Forward resource request information to N next ;

• •    Repeat preview step until request reaches the corresponding node.

• B.    Maintenance Method about Searching Route

The fundamental characteristics of MP2P are the nodes’ mobility and randomness of logging in/logging out. Therefore, maintenance the request routing is the basic problems of application to ensure the smooth of locating. Redundant routing schemes are proposed to maintenance the routing. Redundant routes establishment complete in the first hop of request message transfer. The first hop messages are forward to all the neighbors and their neighbor route in accordance with established methods to establish the search route. Thus the establishment of redundant routing is completed, and achieving a smooth transfer of resources.

• VI.    S IMULATION A NALYSIS

In order to verify the efficiency of the algorithm, we spread from four aspects to prove: the success rate of the resource positioning, the network load, the time delay of locating, and the scales of network. The test uses NS2 platform to validate and evaluate the proposed method. Mobile nodes randomly distributed in the 800m × 800m rectangular area within the coverage area of nodes are 250m, bandwidth of 2Mb / s. In the test there are a total of 600 different size resources randomly distributed in the mobile nodes, the transmission radius is set to 7 hops. The node use Random Waypoint mobility model (Based on the random path of ad hoc network mobile model, the mobile node speed, direction and purpose are independent randomly selected),the pause time is 20s, simulation time is set to 1000s.Mobile node issued resources positioning news time at intervals between the 3s ~ 10s.

Firstly, preheat the network experiment, which means the nodes registration to network, the establishment of initial network connection.

Over time, some nodes meet the requirement for diffusion the resources index information, which provide the basis for the resource location information. Based on this index information, the EIRS methods are used to resource location. Collecting the experimental data and comparing results, the effectiveness of the proposed method is verified.

• A.    Success Rate of Localizations

The success rate of localization can determine the publishing method to join diffusion mechanism significantly improved the application efficiency of the network. The results compared the difference between the resource localization method with index diffusion mechanism and without using index diffusion mechanism of resources positioning success rate. Resource request for the request algorithm using random walk search algorithm, using K = 7, K Road random forwarding the request. The results are shown in Fig 4. In the Fig 4 we can see the introduction of the diffusion mechanism source index K road random forwarding positioning can well improve localization success rate, positioning it to the high success rate close to flooding search methods.

Figure 4. The success rate

• B.    Bandwidth and Loads

Because MP2P node's ability is limited, mobile interconnection wireless channel bandwidth constraints, frequency instability, so they requested resource locator of the localization algorithm used lightweight as possible to reduce energy consumption, make the mobile nodes can be more long-term in working condition. Experimental results of three methods in comparative can meet the needs of the premise of the efficiency of resource location, network load changes. Fig 5 shows the test results, the longer request time interval, the lower the network load, network, the less number of messages delivered. Compare three search algorithms we can know: flood query method has the largest network load flow, distributed Chord algorithm produces lowest network load .This paper presents a method with the spread of infectious diseases, K Road, random walk method, the diffusion of making the network load much more than general random search method, but it will not produce excessive amount of information that not be tolerated.

Figure 6. The time delay

D. The Scale of network

• C.    Positioning time delay

Since the mobility of MP2P nodes can cause the network can’t maintain a stable routing for a long time. Therefore, resource locating method requires a shorter delay within the request, in the rapid response of resources. The results are compared time delay between the propose method with the diffusion mechanism of resource location index method and the method without diffusion in the resource location. The result is shown in Fig 6. It can be seen from the chart data, flood localization approach targeting the largest delay, respond slowly. Structural Chord method has the shortest delay due to the introduction of hash method that reduction the number of hops to forward the message. The EIRS method is close to the structure of the CHORD method. The positioning time is short, and response faster.

Figure 5. Network load

The number of network nodes Reflect the adaptation of proposed method is an important symbol. EIRS method can achieve localization in the demand with increasing the number of network nodes. That means the proposed method has a good scalability of the application. It can meet the growing network needs.

The results in Fig 7 show that when the scale of network is small, the 3 searching methods have similar success rate of resource location. But with the increments of the amount of nodes, all the methods’ success rate rapidly decreases. The flooding one decrease fast, the structural one decrease lowliest, and the EIRS is close to the flooding one. It means that the proposed EIRS scalability is adapted to the incresement of network .It is suitable for the modern network development.

Figure 7. The scale of network

• VII.    C ONCLUSIONS

The key of MP2P network resources index release is index effective maintenance and resources diffusion, thus ensuring the efficiency of resource release, providing strong support resources accurate positioning and transmission .The method this paper put forward can be used on whole distributed mobile terminal, universality, regarding the network hierarchy no property requirements, can satisfy the requirements of MP2P resource sharing .The release and the search of resources is a pair of reciprocal and mutually supporting technology, so the key of future work is more focus on lightweight and specific requirements of weak search algorithm, making MP2P can better applied in real life.

A CKNOWLEDGMENT

T This work was supported, in part, by the Key project of the 11th Five-Year Plan of the National Defences PreResearch Foundation (Grant No. 513XXX602), by Scientific and Technological Project of Heilongjiang Province (Grant No. GC09A104), by the fund of Harbin (Grant No. 2010RFQXG026), by the Fundamental Research Funds for the Central Universities, and by National Natural Science Foundation important project(90718003).