Spatial Queries Processing In Wireless Broadcast Environments Computer Science Essay

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Abstract-----Wireless data broadcast is a promising technique for information dissemination that uses the computational capabilities of the mobile devices, in order to enhance the scalability of the system. Under this environment, the data is always maintained by Server and whenever Client request for some information by sending query. Then Server processes query also finds the nearest neighbor and broadcast it to the Client interleaved with some indexing information for query processing. Clients may then tune in the broadcast channel and obtain his information locally

In this project we use an air indexing framework that (i) outperforms the existing techniques in terms of energy consumption, while achieving low access latency , decreases the Server and Client Complexity(ii)constitutes the first method supporting efficient processing of continuous spatial queries over moving objects.

Index Terms - Spatial databases, query processing, location based services, wireless data broadcast, air Indexes

I .Introduction

Now a day's MOBILE devices becoming popular with computational storage and wireless communication abilities (such as PDAs).Same time, positioning systems technology is enabling the integration of low-cost GPS devices in any portable unit. New mobile computing applications are expected to emerge, allowing users to issue location-dependent queries everywhere. User (mobile client) in an unfamiliar city, who would like to know the 10 closest banks. This is an instance of a k nearest neighbor (kNN) query, where the query point is the current location of the client and the set of data objects contains the city restaurants.

In this project, there is a central server that monitors the locations of both objects and queries. User updates the information of moving objects & the server reports (broadcasts) and continuously updates the query results as the clients and the objects move.

Existing methods, has disadvantage: 1) the processing load at the server side increases with the number of queries and take prohibitively long time to answer them. To avoid this problem, propose a promising technique [2] wireless data broadcast, that uses the computational capabilities of the clients' mobile devices and pushes the query processing task entirely to the client side. In this environment, the server only monitors the locations of the data objects, but is unaware of the clients and their queries. The data objects are continuously broadcast by the server, interleaved with some indexing information. The clients utilize the broadcast index, called air index, to tune in the channel only during the transmission of the relevant data and process their queries locally. Thus, the server load is independent of the number of clients.

II. Choice of the Topic with reasoning

We study spatial query processing in wireless broadcast environments. A central server registers users then client send the query .Server processes the query obtains result also using KNN algo. finds the nearest neighbors and replies to user at the same time also broadcasts the same result to nearest neighbors with indexing information. The clients process their queries locally, by accessing the broadcast channel. In this environment, our target is to reduce the power consumption and complexity at the client side.

We propose an on-air indexing method that uses a regular grid to store and transmit the data objects. This is the study on air indexing that 1) addresses continuous queries and 2) considers moving data objects. A challenging problem is to design cost models for monitoring spatial queries processing in wireless broadcast environments. Such models could reveal the best technique for the given problem settings, and potentially lead to better algorithms. Another interesting direction for is to study different types of spatial queries, such as reverse nearest neighbors.

III Related Work

A. Wireless Broadcasting and Air Indexes [2]

The transmission schedule in a wireless broadcast system consists of a series of broadcast cycles. Within each cycle the data are organized into a number of index and data buckets. A bucket (which has a constant size) corresponds to the smallest logical unit of information, similar to the page concept in conventional storage systems. A single bucket may be carried into multiple network packets (i.e., the basic unit of information that is transmitted over the air).The most common data organization method is the (1, m)interleaving scheme [2], as shown in Figure 1. The data objects are divided into m distinct segments, and each data segment in the transmission schedule is preceded by a complete version of the index. In this way, the access latency for a client is minimized, since it may access the index (and start the query processing) immediately.

Fig 1.Interleaving scheme

B .Air Index [5]

In Wireless Broadcasting Sever continuously

broadcasts data & the client may switches to the sleep mode (i.e., turns off the receiver) whenever the transmitted packets do not contain any useful information. Based on the data organization technique of the query processing at the mobile client is performed as follows: (I) the client tunes in the broadcast channel when the query is issued, and goes to sleep until the next index segment arrives, (ii) the client traverses the index and determines when the data objects qualifying its query will be broadcast, and (iii) the client goes to sleep and returns to the receive mode only to retrieve the corresponding data objects. Advantages are (1) The main motivation behind air indexes is to minimize the power consumption at the mobile client. Although in a broadcast environment the uplink transmissions are avoided, receiving all the downlink packets from the server is not energy efficient. (2). in a broadcast environment the uplink transmissions are avoided, receiving all the downlink packets from the server is not energy efficient

C. Query Processing: Broadcast vs. Point-to-Point

Location based Spatial (LBSs) Queries by and large assume wireless communication since both the clients and the data (e.g., vehicles being tracked) move. Wireless communication supports two basic data dissemination methods.

In periodic broadcast, data are periodically broadcast on a wireless channel accessible to all clients in range. A mobile client listens to the broadcast channel and downloads the data that matches the query.

In on-demand access, a mobile client establishes a point-to-point connection to the server and submits requests to and receives results from the server on the established channel.

In LBS periodic is useless because both the number of clients and the amount of requests to be supported by the LBS could be huge. Periodic broadcast can be used to disseminate information to all participants at very low cost but in order to be useful in LBSs; a data broadcast system must support spatial queries and spatial data. For example, in an intelligent transportation system, the locations of all monitored vehicles can be broadcast so that an onboard navigation system can decide autonomously how to navigate through a crowded downtown area. Similar needs can be envisaged in the coordination of mobile robots on a factory floor in this section, we use the spatial query processing technique in a broadcast environment followed by location-based spatial queries processing in a demand access mode

C.1General Spatial Query Processing on Broadcast Data:

In wireless broadcast, data are available "on air" in the sense that they are available on the channel transiently. Client has to tune with the channel for accessing data, but when a data item is missed, the client has to wait for the next broadcast cycle, which takes a lot of time. Existing database indexes were obviously not designed to meet this requirement because data are stored on disks and can be randomly accessed any time. Hence, they perform poorly on broadcast data.

C.2 Location-based Spatial Queries on demand access mode:

In contrast to conventional spatial processing, queries in LBSs are mostly concerned about objects around the user's current position. Nearest neighbor queries are one example. In a non-location-based system, responses to queries can be cached at the clients and are reusable if the same queries are asked again. In LBSs, however, users are moving frequently. Since the result of a query is only valid for a particular user location, new queries have to be sent to the server whenever there is a location update, resulting in high network transfer and server processing cost. To alleviate this problem, the concept of validity region can be used. The validity region of a query indicates the geographic.

Fig.2.Single nearest neighbor Query

Area (s) within which the result of the query remains valid and is returned to the user together with the query result. The mobile client is then able to determine whether a new query should be issued by verifying whether it is still inside the validity region.. The validity region of course depends on the type of queries. Fig. 2 (c) illustrates the validity region of NN queries which are the same as Voronoi cells. The representation scheme for validity regions should (i) be as small as possible to reduce the network cost and (ii) facilitate the validity checking which is performed on a client with limited computational capability. Representing a validity region as a polygon may cause a high overhead. A better way is to identify the influence objects of a query q as the data points that contribute at least one to the validity region V (q). In other words, the influence set is the minimal set of objects which determines the validity region. In Fig. 2, the influence objects of query q are those whose perpendicular bisectors with object o constitute the edges of the Voronoi cell. Finally, the server returns the query result to the client along with the influence objects. The validity checking at the client side is performed by examining whether the new user location is inside the half-plane formed with respect to each influence point, which is equivalent to checking whether the query focus lies in the Voronoi cell of the result.


The utilization of validity region reduces significantly the number of new queries issued to the server and thus the communication via the wireless channel.

IV Existing Systems

A. Central Server

In this environment, the server only monitors the locations of the data objects, updates database, when client issue query that is also processed by server results in the overhead of complexity results in following Disadvantages: 1) The processing load at the server side increases with the number of queries.2) In applications involving numerous clients, the server may be overwhelmed by their queries or take prohibitively long time to answer them.

To avoid this problem, [14] propose wireless data broadcast, a promising technique that leverages the computational capabilities of the clients' mobile devices, and pushes the query processing task entirely to the client side.

B. Broadcast Grid Index [1][6]

In this paper we propose the Broadcast Grid Index (BGI) method, which is suitable for both snapshot and continuous queries also supports dynamic changes Figure 1 shows an example of continuous monitoring using BGI. The data objects are taxis that issue location updates to a central server using unicast uplink messages. The server processes the location updates, and continuously broadcasts the object information along with an up- to-date index using a wireless (e.g., 3G) network. Finally, the interested clients (e.g., mobile devices) listen to the broadcast channel and process their queries locally.


1. Note that since the server tasks are independent of the number and the positions of the clients, this architecture may theoretically support infinite concurrent clients/queries.


1. On the other hand, high object (e.g., taxi) cardinality increases both the server load (for processing the updates) and the length of the broadcast cycle.

BGI and broadcast techniques in general, are preferable for applications where the number of clients is large with respect to the number of data objects. As an example, Microsoft's MSN Direct ( uses broadcasting as an information dissemination method. Subscribers can receive live information regarding traffic conditions, stock quotes, gas prices, movie times, weather reports, etc. Even though location-based queries are not supported, we believe that this will be the next step, i.e., allowing the user to filter out unnecessary information using selective tuning (thus reducing the power consumption).

Fig. 8 Broadcast Grid Index

In the case of static data, the index information is broadcast in two parts. The first one contains the cell cardinalities, and the second one contains the coordinates of the objects falling in each cell. This allows for efficient query processing at the client side. For applications where the objects are moving, the server broadcasts a dirty grid in the beginning of each cycle. The dirty grid indicates the regions of the data space that have received updates since the last cycle. The clients re-evaluate their queries only if the affected regions can potentially invalidate their current result.

V. Proposed Work

A. Objectives

Aim to decrease the Server Complexity by processing the Query only once.

Also decrease the Client Complexity as Result is already present with the client. And client has to retrieve his required data.

B. Outline of Proposed work

Here proposed work is to monitor the Spatial Query processing in wireless broadcast environments. Definition says that suppose nay user has entered in an unknown city for any purpose for visiting purpose or he may want to access some information. What is the solution he may go cyber café and obtain the information by using internet ( limitations are there that user should first know the location/address of cyber café and if he is a non-technical person. The solution is nothing but this application. Now a day each and every user has a mobile so same limitations can be overcome by using the computational capabilities of the wireless devise by sending just one query (SMS).

For this purpose Server always maintains the database which can be used to process the query. For getting this application it is required to register the user. First Server will advertise himself Client then register himself. While registering Server will update his data which can be used to process KNN algorithm

If object changes his location the same can be monitored by server and update his database .Hence it supports location based queries. Then client send his query. Server applies KNN also processes the query and broadcasts the result back to the client also to the number of nearest neighbors obtained by applying KNN.

This project proposes an air indexing framework that 1) outperforms the existing (i.e., snapshot) techniques in terms of energy consumption while achieving low access latency and 2) constitutes the first method supporting efficient processing of spatial queries over moving objects.3) uses BGI method concept explained above. Actually this system will work as given below.

1) The database is created/maintained at server side.

2) Server broadcast the SMS about services the application is

going to provide and ask for the reply as a token for

registering the user.

3) Client sends reply having token/choices send by the server.

4) Server registers the Client.

5) Client issue Query about the college in particular area in the


6) Server processes Query by using logic also search the no of

registered nearest neighbors using KNN Algorithm given


7) Server Broadcasts the result + list of nearest neighbors to the

Requested client. And broadcast the result to the Number of

nearest neighbors

8) Client then if required broadcast the result to all nearest

neighbors so to void the server's complexity using air

indexing method.

C. Basic Algorithm used

Search the k number of nearest neighbors

Here input is

T //Training data (Here we have training data of database

having the mappings of Various places in city)

K //Number of neighbors (consist the NN)

d //Input tuple to classify (User input such as Query)

KNN algorithm:

//Algorithm to classify tuple using KNN


Find set of neighbors, N, for t

For each d ε T do

if I N I ≤ K , then

N = N Ụ {d};


if Ǝ u ε N such that sim (t,u) ≤ sim (t,d), then


N = N-{u};

N = N Ụ {d};


//Find class for classification

c=class to which the most u N are classified;

KNN algorithm has advantages (1). To exclude the non-relevant attributes from consideration at the data preparation stage (2). To weight each attribute differently when calculating the distance between two instances.


VI. System Design

A. Overall structure

Centralized Server





MH-Mobile Host

Overall system consist the centralized Server which is connected to all registered users. Also each and every user is also connected to each other. So that it will create an easy interface between Server and Clients. Here Clients are static/dynamic e.g. desktop or laptop or mobile user

B. Server Process

As shown in above server process Database is at Server side .When user(MH1 Or MH2 or MH3) issue Query, Centralized Server will process the Query by using his logic Also apply the defined algorithm to find the no of users falling in that area & Sends the RESULT(Query result & Number of nearest neighbors) to requested client..And broadcasts the result to the nearest neighbors.

C .Client Process (process known as air indexing)

MH-Mobile Host

NN-Nearest Neighbor

Description: - MH is Mobile Hosts or it may be a simple system while showing in simple n/w. In above diagram four Mobile hosts are there but we can also increase this no.

MH1 issue query. Server process the Query also finds the list of nearest neighbors (MH2 & MH3) of the requested client (MH1).Broadcast the result and list of nearest neighbors to the MH1. And also broadcast it to the list of nearest neighbors MH2 & MH3.

VII. Conclusions

In this paper we studied spatial query processing in wireless broadcast environments Existing methods have some disadvantages e.g. increases complexity at server and client side.

Which can be overcome in this paper.

In this paper a central server maintains the database, when client sends Query, Sever processes that query and finds the results also finds the no of nearest neighbors using KNN algorithm and broadcasts the Result with the list of nearest neighbors to the requested Client and the results to the nearest neighbor. The clients may process their queries locally, by accessing the broadcast channel. In this setting, our target is to reduce the power consumption and the access latency at the client side. This uses on air indexing that (i) addresses continuous queries, and (ii) considers moving data objects (iii) uses algorithm for to find no. of nearest neighbors.

Broadcast Grid Index (BGI) used in this project is not affected significantly by link errors, and comparison with the current state-of-the-art frameworks for snapshot queries & continuous queries.

A challenging problem is to devise cost models for monitoring spatial queries processing in wireless broadcast environments.

Another interesting direction is to study different types of spatial queries, such as reverse nearest neighbors, and to extend.