Globecom 2013-Ad Hoc and Sensor Networking Symposium I=(4,3,1),the current time tno=5.Then vertex v11 will region.The center of the circle is the user's initial position and be selected as the next intermediate vertex.Because the cost the radius of the circle obeys a normal distribution N(μ，62)， of v is 7.57 which is less than the cost of v2,v4 or v21. where u is the expectation of radius.The stay time of each user obeys a truncated power-law distribution p(t)=Cxt-2.5(s). (5 <t 60).Parameters used in the experiments are showed in Table 1.For all figures presented,we run the simulation 1,000 times to get average values. Table 1.Parameters used in the simulation Parameter Description Value m number of users 50..,500 8R(S) time to live of request message 10,.,200 k number of event message 1,.,10 4(m) expectation of region radius 6..,60 Fig.2.Select the next position (vertex)and move to a target region B.Experiments Result VI.PERFORMANCE EVALUATION 1)Average Searching Time:In Figure 3a,3b,we plot the average searching time of three solutions under two mobility We implement a simulator in Java to simulate the navigation models with different numbers of users.We guarantee that process,thus to evaluate the performance of our solution.We the inputs of users'movement behaviors for each solution are conduct the simulation based on a 30 x 30 grid-graph.Each the same.As we can see from these 2 subfigures,with the vertex on the graph represents a tag in the RFID-based delay number of users increasing,the average searching time of our tolerant network.In addition to the boundary vertices,each solution is reduced gradually.When increasing the number of vertex has four neighbor vertices.To simulate the movement users from 50 to 500,our solution's average searching time behaviors of users on the graph,we use two classical human is reduced from 742/487 seconds to 226/234 seconds.While mobility models [15.161. the average searching time of blind navigation or centralized We compare the performance of our solution with two other navigation is essentially unchanged.This is consistent with our solutions:blind navigation solution and centralized navigation intuition that more users means more helpers for the searcher. solution by the average searching time.In blind navigation In Figure 3c,3d,we plot the average searching time of solution,searcher randomly selects a vertex on the graph our solution under two mobility models with different values and moves to the vertex with shortest path.If the searcher of 0r and 0.When the value of 0R is small,the average doesn't find the target on the path,then the searcher will searching time is large.Because only a few number of users repeat the above process until he finds the target.In centralized could receive request messages and the searcher gets little help solution,we suppose that the searcher can obtain the target's from others.When increasing the value of og from 10 seconds current position in real time.The searcher always moves to the to 200 seconds,the average searching time is reduced more neighbor vertex which is nearest to the target.In this paper, than 30%.Different from 0R,the impact of is little.When we regard the centralized solution as the approximate optimal the value of is 1,5 under RW or 1,3,9 under RWP,the solution and the blind navigation solution as the worst solution. average searching time is slightly smaller than others. In Figure 3e,we plot the average searching time of our so- A.Experiments Settings lution under RWP with different localities of users'movement At the beginning of the simulation,we randomly select a behaviors.When the value of u is less than 12,users move vertex on the 30 x 30 grid-graph for each user as the user's in a small region.The request messages of searcher spread initial position.All the users are limited to move on the edges slowly.Thus it takes a long time for the searcher to detect the of the grid-graph.The length of each edge is 4 m.In order to target's traces,and the average searching time is large.When avoid situation that searcher never catches up with the target, the locality of users'movements is week,sayμ≥30，the we assign the movement speed of the searcher is 2 m/s and movement region of the target is large.So.it is also difficult other users'are 1 m/s.If searcher and the target happen to be for the searcher to find the target.We find that when u is 20 on the same edge,we think the searcher has found the target.the average searching time is the smallest. To simulate the movement behaviors of users,we use a 2)Number of Messages:In Figure 3f,we plot the average simplified Random Walk Mobility Model(RW)and a Random number of messages stored in the delay tolerant network as Way-Point Mobility Model(RWP).Under the random walk time grows.The number of request messages under RWP is mobility model,whenever a user reaches a vertex,the user sightly smaller than RW.When the time is about 200(s), will randomly select a neighbor vertex to move.Under the the number of request messages reaches its maximum.The random way-point mobility model,each user randomly selects number decreases as the request message's time to live is a vertex within a local region on the graph and moves to the reduced to zero.The number of event messages grows fast vertex with shortest path.When arriving at the vertex,the user between 150(s)to 350(s).After 400(s),the number of event will stay on the vertex for a period of time,then repeat the messages is essentially unchanged.Because no more request above process.We use a circular region to describe such a local messages are generated after that. 187Γ = h4, 3, 1i, the current time tnow = 5. Then vertex v11 will be selected as the next intermediate vertex. Because the cost of v11 is 7.57 which is less than the cost of v2, v4 or v21. Fig. 2. Select the next position (vertex) and move to a target region VI. PERFORMANCE EVALUATION We implement a simulator in Java to simulate the navigation process, thus to evaluate the performance of our solution. We conduct the simulation based on a 30 × 30 grid-graph. Each vertex on the graph represents a tag in the RFID-based delay tolerant network. In addition to the boundary vertices, each vertex has four neighbor vertices. To simulate the movement behaviors of users on the graph, we use two classical human mobility models [15, 16]. We compare the performance of our solution with two other solutions: blind navigation solution and centralized navigation solution by the average searching time. In blind navigation solution, searcher randomly selects a vertex on the graph and moves to the vertex with shortest path. If the searcher doesn’t find the target on the path, then the searcher will repeat the above process until he finds the target. In centralized solution, we suppose that the searcher can obtain the target’s current position in real time. The searcher always moves to the neighbor vertex which is nearest to the target. In this paper, we regard the centralized solution as the approximate optimal solution and the blind navigation solution as the worst solution. A. Experiments Settings At the beginning of the simulation, we randomly select a vertex on the 30 × 30 grid-graph for each user as the user’s initial position. All the users are limited to move on the edges of the grid-graph. The length of each edge is 4 m. In order to avoid situation that searcher never catches up with the target, we assign the movement speed of the searcher is 2 m/s and other users’ are 1 m/s. If searcher and the target happen to be on the same edge, we think the searcher has found the target. To simulate the movement behaviors of users, we use a simplified Random Walk Mobility Model (RW) and a Random Way-Point Mobility Model(RWP). Under the random walk mobility model, whenever a user reaches a vertex, the user will randomly select a neighbor vertex to move. Under the random way-point mobility model, each user randomly selects a vertex within a local region on the graph and moves to the vertex with shortest path. When arriving at the vertex, the user will stay on the vertex for a period of time, then repeat the above process. We use a circular region to describe such a local region. The center of the circle is the user’s initial position and the radius of the circle obeys a normal distribution N(µ, 6 2 ), where µ is the expectation of radius. The stay time of each user obeys a truncated power-law distribution p(t) = C ×t −2.5 (s), (5 ≤ t ≤ 60). Parameters used in the experiments are showed in Table 1. For all figures presented, we run the simulation 1,000 times to get average values. Table 1. Parameters used in the simulation Parameter Description Value m number of users [50, ..., 500] θR (s) time to live of request message [10, ..., 200] θk number of event message [1, ..., 10] µ (m) expectation of region radius [6, ..., 60] B. Experiments Result 1) Average Searching Time: In Figure 3a, 3b, we plot the average searching time of three solutions under two mobility models with different numbers of users. We guarantee that the inputs of users’ movement behaviors for each solution are the same. As we can see from these 2 subfigures, with the number of users increasing, the average searching time of our solution is reduced gradually. When increasing the number of users from 50 to 500, our solution’s average searching time is reduced from 742/487 seconds to 226/234 seconds. While the average searching time of blind navigation or centralized navigation is essentially unchanged. This is consistent with our intuition that more users means more helpers for the searcher. In Figure 3c, 3d, we plot the average searching time of our solution under two mobility models with different values of θR and θk. When the value of θR is small, the average searching time is large. Because only a few number of users could receive request messages and the searcher gets little help from others. When increasing the value of θR from 10 seconds to 200 seconds, the average searching time is reduced more than 30%. Different from θR, the impact of θk is little. When the value of θk is 1, 5 under RW or 1, 3, 9 under RWP, the average searching time is slightly smaller than others. In Figure 3e, we plot the average searching time of our so￾lution under RWP with different localities of users’ movement behaviors. When the value of µ is less than 12, users move in a small region. The request messages of searcher spread slowly. Thus it takes a long time for the searcher to detect the target’s traces, and the average searching time is large. When the locality of users’ movements is week, say µ ≥ 30, the movement region of the target is large. So, it is also difficult for the searcher to find the target. We find that when µ is 20 the average searching time is the smallest. 2) Number of Messages: In Figure 3f, we plot the average number of messages stored in the delay tolerant network as time grows. The number of request messages under RWP is sightly smaller than RW. When the time is about 200 (s), the number of request messages reaches its maximum. The number decreases as the request message’s time to live is reduced to zero. The number of event messages grows fast between 150 (s) to 350 (s). After 400 (s), the number of event messages is essentially unchanged. Because no more request messages are generated after that. Globecom 2013 - Ad Hoc and Sensor Networking Symposium 187