FIELD OF INVENTION
[0001] The present subject matter relates to tracking systems and, particularly, but not
exclusively, to transit vehicle tracking systems.
BACKGROUND
[0002] People daily travel from one place to other, utilizing different modes of transport.
Many passengers frequently use a transit system to travel between two places, such as workers
travel between home and work, students travel between home and school, and tourists travel to
different places in a city or town. Generally the travel is either through independent vehicles,
such as an automobile or; through a common public transit transport, such as a bus, a train, hopon/
hop-off service vehicles, and a subway. More often than not, in many cities and towns,
common public transit transport vehicles like busses provide transportation on different routes
with several predetermined stops.
[0003] The arrival and departure time of the common public transit transport at any given
stop can vary significantly from day to day for various reasons. Inclement weather, such as fog,
snow, rain, ice, and extreme cold may decrease the travelling speed of the common public transit
vehicle and thus may impede its arrival and departure from the scheduled time. Also, situations,
such as mechanical problems, heavy traffic, intermittent blockades, and accidents may cause
unpredictable delays in timely arrival of the public transit vehicle. In such situations, passengers
utilizing the public transit transport are not generally apprised as to the arrival time, delay if any,
departure time, and other information related to any specific vehicle on a route or, the transit
transport system as a whole.
[0004] Thus, it is desired by all passengers to know when a public transit vehicle, such as
a bus, a truck, a train, and a ferry would be arriving at a specific stop. In situations where the
arrival is delayed, the expected delay and expected time of arrival are also desired. Passengers
sometimes also wish to know the present location of the public transport vehicle or, the last stop
reached by the public transport vehicle for the sake of estimation of arrival time. In order to
provide such information to passengers, various tracking and transit information systems have
been deployed and distributed along the routes of the common public transit transport system.
3
SUMMARY
[0005] This summary is provided to introduce concepts related to transit vehicle tracking
system. This summary is not intended to identify essential features of the claimed subject matter
nor is it intended for use in determining or limiting the scope of the claimed subject matter.
[0006] According to an implementation of the present subject matter, a method for
tracking a transit vehicle on a route travelled by passengers is described. The method includes
broadcasting a first discovery message, through a first communication device of a first
passenger, to the plurality of passengers based on determination of a speed of the transit vehicle
through the speed sensor of the first communication device. The first discovery message includes
a boarding time of the first passenger and a unique identifier (UI) associated with the first
communication device. Further, the method includes receiving discovery messages from a first
set of passengers from amongst the plurality of passengers and, at least one response to the first
discovery message from a second set of passengers from amongst the plurality of passengers.
Each of the responses to the first discovery message includes a boarding time and a UI associated
with a corresponding passenger from amongst the second set of passengers. Furthermore, the
method includes generating a cluster record for the first passenger based on the received
discovery messages and responses to the first discovery message. The cluster record includes
clusters and a cluster chain. Each cluster from amongst the clusters includes a set of passengers
from amongst the plurality of passengers who board the transit vehicle from a same stop.
BRIEF DESCRIPTION OF THE FIGURES
[0007] The detailed description is described with reference to the accompanying figures.
In the figures, the left-most digit(s) of a reference number identifies the figure in which the
reference number first appears. The same numbers are used throughout the figures to reference
like features and components. Some embodiments of system and/or methods in accordance with
embodiments of the present subject matter are now described, by way of example only, and with
reference to the accompanying figures, in which:
[0008] Fig. 1 illustrates a route of a public transport system, in accordance with an
embodiment of the present subject matter;
4
[0009] Fig. 2 schematically illustrates a vehicle tracking system, in accordance with an
embodiment of the present subject matter;
[0010] Fig. 3(a) and 3(b) illustrate a method for cluster formation, in accordance with an
embodiment of the present subject matter; and
[0011] Fig. 4(a) and 4(b) illustrate a method for estimating time of arrival of a transit
vehicle, in accordance with an embodiment of the present subject matter.
[0012] It should be appreciated by those skilled in the art that any block diagrams herein
represent conceptual views of illustrative systems embodying the principles of the present
subject matter. Similarly, it will be appreciated that any flow charts, flow diagrams, state
transition diagrams, pseudo code, and the like represent various processes which may be
substantially represented in computer readable medium and so executed by a computer or
processor, whether or not such computer or processor is explicitly shown.
DESCRIPTION OF EMBODIMENTS
[0013] Systems and methods for tracking transit vehicle of a common public transit
transport are described herein. The methods can be implemented in various computing devices
communicating through various networks. Although the description herein is with reference to
computing devices of a communication network, the methods and systems may be implemented
in other computing devices capable of communication with other computing devices, albeit with
a few variations, as will be understood by a person skilled in the art.
[0014] In a busy lifestyle of cities and towns these days, people frequently travel from
one place to another through common public transit transport. Children utilize busses to travel
between their homes and school, while workers travel between their homes and work places. It is
also common for frequent travelers to catch and change multiple transit vehicles to reach their
destination.
[0015] Different tracking and monitoring systems have been developed and are being
utilized by agencies to provide information of the common public transit transport system to the
passengers. Instead of published schedules and printed time tables, technical systems have been
implemented by various agencies to provide live updates about public transit vehicles to
5
passengers, thereby making the travel predictable and reducing wastage of time and energy.
Some agencies provide updated information on the World Wide Web while others display the
information at different stops and major junction stations. Few agencies also provide update
messages and e-mails to the passengers about the updated information. To provide such
information to the passengers, agencies collect, collate, process, and transmit the updated
information periodically. In certain situations, the information is even collected and processed in
real time.
[0016] To collect and provide the information about public transit vehicles, various
techniques are utilized. While large and state run agencies implement their own tracking systems
including installation of sensing devices to collect such information, certain small agencies rely
on information provided by third party services, such as Google® maps, automatic transit
directions, real-time tracking, and arrival time prediction to provide such information. With
advancement in technology, agencies install dedicated devices, such as Global Positioning
Systems (GPS) and accelerometer sensors on public transit vehicles to track and collect
information about the public transit vehicle.
[0017] Although techniques and systems such as GPS are available for collection and
dissemination of information, the usage of such advanced techniques is more limited to large
transit agencies that either have the necessary in-house expertise or can afford the huge expense
of implementing such systems. In many cities where several small transit agencies provide public
transport facilities, tracking of public transport vehicles is still a problem. Small agencies
generally adopt third party solutions such as described earlier, however, the use of such methods
limit the amount of information and its accuracy.
[0018] Still, to provide information related to public transit transport in a cost effective
manner, recently many agencies have adopted collaborative techniques where tracking
information for public transit transport is collected through Location Based Services (LBS) and
ambience detection methods, with the help of passengers and their communication devices, to
track and identify status of a particular transit vehicle. Agencies collect data through LBS
utilizing GPS coordinates, accelerometer readings, and triangulation of cell phone via the service
provider of the passengers travelling on the public transit vehicle. Although the use of LBS and
6
ambience detection provide tracking information related to public transit transport vehicles, the
implementation is either in-efficient in terms of energy utilization or, faces scalability issues.
[0019] Essentially, the use of collaborative LBS based on GPS consume huge amount of
battery power which drains the battery of the mobile phone of the passenger rather very quickly.
With battery life of mobile phones being unnecessarily drained, not many passengers activate
GPS for information providing purpose during travel. Further, the use of transit information also
requires support from multiple transport agencies, which always is not available. For example,
when the tracking of a transit vehicle is based on a GPS sensor, the location values provided by
the GPS sensor are coordinate values, e.g., longitude and latitude values. These coordinate values
should be compared to the location values defining the vehicle's schedule to determine the
location of the transit vehicle in its respective route. Therefore, the location values produced by
the GPS sensor should be checked for compatibility and correctness with the location values of
the transit vehicle’s schedule that requires huge computations and a constant backend and
transport agency support.
[0020] With use of collaborative LBS utilizing accelerometers and triangulation of
mobile phones of the passengers, cell tower information of the participating mobile phones are
accessed by backend servers of the agencies to detect the route, the travel mode, the current
location and also the traffic condition to predict the arrival time. However, these systems require
a lot of communication with the backend servers due to the continuous upload of cell
information to maintain accuracy. Similarly, utilizing ambience detection methods requires
upload of recorded ambience and continuous communication with the backend servers. Hence,
the use of LBS and ambience detection methods take a toll on the battery life of the participating
mobile devices thereby discouraging passengers to allow communication of information from
their mobile devices. Further, sharing of information through LBS and ambience detection also
possesses privacy concerns as passenger’s information and his whereabouts are shared with a
third party with no absolute control. Many passengers are averse to such disseminate of personal
information as it can lead to privacy issues.
[0021] Moreover, for use of collaborative techniques based on LBS and ambience
detection, data provided by participating passengers needs to be centrally collected, collated and
processed. With colossal coverage area and large number of vehicles in a public transit transport
7
system, implementation of centralized intelligent backend servers is cost intensive and involves
third party support that involves considerable incentive.
[0022] According to an implementation of the present subject matter, methods for
tracking transit vehicles of a public transit transport system are described herein. On one hand,
the described methods provide efficient techniques of tracking transit vehicles and on the other
allow data collection without any backend server, LBS, or third party support. According to the
described implementation of the present subject matter, the data collection is achieved by
collaborative contribution of multiple passengers travelling frequently from one stop to another
in a route. Communication devices of the passengers may provide information about the
boarding time as well as the accelerometer readings to track the transit vehicle. It would be
understood that the public transport vehicles may include, and is not limited to, busses, trains,
trucks, ferries, and other modes of commuting from one place to another.
[0023] In operation, according to the said implementation, passengers travelling
frequently through a route may follow a clustering phase and a subsequent query phase to enable
tracking of the transit vehicle. Further, the communication devices of the passengers may be
configured to communicate to each other based on different communication techniques known in
the art.
[0024] In clustering phase, passengers are identified and assembled to form different
clusters. As described earlier, the transit vehicle may travel from a starting point to a destination
on a fixed route. During the travel between the starting point and the destination, the transit
vehicle may make multiple stops to facilitate boarding and de-boarding of passengers. Few
passengers may board the transit vehicle at the starting point and de-board the transit vehicle at
the destination point while, others may board at any stop during the journey and de-board at any
stop later in the journey. According to the said implementation of the present subject matter,
passengers boarding the transit vehicle from any given stop are collectively included to form one
cluster. For example, during a journey of the transit vehicle, all passengers boarding the transit
vehicle at the starting point may form one cluster. Similarly, all passengers boarding the transit
vehicle at the 1st stop may form another cluster.
[0025] Moreover, the clusters thus formed may be linked to each other by way of a
predecessor or a successor cluster to form a chain of clusters and chain of passengers for the
8
given route. In other words, the clusters and their passengers are linked to form a chain of
communication to exchange information. For example, if passengers i1, i2, …, im board at stop 1,
passengers j1, j2, … jn board at stop 2, passengers k1, k2, … kp board at stop 3, where the transit
vehicle is travelling through stops 1 to stop 3; the passengers i1, i2, …, im collectively form a
cluster Ci, the passengers j1, j2, … jn collectively form a cluster Cj, and the passengers k1, k2, …
kp collectively form a cluster Ck. Further, based on the order of appearance of the clusters in the
journey, the cluster are associated in a chain such as Ci Cj Ck. For the sake of clarity, each
cluster is identified based on a cluster identification or cluster Id. denoted by the cluster number,
such as i, j, and k. For example, for a cluster C1, the cluster Id. associated with it would be 1 and
similarly, the cluster Id. associated with the cluster Ck would be k. In one implementation, the
cluster Id. associated with clusters is incremented based on the order of appearance of the
clusters in the cluster chain. That is, the starting station may have a cluster Id. of 1 and
represented by C1, the second cluster may have a cluster Id. of 2 and represented by C2, and so
on.
[0026] Similar to the cluster chain, a passenger chain may also be formed based on the
order of appearance of their clusters in the route. For example, in the above described scenario,
passengers i1 j1 k1 may form a passenger chain. It would be understood that similar to the
passenger chain of i1 j1 k1, other passenger chains may be formed such as i1 j2 k1, and
i3 j1 k2.
[0027] In an implementation, during the clustering phase, the passengers frequently
travelling through the route may form clusters, cluster chains and passenger chains through their
computing devices, based on boarding time of each passenger. In other words, passengers
sharing a common boarding time may form a part of one cluster while passenger sharing another
common boarding time may form a part of another cluster. As described above, it would be
understood that the passengers with an earlier boarding time would form part of an earlier
cluster. In said implementation, the communication devices of the passengers are configured to
determine the boarding time based on their accelerometer readings.
[0028] To enable formation of clusters in the clustering phase, the communication
devices may broadcast a discovery message including their boarding time and a unique identifier
(UI) to other passengers. Since each passenger would broadcast a discovery message, he may
9
receive multiple discovery messages broadcasted by other passengers. Upon receiving the
discovery messages, based on the boarding time and the UI received in the discovery message,
the computing device of each passenger may form clusters and identify different passengers in
such clusters. For example, if the communication device of a passenger receives 20 discovery
messages from different passengers with 5 unique boarding times, the communication device of
the passenger may identify possibility of existence of 5 clusters and generate a corresponding
cluster record. Further, based on the boarding time of each passenger, the communication device
may identify the passengers to be a part of each of these clusters. For the sake of explanation and
clarity, the cluster to which a passenger himself belongs is referred to as a cluster native to the
passenger and; the clusters to which the passenger does not belong and which merely forms a
part of cluster chain for the passenger are referred to as a clusters non-native to the passenger.
Further, the record of all the clusters, native and non-native to a passenger, along with the
passengers in these clusters are recorded and stored as cluster records by each passenger.
[0029] It would be appreciated that during the clustering phase, communication devices
of passengers already onboard in the transit vehicle may update their cluster records at each stop
to add any new cluster or passenger to the cluster records while, the passengers boarding at each
stop may update their records with passengers onboard in the transit vehicle. Hence, based on
boarding time of each passenger, the communication devices of passengers identify and form
clusters during the clustering phase for future query generation and tracking of the transit
vehicle. It would be further appreciated that the communication device of each passenger may
include cluster records for more than one route generated and collated over a period of time
while the passenger has travelled through the more than one routes in due course of time.
[0030] Upon completion of the clustering phase, passengers with cluster records of a
route and waiting for the transit vehicle may send a query message to determine an estimated
time of arrival (TOA). The communication device of the waiting passenger may determine a
cluster associated with passengers to last board the transit vehicle from the clusters trailing in the
cluster chain. Clusters trailing in the cluster chain with respect to a specific cluster can be
understood to be the clusters whose passengers board the transit vehicle before the said specific
cluster and have a cluster Id. prior than the specific cluster. Upon determination of the cluster to
last board the transit vehicle, the communication device of the waiting passenger may also
determine the boarding time of the passengers of the cluster and its respective cluster Id.
10
[0031] In one implementation, based on the boarding time of passengers to last board the
transit vehicle and the cluster Id., the estimated TOA for the transit vehicle may be determined.
In said implementation, the estimation of TOA is based on average time required by the transit
vehicle to travel from the stop of the identified cluster to last board the transit vehicle till the stop
of the waiting passenger. In said implementation, for frequent passengers, the communication
devices may determine the time taken by the transit vehicle to travel between stops during
previous journeys to ascertain an average time. It would be understood by those skilled in the art
that the accuracy of estimation for TOA may improve with increased number of journeys for
each passenger as the accuracy of value of average time taken by the transit vehicle between
each stop may improve with a large set of previous journey data.
[0032] According to an implementation of the present subject matter, to exchange
messages, such as broadcasting of the discovery messages and response of the broadcasted
discovery messages, the communication devices of the passengers may utilize various
communication techniques known in the art. For instance, the communication devices may
broadcast the discovery messages through Wi-Fi Direct to allow reception by communication
devices in the vicinity. Similarly, in another implementation, the communication devices may
communicate utilizing the near field communication (NFC) techniques to allow limited area
broadcast. In yet another implementation, the communication devices may even utilize radio
access network (RAN) and its communication channels for the purpose of communication with
other communication devices.
[0033] Hence, based on the described method, information of estimated TOA for a transit
vehicle for those passengers waiting at subsequent stops can be determined without the use of
GPS sensors and backend server. The direct exchange of information among the communication
devices of the passengers; the use of accelerometers to identify passengers travelling in the same
vehicle and; involving only client side processing, that is, at the communication devices of the
passengers to map passengers to the location of the transit vehicle and determine TOA allow
easy and efficient way of tracking the transit vehicle. Further, the described methods maintain
user privacy and also reduce communication costs besides providing fairly accurate location and
arrival time prediction.
11
[0034] The described methodologies can be implemented in hardware, firmware,
software, or a combination thereof. For a hardware implementation, the processing units can be
implemented within one or more application specific integrated circuits (ASICs), digital signal
processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices
(PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers,
microprocessors, electronic devices, other electronic units designed to perform the functions
described herein, or a combination thereof. Herein, the term "system" encompasses logic
implemented by software, hardware, firmware, or a combination thereof.
[0035] For a firmware and/or software implementation, the methodologies can be
implemented with modules (e.g., procedures, functions, and so on) that perform the functions
described herein. Any machine readable medium tangibly embodying instructions can be used in
implementing the methodologies described herein. For example, software codes and programs
can be stored in a memory and executed by a processing unit. Memory can be implemented
within the processing unit or may be external to the processing unit. As used herein the term
"memory" refers to any type of long term, short term, volatile, nonvolatile, or other storage
devices and is not to be limited to any particular type of memory or number of memories, or type
of media upon which memory is stored.
[0036] In another firmware and/or software implementation, the functions may be stored
as one or more instructions or code on a non transitory computer-readable medium. Examples
include computer-readable media encoded with a data structure and computer-readable media
encoded with a computer program. Computer-readable media may take the form of an article of
manufacturer. Computer-readable media includes physical computer storage media. A storage
medium may be any available medium that can be accessed by a computer. By way of example,
and not limitation, such computer-readable media can comprise RAM, ROM, EEPROM, CDROM
or other optical disk storage, magnetic disk storage or other magnetic storage devices, or
any other medium that can be used to store desired program code in the form of instructions or
data structures and that can be accessed by a computer; disk and disc, as used herein, includes
compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and Blu-ray
disc where disks usually reproduce data magnetically, while discs reproduce data optically with
lasers. Combinations of the above should also be included within the scope of computer-readable
media.
12
[0037] It should be noted that the description merely illustrates the principles of the
present subject matter. It will thus be appreciated that those skilled in the art will be able to
devise various arrangements that, although not explicitly described herein, embody the principles
of the present subject matter and are included within its spirit and scope. Furthermore, all
examples recited herein are principally intended expressly to be only for pedagogical purposes to
aid the reader in understanding the principles of the invention and the concepts contributed by
the inventor(s) to furthering the art, and are to be construed as being without limitation to such
specifically recited examples and conditions. Moreover, all statements herein reciting principles,
aspects, and embodiments of the invention, as well as specific examples thereof, are intended to
encompass equivalents thereof.
[0038] The manner in which the systems and methods shall be implemented has been
explained in details with respect to the Fig. 1-4. While aspects of described systems and methods
can be implemented in any number of different computing systems, transmission environments,
and/or configurations, the embodiments are described in the context of the following exemplary
system(s).
[0039] Fig. 1 illustrates a route of a public transit transport system 100 including a route
of a transit vehicle. The public transit transport system 100 may implement a vehicle tracking
system 102 for providing tracking of the transit vehicle, in accordance with an embodiment of
the present subject matter. For the sake of explanation, the vehicle tracking system 102 is
referred to as system 102 hereinafter. The system 102 described herein, can be implemented in
any network environment comprising a variety of communication networks and network devices.
The route may include an origin 103-1 and a destination 103-2 between which a transit vehicle
104 may travel.
[0040] In one implementation, the system 102 for tracking the transit vehicle 104 is
implemented in a communication device including, but not limited to, pagers, communicators,
hand-held devices, laptops or other portable computers, tablet computers, mobile phones, PDAs,
Smartphones, and the like. The communication devices implementing the system 102 are carried
by the passengers of the transit vehicle 104 during their journey from location to another.
[0041] The transit vehicle 104 may be any transit vehicle that may be used by passengers
to travel from one place to another. The transit vehicle 104 may include, but not limited to, bus,
13
truck, train, ferry, and the like. Further, the transit vehicle 104 while travelling between the
origin 103-1 and the destination 103-2 may halt at different stops 106-1, 106-2, …., 106-7,
commonly referred to as stops 106 hereinafter, for boarding and de-boarding of passengers on
the route. For the sake of explanation, individual stops 106 have been depicted as A, B, …, H
respectively. The passengers may board at any stop 106 including the origin 103-1 and, may deboard
at any later stop in the route including the destination 103-2.
[0042] As described before, passengers boarding the transit vehicle 104 from one stop
are combined together to form one cluster. Hence, the passengers boarding the transit vehicle
104 from the origin 103-1 are combined to form cluster C0. Similarly, the passengers boarding
the transit vehicle 104 at the 1st stop ‘A’ may form a cluster C1 and the passengers boarding the
train at stop ‘H’ may form a cluster C7. As described before, each cluster is also associated with a
cluster Id. and is denoted in increasing order of their appearance on the route. Hence, the cluster
Id. for cluster C2 is defined as 2 while the cluster Id. associated with cluster C5 is defined as 5.
As depicted in the figure, there may be different number of passengers in each cluster as there
may be different number of passengers boarding the transit vehicle at each stop. For example, at
stop ‘B’, it is depicted that the cluster C2 includes 5 passengers while at stop D only 3 passengers
are included in the cluster C3.
[0043] For the purpose of explanation, it is assumed that the transit vehicle 104 while
traveling through the route from the origin 103-1 to the destination 103-2, has crossed stops ‘A’
and ‘B’ and, is travelling towards stop ‘D’. Further, it is also assumed that the passengers of the
clusters C0, C1, and C2 have boarded the transit vehicle 104 while the passengers of the
successive clusters, such as C3, C4, C5, C6, and C7 are still waiting to board the transit vehicle
104 from their respective stops 106.
[0044] In situations such as described above, for the passengers waiting at their
respective stops 106 to track the transit vehicle, the communication devices of the passengers are
configured to follow a clustering phase and a subsequent query phase. During the clustering
phase, communication devices of the passengers who have boarded the transit vehicle 104 may
determine the other passengers onboard and, update their cluster records accordingly. In one
implementation, a clustering module 112 of the vehicle tracking system 102 is configured to
update the cluster records for each passenger.
14
[0045] In said implementation, when a passenger boards the transit vehicle 104 at a stop
106, the communication device of the passenger initiates the clustering phase. In operation, the
clustering module 112 may broadcast a discovery message upon boarding the transit vehicle 104.
The discovery message may include the boarding time of the passenger along with a unique
identifier (UI) of the passenger. The boarding time of the passenger may be accessed based on
reading of a sensor, such as an accelerometer of the communication device of the passenger.
Further, the UI of the passenger may uniquely identify the passenger, such as an Internet
Protocol (IP) address. Since multiple passengers may board the transit vehicle at a stop, all
passengers boarding the transit vehicle at a stop would transmit their own discovery message for
cluster identification. For example, after the passengers of the cluster C2 have boarded the transit
vehicle 104 at the stop B, the communication devices of the passengers may transmit the
discovery message to all the passengers in the transit vehicle 104.
[0046] In such a situation, while the communication devices of last boarded passengers
are broadcasting and receiving discovery messages, the communication devices of passengers
already on board are only receiving the discovery messages. For example, in the above described
scenario, while the passengers of cluster C2 are broadcasting their own discovery messages and
receiving discovery messages from other passengers of cluster C2, the passengers of cluster C1
and C0 are only receiving the discovery messages.
[0047] In one implementation of the present subject matter, upon receiving a discovery
message, clustering module 112 in the communication device of each passenger may reply with
a response message including their own boarding time and UI. According to an implementation
of the present subject matter, to broadcast the discovery messages and response of the
broadcasted discovery messages, the communication devices of the passengers may utilize
various techniques known in the art. For instance, the communication devices may broadcast the
discovery messages through Wi-Fi Direct to allow reception by communication devices in the
vicinity. Similarly, in another implementation, the communication devices may communicate
utilizing the near field communication techniques to allow limited area broadcast. In yet another
implementation, the communication devices may even utilize radio access network (RAN) and
its communication channels for the purpose of communication with other communication
devices.
15
[0048] In said implementation of the present subject matter, upon receiving the discovery
messages and their corresponding response from the communication devices of fellow
passengers, the clustering module 112 is configured to form clusters and update cluster records.
For example, in the above described scenario where the passengers of cluster C2 have last
boarded the transit vehicle 104, the passengers who have boarded the transit vehicle at origin
103-1 and stop ‘A’ would identify the presence of cluster C2 and its respective passengers based
on the received discovery messages whereas; the passengers of the cluster C2 would identify the
fellow passengers of their own native cluster based on the received discovery messages.
Similarly, based on the response messages received from the communication devices receiving
the discovery message, the passengers of the cluster C2 would determine their predecessor
clusters and their respective passengers.
[0049] In situations where a passenger is boarding the transit vehicle 104 on the route for
the first time, the clustering module 112 may create cluster records based on boarding time and
UI of passengers received through the discovery messages and their response. For example, if a
passenger boards the transit vehicle 104 for the first time from the stop ‘B’, the clustering
module 112 through the communication device of the passenger may identify the fellow
passengers belonging to the native cluster based on the discovery messages and, may identify the
predecessor clusters C0, and C1 and; their respective passengers based on the discovery message
responses. However, it would be understood that in situations when a passenger has already
travelled on the route before and boards the transit vehicle 104, the clustering module 112 may
merely update the cluster records with any new passengers on the transit vehicle 104, based on
the received discovery messages and their response.
[0050] In one implementation of the present subject matter, the passengers with cluster
records available with their communication devices based on previous journeys may send query
messages to track the transit vehicle 104. To this end, the passengers waiting for the transit
vehicle at their stops 106 may send a query message directly to passengers in the predecessor
clusters with respect to their native cluster and determine the cluster which has last boarded the
transit vehicle 104. The proposed methods of determination and query message propagation
through the cluster chains are described with respect to the subsequent figures for the sake of
clarity and brevity. In said implementation, upon determining the cluster, the communication
16
device of the passenger may identify a probable position of the transit vehicle 104 and an
estimated time of arrival (TOA) of the transit vehicle 104 at a particular stop 106.
[0051] Fig. 2 describes the schematic implementation of the system 102, in accordance
with an implementation of the present subject matter. The system 102 includes processor(s) 204.
The processor 204 may be implemented as one or more microprocessors, microcomputers,
microcontrollers, digital signal processors, central processing units, state machines, logic
circuitries, and/or any devices that manipulate signals based on operational instructions. Among
other capabilities, the processor(s) is configured to fetch and execute computer-readable
instructions stored in the memory.
[0052] The functions of the various elements shown in the figure, including any
functional blocks labeled as “processor(s)”, may be provided through the use of dedicated
hardware as well as hardware capable of executing software in association with appropriate
software. When provided by a processor, the functions may be provided by a single dedicated
processor, by a single shared processor, or by a plurality of individual processors, some of which
may be shared. Moreover, explicit use of the term “processor” should not be construed to refer
exclusively to hardware capable of executing software, and may implicitly include, without
limitation, digital signal processor (DSP) hardware, network processor, application specific
integrated circuit (ASIC), field programmable gate array (FPGA), read only memory (ROM) for
storing software, random access memory (RAM), non-volatile storage. Other hardware,
conventional and/or custom, may also be included.
[0053] Also, the system 102 includes interface(s) 206. The interfaces 206 may include a
variety of software and hardware interfaces that allow the system 102 to interact with the entities
of communication device, such as sensors; and communication network, or with each other. The
interfaces 206 may facilitate multiple communications within a wide variety of networks and
protocol types, including small range and long distance wireless networks, RAN, cellular,
satellite-based network, etc.
[0054] In another embodiment of the present subject matter, the system 102 may also
include a memory 208. The memory 208 may be coupled to the processor 204. The memory 208
can include any computer-readable medium known in the art including, for example, volatile
memory, such as static random access memory (SRAM) and dynamic random access memory
17
(DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable
programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes.
[0055] Further, the system 102 may include module(s) 210 and data 212. The modules
210 and the data 212 may be coupled to the processors 204. The modules 210, amongst other
things, include routines, programs, objects, components, data structures, etc., which perform
particular tasks or implement particular abstract data types. The modules 210 may also be
implemented as, signal processor(s), state machine(s), logic circuitries, and/or any other device
or component that manipulate signals based on operational instructions.
[0056] Further, the modules 210 can be implemented in hardware, instructions executed
by a processing unit, or by a combination thereof. The processing unit can comprise a
communication device, a processor, a state machine, a logic array or any other suitable devices
capable of processing instructions. The processing unit can be a general-purpose processor which
executes instructions to cause the general-purpose processor to perform the required tasks or, the
processing unit can be dedicated to perform the required functions.
[0057] In an implementation, the module(s) 210 includes the clustering module 112, a
query managing module 214, a communicating module 216, and other module(s) 218. The other
module(s) 218 may include programs or coded instructions that supplement applications or
functions performed by the system 102. In said implementation, the data 212 includes route and
cluster data 220, Travelling time data 222, and other data 224. The other data 224 amongst other
things, may serve as a repository for storing data that is processed, received, or generated as a
result of the execution of one or more modules in the module(s) 210.
[0058] As mentioned before, the system 102 is configured to allow passengers of the
transit vehicle 104 to track the transit vehicle’s location and estimate its expected TOA. In one
implementation of the present subject matter, the system 102 is implemented in communication
devices of passengers traveling with the transit vehicle 104. The clustering module 112 of the
system 102 is configured to form clusters and update cluster records based on boarding time and
unique identifier (UI) associated with the passengers.
[0059] In operation, passengers of a route are divided into clusters based on the stop
from which they board the transit vehicle 104. In other words, passengers boarding the transit
vehicle 104 from one stop form one cluster while the others boarding from another stop form
18
another cluster. Communication devices of passengers may determine that the passenger has
boarded the transit vehicle 104 based on speed of the transit vehicle 104. In one implementation,
through the interface 206, the clustering module 112 may determine the speed of the transit
vehicle 104 based on reading of a sensor, such as an accelerometer. In said implementation, the
sensor to detect the speed of the transit vehicle 104 may either be present on the communication
device of the passenger or, may be installed on the transit vehicle 104.
[0060] In situations where the sensor is present on the communication device, the
determination of the speed of the transit vehicle 104 may be made through a direct access to the
sensor data and a corresponding boarding time may be estimated. For example, the boarding time
may be estimated to the instance when the speed of the transit vehicle 104 is determined to be
greater than a pre-determined threshold speed value. It would be understood that when the
passengers have boarded the transit vehicle 104, the transit would accelerate to increase its speed
and; the pre-determined threshold speed value may be a threshold speed to identify that the
transit vehicle 104 has left the stop and is in motion.
[0061] Similarly, in situations where the sensor is installed on the transit vehicle 104, the
sensor may broadcast a boarding message at every stop to the communication devices of the
passengers travelling in the transit vehicle 104. The boarding message, in one implementation,
may include stop details along with the boarding time. For example, when the transit vehicle 104
leaves a stop after passengers have de-boarded and boarded the transit vehicle 104, the sensor
may determine the speed of the transit vehicle 104. Upon determination of the speed to be
greater than the pre-determined threshold speed value, a boarding time for the passengers may be
set to the time at which the speed had become greater than the pre-determined threshold speed
value. It would be understood that only the passengers who have boarded the transit vehicle 104
on the stop for which the boarding message has been broadcasted may accept the message based
on the stop details, while the passengers who are already travelling in the transit vehicle 104
from before may reject the boarding message.
[0062] The communication module 216 of the system 102, upon determining the
boarding time of the passenger may broadcast the discovery message. As described before, the
communication module 216 may also receive discovery messages and response to the discovery
messages from other fellow passengers. Based on the received discovery messages and response
19
of discovery messages, the clustering module 112 may identify clusters and determine cluster
chains for the route. It would be appreciated that few passengers may travel on the route for the
first time while others may have travelled on the route before. Hence, based on the situation as it
may be, the clustering module 112 may either generate a new cluster record or, may update it
own previous cluster record during the clustering phase. The clusters thus formed may also be
linked to form cluster chain based on which the transit vehicle 104 is tracked. Since the method
of cluster determination and cluster chain formation has been described with respect to the Fig.
1, the details have been omitted here for the same of brevity.
[0063] In one implementation of the present subject matter, the clustering module 112 is
configured to either update the existing cluster records or generate a new cluster record based on
route parameters. Route parameters are associated with each cluster record to distinguish cluster
records for one another. That is, a passenger may travel through different routes during his
journey from one geographical location to another. Further, the passenger may also travel
between different geographical locations. For example, the passenger may travel from point A to
point B from routes 1, 2, and 3 depending on the day and time of travel considering traffic and
other conditions. Similarly, on certain occasions, the passenger may also travel from point C to D
through route 4 and; from M to N through routes 5 and 6. In such situations, the clustering
module 112 may maintain different cluster records along with passenger details independently
for each route. Hence, in the above described example, the clustering module 112 of the
passenger may have a separate cluster record for each route 1, 2, 3, 4, 5, and 6. The route
parameters associated with each cluster record may signify the route details, such as route Id.,
route location, route distance, number of clusters on the route, the transit vehicle 104 number
travelling on the route. Days and time on which the route is travelled by the passenger, and
frequency of travel of the passenger on the route. Based on the route parameters, the clustering
module 112 may determine the exact route travelled by the passenger and may determine the
clusters and associated corresponding cluster chain. Further, the clustering module 112 may store
the formed clusters along with corresponding route in the route and cluster data 220.
[0064] In one implementation, the clustering module 112 is further configured to store
the time taken to travel between stops of the transit vehicle. This time may be determined based
on the difference of boarding time of two different passengers of consecutive clusters. Hence, the
travelling time between two stops may be computed and stored in the travelling time data 222.
20
[0065] In situations where based on the route parameters the clustering module 112 does
not determine any exiting cluster record, the clustering module 112 is configured to generate a
new cluster record for the route and form cluster chain thereafter. For example, if the passenger
plans to travel through a new route, say route 7 for which no cluster record exists, the clustering
module 112 may generate a separate cluster record for the same by exchanging information with
other passengers during the clustering phase.
[0066] In one implementation of the present subject matter, the clustering module 112
identifies the route parameters either through the communication device sensors of the
communication device or through inputs provided by the passenger. For example, a passenger
before travelling a route may provide the route Id. on which he wishes to travel. Based on the
route Id., the clustering module 112 may determine whether a cluster record for the route exist or
not. Upon such a determination, the appropriate action of either updating or creating a cluster
record for the route may be adopted by the clustering module 112 during the clustering phase.
[0067] While a passenger is waiting, referred to as a waiting passenger hereinafter, for
the transit vehicle 104 to arrive at his stop, he may wish to determine the status of the transit
vehicle 104 and, an estimated TOA. In one implementation of the present subject matter, to
determine the status of the transit tracking vehicle 104, the cluster which has last boarded the
transit vehicle 104 may be determined by the waiting passenger. To this end, the communicating
module 216 is configured to identify communication devices of other passengers in the cluster
record and, send a query message to the identified communication devices. The communication
module 216 of the system 102 may either utilize a hopping communication method, or a direct
communication method to send the query message.
[0068] Through the hopping communication method, the communication module 216 of
the waiting passenger may first send the query message to the communication devices of
passengers who are identified to be a part of the cluster native to the waiting passenger which is
propagated to predecessor cluster in the cluster chain. That is, the query is first sent to the
passengers who board the transit vehicle 104 from the same stop as that of the waiting passenger,
which is then propagated to the passengers who board the transit vehicle 104 on a previous stop,
and so on. In one implementation, the query message may include a hop parameter to track the
number of cluster being queried. In other words, if query message is sent to the passengers of the
21
cluster native to the waiting passenger, the hop parameter value may be 0 while when a cluster
predecessor to the native cluster of the waiting passenger is queried, the hop parameter value
may be 1. Hence in a cluster chain of clusters C1 C2 C3 C4 C5 C6 , if the native
cluster of the waiting passenger is C5, the hop parameter value for the query message sent to the
passengers of cluster C5 may be 0 and the hop parameter value for the cluster C2 may be 3. It
would be appreciated by those skilled in the art that the hop parameter is associated with the
query message to determine the number of clusters queried and therefore, the hop parameter
value may be incremented through any predetermined quantum.
[0069] The query message is sent first to the passengers which are a part of the cluster
native to the waiting passenger to identify whether the transit vehicle 104 is yet to arrive at the
stop or has already left from the stop. For example, it is possible that the waiting passenger may
be standing on the stop waiting for the transit vehicle 104 while the transit vehicle has already
left the stop before the waiting passenger actually arrived. Hence, the communication module
216 of the system 102 may first send the query message to the passengers of the cluster native to
the waiting passenger. As described earlier, during the clustering phase communication devices
exchange their UI with communication devices of other passengers and the UI details are stored
by the clustering module 112 in the cluster records along with the passengers’ details. Hence, in
one implementation of the present subject matter, the query message may be sent to the
passengers based on their UI. In situation where the UI is the IP address of the passengers, the
query message may be sent through Internet. Further, if the UI is an International Mobile
Subscriber Identity (IMSI) number, the query message may be sent through a RAN, such as
Global System for Mobile (GSM), Universal Mobile Telecommunications System (UMTS),
Code division multiple access (CDMA), and Long Term Evolution (LTE).
[0070] In the hopping communication method, the communication devices of the
passengers receiving the query message, referred to as query receiving passengers, are
configured to determine whether their cluster is travelling in the transit vehicle 104 or not. The
query receiving passengers may attempt to find other passengers of their native cluster in the
vicinity and checks whether they are travelling in the same direction using the speed sensor of
the communication device, such as the accelerometer. To this end, the query managing module
214 of one of a query receiving passenger’s communication device may determine other
22
passengers of its own native cluster in the vicinity by sending a ping message through a short
distance communication technique, such as Wi-Fi Direct.
[0071] If the determined number of other passengers is greater than a pre-determined
number, the query managing module 214 is further configured to determine a relative speed
between the query receiving passenger and the determined other passengers. For this purpose,
the query managing module 214 may send multiple probe messages with a sent_time time stamp
to the other passengers. The sent_time time stamp may indicate the time at which the probe
message was been sent. In one implementation, each of the multiple probe messages may be sent
after a short duration of time. Each of the other passengers upon receiving the probe message
may reply with a response probe message with a receive_time time stamp. The receive_time time
stamp may indicate the time at which the probe message was received by the other passengers.
Upon completion of the exchange of probe messages and their corresponding response probe
messages, if the query managing module 214 of the query receiving passenger determines that
the difference between the receive_time time stamp and the sent_time time stamp is less than a
threshold and; the reading of a speed sensor of the communication device indicates that the
transit vehicle 104 is in motion, it is determined that the cluster is in motion and the passengers
of the cluster has boarded the transit vehicle 104. As described before, the speed sensor may be a
sensor that may determine speed of an object based on its motion, such as the accelerometer.
Hence, if a threshold number of passengers of the queried cluster are found to be near and
moving, the query managing module 214 of the query receiving passenger’s communication
device may determine that the transit vehicle has left the stop corresponding to the cluster and,
send a response message to the waiting passenger’s communication device.
[0072] However, in situations where either the number of other passengers is not greater
than a pre-determined number or, the difference between the receive_time time stamp and the
sent_time time stamp is greater than a threshold or, the reading of a speed sensor of the
communication device indicates that the transit vehicle 104 is not in motion, the query managing
module 214 determines that the queried cluster has not boarded the transit vehicle 104. In such a
situation, the query managing module 214 is configured to increment the hop parameter value
and send the query message with the modified hop parameter value to a predecessor cluster in
the cluster chain.
23
[0073] For example, in a cluster chain of clusters C1 C2 C3 C4 C5 C6, if the
waiting passenger is at cluster C5, the query message with hop parameter value 0 is first received
by a query receiving passenger of the cluster C5 itself. The query managing module 214 may
determine the other passengers of the cluster C5 to be in the transit vehicle 104 based on their
relative speed and speed of the transit vehicle. In situation where the cluster C5 is identified to be
in the transit vehicle 104, the communication module 216 may send the response to the received
query message to the waiting passenger to indicate that the transit vehicle has already left the
stop. However, if the query managing module 214 determines the cluster C5 to have not boarded
the transit vehicle 104, the query message with incremented hop parameter value 1 is sent to the
passengers of the cluster C4.
[0074] Now, in the above described situation where the cluster C5 is determined to have
not boarded the transit vehicle 104, the passengers of the cluster C4 may now determine if they
have boarded the transit vehicle or not. If based on the above described method, it is determined
that the cluster C4 has boarded the transit vehicle 104, the waiting passenger may receive the
reply from the cluster C4 along with a hop parameter value of 2. Further, if it is determined that
the cluster C4 has also not boarded the transit vehicle 104, the query message would be
forwarded to the passengers of the cluster C3 with the incremented hop parameter value of 3.
Therefore, it would be appreciated that in the hopping communication method, the waiting
passenger receives a response to the query message along with a hop parameter value, sent only
from the cluster which has last boarded the transit vehicle 104. Otherwise, the query message is
propagated from one cluster to another down the cluster chain.
[0075] In one implementation of the present subject matter, the query managing module
214 of the query receiving passenger’s communication device is configured to determine the
estimated TOA for the transit vehicle 104 to reach the waiting passenger’s stop, based on the
received hop parameter value. Since the query message has been received by the hopping
communication method, the stop of the waiting passenger is determined by the query managing
module 214 based on the hop parameter value. The query managing module 214 may add the
hop parameter value to its native cluster’s cluster Id. to determine the cluster from which the
query was generated and, the stop at which the waiting passenger is waiting. For example, in the
above described example where the cluster chain includes clusters C1 C2 C3 C4 C5
C6 and the waiting passenger is at cluster C5, if a passenger of cluster C2 is determined to be the
24
last boarded cluster, based on the hop parameter value of 3 and the cluster Id., the sum would be
determined to be 5 indicating that the query generated at cluster C5. In such situations since at
least one passenger of the cluster C2 would have travelled to cluster C5 before, an estimated TOA
for the transit vehicle 104 to reach the cluster C5 is determined and provided to the waiting
passenger through a response message.
[0076] In another implementation of the present subject matter, the estimated TOA for
the transit vehicle 104 to reach the stop of the waiting passenger is computed by the waiting
passenger’s computing system itself. In said implementation, the query managing module 214 of
the waiting passenger’s communication device is configured to determine the estimated TOA for
the transit vehicle 104, based on the received hop parameter value in the response to the query
message. In operation, the query managing module 214 is configured to compute a difference
between the cluster Id. of the waiting passenger and the hop parameter value received in the
response to the query message to determine the cluster which has last boarded the transit vehicle.
For example, in the above described scenario where the cluster chain includes clusters C1 C2
C3 C4 C5 C6 and the waiting passenger is at cluster C5, if a response to the query
message is received with hop parameter value 3, it is computed that the last cluster to board the
transit vehicle is C2. Since the waiting passenger has cluster information, it would be understood
that the waiting passenger have at least once travelled through the route. Further, since the
clusters on a route are identified based on boarding time of different passengers, it would also be
understood that the waiting passenger would include the travel time data defining the time taken
by the transit vehicle to travel from one stop to another. Hence, based on the travel time 222, an
estimate to travel from the stop of the last boarded cluster to the stop of the waiting passenger’s
stop can be computed.
[0077] As described before, the communication module 216 of the system 102 may
either utilize a hopping communication method, or a direct communication method to send the
query message and determine the last cluster to board the transit vehicle 104. While the
communication module 216 utilizes the direct communication method, the query message is not
propagated from one cluster to another and instead, the waiting passenger itself queries the
clusters in the cluster chain. In operation, the first query message is sent to the passengers in the
cluster native to the waiting passenger’s cluster. In situation it is determined that the passengers
of the cluster have not boarded the transit vehicle 104, a response query message is sent by the
25
passengers of the native cluster to the waiting passenger. Since the communication mode is
direct, instead of propagation of the query message to the predecessor cluster by the passenger of
the native cluster, a new query message is sent by the waiting passenger itself to the predecessor
cluster with an incremented hop parameter value. Hence, the waiting passenger queries each
cluster in the cluster chain one by one to identify the last cluster to board the transit vehicle.
Since the method adopted by the passengers of a cluster to identify if they have boarded the
transit vehicle 104 is the same as explained before, the details of the same have been omitted
here for the sake of brevity. Further, the estimated TOA may also be determined either by the
waiting passenger based on the identified cluster and travel time data 222 or, by a passenger of
the last boarded cluster based on average speed of the vehicle.
[0078] Fig. 3(a) and 3(b) illustrates method to generate clusters during the clustering
phase for tracking of a transit vehicle, according to an embodiment of the present subject matter.
Further, Fig. 4(a) and 4(b) illustrate method to determine an estimated Time of Arrival (TOA) of
the transit vehicle to a stop, according to an embodiment of the present subject matter. The order
in which the methods 300, 350, 400 and 450 are described is not intended to be construed as a
limitation, and any number of the described method blocks can be combined in any order to
implement the methods, or any alternative methods. Additionally, individual blocks may be
deleted from the methods without departing from the spirit and scope of the subject matter
described herein. Furthermore, the methods can be implemented in any suitable hardware,
software, firmware, or combination thereof.
[0079] The methods may be described in the general context of computer executable
instructions. Generally, computer executable instructions can include routines, programs, objects,
components, data structures, procedures, modules, functions, etc., that perform particular
functions or implement particular abstract data types. The methods may also be practiced in a
distributed computing environment where functions are performed by remote processing devices
that are linked through a communications network. In a distributed computing environment,
computer executable instructions may be located in both local and remote computer storage
media, including memory storage devices.
[0080] A person skilled in the art will readily recognize that steps of the methods can be
performed by programmed computers and communication devices. Herein, some embodiments
26
are also intended to cover program storage devices, for example, digital data storage media,
which are machine or computer readable and encode machine-executable or computerexecutable
programs of instructions, where said instructions perform some or all of the steps of
the described methods. The program storage devices may be, for example, digital memories,
magnetic storage media, such as a magnetic disks and magnetic tapes, hard drives, or optically
readable digital data storage media. The embodiments are also intended to cover both
communication network and communication devices configured to perform said steps of the
exemplary methods.
[0081] Referring to Fig. 3(a), at block 302, speed of a transit vehicle is determined to be
greater than a threshold, based on speed sensor reading from a communication device of a
passenger travelling in the transit vehicle. In one implementation of the present subject matter, a
vehicle tracking system, such as the system 102 may be implemented in the communication
device of the passenger. In said implementation, the communication device of the passenger who
has boarded the transit vehicle, such as a train, a bus, a track, and a ferry may determine the
speed of the transit vehicle through the speed sensor, such as an accelerometer. A speed greater
that the threshold speed signifies that the transit vehicle is in motion and has left a stop from
which the passenger has boarded the transit vehicle.
[0082] At block 304, upon determining that the transit vehicle is in motion with a speed
greater than the threshold, a boarding time for the passenger is identified. The system 102 may
determine the boarding time to be the time instance at which the transit vehicle attains the speed
greater than the threshold. In another implementation, the passenger may receive a boarding time
broadcast message from a sensor on the transit vehicle with the boarding time details.
[0083] At block 306, the communication device of the passenger may broadcast a
discovery message to the other passengers of the transit vehicle. The discovery message may
include at least a unique identifier (UI) associated with the communication device of the
passenger and, the boarding time of the passenger. It would be understood that the boarding time
of the passenger is the time at which the passenger boards the transit vehicle, determined by the
time instance when the transit vehicle is set in motion. Based on the discovery message, the
passenger may determine other passengers that have boarded the transit vehicle along with the
27
passenger. Further, the passengers who are already onboard in the transit vehicle may also
identify the newly boarded passenger through the discovery message.
[0084] Referring to Fig. 3(b), cluster information is updated by passengers of the transit
vehicle based on the described method 350. At block 352, a first boarding time associated with a
first passenger is identified based on speed sensor reading of a first communication device of the
first passenger. In one implementation, the first passenger may have recently boarded the transit
vehicle on a route to travel from one point to another.
[0085] At block 354, a discovery message is received by the first passenger, from a
second communication device of a second passenger. Further, the discovery message may
include at least a second boarding time and a unique identifier (UI) associated with the second
passenger. The UI may identify each communication device of a passenger uniquely and
therefore may include, but not limited to, IP address, IMSI number, IMEI number, and the like.
In one implementation of the present subject matter, the second passenger may either be a
passenger who has boarded the transit vehicle with the first passenger from a same stop or, may
have boarded the transit vehicle after the first passenger from a later stop. It would be
appreciated that since the first passenger receives the discovery message from the second
passenger, the second passenger has either boarded along with the first passenger or, has boarded
later than the first passenger.
[0086] At block 356, the communication device of the first passenger may compare the
boarding time of the second passenger with its own boarding time to identify a differential
boarding time. That is, a comparison of the first boarding time with the second boarding time.
[0087] At block 358, it is determined whether the identified differential boarding time is
greater than a pre-determined threshold. In case the determination is negative, the control flows
to block 360 (‘No’ branch), whereas if the determination is positive, the control flows to block
366 (‘Yes’ branch). It would be understood that in situation where the differential boarding time
is not greater than the threshold, the first passenger and the second passenger would have
boarded the transit vehicle from the same stop. Similarly, where the differential boarding time is
greater than the threshold, the second passenger would have boarded the transit vehicle after the
first passenger.
28
[0088] At block 360 (‘NO’ branch) where it has been determined that both the first and
the second passenger have boarded the transit vehicle together, the second passenger details are
stored in a cluster native to the first passenger. The second passenger details may include the
boarding time of the second passenger along with the UI of the second communication device.
[0089] At block 362, the first passenger details are sent to the second communication
device along with the UI and boarding time of the first passenger for storage. The
communication device of the second passenger may store the first passenger details in a cluster
native to the second passenger as the first and second passenger have boarded the transit vehicle
at the same stop and, belong to the same cluster.
[0090] At block 364, the first communication device may exchange the cluster record of
its own, which is native to the first passenger, with other passengers for updating the cluster
information. In one implementation, based on the exchange of cluster record, the passenger
information gathered by the first communication device is made available to other passengers as
well. Furthermore, based on the exchange, the cluster records can also be verified for
correctness. Hence, exchange of cluster record information may allow effective updating of
cluster records.
[0091] At block 366, (‘Yes’ branch) where it has been determined that both the first and
the second passenger have not boarded the transit vehicle together, first passenger details along
with an associated UI and the first boarding time are sent to the second communication device of
the second passenger. The first passenger details can be stored by the second passenger in a
cluster non-native to the second passenger since the first passenger is determined to have
boarded the transit vehicle from a stop prior to the stop of the second passenger.
[0092] At block 368, the details of the first passenger received through the discovery
message including the boarding time and the UI are sent by the first communication device to the
passengers in the cluster native to the first passenger to share the second passenger details with
other passengers.
[0093] Referring to Fig. 4(a), a waiting passenger at a stop may query to determine an
estimated time of arrival (TOA) based on the described method 400. At block 402, at least one
communication device associated with a corresponding passenger is discovered. The
29
communication device is determined to be associated with a cluster record of a primary
passenger where the primary passenger is waiting at a stop for the transit vehicle.
[0094] At block 404, a communication device associated with the primary passenger
connects to the at least one communication device of the corresponding passenger discovered in
block 402, based on its associated UI. As described before, each communication device has an
associated UI based on which it can be uniquely determined.
[0095] At block 406, the communication device associated with the primary passenger
sends a query message to at least one connected communication device. In one implementation,
the query message also includes a hop parameter. Further, the query message is sent either based
on hopping communication method or based on direct communication method. In case hopping
communication method is selected, the query message is sent only to the communication devices
of passengers forming part of the cluster native to the primary passenger. Whereas, if a direct
communication method is selected, the query message is sent to individual clusters in cluster
chain one after another based on determination of any cluster boarding the transit vehicle.
[0096] Referring to Fig. 4(b), an estimated time of arrival of the transit vehicle is
determined based on the method 450. At block 452, a query message is received, by a first
communication device of a first passenger, from a second communication device of a second
passenger. In one implementation, the second passenger is waiting at a stop for the transit vehicle
and sends the query message to the first passenger. Depending on the method of communication,
such as the hopping communication method and direct communication method, the first
passenger may either be a part of native cluster or non-native cluster of the second passenger,
respectively.
[0097] At block 454, other communication devices of passengers forming part of a
cluster native to the first passenger are identified. In situation where the first passenger is a part
of the native cluster of the second passenger, the other communication devices of passengers
would form a part of cluster native to both, the first passenger and the second passenger.
However, in situation where the first passenger is a part of non-native cluster of the second
passenger, the cluster native to the first passenger would include different passengers.
[0098] At block 456, it is determined whether the number of other passengers identified
is greater than a threshold. If the determination is positive, the control flows to block 458 (‘YES’
30
branch). If the determination is negative, the control flows to block 460. The determination of a
threshold number of other passengers is done to accurately determine whether the passengers of
the cluster have boarded the transit vehicle.
[0099] At block 458, a plurality of probe messages are sent by the first communication
device of the first passenger to each of the identified other communication device along with a
sent_time time stamp, where each of the plurality of the probe message is sent after a pre-defined
time interval. The sent_time time stamp is indicative of the time at which the probe message is
sent.
[00100] At block 462, a plurality of response probe messages are received by the first
communication device of the first passenger, from each of the identified other communication
device corresponding to each of the plurality of probe messages along with a receive_time time
stamp. The receive_time time stamp is indicative of the time instance when the probe message
was received by the each of the identified other communication device.
[00101] At block 464, the sent_time and the receive_time time stamp of the plurality of
probe messages and the plurality of response probe messages are compared to determine a
relative time stamp. The relative time stamp is indicative of whether the first communication
device associated with the first passenger and the other communication device associated with
other passengers are travelling in the same direction or not.
[00102] At block 466, it is determined whether the relative time stamp value is less than a
pre-defined threshold. If the determination is positive, the control flows to block 468 (‘YES’
branch). If the determination is negative, the control flows to block 460 (‘NO’ branch). It would
be understood that when the relative time stamp is greater than the threshold, the first passenger
and the other passengers would be travelling in other directions whereas, while the relative time
stamp is not greater than the threshold, the first passenger and the other passengers are traveling
in the same direction. At block 468, the control flows to block 470.
[00103] At block 470, speed sensor reading of the first communication device is
determined to identify the speed of the first passenger. The speed of the first passenger may
allow determination of whether the first passenger has boarded the transit vehicle.
31
[00104] At block 472, it is determined whether the speed of the first communication
device indicates that the first passenger is travelling. If the determination is positive, the control
flows to the block 474 (‘YES’ branch). If the determination is negative, the control flows to
block 460 (‘NO’ branch).
[00105] At block 474, an estimated time of arrival (TOA) at a stop corresponding to the
second passenger is predicted based at least on one of boarding time of the first passenger and
hop parameter in the query message. In one implementation, based on the boarding time and the
hop parameter, the stop at which the second passenger is waiting is determined. Further, to
predict the TOA an average time taken by the transit vehicle to reach the stop of the second
passenger may be utilized.
[00106] At block 476, the estimated TOA is sent to the second communication device of
the second passenger. In one implementation, based on the estimated TOA, the second passenger
may also determine the approximate location of the transit vehicle.
[00107] At block 460, the control flows to block 478. At block 478, the received query
message is sent to passengers of a predecessor cluster with an incremented hop parameter value.
Based on the propagation of the query message to the predecessor cluster, it can be determined
whether the passengers of the predecessor cluster have boarded the transit vehicle or not.
[00108] Although embodiments for methods and systems for tracking a transit vehicle
have been described in a language specific to structural features and/or methods, it is to be
understood that the invention is not necessarily limited to the specific features or methods
described. Rather, the specific features and methods are disclosed as exemplary embodiments for
tracking the transit vehicle.
32
I/We claim:
1. A method for tracking a transit vehicle on a route travelled by a plurality of passengers,
the method comprising:
broadcasting a first discovery message, by a first communication device of a first
passenger, to the plurality of passengers based on determination of a speed of the transit
vehicle through a speed sensor of the first communication device, wherein the first
discovery message includes at least a boarding time of the first passenger and a unique
identifier (UI) associated with the first communication device;
receiving at least one discovery message from a first set of passengers from
amongst the plurality of passengers and, at least one response to the first discovery
message from a second set of passengers from amongst the plurality of passengers,
wherein each of the at least one response to the first discovery message includes at least a
boarding time and a UI associated with a corresponding passenger from amongst the
second set of passengers; and
generating a cluster record for the first passenger based on the received at least
one discovery message and the least one response to the first discovery message, wherein
the cluster record includes a plurality of clusters and a cluster chain, and wherein each
cluster from amongst the plurality of clusters includes a set of passengers from amongst
the plurality of passengers who board the transit vehicle from a same stop.
2. The method as claimed in claim 1 further comprising:
receiving a second discovery message from a second communication device of a
second passenger, wherein the second discovery message includes at least a boarding
time of the second passenger and a UI associated with the second communication device;
and
sending a response to the second discovery message, wherein the response
includes at least the boarding time of the first passenger and the UI of the first
communication device.
3. The method as claimed in claim 1 further comprising:
33
receiving a query message from a third passenger from amongst the plurality of
passengers, waiting for the transit vehicle at a third stop, wherein the query message
includes a hop parameter, and wherein value of the hop parameter is indicative of cluster
Id. of the third passenger;
determining other passengers of a cluster native to the first passenger to have
boarded the transit vehicle based at least on relative speed of the other passengers and the
speed of the transit vehicle, wherein the cluster native to the first passenger includes
passengers who board the transit vehicle from the stop of the first passenger; and
estimating, upon determining, a time of arrival (TOA) for the transit vehicle to
reach the third stop based on the value of the hop parameter, speed of the transit vehicle,
and boarding time of the first passenger.
4. The method as claimed in claim 3, wherein the determining comprises:
sending a plurality of probe messages to the other passengers of the cluster native
to the first passenger with a sent_time time stamp, wherein each of the plurality of probe
messages is sent after a pre-defined time interval, and wherein the sent_time time stamp
associated with each of the plurality of probe messages is indicative of the time instance
when a corresponding probe message is sent;
receiving a plurality of response probe messages from the other passengers with a
receive_time time stamp, wherein the receive_time time stamp associated with each of
the plurality of response probe messages is indicative of the time instance when a
corresponding probe message was received by the other passengers;
determining a relative time stamp to be less than a threshold, wherein the relative
time stamp is based on comparison of the sent_time time stamp and the receive_time time
stamp; and
ascertaining, upon determining, the speed of the transit vehicle through the speed
sensor of the first communication device of the first passenger to identify motion of the
transit vehicle.
5. The method as claimed in claim 3, wherein the method further comprises sending the
estimated TOA to the third passenger.
34
6. A vehicle tracking system (102) implemented in a communication device for tracking a
transit vehicle on a route travelled by a plurality of passengers comprising:
a processor (204);
a communicating module (216) coupled to the processor (204), configured to:
broadcast a first discovery message, by the communication device
associated with a first passenger, to the plurality of passengers based on
determination of a speed of the transit vehicle through a speed sensor of the
communication device, wherein the first discovery message includes at least a
boarding time of the first passenger and a unique identifier (UI) associated with
the communication device;
receiving at least one discovery message from a first set of passengers
from amongst the plurality of passengers and, at least one response to the first
discovery message from a second set of passengers from amongst the plurality of
passengers, wherein each of the at least one response to the first discovery
message includes at least a boarding time and a UI associated with a
corresponding passenger from amongst the second set of passengers; and
a clustering module (112) coupled to the processor (204), configured to:
generate a cluster record for the first passenger based on the received at
least one discovery message and the least one response to the first discovery
message, wherein the cluster record includes a plurality of clusters and a cluster
chain, and wherein each cluster from amongst the plurality of clusters includes a
set of passengers from amongst the plurality of passengers who board the transit
vehicle from a same stop.
7. The vehicle tracking system (102) as claimed in claim 6, wherein the communicating
module (216) further configured to:
receive a second discovery message from a second communication device of a
second passenger, wherein the second discovery message includes at least a boarding
time of the second passenger and a UI associated with the second communication device;
and
35
send a response to the second discovery message, wherein the response includes
at least the boarding time of the first passenger and the UI of the communication device
associated with the first passenger.
8. The vehicle tracking system (102) as claimed in claim 6, further comprises a query
managing module (214) coupled to the processor (204), configured to:
receive a query message from a third passenger from amongst the plurality of
passengers, waiting for the transit vehicle at a third stop, wherein the query message
includes a hop parameter, and wherein value of the hop parameter is indicative of cluster
Id. of the third passenger;
determine other passengers of a cluster native to the first passenger to have
boarded the transit vehicle based at least on relative speed of the other passengers and the
speed of the transit vehicle, wherein the cluster native to the first passenger includes
passengers who board the transit vehicle from the stop of the first passenger; and
estimate, upon determination, a time of arrival (TOA) for the transit vehicle to
reach the third stop based on the value of the hop parameter, speed of the transit vehicle,
and boarding time of the first passenger.
9. The vehicle tracking system (102) as claimed in claim 6, wherein the speed sensor of the
communication device is an accelerometer.
10. The vehicle tracking system (102) as claimed in claim 8, wherein the query managing
module (214) is configured to:
send a plurality of probe messages to the other passengers of the cluster native to
the first passenger with a sent_time time stamp, wherein each of the plurality of probe
messages is sent after a pre-defined time interval, and wherein the sent_time time stamp
associated with each of the plurality of probe messages is indicative of the time instance
when a corresponding probe message is sent;
receive a plurality of response probe messages from the other passengers with a
receive_time time stamp, wherein the receive_time time stamp associated with each of
36
the plurality of response probe messages is indicative of the time instance when a
corresponding probe message was received by the other passengers;
determine a relative time stamp to be less than a threshold, wherein the relative
time stamp is based on comparison of the sent_time time stamp and the receive_time time
stamp; and
ascertain, upon determination, the speed of the transit vehicle through the speed
sensor of the first communication device of the first passenger to determine other
passengers of a cluster native to the first passenger to have boarded the transit vehicle.