دانلود رایگان مقاله محل منابع بر اساس محاسبه گام های تصادفی جزئی در شبکه پویا

Abstract

The problem of finding a resource residing in a network node (the resource location problem) is a challenge in complex networks due to aspects as network size, unknown network topology, and network dynamics. The problem is especially difficult if no requirements on the resource placement strategy or the network structure are to be imposed, assuming of course that keeping centralized resource information is not feasible or appropriate. Under these conditions, random algorithms are useful to search the network. A possible strategy for static networks, proposed in previous work, uses short random walks precomputed at each network node as partial walks to construct longer random walks with associated resource information. In this work, we adapt the previous mechanisms to dynamic networks, where resource instances may appear in, and disappear from, network nodes, and the nodes themselves may leave and join the network, resembling realistic scenarios. We analyze the resulting resource location mechanisms, providing expressions that accurately predict average search lengths, which are validated using simulation experiments. Reduction of average search lengths compared to simple random walk searches are found to be very large, even in the face of high network volatility. We also study the cost of the mechanisms, focusing on the overhead implied by the periodic recomputation of partial walks to refresh the information on resources, concluding that the proposed mechanisms behave efficiently and robustly in dynamic networks.

7. Conclusions

We have proposed a mechanism to locate a desired resource in randomly built networks with dynamic resource behavior (resource instances can appear and disappear) or dynamic node behavior (nodes can join and leave the network). The mechanism is based on building a total walk with partial walks that are precomputed as random walks and available at each network node. When precomputing each partial walk, information on the resources held by its nodes is stored and associated to it. This information is used by the searches, so that they can jump over partial walks in which the desired resource is not located. Two versions of the mechanism have been described. In the choose-first version, one of the partial walks at the current node is randomly chosen, and then checked for the desired resource. In the check-first version, all the partial walks of the node are checked for the resource, and then one is randomly chosen among those in which the resource was found. We have presented an analytical model that predicts the expected search length achieved by the two versions of the mechanism. Simulation experiments have been used to validate the model and to assess the effect of resource and node dynamics. We have found that the choose-first version achieves large reductions of the average search length in relation to searches based on simple random walks. These reductions remain significant even in the face of high volatility of resources or nodes. The check-first version produces larger reductions as we increase the number of partial walks precomputed at each node (at the corresponding extra cost). Results have been found to be very similar for networks with different degree distributions (k-regular, Erdos-Rényi ˝ and scale-free). Finally, we have analyzed the cost of the PW-RW mechanisms, concluding that the choice of the length of the PW precomputation interval does not have a significant impact on the cost in a wide range of interval lengths. An interesting future work line for this study is to measure the improvement in the search length that can be obtained by using different strategies to choose one of the partial walks available in a node. Another possibility to shorten search lengths is to use more intelligent (and more costly) variations of random walks instead of simple random walks.