paper no: mob1
last update: 20/05/08
(data on the road in intelligent transportations systems)
Consider an urban area with hundreds of thousands of vehicles.Drivers and passengers in these vehicles are interested in information relevant to their trip.For eg, a driver would like his/her vehicle to continuously display on a map at any time, the available parking spaces around the current location of the vehicle.Or, the driver may be interested in the traffic conditions one mile ahead.such information is important for drivers to optimize their travel, to alieviate traffic congestions,or to avoid wasteful driving.the challenge in processing queries in this highly mobile environment with an acceptable delay,overhead and accuracy.In this paper we explore a new paradigm that is based on peer to peer communication in mobile computing.
Mobile Computing is a technology that allows transmission of data, via a computer, without having to be connected to a fixed physical link. P2P computing can be simply defined as the sharing of computer resources and services by direct exchange. The peer computer can respond to request from other peers. The p2p computing model offers a number of compelling advantages to individual users and large organizations. P2p can be use3d to distribute data and in addition the p2p infrastructure allows direct access and shared spaces and this can enable remote maintanance capability.
1.THE SYSTEM MODEL:
The system consists of fixed stations and moving objects. Each station senses resources and continuously announces them by wireless broadcast. Each announcement message, contains the home and the create-time of the resource. An object is capable of detecting the objects that are within its transmission range. We say that two objects encounter each other when their distance is smaller than the transmission rang. If two moving objects travel within the transmission range for a period of time, after the initial exchange only newly arrived resources are exchanged.
In the parking slots example, a sensor in a parking slot monitors the slot, and, while unoccupied, announces its availability to the neighboring vehicles.
In the car accident example, the event may be announced by the sensor that deploys the air-bag.
2. RESOURCES AND THEIR RELEVANCE:
Resources may be spatial, temporal, or spatio-temporal . Spatio – temporal resources generalize the spatial and the temporal resources. A spatio – temporal resource, or a resource for short, is a piece of information about an event(e.g. the availability of a parking space, or a car accident, the speed of a vehicle at a particular time – point, the availability of a taxi-cab customer at a particular location). The event is specific to a certain location that is referred to as the home of the resource.Each resource has a time duration for which it is valid. This duration is referred to as the valid duration. For example, the valid duration of the resource regarding the availability of a parking space is the time period since the space becomes available until it is occupied.We use the following function to compute the relevance of compute the relevance of resource R:
F (R) = a .t - b .d ( a , b >0)
Where d is the distance form the home location of R. a and b are constants that represent the decay factors of time and distance respectively. The bigger the ratio a b , the more the relevance is sensitive to time than to distance; conversely, the relevance is more sensitive to distance than to time.
3. DISSEMINATION ALGORITHMS:
In this section we describe two possible opportunistic resource dissemination algorithms.
3.1.OPPORTUNISTIC RESOURCE DISSEMINATION:
The resources in memory are ranked according to their relevance. If the number of received resources exceeds the allocated memory,less relevant resources must be shed from memory to accommodate more relevant ones. We assume that a moving object has a fixed amount of memory allocated to each application (e.g the user allocates 10 entries for relevant parking slots. In other words, the user wants only 10 parking slots to be saved and displayed)
Two types of operations may be performed at a moving object O. The first type is resource acquisition, which is performed when O is within the coverage area of a station while the station is announcing a resource R. Upon reception of R, if O's memory space is not full, R is saved in memory. If the memory is full, O computes the relevance of R based on the age of R and on the distance between the current location of O and the home of R.O also recomputes the relevance for each stored resource. If the relevance of R is higher than that of any stored resource, the least relevant one is purged, and then R is saved otherwise R is discarded.
The second type of operations is resource exchange, which is performed when O encounters a new object O',it neither O nor O' is in the middle of data exchange with a third vehicle, the resource exchange is performed between A and B as follws.O and O' first exchange their resources. Upon receiving new resources, moving object O computes the relevance for each received resource and re-evaluates the relevance of its own resources. If all the resources do not fit in the memory space of O, the least relevant ones are purged. In either resource acquisition or resource exchange, when O receives a resource R, if O has a resource R in its memory such that R and R have the same home and the create-time of R is greater than that of R' then R' is replaced by R.
3.2. OPPORTUNISTIC RESOURCE DISSEMINATION WITH INVALIDATION (ORDI):
With ORD, a resource in an object's memory may become invalid before it is purged out. This invalid resource introduces wrong information for decision making. For example, the resource may indicate an available parking space that is actually already occupied, or it may indicate a cab request that is already satisfied. Time may be wasted if the driver uses this resource to make decisions. In order to reduce the invalid resources, we developed Opportunistic Resource Dissemination with Invalidation (ORDI).
ORDI works as follows. At each station, whenever the valid duration of a resource R ends, the station starts to announce an invalidation message for R until the beginning of the announcement of the next resoure. The invalidation message contains the following three data items:
T invalid (R) the time when R becomes invalid (which is also the time when the invalidation message is created)
T create (R) the create-time of R
H(R) the home of R. the invalidation message is a special resource. Its home is H(R) and its create-time is T invalid (R), and it uses the same relevance function as a regular resource. We will refer to the invalidation message as the invalidating resource of R, and refer to R as a regular resource. The invaliding resource is acquired and exchanged similarly to a regular resource. The only difference is a follows. When an invalidating resource (T invalid(R), T create(R), H(R) is received by an object, the object uses T create (R) and H(R) to search R in its memory. If R is found, then it is replaced by the invalidating resource.
For Further more download pdf...