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

Ajay Arunachalam,Vinayakumar Ravi,Moez Krichen,Roobaea Alroobaea and Jehad Saad Alqurni

1Centre for Applied Autonomous Sensor Systems(AASS),Örebro University,Örebro,Sweden

2Center for Artifcial Intelligence,Prince Mohammad Bin Fahd University,Khobar,Saudi Arabia

3Faculty of CSIT,Al-Baha University,Saudi Arabia ReDCAD Laboratory,University of Sfax,Tunisia

4Department of Computer Science,College of Computers and Information Technology,Taif University,P.O.Box 11099,Taif,21944,Saudi Arabia

5Department of Education Technologies,College of Education,Imam Abdulrahman Bin Faisal University,Saudi Arabia

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

Keywords: Mathematical model; MANET; P2P networks; P2P MANET;unstructured; search algorithms; Peer-to-Peer; ad-hoc; fooding; random walk; resource discovery; content discovery; mobile peer-to-peer;broadcast; peer

1 Introduction

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 fooding were extensively employed for the resource discovery process.In fooding, 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 selforganizing 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 defciency, and churn, their performance is not validated against MANETs.

Noor et al.[1] studied the effectiveness of the random walk approach for MANETs and they have discussed its issues like unicast transmission disadvantage, valid termination check parameter, next-hop selection criteria, etc.P2P networks are very common, and they constitute a majority of internet traffc [2].P2P networks are known for their fexibility and distributive network properties and P2P based systems are employed over the internet for services like video conferencing applications, torrent applications, information retrieval systems, telephony, fle sharing, etc.Based on the architecture design, the P2P networks are categorized into 2 types.One is the structured type, where the peers are strictly well-organized with each peer maintaining a DHT index.Some of the cases that belong to this type are Tapestry, Pastry, Chord, CAN, etc.In this type, since the involved peer positions are structured, the query searches are more effective.But these systems have major shortcomings in a mobile ecosystem mainly due to peer churn.Due to rapid movement, index pointer is required to be altered constantly which increases overhead and complexity.Contrary to this, there are no strict rules for forming topology and placement of the peers in the unstructured type.Further, there is no need for any central indexing and nodes join arbitrarily.Some of the cases that belong to this type are Freenet, Random walk, Kazaa,Fastrack, Gnutella, etc.In a fully distributed P2P system, every peer has an equivalent role in the network.Centralized architecture is used for most mobile communication even today and the bottleneck issue created by them can be overcome by employing the P2P platform [3].This P2P based approach suits wired and wireless networks including MANETs.

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 diffculties 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 fooding and random walk techniques for searching.As a preliminary study, we evaluated the unstructured P2P searching techniques over MANET [4,5].According to our study, the pure random walk approach under MANETs consumes more battery power,increases network overhead, has high search latency, and lowered hit rate when compared to other unstructured protocols.To overcome this, we proposed a resource discovery protocol based on the cross-layered architecture to suit better and work well under P2P-MANETs as shown in Fig.1.It is essential to take the topology of the underlying physical links into consideration when developing an effcient search strategy for such dynamic evolving networks [6–8].For the same,we proposed an alternate technique for discovering the neighbor nodes and extracting the node density information for P2P applications running over MANET as given in Algorithm 1, whose source code is publicly available in SourceForge1https://sourceforge.net/projects/neighbordiscovery/and the complete P2P network resource discovery simulation over mobile ad-hoc network with our proposed neighbor node discovery method is publicly available in GitHub.2https://github.com/ajayarunachalam/Neighbor-Discovery

Figure 1:Proposed addressed cross-layered architecture

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 fooding-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 fnally, Section 6 concludes the paper.

2 Related Works

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 fooding-based schemes and its variants, the mathematical results are still lacking especially in the context of P2P networks over MANET.Effciently and quickly locating a resource is a major issue in unstructured networks.Techniques such as probabilistic forwarding, random walk, and fooding are extensively used in such unstructured architecture.Barjini et al.[9] analytically review many search techniques that are based on a fooding approach for an unstructured P2P network.They measure the coverage growth rate and traffc loads for each scheme.They introduce a metric, i.e., the critical value which is the ratio of the amount of redundant messages over the coverage growth rate.According to their study and simulation results,the probabilistic limit-based fooding schemes (i.e., teeming, modifed breadth-frst search, random walk, etc.) have better performance than the TTL limit based fooding schemes (such as local indices, expanding ring, iterative deepening, etc.).Bisnik et al.[10] present an analytical expression to measure the performance metrics of random walk protocol in unstructured P2P networks in terms of TTL of walkers, count of walkers, and demand of the resource.Their work focuses on a wired P2P network.Dimakopoulos et al.[11] study the performance of teeming, random path,and fooding search schemes, in P2P systems.Their study considers two scenarios, i.e., resource requests in the presence of popular and unpopular resources.Further, they assume that a cache is used to store the details of the resources and their corresponding resource providers at each node.To overcome the drawbacks observed in fooding and random walk techniques, Lin et al.[12]propose a technique that is the combination of both schemes.Depending on the search context, it performs fooding for a short-term search and follows the random walk technique for a long-term search.They use Newman’s work [13] for the random graph and adopt generating functions to model distribution degrees.An alternative to the fooding scheme is the gossip protocol, where every node transmits the message to a subset of its neighbors in a random fashion based on some probability.In [14], costs of Gnutella’s fooding-based broadcasting and the classic gossip protocol are studied by varying network size and the average number of neighbors.Further, they calculate the bandwidth required for each node in the fooding mechanism.They propose a deterministic gossip-based protocol and compare their performance with the fooding technique.Ferretti [15]proposes a mathematical model for the gossip-based resource discovery protocol in unstructured P2P overlay networks.Their analysis is based on complex network theory.They analyze and evaluate the count of nodes receiving the query and the amount of query hits.Specifc work to model and optimize random walk protocol over MANET is presented in [16].They modeled their method using a queuing system called G-network which has positive and negative kinds of customers.Further, they used the gradient descent method to optimize their method which uses 3 parameters such as consumption of energy, response time, and hit rate as part of the cost function.Most of the aforementioned works are evaluated over a wired and fxed layout like the internet.Further, in the case of analysis and evaluation of P2P content searching techniques under MANET, there is a lack of empirical study that considers the underlay network topology.A game theory-based resource search algorithm is proposed in [17].In their work, a Rock-Paper-Scissors-Game-Based (RPSGB) strategy is deployed for resource discovery to complement mobile P2P networks.We apply the probability and queuing theory concepts to model the unstructured search techniques over MANET.

3 Problem Specifcation,and Analytical Modeling

An Overlay GraphOG=(V,E)is used to represent a P2P overlay network, whereVis the count of nodes, andEis the count of links.The vertices and the edges of this graph represent the participating peers and virtual links respectively.Therefore,OGcan be explicitly defned as,OG=(V,E)where |V|=p andlink(i,j)∈Eifiis a neighbour ofj, and vice versa, andpis the count of peers.The underlay structure is formed by ad-hoc and peer nodes.Under MANETs, the P2P platform is implemented as an overlay network at the application layer, formed by communications between the peers wherein each link of the overlay is supported by a path in the underlay physical network.In our analysis, the underlay structure is considered as a connected graphCG=(V,E)where |V|=WNandlink(i,j)∈Eif and only ifDij≤TxwhereWNis the count of wireless nodes, andDijis the Euclidean distance between them.If the Euclidean distance between 2 nodes is less thanTx(transmission range of the node), then it means that they are in the transmission range of each other.Fig.2 depicts the above explanation, where each virtual link of the overlay network is supported by a path in the underlying physical network.

Algorithm 1:Neighbor discovery with density Procedure neighbor discovery(){create neighbour array if (strcmp(argv[1], “neighbour_list”)==0) then initialize neigbhour_list array point to the frst element in neighbour cache from AODV_Neighbour for each neighbour link to neighbour →next node obtain the address of the neighbour append AODV routing layer neighbour list information to neighbour array pass this information to the P2P application}Procedure node density(){if (strcmp(argv[1], “neighbour_count”)==0) then initialize nbrs=0 point to the frst element in neighbour cache from AODV_Neighbour for each neighbour link to neighbour →next node increment and update nbrs pass this information to the P2P application}

Figure 2:P2P Overlay running on MANET

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 effciently while lowering the message overhead is the aim of our proposed scheme, validated further with analytical modeling.

We preliminarily assume a random network topology ofNmobile nodes where only one node provides the resourcex, and there is a single nodeSsearching for that resource.Each node knows itsdneighbors.We use the work done in [11] as the basis for our further analysis.Tab.1 contains the summary of the notations used in the model along with their descriptions.

Table 1:Notations used and derived.

To limit the broadcast storm, the search is bounded to the maximumtnumber of steps (i.e.,TTL value).Let us assume thatFis the probability of resourcexbeing known to a specifc node.A node can know a resource only when it holds that resource.

F=1 −P[the node doesn’t hold x]

Letnxbe the count of nodes offering the resource “x”.Since a resourcexis offered by only one node, we havenx=1.

Letabe the probability that a node is not aware of the resource.So,a=1 −F.LetQtbe the probability of fnding a resource withintsteps.We assume that withintsteps, a resource can be located.Hence, the mean of steps needed to fnd the resourcexis given as,

The derivation of Eq.(3) is given at the end of the section.In the equation,Qtdepends on the searching strategy.We consider fooding, random walk and our proposed addressed random walk methods which are depicted as a d-ary tree that unfolds as the search progresses, shown in Fig.3.A tree representation may not be perfect for representing such wireless network topology as many nodes may overlap each other’s range and, multiple nodes may communicate with a single node.Yet, the tree representation can visualize the search scenario pictorially.

The focus of this article is on several decentralized resource discovery schemes.In fooding,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 Fig.3a.The fooding method can fnd a resource without any hierarchy or prior specifc information about the system, thus an ideal candidate in such dynamically evolving networks.One of the disadvantages of this pure fooding method is that it increases the network traffc exponentially.Therefore, another variation of fooding called random walk is considered.This method restricts the search space by restricting the node to communicate only with one of its neighbors in a random fashion as presented in Fig.3b.The limitation of this method is that it takes more steps to fnd a resource.Both the abovediscussed schemes have their drawbacks and limitations.From our preliminary study [4,5], we observe that the random walk scheme under MANET increases the network overhead, battery power consumption, bandwidth usage, search latency, etc.And, further has a low success ratio.To overcome these issues, we propose a simple and lightweight resource discovery technique to suit well under MANET where the node propagates the inquiring message to exactly one of their neighbors at each hop, but at the same time end up unfolding different virtual paths concurrently,as shown in Fig.3c.So, it will lower the network traffc even without restricting the search space.

Figure 3:Comparison of different fooding-based search strategies and our proposed scheme.(a) Flooding, (b) random walk (c) addressed random walk

Derivation of Eq.(3):Letsiis the probability of fnding a resource inith step exactly.The probability of fnding it withint≥1 steps is formulated as:

This implies thatst=Qt−Qt−1.Under the assumption that withintsteps, the resource is found, the probability of fnding it inith step exactly is given byand the mean of steps is given by:

Substituting forst, we obtain:

Letgt=Qtthe recurrence takes the following form:

gt=gt−1+tQt−tQt−1, with the boundary ofg0=S0Q0=0

Evaluatinggtwe get,

Since,gt=follows,

4 Performance Analysis

4.1 Flooding Algorithm

In fooding, a node that requires the resource will food 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 Fig.4 , where the resource requesting nodeSis the root and nodeDholds the resource being searched.Fig.4a shows a sample network where fooding technique is used while its corresponding rough d-ary tree representation is shown in Fig.4b.Within consecutive search steps, the tree will contact at mostdidifferent nodes in theith level.

Figure 4:Searching using naive fooding technique (a) searching using broadcast by fooding technique (b) d-ary tree representation

Letbe the probability to fnd the resourcexwithintsteps for the fooding algorithm.Fis the probability that a resource is known to a node and ‘a’ is the probability that a resource is not known to a node.Hence,a=1 −F.

At ‘0’ step, the probability of not locating the resourcexis given as,

1 −=Probability of not locating the resource within “1” step

1 −=Probability of not locating in 0 step ∗Probability of not fnding in Step 1

Similarly,

1 −=Probability of not locating in 0 steps ∗Probability of not locating in Step 1 ∗

Probability of not locating in Step 2

Continuing this way, if we unfold the subsequent inquiring node’s neighbors until thetsteps,then the probability of not locating resourcexis generated as,

From Eq.(4), it is clear than the initial boundary condition is= 1 −a=F.The probabilityQt−1occurs only if it fnds the required resource until thet−1 levels of the subtree.

Therefore,

Now replace 1 −asqt, so Eq.(6) becomes,qt=a∗(qt−1)d.Solving further we get,

Now evaluating for different values oft,

Hence Eq.(7) becomes,

Next, we determine the average number of steps required to locate the resource.In general,the average steps needed are given as in Eq.(3).Now substituting Eqs.(8) in (3), we get the average number of steps required to fnd the resource withintsteps for the fooding algorithm fort≥1.

We now compute the average number of messages that will be generated for the fooding technique.In fooding, the messages are fooded through the network.A 1-hop broadcast with the message will be transmitted by the nodeS.Once the message is received by the 1-hop neighbors,the processed messages list will be updated with the newly received message’s sequence ID.This is done to avoid retransmitting the same message again in case if the message is received again through a different path.Now, if the required resource is held by a neighboring nodeD, an exclusive multi-hop reply will be transmitted by nodeDthrough the path resolved by routing protocol to the sourceS.However, even after the transmission of the resource reply message,the request message may be forwarded meaninglessly by all the other nodes that have received the request until every node in the network is reached.So, under MANETs, “d” messages will be generated by “d” neighboring nodes of the root, plus for the internal subtrees of those neighboring nodes.Thus,

where,m(t−1)denotes the transmission along the subtreeTwith(t−1)levels.In a subtreeT,if the resourcexis located at the root, a response will be sent to the querying node or elsedmessages will be generated by the child nodes plus the generated messages internally for each respective child subtreesTwith(t−2)levels.

Symbolically it means,

m(t−1)=F+(d+dm(t−2))∗(1 −F)

m(t−1)=1 −a+ad+adm(t−2)

which has initial boundary condition ofm(0)=1.After evaluating the recurrence, we get,

Now substituting Eqs.(12) in (11) and evaluating further we have,

4.2 Random Walk Algorithm

In the random walk algorithm under MANET, the querying node transmits the message to a specifc neighboring nodenthat is selected in a random fashion from a list of neighbors resolved from the routing layer information over a unicast transmission.For such a random walk scenario,there will beprandomly unfolding paths to reach the destination, i.e., the node sends the request top≥1 of its neighboring nodes and each of those neighboring nodes will unfold a random path of which one possibility is shown in Fig.5.

Figure 5:Searching using simple random walk technique (a) searching the network using classic random walk protocol (b) d-ary tree representation

Letbe the probability of fnding a resource withintsteps for the random walk algorithm wherepis one of the randomly unfolding paths of lengtht−1.Fis the probability that a resource is known to a node andais a probability that a resource is not known to a node.Hence,a=1 −F.At “0”, step the probability of not locatingxis given as,

1 −=1 −F=a

1 −= Probability(‘x’ is not occur in ‘t’ step)

1 −= Probability(‘x’ is not occur in ‘0’ step) and Probability(‘x’ is not occur in ‘1’ to‘t’ step)

where(1 −F)is the probability that a resource is not known to a given node and(1 −qt−1)is the probability of not fnding the resource in one of the “p” randomly unfolding paths of lengtht−1.

After further evaluation we get,

The average number of steps needed in general to locate the resourcexis given in Eq.(3).Now substituting Eqs.(15) in (3) we get the average number of steps needed to fnd a resource withintsteps for the random walk algorithm forp≥1,t≥1.

which further is evaluated to,

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 bepmessages generated bydneighbors for everypof its children,plus the messages generated in each of theppaths.

where,m(t−1)denotes the transmissions that take place along a pathpoft−1 nodes.

For such a pathp, the reply will be unicasted through the path resolved by the routing protocol if resourcexis located at the root node.Further, the query will be terminated at that moment since the received message also contains the addressSand the process will get terminated or else a message will be generated while forwarding to next node of the path plus the message generated inside the subpathp′witht−2 nodes rooted at the next node.This gives the recurrence relation:

m(t−1)=1 ∗F+(1+m(t−2))∗(1 −F)=am(t−2)+1

where,m(0)=1.On solving the recurrence relation, we get:

Now substituting Eqs.(18) in (17) it gives:

4.3 Addressed Broadcast Random Walk(ABRW)Algorithm

To reduce the overhead in the classic random walk protocol, we proposed an improved random walk algorithm [7].Our technique is based on the addressed broadcast transmission mechanism in which the querying node will pass the request to a particular random node over a 1-hop addressed broadcast transmission, i.e., the request is forwarded to that node, while the neighboring nodes within the hop range will overhear the request, but only the addressed node will process the request further and continue the resource discovery.So, in short, every neighbor node will receive the message at its application layer, but inside the message, there will be the nodeID for which that message is actually addressed to.The P2P agent at the application layer will process it differently based on the message content.So, the addressed node will only try to forward the message again.For our addressed random walk algorithm also, there will be aprandomly unfolding paths that can be followed to reach the destination.Our scheme is different from the standard random walk protocol as even thedoverhearing neighbors can also see or receive the message, and hence there is a high probability of reaching the destination as the intermediate nodes can also reply if they have the resourcexalong the pathp.And onlypmessages will be generated for itspchildren, as the addressed node will only continue with the resource discovery process further, i.e., the node transmits the message top≥1 of its neighbors where each such neighbor unfolds a sub-tree withdneighbors of lengtht−1 where everydneighbors can also overhear the message.Letbe the probability of locating a resource withintsteps for our proposed scheme wherepis one of the randomly unfolding paths and for every suchpchildren it unfolds a sub-tree of lengtht−1 with theirdneighbors shown in Fig.6.

LetFbe the probability that a resource is known to a node, andais the probability that a resource is not known to a node.Hence,a=1 −F.At step “0”, the probability of not locatingxis given as,

Now,

1 −=Probability that ‘x’ is not found in ‘t’ step

1 −=(Probability that ‘x’ is not found in ‘0’ step) * (Probability that ‘x’ is not occur in‘1’ to ‘t’ step)

where, 1 −Pt−1is the probability of not locating the resource in one ofprandomly unfolding sub-tree of lengtht−1 withdneighbors.

Now substituting Eqs.(21) in (20) we have,

Figure 6:Searching using addressed broadcast random walk technique (a) searching the network using addressed broadcast random walk technique (b) d-ary tree representation

In our proposed random walk technique, the probability of fndingxis high at eachpchildren along the path, as even thedneighbors can respond immediately.Hence, the number of steps required to fnd the resource will be minimal when compared to the other discussed techniques.

The average number of steps needed to fnd the resource “x”can be found using Eq.(3), now substituting Eqs.(22) in (3) we have,

which further evaluates to,

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.Ifxis not offered by the addressed node then there will be one fxed message generated while forwarding to every addressed child node and the message generated in each of theppaths.

where,m(t−1)are the transmission occurring along the pathpoft−1 nodes.

For such a pathp, if resourcexis found in its addressed node or any of itsdneighbors of the broadcasting node then it will generate a reply to the querying node which is unicasted back using the path resolved by the routing protocol, and the query gets terminated only if the reply was from the addressed node or else a message will be generated while forwarding to next addressed node of the path plus the message generated inside the subpathp′witht−2 nodes rooted at the next node.This gives the recurrence relation:

m(t−1)=1 ∗F+(1+m(t−2))∗(1 −F)=am(t−2)+1

where,m(0)=1, since the last node receiving the message will always reply to the querying node whether it knowsxor not.On solving the recurrence relation, we get:

Now substituting Eqs.(25) in (24) it gives:

5 Theoretical Analysis

We compare the three search strategies analytically with the following settings.The network consists ofN=100 nodes, andnx=1 (as only one node holds the resource “x”).We consider for two different node degrees, i.e., sparse (d=4) and dense (d=6) scenarios.We evaluate withp=1 andp=4 paths for both the random walk protocol and our proposed method.We measure the probability of not fnding the resource within “t” steps (1 −Qt), the average number of steps requiredand the number of messages generated within “t” stepsfor each of the algorithms.The results are shown in Fig.7.

Figure 7:Comparisons of different search techniques using the metrics:Probability of not fnding the resource, average number of steps needed to locate the resource, and average number of messages generated during the search process

The mathematical results are summarized in Tab.2.for each of the search techniques.

Table 2:Search algo.evaluation performance metrics (t ≥1,p ≥1,Q0=1 −a)

6 Conclusion

In this work, the focus is on the general issues of resource discovery under a highly dynamic mobile P2P network.Specifcally, the performance of random walk and fooding 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 fooding 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 fnding a resource, the mean of steps needed to fnd a resource, and the mean of messages generated while fnding 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.

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

Funding Statement:Taif University Researchers Supporting Project Number (TURSP-2020/36),Taif University, Taif, Saudi Arabia.

Conficts of Interest:The authors declare that they have no conficts of interest to report regarding the presented study.