86 H.Ji et aL Journal of Network and Computer Applications 52 (2015)79-89 .Intuitive navigation:The searcher leverages the RFID-based While the average searching time of blind navigation or centralized delay tolerant network to search the target,once the searcher navigation is essentially unchanged.This is consistent with our gets one record of the target from the surrounding tags,he goes intuition that more users means more helpers for the searcher. to the corresponding position directly.If he does not find the Specifically,the blind navigation just randomly chooses a way to target at the specified position,he then further queries the find the target,which is irrelevant to the number of users and leads surrounding tags for the target. to stable average searching time.The centralized navigation always .Escort (Constandache et al,2010):Once a user meets other achieves the least searching time,since it is always close to the users,they will exchange their own information with each other optimal solution.With the number of users increasing,the average to help find the target.As the number of users increases,the searching time of CrowdSensing,Escort and Intuitive Navigation are probability to meet the target increases,this helps the searcher all reduced gradually.Escort suffers from rare users at first,which to quickly collect enough information to search the target. leads to long searching time.However,as the number of user increases,the number of users is close to the intersections in the Here,in the following we call our solution as CrowdSensing.we graph,which leads to close searching time of CrowdSensing.The regard the centralized navigation as the approximate optimal solu- intuitive navigation can only follow the one historical record of the tion and the blind navigation as the worst solution.The intuitive target,which leads to relatively high searching time in RW model, navigation is usually proposed in recent literatures for adaptive because the target keeps on moving.However,in RWP model,the navigation,which is greedy by focusing on the present record,and target will not move so often,which makes the searching time usually efficient to find a target moving regularly.The Escort should smaller than the RW model.Since CrowdSensing can make use of all be efficient in searching when the number of users is fairly large. the crowd-sourcing information,it achieves better performance than the above two solutions. 5.1.1.Experiment settings In Fig.4(c)and (d),we plot the average searching time of Crowd- At the beginning of the experiment,we randomly select a vertex Sensing under two mobility models with different values of dg and d on the 30 x 30 grid-graph for each user as the user's initial position. When the value of o is small,the average searching time is large. All the users are limited to move on the edges of the grid-graph.The Because only a few number of users could receive request messages length of each edge is 4 m.In order to avoid situation that searcher and the searcher gets little help from others.When increasing the never catches up with the target,we assign the movement speed of value of e from 10s to 200 s,the average searching time is reduced the searcher to 2 m/s and other users'to 1 m/s.If searcher and more than 30%.Different from 6g.the impact of is little.When the target happen to be on the same edge,we think that the searcher values of are 1,2,6.and 8 under RW or 1,3 and 4 under RWP,the has found the target. average searching time is slightly smaller than others To simulate the movement behaviors of users,we use a simplified In Fig.4(e),we plot the average searching time of CrowdSensing Random Walk(RW)Mobility Model and a Random Way-Point(RWP) under RWP with different localities of users'movement behaviors. Mobility Model.Under the Random Walk Mobility Model,whenever a When the value of u is less than 12,users move in a small region. user reaches a vertex,the user will randomly select a neighbor vertex The request messages of searcher spread slowly.Thus it takes a to move.Under the random way-point mobility model,each user long time for the searcher to detect the target's traces,and the randomly selects a vertex within a local region on the graph and average searching time is large.When the locality of users'move- moves to the vertex with the shortest path length.When arriving at ments is weak,sayμ≥30，the movement region of the target is the vertex,the user will stay on the vertex for a period of time,then large.So,it is also difficult for the searcher to find the target.We repeat the above process.We use a circular region to describe such a find that when w is 20 the average searching time is the smallest. local region.The center of the circle is the user's initial position and the Number of messages:In Fig.4(f).we plot the average number of radius of the circle obeys a normal distribution N(,6),where u is the messages stored in the delay tolerant network as time grows.The expectation of radius.The stay time of each user obeys a truncated number of request messages under RWP is sightly smaller than RW. power-law distribution p(t)=Cxt-25(s).(5sts60).Parameters When the time is about 200s,the number of request messages used in the experiment are shown in Table 1.For all figures presented, reaches its maximum.The number decreases as the request mes- we run the experiment 1000 times to get average values,and provide sage's time to live is reduced to zero.The number of event messages the 95%confidence interval of the experiment results grows fast between 150 s and 350 s.After 400 s,the number of event messages is essentially unchanged.Because no more request mes- 5.1.2.Experiments result sages are generated after that. Average searching time:In Fig.4(a)and (b),we plot the average searching time of three solutions under two mobility models with 5.2.Realistic experiment under shopping mall mobility model different numbers of users.We guarantee that the inputs of users' movement behaviors for each solution are the same.As we can see To evaluate the performance of CrowdSensing under real world from these 2 figures,with the number of users increasing.the environment,we conduct our experiment using a mobility model average searching time of CrowdSensing is reduced gradually.When for shopping mall environments founded on real-world human increasing the number of users from 50 to 500,CrowdSensing's traces which is presented by Galati et al.(2013).They ran a field average searching time is reduced from 722/499 s to 216/230 s. trial to collect Bluetooth contact data from shop employees and clerks in a shopping mall over six days.The field trial started on Monday the 15th of June 2009 and went on till Saturday the 20th Table 1 of June 2009.The traceset can be accessed from community Parameters used in the experiment resource for archiving wireless data at Dartmouth (CRAWDAD) (Galati and Greenhalgh,2013).They analyzed the collected contact Description Value traces and designed the shopping mall mobility model. Number of users 50...500 B (s) Time to live of request message [10.,200 5.2.1.Shopping mall mobility model Number of event message 1,.,10 4(m) Expectation of region radius 6..,60 In the shopping mall environment,there are twenty-five mobile devices running symbianOS and using Bluetooth,eighteen of which
Intuitive navigation: The searcher leverages the RFID-based delay tolerant network to search the target, once the searcher gets one record of the target from the surrounding tags, he goes to the corresponding position directly. If he does not find the target at the specified position, he then further queries the surrounding tags for the target.
Escort (Constandache et al., 2010): Once a user meets other users, they will exchange their own information with each other to help find the target. As the number of users increases, the probability to meet the target increases, this helps the searcher to quickly collect enough information to search the target. Here, in the following we call our solution as CrowdSensing, we regard the centralized navigation as the approximate optimal solu￾tion and the blind navigation as the worst solution. The intuitive navigation is usually proposed in recent literatures for adaptive navigation, which is greedy by focusing on the present record, and usually efficient to find a target moving regularly. The Escort should be efficient in searching when the number of users is fairly large. 5.1.1. Experiment settings At the beginning of the experiment, 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 to 2 m/s and other users' to 1 m/s. If searcher and target happen to be on the same edge, we think that the searcher has found the target. To simulate the movement behaviors of users, we use a simplified Random Walk (RW) Mobility Model and a Random Way-Point (RWP) Mobility Model. 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 the shortest path length. 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ðμ; 62 Þ, 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Þ, ð5rtr60Þ. Parameters used in the experiment are shown in Table 1. For all figures presented, we run the experiment 1000 times to get average values, and provide the 95% confidence interval of the experiment results. 5.1.2. Experiments result Average searching time: In Fig. 4(a) and (b), 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 figures, with the number of users increasing, the average searching time of CrowdSensing is reduced gradually. When increasing the number of users from 50 to 500, CrowdSensing's average searching time is reduced from 722/499 s to 216/230 s. 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. Specifically, the blind navigation just randomly chooses a way to find the target, which is irrelevant to the number of users and leads to stable average searching time. The centralized navigation always achieves the least searching time, since it is always close to the optimal solution. With the number of users increasing, the average searching time of CrowdSensing, Escort and Intuitive Navigation are all reduced gradually. Escort suffers from rare users at first, which leads to long searching time. However, as the number of user increases, the number of users is close to the intersections in the graph, which leads to close searching time of CrowdSensing. The intuitive navigation can only follow the one historical record of the target, which leads to relatively high searching time in RW model, because the target keeps on moving. However, in RWP model, the target will not move so often, which makes the searching time smaller than the RW model. Since CrowdSensing can make use of all the crowd-sourcing information, it achieves better performance than the above two solutions. In Fig. 4(c) and (d), we plot the average searching time of Crowd￾Sensing 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 s to 200 s, the average searching time is reduced more than 30%. Different from θR, the impact of θk is little. When the values of θk are 1, 2, 6, and 8 under RW or 1, 3 and 4 under RWP, the average searching time is slightly smaller than others. In Fig. 4(e), we plot the average searching time of CrowdSensing 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' move￾ments is weak, say μZ30, 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. Number of messages: In Fig. 4(f), 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 mes￾sage's time to live is reduced to zero. The number of event messages grows fast between 150 s and 350 s. After 400 s, the number of event messages is essentially unchanged. Because no more request mes￾sages are generated after that. 5.2. Realistic experiment under shopping mall mobility model To evaluate the performance of CrowdSensing under real world environment, we conduct our experiment using a mobility model for shopping mall environments founded on real-world human traces which is presented by Galati et al. (2013). They ran a field trial to collect Bluetooth contact data from shop employees and clerks in a shopping mall over six days. The field trial started on Monday the 15th of June 2009 and went on till Saturday the 20th of June 2009. The traceset can be accessed from community resource for archiving wireless data at Dartmouth (CRAWDAD) (Galati and Greenhalgh, 2013). They analyzed the collected contact traces and designed the shopping mall mobility model. 5.2.1. Shopping mall mobility model In the shopping mall environment, there are twenty-five mobile devices running symbianOS and using Bluetooth, eighteen of which Table 1 Parameters used in the experiment. 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 86 H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89