Adaptive Multifactor Routing with Constrained Data Sets

TitleAdaptive Multifactor Routing with Constrained Data Sets
Publication TypeConference Paper
Year of Publication2015
AuthorsMiller, T, Ross, C, Barbosa, MMarques, Hirzallah, M, Volos, H, Sprinkle, J
Conference NameWireless Innovation Forum Conference on Wireless Communication Technologies and Software Defined Radio (WInnComm)
Date Published03/2015
Conference LocationSan Diego, CA
Abstract

Autonomous Vehicles can benefit greatly from the use of cellular infrastructure. Consequently, it may be desirable at times to consider the availability of this infrastructure when planning autonomous vehicle routes. In order to make such decisions it is necessary to have up-to-date knowledge of signal strength in surrounding areas. We consider the quality of routing possible when using incomplete knowledge of signal strength along a route. As our motivation for how signal strength information would be constrained we consider Vehicle to Vehicle communications. Such communications offer great promise in creating real-time signal maps through a decentralized data collection and aggregation process. One might envision such a process involving the transfer of signal reception information between cars within an area. Such a process, while low-latency and low-cost, could suffer from limited data availability beyond relatively short ranges. In order to route based on signal strength we employ a weighting formula to combine distance and signal strength into a single cost quantity. Then, we apply this formula to a city grid map with signal strength information. We replace the distance values with the formula’s aggregate cost values. The cost values are then presented to a shortest path routing algorithm to determine the lowest cost path. Finally, we simulate a vehicle which regularly updates a signal map of its surroundings and continuously updates its route in response. The costs of its chosen path and the cost of the ideal path are then recorded. In order to rigorously test our routing formula’s performance with varying degrees of information we employ a Matlab program that randomly generates thousands of city signal maps to run the routing formula and algorithms on. The routing algorithms are run with route signal knowledge between 0% and 100%. We chart the average ratio between partial knowledge and full knowledge path costs. We consider the performance of a variety of algorithms and conclude that using Dijkstra we may produce routes that are 95% optimal using a signal knowledge window only 1/10 of our total route size. These results indicate the potential for excellent routing even when V2V communication can only offer highly constrained data sets. However, the use of random maps potentially weakens our results as real world signal maps tend to be patterned and non-random. Such patterns are extremely problematic as there is great potential for scenarios that do not occur frequently in a randomly generated map and that require extensive map knowledge. For example, the need to find an exit to a signal dead-zone One might view our randomized maps as presenting the signal knowledge limited algorithm a series of local minima optimization problems. In a random map with extremely high signal value variance there is likely to be a variety of immediately visible signal dead-zones and strong signal zones that all have small sizes and are consistently intermixed. As a result, a knowledge limited algorithm can easily avoid a high cost path by moving between small strong signal zones while avoiding the interspersed dead zones with little advanced knowledge. We expect that the most relevant metric for signal formula routing performance may be the ratio between the median size of extreme signal zones and the size of the signal knowledge window. This ratio directly determines the ability of the path cost minimization algorithm to solve path cost as a series of local minima. In order to test the potential value of this metric we tweak our random map generation algorithm to assign a random signal values to increasing numbers of intersections. For example, we might assign each random value to 4x4 intersection grids. Then, we would apply that single value to 8x8 grids. This modification allows us to directly alter the size of extreme signal zones and test the performance of the routing algorithm as extreme signal zones outsize the size of the signal knowledge window