Quantifying the sensing power of vehicle fleets

To compare our model to data, we quantify the sensing power of a vehicle fleet as its covering fraction $⟨C⟩$, defined as the average fraction of street segments in $S$ that are “covered” or sensed by a taxi during time period $\mathcal{T}$, assuming that $N_V$ vehicles are selected uniformly at random from the vehicle fleet $\mathcal{V}$. (In SI Appendix, we consider an alternate definition.)

We have computed $⟨C⟩$ for 10 datasets from 9 cities: New York (confined to the borough of Manhattan), Chicago, Vienna, San Francisco, Singapore, Beijing, Changsha, Hangzhou, and Shanghai. (We used two independent datasets for Shanghai, one from 2014 and the other from 2015. For the 2015 dataset, we chose the subset of taxi trips starting and ending in the subcity “Yangpu” and hereafter consider it a separate city.) Each dataset consists of a set of taxi trips. The representation of these trips differs, however, by city and roughly falls into two categories. The Chinese cities comprise the first category, in which the global positioning system (GPS) coordinates of each taxi’s trajectory were recorded, along with the identification (ID) number of the taxi. Knowing taxi IDs lets us calculate $⟨C⟩$ explicitly as a function of the number of sensor-equipped vehicles $N_V$, as desired. Accordingly, we call these the “vehicle-level” datasets. For the remaining cities, however, trips were recorded without taxi IDs; in these cases, we know only how many trips were taken, not how many taxis were in operation for the duration of our datasets. (Although taxi IDs are available for Yangpu and New York City, for reasons discussed in SI Appendix, we exclude them from the vehicle-level datasets.) So for these “trip-level” datasets, we can only calculate the dependence of $⟨C⟩$ on $N_T$, the number of trips, which serves as an indirect measure of the sensing power. Finally, since we represent cities by their street networks, and not as domains in continuous space, we map GPS coordinates to street segments using OpenStreetMap, so that trips are expressed by sequences of street segments $\left(S_1,S_2,\dots \right)$.

We find that, despite its simplicity, the taxi-drive process captures the statistical properties of real taxis’ movements. Specifically, it produces realistic distributions of segment popularities $p_i$, the relative number of times (so that the $p_i$ sum to 1) each street segment is sensed by the fleet $\mathcal{V}$ during $\mathcal{T}$ (in turn, these $p_i$ allow us to calculate our main target, $⟨C⟩$). Fig. 2D shows the empirical distribution of the $p_i$ obtained from our New York dataset (brown histogram). Consistent with previous findings (15), the distribution is heavy-tailed and closely follows Zipf’s law (this is also true of the other cities; SI Appendix, Fig. S2). The distribution predicted by the taxi-drive process (blue histogram) is consistent with the data. This good agreement is surprising. One might expect that the many factors absent from the taxi-drive process—variations in street-segment lengths and driving speeds, taxi–taxi interactions, human-routing decisions, and heterogeneities in passenger-pickup and -dropoff times and locations—would play a role in the statistical properties of real taxis. Yet our results show that, at the macroscopic level of segment popularity distributions, these complexities are unimportant. Moreover, the agreement of the model and the data are not trivial. Compare, for example, the predictions of a random-walk model (Fig. 2E). With their skewed unimodal distribution, the random-walk $p_i$ fails to capture the qualitative behavior observed in the data.

Having obtained the segment popularities $p_i$, we can predict the sensing power ${⟨C⟩}_{N_V}$ analytically by using a simple ball-in-bin model. We treat street segments as “bins” into which “balls” are placed when they are traversed by a sensor-equipped taxi. Using the segment popularities $p_i$ as the bin probabilities (recall that the $p_i$ are normalized and can thus be used as probabilities), we derive (Materials and Methods) the approximate expressionHere, $⟨B⟩$ is the average distance (measured in segments) traveled by a taxi chosen randomly from $\mathcal{V}$ during $\mathcal{T}$, and $N_S$ is the number of scannable street segments (SI Appendix). The trip-level expression ${⟨C⟩}_{N_T}$ is the same as Eq. 1 with $⟨B⟩$ replaced by $⟨L⟩$, the average number of segments in a randomly selected trip ( Materials and Methods, Eq. 10).

Fig. 3 compares the analytic predictions for $⟨C⟩$ against our data for a reference period of $\mathcal{T}=1$ d (see SI Appendix for how the empirical $C$ were calculated). We tested the prediction given by Eq. 1 in two ways: using $p_i$ estimated from our datasets (thick line) and using $p_i$ estimated from the stationary distribution of the taxi-drive process (dashed line). In both cases, theory agrees well with data, although the latter estimate is less accurate (which is to be expected, since it is derived from a model). Note that the $⟨C⟩$ curves from different cities in Fig. 3 are strikingly similar. This similarity stems from the near-universal distributions of $p_i$ (shown in SI Appendix, Fig. S1 and discussed in SI Appendix) and suggests that $⟨C⟩$ might also be universal.

Fig. 4 tests for universality in the $⟨C⟩$ curves. Using the vehicle-level data, we plot $⟨C⟩$ vs. $N_V/⟨B⟩$, which removes the city-dependent term $⟨B⟩$ from Eq. 1 (SI Appendix, Figs. S4 and S5 shows how $⟨B⟩$ and $⟨L⟩$ are city-dependent. Note that we assume the $p_i$ are universal, so we do not scale them out.) With no other adjustments, the resulting curves nearly coincide, as if collapsing on a single, universal curve. (The fidelity of the collapse, however, varies by day; SI Appendix.) In SI Appendix, Fig. S10, we perform the same rescaling for the trip-level data, which shows a poorer collapse. However, since these datasets are of lower quality than the vehicle-level data, less trust should be placed in them. Hence, given the good collapse of the vehicle-level data, we conclude that the sensing power of vehicle fleets, as encoded by $⟨C⟩$, might be universal.

The fast saturation of the $⟨C⟩$ curves tells us that taxi fleets have large, but limited, sensing power; popular street segments are easily covered, but unpopular segments, being visited so rarely, are progressively more difficult to reach. A law of diminishing returns is at play, which means that, while scanning an entire city is difficult, a significant fraction can be scanned with relative ease. In particular, as detailed in SI Appendix, $\sim 50\%$ of vehicles are required to scan 80% of a city’s scannable street segments, but $50\%$ of segments are covered by just $N_V^{*}\sim 200\sim 5\%$ of vehicles (SI Appendix, Table S3 reports similar numbers for the trip-level data). Most strikingly, as shown in SI Appendix, Fig. S11, one-third of the street segments in Manhattan are sensed by as few as 10 random taxis. In fact, because our estimates for $B$ are lower bounds (SI Appendix), the above-quoted values for $N_V^{*}$ are likely lower. These remarkably small values of $N_V^{*}$ and $N_T^{*}$ are encouraging findings and certify that drive-by sensing is readily feasible at the city scale, thus achieving the main goal of our work.

Requiring that segments be scanned just once a day, as assumed in our analysis, could be too coarse a temporal resolution for some urban quantities which we desire to monitor. Air quality, for instance, has large temporal variations and would therefore require multiple readings dispersed evenly over time to be adequately sensed. To see if drive-by sensing can accommodate more demanding temporal requirements, we derived (SI Appendix) an expression for the adjusted sensing power $⟨C^{*}⟩\left(N_T,N_w\right)$ of a vehicle fleet, defined as the average number of segments covered at least once in each of $N_w$ equally sized subintervals of 1 d. Larger $N_w$ thus corresponds to greater temporal resolution. In SI Appendix, Fig. S12, we plot $⟨C^{*}⟩$ for $N_w=3$, so that segments must be scanned at least once in the morning, afternoon, and evening, defined by the intervals $\left(12\text{AM},8\text{AM}\right),\left(8\text{AM},4\text{PM}\right),\left(4\text{PM},12\text{AM}\right)$. We find that while reduced, the sensing power is still large; $N_V=355=3\%$ of vehicle are needed to scan half of Manhattan’s street segments, and $N_V=100<1\%$ of vehicles scan one-third of segments. This demonstrates that drive-by sensing can still efficiently provide sensing at finer resolutions in time. SI Appendix further discusses this point.

Because taxis are concentrated in commercial and tourist areas, taxi-based drive-by sensing has an inherent spatial bias. This bias could have harmful consequences, such as underserving socioeconomically disadvantaged neighborhoods. A hybrid approach to sensing could overcome this pitfall. Sensor-equipped taxis could be used to scan popular areas of a city, while the remaining hard-to-reach areas could be scanned by vehicles dedicated exclusively to sensing (as opposed to third-party vehicles on which drive-by sensing “parasitically” relies). We discuss the spatial bias of drive-by sensing comprehensively in SI Appendix.

There are many ways to extend our results. To keep things simple, we characterized the sensing power of taxi fleets with respect to the simplest possible cover metric: the raw number of segments traversed by a taxi at least once, $C=\sum 1_{\left(M_i\ge 1\right)}$ (where, as defined in Materials and Methods, $M_i$ is the number of times the $i$-th segment is sensed at the end of the reference period). A more general metric would be $C=\sum b_i{1}_{\left(M_i\ge 1\right)}$, where $b_i$ could represent the length of the segment or an effective sensing area. Extensions to the taxi-drive model would also be interesting. We have shown that the taxi drive produces realistic distributions of segment popularities $p_i$, but have said nothing about the spatial patterns of $p_i$—could the model be tweaked to capture these patterns? The techniques used in ref. 16 could be useful here. Finally, it would also be interesting to see if the sensing power could be inferred from the street network $S$ alone—that is, without data on taxi-mobility patterns. First steps in this direction are taken in SI Appendix.

Taxis traveling in cities share some of the features of nonstandard diffusive processes. Like Levy walks (17) or the run-and-tumble motion of bacteria (18), their movements are partly regular and partly random. As such, they produce stationary densities on street networks that obey Zipf’s law, contrary to a standard random walk. Future work could examine if other aspects of taxis’ spreading behavior are also unusual. Perhaps the hybrid motion exemplified by taxis offers advantages in graph exploration (19), foraging (20), and other classic applications of stochastic processes (21).

The work most closely related to drive-by sensing is on “vehicle-sensor networks” (22). Here, sensors capable of communicating with each other are fitted on vehicles, resulting in a dynamic network. The ability to share information enables more efficient, “cooperative” sensing, but has the drawback of large operational cost. Most studies of vehicle-sensor networks are therefore in silico (23). Since the sensors used in drive-by sensing do not communicate, drive-by sensors are significantly cheaper to implement than vehicle-sensor networks.

Vehicles other than taxis can be used for drive-by sensing. Candidates include private cars, trash trucks, or school buses. Since putting sensors on private cars might lead to privacy concerns, city-owned buses or trucks seem better choices for sensor hosts. The mobility patterns of school buses and trash trucks are, however, different from those of taxis; they follow fixed routes at fixed times, limiting their sensing power.

The diverse data supplied by drive-by sensing have broad utility. High-resolution air-quality readings can help combat pollution, while measurements of air temperature and humidity can help improve the calibration of meteorological models (24, 25) and are useful in the detection of gas leaks (26). Degraded road segments can be identified with accelerometer data, helping inform preventive repair (27, 28), while pedestrian-density data can be helpful in the modeling of crowd dynamics (29). Finally, information on parking-spot occupancy, Wi-Fi access points, and street-light infrastructure—all obtainable with modern sensors—will enable advanced city analytics as well as facilitate the development of new big-data and internet-of-things services and applications.

In short, drive-by sensing will empower urban leaders with rich streams of useful data. Our study reveals these to be obtainable with remarkably small numbers of sensors.

We derive an expression for the sensing power of a vehicle fleet. We quantify this by their covering fraction ${⟨C⟩}_{N_V}$, the average fraction of street segments covered at least once when $N_V$ vehicles move on the street network $S$, according to the taxi-drive process during a reference period $\mathcal{T}$. Given the nontrivial topology of $S$ and the non-Markovian nature of the taxi-drive process, it is difficult to solve for ${⟨C⟩}_{N_V}$ exactly. We can, however, derive a good approximation. It turns out that it is easier to first solve for the trip-level ${⟨C⟩}_{N_T}$ metric—that is, when $N_T$, the number of trips, is the dependent variable, so we begin with this case; the vehicle-level expression ${⟨C⟩}_{N_V}$ then follows naturally.

Imagine we have a population $\mathcal{P}$ of taxi trajectories. We define a taxi trajectory $T_r$ as a sequence of street segments $T_r=\left(S_{i_1},S_{i_2},\dots \right)$. The source of the population $\mathcal{P}$ of trajectories is unimportant for now; it could come from a taxi (or fleet of taxis) moving according to the taxi-drive process or from empirical data, as we later discuss. Given $\mathcal{P}$, our strategy to find ${⟨C⟩}_{N_T}$ is to map to a “ball-in-bin process”: We imagine street segments as bins into which balls are added, when they are traversed by a trajectory taken from $\mathcal{P}$. Note that, in contrast to the traditional ball-in-bin process, a random number of balls is added at each step, since taxis’ trajectories have random length.

We thank Allianz, Amsterdam Institute for Advanced Metropolitan Solutions, Brose, Cisco, Ericsson, Fraunhofer Institute, Liberty Mutual Institute, Kuwait–MIT Center for Natural Resources and the Environment, Shenzhen, Singapore–MIT Alliance for Research and Technology, UBER, Victoria State Government, Volkswagen Group America, and all of the members of the MIT Senseable City Laboratory Consortium for supporting this research. S.H.S. was supported by NSF Grants DMS-1513179 and CCF-1522054.