H.Ji et al Journal of Network and Computer Applications 52 (2015)79-89 85 The larger the number of people N is,the larger the tag density p is.Because more users means more event messages need to be stored on tags which leads to appropriate number of tags need to be deployed. The faster the speed of users'movement 9 and the larger the range of users'activity area y are,the larger the tag density p is. Because more event messages and request messages are generated in the same time which leads to more tags that are V30 needed in the system. The tag density p is also related to which kind of writing and V29 replacing strategy is chosen.For example,MRME strategy needs more tags than OROE strategy. V24 V25 V26 V27 V28 Fig.3.Select the next position (vertex)and move to a target region 4.6.Discussion on practical issues 4.5.Analysis In realistic settings of the applications,several practical issues like the tag collisions and the localization accuracy might impact In the field of large-scale wireless ad hoc networks research, the actual performance of our indoor navigation solution.We thus previous works (Dousse et al.,2004:Kong and Yeh,2008;Zhao provide a detailed discussion on these issues as follows: et al.,2011)have already showed the relationship between In regard to the issue of tag collisions in MAC layer,since in our transmission delay and distance from source to destination. application settings,the RFID tags are not deployed in a rather However,our problem is different from the above problems dense approach,i.e.,one tag is deployed for every 4-10 m,as we studied in previous works.The focus of our problem is locating suppose to use a mobile reader(like smart phone)to continuously and navigating to a mobile user.We analyze our distributed scan the surrounding tags,the scanning range is usually less than solution on the undirected graph G=(V,E)which is an abstraction 3 m,the possibility of tag collision is very low in our application of the RFID-based delay tolerant network.On the graph,we want scenarios.Therefore,we mainly consider the performance in terms to find the optimal vertex sequence (vi.v2.....vn).((vi.v)EE. of application layer,the collision in physical layer will not have a 1sisn-1),where v is the current location of the searcher S. great effect on the system performance. and v is the finally location where the searcher found the target T. In regard to the issue of localization accuracy,our main goal is so as to minimize the total distance of the vertex sequence.Let L to conduct efficient indoor navigation instead of indoor localiza- be the total distance and our goal is to tion based on RFID systems.In our application settings,we deploy at least one tag for every 4-10 m,each tag is labeled with an exact minL÷min∑wv+i] (2) position,the scanning range of a mobile reader is less than 3 m, hence the localization error is at most 3 m.As our indoor subject to the memory size si for each vertex v. navigation solution is designed towards a large scale application Since the memory size of each RFID tag is limited,in order to scenario,for example,indoor navigation in a shopping mall or a ensure the locating and navigating performance in the RFID-based large office building.this localization scheme is accurate enough delay tolerant network,appropriate number of tags should be for our application scenarios. deployed.We use tag density p as the guide to deploy tags in the system.Let s2 be the volume of the indoor environment and be the average memory size of tag Obviously.we have. 5.Performance evaluation To determine the value of p,we introduce a new concept steady- 5.1.Large-scale experiment under classical human mobility model state.Considering an ideal situation,the memory size of each RFID tag is infinity.as the navigation system running.the total occupied We implement a simulator in Java to simulate the navigation memory size of tags (t)changes as well.We define that the system process,thus to evaluate the performance of our solution.We reaches its steady-state when the value (t)no longer increases. conduct the experiment based on a 30 x 30 grid-graph.Each Then,if the system can reach its steady-state,the following condi- vertex on the graph represents a tag in the RFID-based delay tions must be satisfied: tolerant network.Except the boundary vertices,each vertex has 6≥mx0 (3) four neighbor vertices.We consider the simulation as an event- 斯eV driven scenario,that is.when a user is approaching the vertex (tag)within a distance of less than 1 m,we allow the user to leave Then we obtain a trace or send a query to the surrounding tags.To simulate the p≥maxo≤so movement behaviors of users on the graph,we use two classical (4) human mobility models (Camp et al.,2002;Lee et al.,2009). 2*6 We compare the performance of our solution with the follow- However,it still remains as an open problem how maxo(t) ing solutions in regard to the average searching time: varies in accordance with network parameters,such as the number of people N in the network,the movement speed of each person 9, Blind navigation:The searcher randomly selects a vertex on the and the range of each person'activity area y.Theoretically analyzing graph and moves to the vertex with the shortest path length.If the exact relationship between them is very difficult.In Section 5,we the searcher does not find the target on the path,then the use experiment result to reveal the above quantitative relation.In searcher will repeat the above process until he finds the target. this paper,average searching time will be used to measure the Centralized navigation:The searcher can obtain the target's performance of our solution.Intuitively.we can qualitatively describe current position in real time.The searcher always moves to the relationship between them as follows: the neighbor vertex which is nearest to the target.4.5. Analysis In the field of large-scale wireless ad hoc networks research, previous works (Dousse et al., 2004; Kong and Yeh, 2008; Zhao et al., 2011) have already showed the relationship between transmission delay and distance from source to destination. However, our problem is different from the above problems studied in previous works. The focus of our problem is locating and navigating to a mobile user. We analyze our distributed solution on the undirected graph G ¼ ðV; EÞ which is an abstraction of the RFID-based delay tolerant network. On the graph, we want to find the optimal vertex sequence v0 1; v0 2; …; v0 n
;ð ðv0 i ; v0 iþ1ÞAE; 1rirn1Þ, where v0 1 is the current location of the searcher S, and v0 n is the finally location where the searcher found the target T, so as to minimize the total distance of the vertex sequence. Let L be the total distance and our goal is to min L3min n X1 i ¼ 1 w½v0 i ½v0 iþ1 ð2Þ subject to the memory size rδi for each vertex v0 i . Since the memory size of each RFID tag is limited, in order to ensure the locating and navigating performance in the RFID-based delay tolerant network, appropriate number of tags should be deployed. We use tag density ρ as the guide to deploy tags in the system. Let Ω be the volume of the indoor environment and δ be the average memory size of tag. Obviously, we have ρnΩnδ ¼ P vi AV δi. To determine the value of ρ, we introduce a new concept steady￾state. Considering an ideal situation, the memory size of each RFID tag is infinity, as the navigation system running, the total occupied memory size of tags ϕðtÞ changes as well. We define that the system reaches its steady-state when the value ϕðtÞ no longer increases. Then, if the system can reach its steady-state, the following condi￾tions must be satisfied: X vi AV δiZ max 0ot o1ϕðtÞ ð3Þ Then we obtain ρZmax0ot o1ϕðtÞ Ωnδ ð4Þ However, it still remains as an open problem how max0ot o1ϕðtÞ varies in accordance with network parameters, such as the number of people N in the network, the movement speed of each person ϑ, and the range of each person' activity area γ. Theoretically analyzing the exact relationship between them is very difficult. In Section 5, we use experiment result to reveal the above quantitative relation. In this paper, average searching time will be used to measure the performance of our solution. Intuitively, we can qualitatively describe the relationship between them as follows:
The larger the number of people N is, the larger the tag density ρ is. Because more users means more event messages need to be stored on tags which leads to appropriate number of tags need to be deployed.
The faster the speed of users' movement ϑ and the larger the range of users' activity area γ are, the larger the tag density ρ is. Because more event messages and request messages are generated in the same time which leads to more tags that are needed in the system.
The tag density ρ is also related to which kind of writing and replacing strategy is chosen. For example, MRME strategy needs more tags than OROE strategy. 4.6. Discussion on practical issues In realistic settings of the applications, several practical issues like the tag collisions and the localization accuracy might impact the actual performance of our indoor navigation solution. We thus provide a detailed discussion on these issues as follows: In regard to the issue of tag collisions in MAC layer, since in our application settings, the RFID tags are not deployed in a rather dense approach, i.e., one tag is deployed for every 4–10 m, as we suppose to use a mobile reader (like smart phone) to continuously scan the surrounding tags, the scanning range is usually less than 3 m, the possibility of tag collision is very low in our application scenarios. Therefore, we mainly consider the performance in terms of application layer, the collision in physical layer will not have a great effect on the system performance. In regard to the issue of localization accuracy, our main goal is to conduct efficient indoor navigation instead of indoor localiza￾tion based on RFID systems. In our application settings, we deploy at least one tag for every 4–10 m, each tag is labeled with an exact position, the scanning range of a mobile reader is less than 3 m, hence the localization error is at most 3 m. As our indoor navigation solution is designed towards a large scale application scenario, for example, indoor navigation in a shopping mall or a large office building, this localization scheme is accurate enough for our application scenarios. 5. Performance evaluation 5.1. Large-scale experiment under classical human mobility model We implement a simulator in Java to simulate the navigation process, thus to evaluate the performance of our solution. We conduct the experiment based on a 30  30 grid-graph. Each vertex on the graph represents a tag in the RFID-based delay tolerant network. Except the boundary vertices, each vertex has four neighbor vertices. We consider the simulation as an event￾driven scenario, that is, when a user is approaching the vertex (tag) within a distance of less than 1 m, we allow the user to leave a trace or send a query to the surrounding tags. To simulate the movement behaviors of users on the graph, we use two classical human mobility models (Camp et al., 2002; Lee et al., 2009). We compare the performance of our solution with the follow￾ing solutions in regard to the average searching time:
Blind navigation: The searcher randomly selects a vertex on the graph and moves to the vertex with the shortest path length. If the searcher does not find the target on the path, then the searcher will repeat the above process until he finds the target.
Centralized navigation: 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. Fig. 3. Select the next position (vertex) and move to a target region. H. Ji et al. / Journal of Network and Computer Applications 52 (2015) 79–89 85