System and method for rendering a distributed location-aware system

Description

CROSS REFERENCE TO RELATED APPLICATIONS

This application claims priority to currently co-pending U.S. patent application Ser. No. 12/843,143, filed Jul. 26, 2010, which claims priority to U.S. Provisional Patent Application 61/228,376, filed Jul. 24, 2009, both of which are herein incorporated by reference.

FIELD OF INVENTION

This invention relates to a location-based services (LBS) system and more specifically to the decentralization of an LBS system.

BACKGROUND OF THE INVENTION

In the past, location based services (LBS) systems traditionally consisted of one server controlling a series of field client devices in the same geography.

Accordingly, what is needed in the art is a location bases services (LBS) system that provides for the use of multiple servers and a series of field client devices in a common geographic area.

SUMMARY

This invention includes system-wide scalability of massive location-aware systems. The present invention allows the LBS system to have many servers and shows the network of servers in a single view from where to send ALERT messages to other servers (and their clients) and also zoom in to see the internal network of a particular server. This new network of servers has been implemented using a distributed protocol.

The present invention includes a distributed and decentralized location-aware system. The system includes a number of peers (e.g. LBS servers). Each of the plurality of peers is in communication with the other peers. Each of the plurality of peers is also adapted to communicate a PING message, a PONG message, and an ALERT message. Each of the messages has a header that includes location information. The location information may include latitude and longitude data of the peer or the covering distance of the respective peer.

The peers may also have peer tables. Peer tables include a list of a peer's peers that are online.

Each peer may be in communication with one or more field clients. The covering distance of the peer will expand and contract according to the distance of the field client located farthest from the peer.

Also included is a method of communication between two peers in a distributed location-aware system. The method begins by transmitting a PING message from the first peer to the second peer. The PING message includes a header and a payload. The header of the PING message includes location information and the payload indicates the listening port of the first peer. In response to the PING message, the second peer transmits a PONG message back to the first peer. The PONG message includes a header having location information and a payload indicating the listening port of the second peer, the number of field clients connected to the second peer, and the last message received from the first peer. The first peer transmits an ALERT message to the second peer. The ALERT message includes a header having location information and a payload including an alert message. The location information may include latitude and longitude data of the peer or the covering distance of the respective peer.

Another method of communication in a distributed location-aware system is also included. Here, a peer transmits a PING message. The PING message has a header and a payload. The header contains location information and the payload indicates the peer's listening port. The peer then receives a PONG message. The PONG message also has a header and a payload. The header contains location information and the payload indicates the listening port of another peer, the number of field clients connected to the other peer, and the last message received by the other peer from the original peer. The peer then transmits an ALERT message. The ALERT message includes a header a payload. The header contains location information and the payload includes the alert message. The location information may include latitude and longitude data of the peer or the covering distance of the respective peer.

In addition, the present invention includes a method of rendering a distributed location-aware system. In the method, a communication link between an electronic map and a number of peers is provided. The location information and the covering distance of each of the peers is obtained and used to plot the location and render the covering distance of each peer on the electronic map. A communication link between an electronic control device, such a computer or a smart phone, and the electronic map is additionally provided.

The method may further include receiving a selection of a peer-of-interest and changing the viewing perspective of the electronic map according to the location of the peer-of-interest. This allows a user to view the network of peers from the perspective of the peer-of-interest even when the user is remotely located. In some embodiments, the electronic map is a web-based electronic map, such as Google® Earth. The covering distance may be the area covered by a circle having the location information as the center and a radius given by the distance of the farthest client connected to the peer.

BRIEF DESCRIPTION OF THE DRAWINGS

For a fuller understanding of the invention, reference should be made to the following detailed description, taken in connection with the accompanying drawings, in which:

THE FIGURE is a screen shot of a web interface showing the overlay network of LBS servers in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings, which form a part hereof, and within which are shown by way of illustration specific embodiments by which the invention may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the invention.

The present invention includes a protocol that interconnects several location-based services (LBS) servers. This allows for the scaling and decentralization of LBS systems. The main idea is that field clients are assigned to a particular LBS server and the server represents a group of users to be tracked in some geographical area. Because several (or many) servers could be installed in many different places, a way to create a complete picture of the entire system of servers while not over utilizing the communication lines and the servers was needed. To provide this complete visualization, a decentralized system architecture where all of the servers are interconnected and a new communication protocol to allow for the exchange of required information was created. The visualization can be displayed on any electronic map. Ideally, the electronic map is a web-based electronic map, such as a Google® Earth map. The visualization includes a map of the location, the interconnection of all of the servers and the area that each server is currently tracking. By selecting a desired server through the visualization, the system can connect the desired server and visualize that particular system as if the control station were in that particular place. The connectivity among servers has been developed by a novel protocol, which is described below.

The novel protocol interconnects LBS servers, which may also be referred to herein as peers. To facilitate this, the message headers of the protocol contain location information.

There are three classes of messages in the protocol, which are referred to herein as PING, PONG, and ALERT messages. The first two types of messages, PING and PONG, keep the state of the system and the last peer to broadcast a geographically aware ALERT. The system also provides reliability of the messages by asking a receiving peer to acknowledge a message that has been sent to it. This is because the implementation of the messages uses an unreliable transport layer protocol (e.g. UDP).

Message Header

The message header of the protocol contains the location (latitude, longitude) of the peer that sends a message. An exemplary header is shown in Table 1 below. The fields of the header are described in Table 2 below.

PING Message

A PING message sent by a peer initializes a node in the peer network through a node discovery process. A PING message also serves as a keep alive message for indicating that the node sending the PING is active.

A PING message is responded to by a PONG message. An initial PING message is defined by the header and a payload of four bytes that indicates the port the peer sending the message uses for listening for responses. The PING message sets the payload type field of the header to zero (‘0’), the time to live field to one (‘1’), and the traversed hops to zero (‘0’).

PONG Message

A PONG message is sent by a peer upon receipt of a PING message. A PONG message contains information about a peer currently connected to the overlay network. A PONG message sets the payload type field of the header to one (‘1’), the time to live field to one (‘1’), and the traversed hops to 0.

An exemplary PONG message is shown in Table 3 below. The fields of a PONG message are described in Table 4 below.

ALERT Message

The ALERT message delivers geographically localized messages. An ALERT message sets the flag of the header to one (‘1’), indicating that this is a message that must be acknowledged. An exemplary ALERT message is shown in Table 5 below. The fields of an ALERT message are described in Table 6 below.

Exemplary Protocol Implementation

In an exemplary embodiment, the novel protocol was implemented using UDP as the transport layer protocol.

The protocol keeps a fully connected topology that is maintained by enforcing peers to send messages, at most, once every forty-five seconds. Suppose Peer A has Peer B in its peer table. If no messages from Peer B are received by Peer A in forty-five seconds, Peer A issues a PING message to Peer B and waits for a response. If no PONG response is received in the next twenty seconds, Peer A deletes Peer B from its peer table.

When an ALERT message needs to be sent, the system performs a geographical query over its peer list. The ALERT message is then sent to those peers that comply with one or more of the two following conditions:

• (1) If it lies within the area of the ALERT message, or
• (2) If the area of the ALERT message overlaps some of the area of a peer. This is calculated by adding the radius of the message to the covering radius of the peer. If the peer lies within a circle having a center with the same coordinate of the ALERT message and a radius equal to the summation of the radius of the message and the covering distance, then the peer is notified.

Once each of the selected peers receives the ALERT message, they execute intraALERT procedures, which send the message to all of a peer's field client devices. The system allows any control station (computer) connected to the Internet to connect to any of the servers. Once connected to one particular server, the system displays the overlay network, or the network of servers in the electronic map (e.g. a Google Earth map), each peer in its respective real location, including the area each peer covers. The area covered by each peer is shown as a circumference centered at the server and having a radius equal to the distance of the user located the farthest from the peer. From this map interface, several functions can be performed, as shown in THE FIGURE, and explained in Table 7 below.

THE FIGURE shows two peers in the system. There are two circumferences that describe the current covering area of each of the peers. In the FIGURE, peer 131.247.3.140 has a greater area than the other peer. This is because there is at least one user that is within that area. This area contracts and expands as field clients, which are connected to that particular peer, move.

It will be seen that the advantages set forth above, and those made apparent from the foregoing description, are efficiently attained and since certain changes may be made in the above construction without departing from the scope of the invention, it is intended that all matters contained in the foregoing description or shown in the accompanying drawings shall be interpreted as illustrative and not in a limiting sense.

It is also to be understood that the following claims are intended to cover all of the generic and specific features of the invention herein described, and all statements of the scope of the invention which, as a matter of language, might be said to fall there between.