COOPERATIVE MOBILE DATA COLLECTION IN SMART CITIES
Smart cities are driven by huge amount of data collected from sensors deployed across the city. Sensors typically form a multi-hop network with a base station (BS) in order to send their data to the command and control center. However, sparse deployment of sensors can leave subsets of the network partitioned from the rest of the network. In such a case, isolated partitions cannot forward their data to the BS. Consequently, network coverage and data fidelity decline. A possible solution to link partitions and provide connectivity is employing mobile data collectors (MDCs). A smart vehicle supporting wireless communication can act as an MDC and carry data between sensors and the BS. Using a single MDC extends the average tour length. To minimize the maximum tour length, multiple MDCs can be employed. To identify sensors to be visited by each MDC, this paper clusters partitions as many as the number of MDCs and assigns an MDC for each cluster. Then two different cooperative data collection schemes are considered based on the availability of inter-MDC data exchange. If MDCs collaborate in data delivery, they meet at certain meeting points for data exchange. Such a cooperation avoids the requirement of visiting the BS for some MDCs and reduces tour lengths. On the other hand, MDCs closer to the BS can experience data loss due to buffer overflow given the higher volume of the accumulated data. Presented approaches are evaluated in terms of maximum tour length, data latency, and data loss. The smart city application is simulated with deployment of sensors on certain amenity types. Geographic data is obtained from a volunteered geographic information system and MDC mobility is restricted with the road network. Obtained results indicate that MDC cooperation decreases maximum tour length at the expense of increased rate of data loss and data latency.
Alatartsev, S., Augustine, M., & Ortmeier, F. 2013a. Constricting insertion heuristic for traveling salesman problem with neighborhoods. In Proc. of the 23rd International Conference on Automated Planning and Scheduling (ICAPS2013), pp. 2-10.
Alatartsev, S., Mersheeva, V., Augustine, M., & Ortmeier, F. 2013b. On optimizing a sequence of robotic tasks. In Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS2013), pp. 217-223.
Bektas, T. 2006. The multiple traveling salesman problem: an overview of formulations and solution procedures, Omega, 34(3), pp. 209-219. doi.org/10.1016/j.omega.2004.10.004
Boeing, G. 2017. OSMnx: New methods for acquiring, constructing, analyzing, and visualizing complex street networks, Computers, Environment and Urban Systems, 65, pp. 126-139. doi.org/10.1016/j.compenvurbsys.2017.05.004
Frederick, B. 1958. An algorithm for solving travelling-salesman and related network optimization problems, Operations Research, 6(6), pp. 897-897.
Gulczynski, D. J., Heath, J. W., & Price, C. C. 2006. The Close Enough Traveling Salesman Problem: A Discussion of Several Heuristics. Boston, MA: Springer US, pp. 271-283. doi.org/10.1007/978-0-387-39934-8_16
OR-Tools, G. 2020. The OR-Tools Suite, https://developers.google.com/optimization. Accessed January 20, 2020.
Pan, X., Li, F., & Klette, R. 2010. Approximate shortest path algorithms for sequences of pairwise disjoint simple polygons (Citeseer).
Platform, G. M. 2020. Elevation API, https://developers.google.com/maps/documentation/elevation/start. Accessed January 20, 2020
Senturk, I.F. & Kebe, G. Y. 2019. A New Approach to Simulating Node Deployment for Smart City Applications Using Geospatial Data, International Symposium on Networks, Computers and Communications (ISNCC'19), June 18-20, Istanbul, Turkey, pp. 1-5.
Shuttleworth, R., Golden, B. L., Smith, S., & Wasil, E. 2008. Advances in Meter Reading: Heuristic Solution of the Close Enough Traveling Salesman Problem over a Street Network. Boston, MA: Springer US, pp. 487-501. doi.org/10.1007/978-0-387-77778-8_22
Wikipedia. 2020a. Metropolitan Municipalities in Turkey, https://en.wikipedia.org/wiki/Metropolitan_municipalities_in_Turkey. Accessed January 20, 2020.
Wikipedia. 2020b. Travelling Salesman Problem, https://en.wikipedia.org/wiki/Travelling_salesman_problem. Accessed January 20, 2020.
Wikipedia. 2020c. UPGMA (Unweighted Pair Group Method with Arithmetic Mean), https://en.wikipedia.org/wiki/UPGMA. Accessed January 20, 2020.