Cloaking with footprints to provide location privacy protection in location-based services

1. A method for using a location-based service while preserving anonymity by cloaking a device's instant location using footprints, the method comprising:

receiving a current location associated with the device;

receiving an anonymity level associated with the device;

accessing a database comprising a plurality of footprints, wherein the footprints are different devices' historical location samples;

computing a region containing the current location of the device and a number of footprints from the database based on the anonymity level to thereby cloak when the device is present within the region using the footprints; and

providing the region to a location-based service to thereby preserve anonymity of the device and provide location privacy protection for the device.

2. The method of claim 1 wherein the region is a circle.

3. The method of claim 2 wherein the computing the region comprises determining a minimal bounding circle.

4. The method of claim 3 wherein the minimal bounding circle being computed with a polynomial-time algorithm.

5. The method of claim 1 further comprising adding the current location of the device to the database.

6. The method of claim 1 wherein the anonymity level is determined by a public region selected by a user of the mobile node.

7. An apparatus for providing location-based services while preserving anonymity by cloaking an instant location using footprints, the apparatus comprising an anonymity server configured for receiving a current location associated with a mobile node, determining the anonymity level associated with the mobile node, computing a region containing the current location of the mobile node and a number of footprints based on the anonymity level, and communicating the region to a location-based service to thereby preserve anonymity of the mobile node and provide location privacy protection for the mobile node, wherein the footprints include historical location samples of other mobile nodes such that time at which the mobile node and the other mobile nodes are within the region is cloaked.

8. The apparatus of claim 7 further comprises a footprint database operatively connected to the anonymity server for storing and accessing the footprints.

9. The apparatus of claim 7 wherein the region is a minimal bounding circle computed with a polynomial-time algorithm.

10. The apparatus of claim 9 wherein the determining the anonymity level is determined based on a spatial region specified by a user of the mobile node.

11. A method for providing location-based services to a user by cloaking an instant location using footprints, the method comprising:

providing the user with a mobile device, the mobile device having a cellular transceiver and a global positioning system (gps) receiver and wherein the mobile device is configured to receive a selection of a spatial region from the user;

receiving a selection of the spatial region from the user;

computing an anonymity level associated with the user using a computer;

receiving an instance of a current location associated with the mobile device;

accessing a database comprising a plurality of footprints, wherein the footprints are different mobile devices' historical location samples;

computing a region containing the current location of the mobile device and a number of footprints from the database based on the anonymity level to thereby cloak when the user is within the region; and

providing the region to a location-based service to thereby preserve anonymity of the mobile device.