One of the key challenges in ad-hoc networks is the resource discovery problem. How efficiently & 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 flooding technique floods 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 flooding 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 flooding-based search techniques, and our proposed technique. We analytically derive 3 relevant key performance measures, i.e., the avg. number of steps needed to find a resource, the probability of locating a resource, and the avg. number of messages generated during the entire search process.

MANETs are dynamic mobile ad-hoc wireless networks that use multi-hop routing. The nodes in such networks are capable of communicating using layer-3 routing in case they are not connected at layer-2 directly. The resource discovery process is very challenging in such networks as there is a continuous movement of nodes. Previously, traditional search techniques like random walk and flooding were extensively employed for the resource discovery process. In flooding, the source node transmits the packet to all the other nodes in the network. Contrary to this, the packet is randomly transmitted to a few nodes in the network in the random walk approach. Although both approaches have some disadvantages, they are used in MANETs as it suits the self-organizing nature of the network. Several previous research works have studied the effectiveness of peer-to-peer (P2P) resource discovery approaches for wired networks. The effectiveness of several content searching techniques is tested for the P2P network. But, due to problems related to energy consumption, mobility, infrastructure deficiency, and churn, their performance is not validated against MANETs.

Noor et al. [

Combining P2P network properties in mobile ad-hoc networks is coined as P2P MANETs or Mobile P2P networks. Due to similarities in P2P and MANETs, a P2P overlay can run over Mobile Ad-hoc Network. An overlay network is formed by communication between the peers wherein each link of overlay corresponds to a path in an underlay physical network. But, at the same time, their direct combination also poses difficulties due to differences in the operating layer, transmission mechanism, and rapid mobility in MANETs.

In such a distributed environment, resource discovery is a key issue. Unstructured P2P networks mostly rely on flooding and random walk techniques for searching. As a preliminary study, we evaluated the unstructured P2P searching techniques over MANET [^{1}^{2}

The rest of this paper is structured as follows. In Section 2, we review the existing work related to analytical based analysis for P2P and MANETs. Section 3 discusses the problem statement of modeling the physical situation. Analysis of flooding-based search procedures and our proposed scheme are introduced in Section 4, and their performance measures are derived. In Section 5, we summarize our results, and finally, Section 6 concludes the paper.

In this section, we discuss the various relevant works that estimate the performance of resource discovery protocols analytically. Although there are many empirical studies and simulation-based analyses of flooding-based schemes and its variants, the mathematical results are still lacking especially in the context of P2P networks over MANET. Efficiently and quickly locating a resource is a major issue in unstructured networks. Techniques such as probabilistic forwarding, random walk, and flooding are extensively used in such unstructured architecture. Barjini et al. [

An Overlay Graph _{ij}_{x}

Smart resource discovery is the heart of the P2P system. In ad-hoc networks, routing is expensive, so it requires a more effective resource discovery process. In such resultant networks, resource discovery is the key challenge due to frequent network dynamics. So, how the search query can be resolved quickly and efficiently while lowering the message overhead is the aim of our proposed scheme, validated further with analytical modeling.

We preliminarily assume a random network topology of

_{t} |
---|

To limit the broadcast storm, the search is bounded to the maximum

Let _{x}_{x}

Let _{t}

The derivation of _{t}

The focus of this article is on several decentralized resource discovery schemes. In flooding, when a resource is required by a node, it will communicate with its neighboring nodes and further, those nodes will communicate with their neighbors. This process will be repeated until every node in the network is communicated as shown in

Derivation of _{i}

This implies that _{t}_{t}_{t −1}. Under the assumption that within

Substituting for _{t}

Let

_{t}_{t −1} +_{t}_{t −1}, with the boundary of _{0} = _{0}_{0} = 0

Evaluating _{t}

Since,

In flooding, a node that requires the resource will flood the message to its neighbors which in turn retransmits it to their neighbors. This will continue until the node that is holding the required resource is found or the TTL expires. For better understanding, the nodes in the network are represented as a d-ary tree. To visualize the situation, refer to ^{i} different nodes in the

Let

At ‘0’ step, the probability of not locating the resource

Similarly,

Probability of not locating in Step 2

Continuing this way, if we unfold the subsequent inquiring node’s neighbors until the

From _{t −1} occurs only if it finds the required resource until the

Therefore,

Now replace _{t}

Now evaluating for different values of

Therefore, generalized as,

Hence

Next, we determine the average number of steps required to locate the resource. In general, the average steps needed are given as in

We now compute the average number of messages that will be generated for the flooding technique. In flooding, the messages are flooded through the network. A 1-hop broadcast with the message will be transmitted by the node

where,

Symbolically it means,

which has initial boundary condition of

Now substituting

In the random walk algorithm under MANET, the querying node transmits the message to a specific neighboring node

Let

where

After further evaluation we get,

The average number of steps needed in general to locate the resource

Finally, we compute the avg. generated messages in the random walk scheme under MANET which is different from that as in the wired network. The unicast transmission uses the routing layer information in a standard random walk algorithm under MANET. But the issue is that the nodes move continuously in MANETs. Therefore, there will be a rapid change of neighbors of all nodes over time. So, such transmission may often lead to failure since the topology of the network changes rapidly. Also, this leads to frequent re-route discovery which increases the message overhead. Hence, the overall message generated will be much more than the normal for each path due to the failure thereby incurring frequent re-route discovery at every hop. In such a dynamic scenario, there will be

where,

For such a path

Now substituting

To reduce the overhead in the classic random walk protocol, we proposed an improved random walk algorithm [

Let

Now,

where, 1 − _{t −1} is the probability of not locating the resource in one of

Now substituting

Hence,

In our proposed random walk technique, the probability of finding

The average number of steps needed to find the resource “x” can be found using

Next, we compute the average number of generated messages for our proposed algorithm. In our resource discovery scenario, the nodes reply directly to the querying node. If

where,

For such a path

Now substituting

We compare the three search strategies analytically with the following settings. The network consists of _{x}_{t}

The mathematical results are summarized in

Metric | Flooding | Random walk | Proposed |
---|---|---|---|

_{t} |
1 − ^{pt+1} |
||

In this work, the focus is on the general issues of resource discovery under a highly dynamic mobile P2P network. Specifically, the performance of random walk and flooding techniques related to this problem are studied. Flooding tries to locate the resource in an aggressive manner by visiting almost all the nodes and it has a scalability issue as it leads to the generation of an enormous quantity of queries. Even though random walk searches conservatively, but under MANETs, it also generates huge message overhead at each hop, and further, it takes longer search time. To overcome the above issues, we introduce a cross-layered addressed random walk scheme for MANETs which is a hybrid of random walk and flooding method that is designed considering the physical network aimed to suit such a highly evolving network. The contribution of the article is two-fold. (1) Theoretical modeling of the search algorithms, and deriving analytical measures evaluating their performances. (2) Mathematical modeling of the proposed resource discovery protocol to optimize random walk algorithm over MANETs. Such, evaluation in context to P2P MANETs is not done before. This paper focuses on improving the performance of the random walk method by lowering the message overhead, and increasing the query hit rate while lowering the query delay. We present an analytical model to estimate the performance of each studied search strategy based on the metrics including the probability of finding a resource, the mean of steps needed to find a resource, and the mean of messages generated while finding a resource. The derived parameters are one of the most important performance metrics in MANET. As future work, we decide to validate the theoretical results through simulation experiments. We further also plan to model our game theory-based resource discovery algorithm.

We are thankful to all the collaborating partners in the presented study.