Determining the location of a mobile computing device

Abstract

A method of determining the location of a client device includes selecting sets of four access points (APs) from APs that can communicate with a client device. Each set of four APs forms a quadrilateral that contains the location of the client device. The method further includes selecting a first quadrilateral from quadrilaterals formed by the sets of four APs based on a policy, and, with the first quadrilateral, executing a time-of-flight (ToF)-based distance estimation process to determine the location of the client device.

What is claimed is: 
     
         1 . A method of determining the location of a client device, comprising:
 selecting sets of four access points (APs) from APs that can communicate with a client device, each set of four APs forming a quadrilateral that contains the location of the client device,   selecting a first quadrilateral from quadrilaterals formed by the sets of four APs based on a policy, and   with the first quadrilateral, executing a time-of-flight (ToF)-based distance estimation process to determine the location of the client device.   
     
     
         2 . The method of  claim 1 , in which each quadrilateral is defined by joining the APs of a set of APs. 
     
     
         3 . The method of  claim 1 , further comprising, prior to selecting the sets of four APs, determining the location of the client device using the APs that can communicate with the client device. 
     
     
         4 . The method of  claim 1 , in which selecting the four APs comprises selecting the four APs from the APs in which the quadrilateral formed by joining the selected APs comprises the smallest area. 
     
     
         5 . The method of  claim 1 , in which selecting the sets of four APs from the APs comprises finding all the quadrilaterals given a set of 2-dimensional (2D) points, the 2D points representing the location of the APs that can communicate with the client. 
     
     
         6 . The method of  claim 1 , further comprising reducing the number of quadrilaterals by excluding those quadrilaterals that comprise line segments which are less than a predefined distance. 
     
     
         7 . The method of  claim 6 , in which the predefined distance is 40 meters. 
     
     
         8 . The method of  claim 1 , in which the quadrilaterals are convex quadrilaterals. 
     
     
         9 . The method of  claim 1 , further comprising reducing the number of quadrilaterals based on whether a set of four APs are each separately located in one of four quadrants of a coordinate plane parallel to the area in which the client device exists, and whose origin is the client device. 
     
     
         10 . The method of  claim 1 , in which the policy comprises:
 selecting the first quadrilateral from the quadrilaterals that comprises the smallest area;   selecting the first quadrilateral from the quadrilaterals that comprises a minimum sum of the distances of the location of the client device from the vertices of the quadrilateral; or   selecting the first quadrilateral from the quadrilaterals that comprises a minimum sum-squared of the distances of the location of the client device from the vertices of the quadrilateral.   
     
     
         11 . The method of  claim 1 , in which a point-in-polygon process is executed to determine whether each set of four APs forming a quadrilateral contains the location of the client device. 
     
     
         12 . A computer program product for selecting access points (APs) for time-of-flight (ToF)-based positioning of a client device, the computer program product comprising:
 a computer readable storage medium comprising computer usable program code embodied therewith, the computer usable program code comprising:
 computer usable program code to, when executed by a processor, select sets of four APs from APs that can communicate with a client device, each set of four APs forming a quadrilateral that contains the location of the client device; and 
 computer usable program code to, when executed by the processor, select a first quadrilateral from the quadrilaterals formed by the sets of four APs based on a policy. 
   
     
     
         13 . The computer program product of  claim 12 , further comprising computer usable program code to, when executed by the processor, with the first quadrilateral, execute a time-of-flight (ToF)-based distance estimation process to determine the location of the client device. 
     
     
         14 . A localization system for locating a client device in an area, comprising:
 a plurality of access points (APs) located within the area, each AP comprising:
 a processor; and 
 a memory, the memory comprising executable code that, when executed by the processor:
 determines whether a location of the client device is know; 
 if the location of the client device is not known, determines the location of the client device using the APs; 
 determines all possible quadrilaterals, the quadrilaterals being formed by selecting sets of four APs from APs that can communicate with a client device, each set of four APs forming a quadrilateral that contains the location of the client device; 
 reduces the number of quadrilaterals to create a group of candidate quadrilaterals; 
 selects a quadrilateral from the group of candidate quadrilaterals; and 
 with the selected quadrilateral, executing a time-of-flight (ToF)-based distance estimation process to determine the location of the client device. 
 
   
     
     
         15 . The localization system of  claim 14 , in which the memory comprises executable code that, when executed by the processor, reduces the number of quadrilaterals based on whether a set of four APs are each separately located in one of four quadrants of a coordinate plane parallel to the area in which the client device exists, and whose origin is the client device.