Transit Vehicle Tracking System

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.