Generating optimal itineraries based on network connectivity

• US 8,352,175 B2
• Filed: 12/19/2008
• Issued: 01/08/2013
• Est. Priority Date: 12/17/2008
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bauchot, Frederic, Drouet, Francois-Xavier, Marmigere, Gerard, Dispensa, Jean-Yves
• Primary Examiner(s): Tran, Khoi
• Assistant Examiner(s): Kiswanto, Nicholas
• Application Number:
  US12/339,156
• Publication Number:
  US 20100153001A1
• Time in Patent Office: 1,481 Days
• Field of Search: 701/200, 701/201, 340/988, 340/989, 340/990, 340/995.1, 340/995.12, 340/995.14, 340/995.24, 340/995.27
• US Class Current: 701/408
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries
• CPC Class Codes: G01C 21/3867 Geometry of map features, e.g. shape points, polygons or for simplified maps

Abstract

A method and system for generating optimal itineraries based on network connectivity. A computer receives a first message from which a current position of a vehicle on a trip, destination, service(s) being provided to mobile device(s) in the vehicle, service provider(s) and network(s) are extracted. Optimal itineraries are generated by generating sets of optimal parameters that include paths for which connectivity measures satisfy predefined criteria and hops that indicate positions associated with connectivity changes. A response to the first message indicates the optimal itineraries and the associated sets of optimal parameters and is sent to a vehicle-based device. Sending the response results in the mobile device(s) making the connectivity changes when the vehicle is detected at the hops.

Claims

1. A computer-implemented method of generating optimal itineraries, said method comprising:

a computer system receiving a first message from a global positioning device that determines a geographic position of a vehicle on a trip, wherein said computer system is remote from said vehicle, and wherein said first message indicates said geographic position of said vehicle, a destination of said trip, a service requested for a mobile device being transported by said vehicle, a plurality of service providers that provide said service, and one or more networks via which said plurality of service providers provide said service to said mobile device;

said computer system determining a first cell in which said service to said mobile device is provided by said plurality of service providers;

for each respective cell of a first plurality of cells adjacent to said first cell, said computer system retrieving a first plurality of measures of network connectivity, each measure of network connectivity included in said first plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of said plurality of service providers to any mobile device in said respective cell;

said computer system determining a first measure of network connectivity of said retrieved first plurality of measures of network connectivity indicates a first signal quality provided by a first service provider to any mobile device in a second cell, said first service provider included in said plurality of service providers and said second cell included in said first plurality of cells adjacent to said first cell;

said computer system determining said first signal quality provided by said first service provider to said any mobile device in said second cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of said retrieved first plurality of measures of network connectivity;

based on said first signal quality provided by said first service provider to said any mobile device in said second cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved first plurality of measures of network connectivity, said computer system identifying said first service provider within said plurality of service providers and selecting said second cell from said first plurality of cells adjacent to said first cell;

said computer system determining a first path within said selected second cell;

subsequent to said selecting said second cell and for each respective cell of a second plurality of cells adjacent to said second cell, said computer system retrieving a second plurality of measures of network connectivity, each measure of network connectivity included in said second plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of said plurality of service providers to any mobile device in said respective cell of said second plurality of cells;

said computer system determining a second measure of network connectivity of said retrieved second plurality of measures of network connectivity indicates a second signal quality provided by a second service provider to any mobile device in a third cell, said second service provider included in said plurality of service providers and said third cell included in said second plurality of cells adjacent to said second cell;

said computer system determining said second signal quality provided by said second service provider to said any mobile device in said third cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of said retrieved second plurality of measures of network connectivity;

based on said second signal quality provided by said second service provider to said any mobile device in said third cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved second plurality of measures of network connectivity, said computer system identifying said second service provider within said plurality of service providers and selecting said third cell from said second plurality of cells adjacent to said second cell;

said computer system determining a second path within said selected third cell;

in part based on said first signal quality provided by said first service provider to said any mobile device in said second cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved first plurality of measures of network connectivity and in part based on said second signal quality provided by said second service provider to said any mobile device in said third cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved second plurality of measures of network connectivity, said computer system determining an itinerary for said trip as a plurality of paths including a sequence of said first path followed by said second path, and as one or more hops including a hop indicating a position on said first path at which a connectivity change is to occur from said first service provider providing said service to said mobile device to said second service provider providing said service to said mobile device; and

said computer system sending a second message as a response to said first message, wherein said second message indicates said itinerary, wherein a result of said sending said second message and said vehicle reaching said position indicated by said hop is said mobile device making said connectivity change.

2. The method of claim 1, wherein said receiving said first message includes receiving a time window during which said service is requested to be provided to said mobile device, wherein said identifying said first service provider within said plurality of service providers includes determining said first service provider provides said service within said time window, wherein said identifying said second service provider within said plurality of service providers includes determining said second service provider provides said service within said time window, and wherein said time window indicates a period of time during which said service is required by said mobile device.

3. The method of claim 1, wherein said receiving said first message includes receiving a cost requirement of said service, wherein said identifying said first service provider within said plurality of service providers includes determining a first cost of said first service provider providing said service does not exceed said cost requirement, wherein said identifying said second service provider within said plurality of service providers includes determining a second cost of said second service provider providing said service does not exceed said cost requirement, and wherein said cost requirement indicates a maximum cost of providing said service to said mobile device.

4. The method of claim 1, further comprising:

said computer system determining a plurality of itineraries from said geographic position of said vehicle to said destination of said trip, said plurality of itineraries including said itinerary and a second itinerary, said second itinerary based on a shortest distance from said geographic position of said vehicle to said destination of said trip, wherein said itinerary is different from said second itinerary;

said computer system initiating a display of said plurality of itineraries on a display device being transported by said vehicle, each displayed itinerary including a respective plurality of paths, a respective one or more hops indicating one or more positions at which one or more connectivity changes are to occur, a respective one or more service providers that are to provide said service, and a respective one or more networks via which said service is to be provided by said respective one or more service providers; and

said computer system receiving a selection by a user of one itinerary from said displayed plurality of itineraries.

5. The method of claim 1, wherein said vehicle is a mode of conveyance by which a person travels, and wherein said mode of conveyance is selected from the group consisting of a motor-driven conveyance, a rail transport conveyance, a watercraft, an aircraft, an animal-powered mode of transportation, and a human-powered mode of transportation.

6. The method of claim 1, wherein said first message conforms to a communications protocol, wherein said computer system is configured with a connection stack that defines said communications protocol, and wherein said method further comprises said computer system extracting from said first message said geographic position of said vehicle, said destination of said trip, said service, said service provider, and said one or more networks by applying said communications protocol to said first message.

7. A process for supporting computing infrastructure, said process comprising providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable code in a computer system, wherein the code in combination with the computer system is capable of performing a method of generating optimal itineraries, said method comprising:

said computer system receiving a first message from a global positioning device that determines a geographic position of a vehicle on a trip, wherein said computer system is remote from said vehicle, and wherein said first message indicates said geographic position of said vehicle, a destination of said trip, a service requested for a mobile device being transported by said vehicle, a plurality of service providers that provide said service, and one or more networks via which said plurality of service providers provide said service to said mobile device;

said computer system determining a first cell in which said service to said mobile device is provided by said plurality of service providers;

for each respective cell of a first plurality of cells adjacent to said first cell, said computer system retrieving a first plurality of measures of network connectivity, each measure of network connectivity included in said first plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of said plurality of service providers to any mobile device in said respective cell;

said computer system determining a first measure of network connectivity of said retrieved first plurality of measures of network connectivity indicates a first signal quality provided by a first service provider to any mobile device in a second cell, said first service provider included in said plurality of service providers and said second cell included in said first plurality of cells adjacent to said first cell;

said computer system determining said first signal quality provided by said first service provider to said any mobile device in said second cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of said retrieved first plurality of measures of network connectivity;

based on said first signal quality provided by said first service provider to said any mobile device in said second cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved first plurality of measures of network connectivity, said computer system identifying said first service provider within said plurality of service providers and selecting said second cell from said first plurality of cells adjacent to said first cell;

said computer system determining a first path within said selected second cell;

subsequent to said selecting said second cell and for each respective cell of a second plurality of cells adjacent to said second cell, said computer system retrieving a second plurality of measures of network connectivity, each measure of network connectivity included in said second plurality of measures of network connectivity indicating a respective signal quality provided by a respective service provider of said plurality of service providers to any mobile device in said respective cell of said second plurality of cells;

said computer system determining a second measure of network connectivity of said retrieved second plurality of measures of network connectivity indicates a second signal quality provided by a second service provider to any mobile device in a third cell, said second service provider included in said plurality of service providers and said third cell included in said second plurality of cells adjacent to said second cell;

said computer system determining said second signal quality provided by said second service provider to said any mobile device in said third cell is not exceeded by any other signal quality indicated by any other measure of network connectivity of said retrieved second plurality of measures of network connectivity;

based on said second signal quality provided by said second service provider to said any mobile device in said third cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved second plurality of measures of network connectivity, said computer system identifying said second service provider within said plurality of service providers and selecting said third cell from said second plurality of cells adjacent to said second cell;

said computer system determining a second path within said selected third cell;

in part based on said first signal quality provided by said first service provider to said any mobile device in said second cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved first plurality of measures of network connectivity and in part based on said second signal quality provided by said second service provider to said any mobile device in said third cell not being exceeded by said any other signal quality indicated by said any other measure of network connectivity of said retrieved second plurality of measures of network connectivity, said computer system determining an itinerary for said trip as a plurality of paths including a sequence of said first path followed by said second path, and as one or more hops including a hop indicating a position on said first path of at which a connectivity change is to occur from said first service provider providing said service to said mobile device to said second service provider providing said service to said mobile device; and

said computer system sending a second message as a response to said first message, wherein said second message indicates said itinerary, wherein a result of said sending said second message and said vehicle reaching said position indicated by said hop is said mobile device making said connectivity change.

8. The process of claim 7, wherein said receiving said first message includes receiving a time window during which said service is requested to be provided to said mobile device, wherein said identifying said first service provider within said plurality of service providers includes determining said first service provider provides said service within said time window, wherein said identifying said second service provider within said plurality of service providers includes determining said second service provider provides said service within said time window, and wherein said time window indicates a period of time during which said service is required by said mobile device.

9. The process of claim 7, wherein said receiving said first message includes receiving a cost requirement of said service, wherein said identifying said first service provider within said plurality of service providers includes determining a first cost of said first service provider providing said service does not exceed said cost requirement, wherein said identifying said second service provider within said plurality of service providers includes determining a second cost of said second service provider providing said service does not exceed said cost requirement, and wherein said cost requirement indicates a maximum cost of providing said service to said mobile device.

10. The process of claim 7, wherein said method further comprises:

said computer system determining a plurality of itineraries from said geographic position of said vehicle to said destination of said trip, said plurality of itineraries including said itinerary and a second itinerary, said second itinerary based on a shortest distance from said geographic position of said vehicle to said destination of said trip, wherein said itinerary is different from said second itinerary;

said computer system initiating a display of said plurality of itineraries on a display device being transported by said vehicle, each displayed itinerary including a respective plurality of paths, a respective one or more hops indicating one or more positions at which one or more connectivity changes are to occur, a respective one or more service providers that are to provide said service, and a respective one or more networks via which said service is to be provided by said respective one or more service providers; and

said computer system receiving a selection by a user of one itinerary from said displayed plurality of itineraries.

11. The process of claim 7, wherein said vehicle is a mode of conveyance by which a person travels, and wherein said mode of conveyance is selected from the group consisting of a motor-driven conveyance, a rail transport conveyance, a watercraft, an aircraft, an animal-powered mode of transportation, and a human-powered mode of transportation.