GEOPRIV WG Gabor Bajko Internet Draft Nokia Intended Status: Informational H. Tschofenig Expires: January 05, 2010 Nokia Siemens Networks July 06, 2009 Arcband Shape Binary Encoding draft-bajko-arcband-shape-00.txt Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on January 05, 2010. Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Bajko&Tschofenig January 05, 2010 [Page 1] Arc Band Binary Encoding July 05, 2009 Abstract This document describes a binary encoding format for an arcband, which is compatible with the binary encoding defined by 3GPP [3GPP23.032], and which is widely used in today's cellular networks. This encoding can additionally be used by a number of other protocols, which demand a bandwidth efficient encoding of location information, eg link layers like IEEE 802.11. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Conventions used in this document . . . . . . . . . . . . . . 4 3. Binary Arc Band Encoding . . . . . . . . . . . . . . . . . . . 5 4. Security Considerations . . . . . . . . . . . . . . . . . . . 9 5. IANA Considerations . . . . . . . . . . . . . . . . . . . . .10 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .11 7. Normative References . . . . . . . . . . . . . . . . . . . .12 8. Informative References . . . . . . . . . . . . . . . . . . . 12 Appendix A. Example . . . . . . . . . . . . . . . . . . . . . . .14 Appendix B. Pseudocode . . . . . . . . . . . . . . . . . . . . 16 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . .. . 17 Bajko&Tschofenig January 05, 2010 [Page 2] Arc Band Binary Encoding July 05, 2009 1. Introduction This document describes a binary encoding format for an arcband while RFC 5491 [RFC5491] describes the XML encoding of various geolocation shapes, including an arcband, using the Geography Markup Language (GML). RFC3825bis specifies a binary encoding of location information by approximating the area with a rectangle (in 2D) or a rectangular prism (in 3D). Approximating a relatively small area, like the coverage of an 802.11 access point with a rectangle is a good approximation for convex areas including rectangles, circles, ellipses or their 3D equivalents, but it can't describe an area with a shape of an arch band. RFC5491 does define encoding in XML for arch band, but link layer protocols where the Protocol Data Unit field is limited, will find it difficult to transport an XML encoded shape since that is a large piece of data. The encoding described in this document is specified in 3GPP and widely used in today's cellular networks. It is seen useful to describe the encoding in an IETF document, so that can be used by a number of other than cellular protocols, which demand a bandwidth efficient encoding of location information, eg link layers like IEEE 802.11. Having a binary encoding of an arch band available, enables a number of uses cases, including the possibility for devices to measure and communicate directly their location with the fixed station, using the native link layer of the technology which was used to determine the location. 2. Conventions used in this document The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 3. Arc Band A location in the form of an archband can be the result of a device using radio measurements to measure the distance from itself to a fixed station, based on the time difference of arrival. If the time difference of arrival could be measured with no uncertainty, the resulting location would be a circle (in 2D) or the surface of a sphere (in 3D). Since measuring with uncertainty of zero is practically impossible, the resulting location would be an area which is closer than a distance 'R+U' from the fixed station, and further than a distance 'R': Bajko&Tschofenig January 05, 2010 [Page 3] Arc Band Binary Encoding July 05, 2009 __.......__ _.-'' '-.. ,-' '-. ,' '. ,' _....._ '\ / \/ '' '' ` / SD| _' '_ `. / _' '_ \ | , `\ | | / \ | | | O R | U | | | .<---------->|<----->| | | | .' | \ / | | \ / .' \ \ / / \ \ / ,' ` '_ _' / '. '_ _' ,' '-. ....... _,' '-._ _,-' '`--......---' SD is the sensing device O is the origin of the circle R is the radius of the inner circle U is the uncertainty When the fixed station is not omnidirectional, but radiates with an angle a(o), then the resulting shape will be a partial arch band: N ^ ,.__ | a(s) / `-. | / `-. |--. / `. | `/ \ | /__ \ | . `-. \ | . `. \ |. \ \ . ---o-- a(o) -- | | --> |< / ' | E | . / ' | . / ; v,' / r1 <. / `. / `. ,' `. ,' r2>' Bajko&Tschofenig January 05, 2010 [Page 4] Arc Band Binary Encoding July 05, 2009 A partial arch band is a shape characterised by the co-ordinates of an ellipsoid point o (the origin), inner radius r1, uncertainty radius r2, both radii being geodesic distances over the surface of the ellipsoid, the offset angle (a(s)) between the first defining radius of the ellipsoid arc and North, and the included angle (a(o)) being the angle between the first and second defining radii. The offset angle is within the range of 0 degree to 359,999... degree while the included angle is within the range from 0,000...1 degree to 360 degree. This is to be able to describe a full circle, 0 degree to 360 degree. This shape-definition can also be used to describe a sector (inner radius equal to zero), a circle (included angle equal to 360 degree) and other circular shaped areas. The confidence level with which the position of a target entity is included within the shape is also included. 4. Encoding 7 6 5 4 3 2 1 0 +-+-+-+-+-+-+-+-+ |S| Degrees | Octet 1 +-+-+-+-+-+-+-+-+ | of | Octet 2 +-+-+-+-+-+-+-+-+ | Latitude | Octet 3 +-+-+-+-+-+-+-+-+ | Degrees | Octet 4 +-+-+-+-+-+-+-+-+ | of | Octet 5 +-+-+-+-+-+-+-+-+ | Longitude | Octet 6 +-+-+-+-+-+-+-+-+ | Inner | Octet 7 +-+-+-+-+-+-+-+-+ | Radius | Octet 8 +-+-+-+-+-+-+-+-+ |R| Unc. Radius | Octet 9 +-+-+-+-+-+-+-+-+ | Offset Angle | Octet 10 +-+-+-+-+-+-+-+-+ | Included Angle| Octet 11 +-+-+-+-+-+-+-+-+ |R| Confidence | Octet 12 +-+-+-+-+-+-+-+-+ Legend: R - Reserved. S - Sign of latitude Bit value 0: North Bajko&Tschofenig January 05, 2010 [Page 5] Arc Band Binary Encoding July 05, 2009 Bit value 1: South Degrees of latitude: The latitude is coded with 24 bits: 1 bit of sign and a number between 0 and 2^23-1 coded in binary on 23 bits. The relation between the coded number N and the range of (absolute) latitudes X it encodes is the following (X in degrees): N <= (2^23 / 90) * X < N+1 except for N=2^23-1, for which the range is extended to include N+1. Bit 1 of octet 4 is the low order bit Degrees of longitude: The longitude, expressed in the range -180 degrees, +180 degrees, is coded as a number between -2^23 and 2^23- 1, coded in 2's complement binary on 24 bits. The relation between the coded number N and the range of longitude X it encodes is the following (X in degrees): N <= (2^24 / 360) * X < N+1 Bit 1 of octet 7 is the low order bit. Inner Radius: Inner radius is encoded in increments of 5 meters using a 16 bit binary coded number N. The relation between the number N and the range of radius r (in metres) it encodes is described by the following equation: 5 N <= r < 5 (N+1) Except for N=2^16-1 for which the range is extended to include all greater values of r. This provides a true maximum radius of 327,675 meters. Bit 8 of octet 7 is the high order bit. Bit 1 of octet 8 is the low order bit. Unc. Radius: A method of describing the uncertainty for latitude and longitude has been sought which is both flexible (can cover wide differences in range) and efficient. The proposed solution makes use of a variation on the Binomial expansion. The uncertainty r, expressed in metres, is mapped to a number K, with the following formula: r = C((1+x)^K - 1) with C = 10 and x = 0,1. With 0 <= K <= 127, a suitably useful range between 0 and 1800 kilometres is achieved for the uncertainty, while still being able to code down to values as small as 1 metre. The uncertainty can then be coded on 7 bits, as the binary encoding of K. Bajko&Tschofenig January 05, 2010 [Page 6] Arc Band Binary Encoding July 05, 2009 Offset Angle and Included Angle: Offset angle and Included angle are encoded in increments of 2 degrees using an 8 bit binary coded number N in the range 0 to 179. The relation between the number N and the range offset (ao) and included (ai) of angles (in degrees) it encodes is described by the following equations: Offset angle (ao): 2 N <= ao < 2 (N+1) Accepted values for ao are within the range from 0 to 359,9...9 degrees. Included angle (ai): 2 N < ai <= 2 (N+1) Accepted values for ai are within the range from 0,0...1 to 360 degrees. Confidence: The confidence by which the position of a target entity is known to be within the shape description, (expressed as a percentage) is directly mapped from the 7 bit binary number K, except for K=0 which is used to indicate 'no information', and 100 < K <= 128 which SHOULD NOT be used but MAY be interpreted as "no information", if received. 5. Security Considerations This document defines the binary encoding of an arcband but does not describe the protocols that may be carrying it. No security issues are raised by the format itself. When put into a protocol then the typical communication security aspects and privacy considerations have to be dealt with. 6. IANA considerations 7. Acknowledgements To provide a maximum of compatibility with existing systems this document re-uses the binary encoding of the arcband format defined in the 3GPP TS 23.032 [3GPP-TS-23_032] specification. We would like to thank the 3GPP for their work. 8. Normative References [3GPP23032] "3GPP TS 23.032 V7.0.0 3rd Generation Partnership Project; Technical Specification Group Code Network; Universal Geographic Area Description (GAD)". [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. [RFC2131] Droms, R., "Dynamic Host Configuration Protocol", RFC 2131, March 1997. Bajko&Tschofenig January 05, 2010 [Page 7] Arc Band Binary Encoding July 05, 2009 [RFC2434] Narten, T. and H. Alvestrand, "Guidelines for Writing an IANA Considerations Section in RFCs", BCP 26, RFC 2434, October 1998. [RFC3046] Patrick, M., "DHCP Relay Agent Information Option", RFC 3046, January 2001. [RFC3118] Droms, R. and W. Arbaugh, "Authentication for DHCP Messages", RFC 3118, June 2001. [RFC3825] Polk, J., Schnizlein, J., and M. Linsner, "Dynamic Host Configuration Protocol Option for Coordinate-based Location Configuration Information", RFC 3825, July 2004. [RFC4119] Peterson, J., "A Presence-based GEOPRIV Location Object Format", RFC 4119, December 2005. [RFC5139] Thomson, M. and J. Winterbottom, "Revised Civic Location Format for Presence Information Data Format Location Object (PIDF-LO)", RFC 5139, February 2008. [RFC5191] Forsberg, D., Ohba, Y., Patil, B., Tschofenig, H., and A. Yegin, "Protocol for Carrying Authentication for Network Access (PANA)", RFC 5191, May 2008. [RFC5491] Winterbottom, J., Thomson, M., and H. Tschofenig, "GEOPRIV Presence Information Data Format Location Object (PIDF-LO) Usage Clarification, Considerations, and Recommendations", RFC 5491, March 2009. [WGS84] "World Geodetic System 1984 (WGS 84), MIL-STD-2401, http://www.wgs84.com/". 8. Informative References [RFC1712] Farrell, C., Schulze, M., Pleitner, S., and D. Baldoni, "DNS Encoding of Geographical Location", RFC 1712, November 1994. Bajko&Tschofenig January 05, 2010 [Page 8] Arc Band Binary Encoding July 05, 2009 Appendix A. Example This section provides an example with the corresponding GML encoding. For example, Paul is using a cellular wireless device and is 7 timing advance symbols away from the cell tower. For a GSM-based network this would place Paul roughly between 3,594 meters and 4,148 meters from the cell tower, providing the inner and outer radius values. If the start angle is 20 degrees from north, and the opening angle is 120 degrees, an arc band representing Paul's location would look similar to the figure below. N ^ ,.__ | a(s) / `-. | 20 / `-. |--. / `. | `/ \ | /__ \ | . `-. \ | . `. \ |. \ \ . ---o-- a(o) -- | | --> |. / 120 ' | E | . / ' | . / ; .,' / r(i)`. / (3594m) `. / `. ,' `. ,' r(o)`' (4148m) -43.5723 153.21760 3594 Bajko&Tschofenig January 05, 2010 [Page 9] Arc Band Binary Encoding July 05, 2009 4148 20 20 2003-06-22T20:57:29Z Appendix B. Pseudocode TBD: Code goes in here. 8. Author's Addresses Gabor Bajko gabor(dot)bajko(at)nokia(dot)com Hannes Tschofenig Nokia Siemens Networks Otto-Hahn-Ring 6 Munich, Bavaria 81739 Germany Email: Hannes.Tschofenig@nsn.com URI: http://www.tschofenig.priv.at Bajko&Tschofenig January 05, 2010 [Page 10]