# Collaborative Caching for Implementing a Location-Privacy Aware LBS on a MANET
## 4 Proposed M-LBS Scheme
### Caching Management in M-LBS  
In this work, we employ a two-level cache management system. The first level corresponds to the individual cache management performed by each mobile user. Since these users have limited cache memory available, we propose and evaluate various cache management techniques in our study. When the cache reaches its capacity and the user needs to insert new data, one of the following policies is implemented.  
* _First-In-First-Out Elimination (FIFO)_: The element that was first added to the cache is removed, following an FIFO policy.
* _Random elimination (RAN)_: A random element is selected and deleted to free up space in the cache.
* _Distance Elimination (DIST)_: The distance between each element in the cache and the user's current location is calculated. The element with the longest distance is prioritized for deletion.  
* _Popularity Elimination (POP)_: For each element in the cache of the node, a popularity score is calculated. This score is obtained by maintaining a counter that is incremented when an element is part of a response. The element with the lowest score is deleted.
* _Elimination of the minimum popularity/distance ratio (MINPD)_: For each element in the cache of a node, the popularity score is calculated and divided by the distance between the location of the element and the user. The element with the smallest ratio is deleted.
* _Reset of the cache when changing cells (RST)_: When the user changes cells, all the elements in the cache are deleted.  
By implementing these cache management policies, we anticipate improved space utilization within the cache. The performance of these techniques is evaluated and compared in Section 6.  
The second level of caching corresponds to the cell level. Here, we seek to maintain as much data as possible about POIs in the cell among the mobile users residing in that cell. Through managing the use of the cell exit protocol, we aim to reduce the search time for a response to a location-based query and increase the probability of finding a response in one or more user neighbors.  
In this work, when measuring cache efficiency, we calculate the cache hit rate, which refers to the number of times the same location is queried, and its response is found either in the local cache memory of the user or in one of the neighbors (nodes in the querying user's cell) of the querying user. This idea is grounded on the observation that individuals' living habits are consistently regular, whereas their questioning habits frequently change at a steady rate.  
One aspect is the data redundancy in a cell, which is measured in terms of how many replicas of metadata (extra data describing a location, for a restaurant, its menu, prices) about a POI are stored in the cache memory of the cell's users. While high redundancy allows one to reduce the search times for a response to a location-based query, it does not allow the storage of a wide variety of cell data, which could mean that the user has to access the LBS to resolve their query. Undoubtedly, a balance between response time and redundancy must be found to protect the location or query privacy of the mobile user.