[Search] [txt|pdfized|bibtex] [Tracker] [Email] [Nits]
Versions: 00                                                            
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)

      <?xml version="1.0" encoding="UTF-8"?>
      <presence xmlns="urn:ietf:params:xml:ns:pidf"
       xmlns:gp="urn:ietf:params:xml:ns:pidf:geopriv10"
       xmlns:cl="urn:ietf:params:xml:ns:pidf:geopriv10:civicAddr"
       xmlns:gs="http://www.opengis.net/pidflo/1.0"
       xmlns:gml="http://www.opengis.net/gml"
         entity="pres:paul@somecell.example.com">
        <tuple id="sg89ab">
          <status>
            <gp:geopriv>
              <gp:location-info>
                <gs:ArcBand srsName="urn:ogc:def:crs:EPSG::4326">
                   <gml:pos>
                     -43.5723 153.21760
                   </gml:pos>
                   <gs:innerRadius uom="urn:ogc:def:uom:EPSG::9001">
                     3594

Bajko&Tschofenig           January 05, 2010                   [Page 9]


Arc Band Binary Encoding                                July 05, 2009

                   </gs:innerRadius>
                   <gs:outerRadius uom="urn:ogc:def:uom:EPSG::9001">
                     4148
                   </gs:outerRadius>
                   <gs:startAngle uom="urn:ogc:def:uom:EPSG::9102">
                     20
                   </gs:startAngle>
                   <gs:openingAngle uom="urn:ogc:def:uom:EPSG::9102">
                     20
                   </gs:openingAngle>
                </gs:ArcBand>
              </gp:location-info>
              <gp:usage-rules/>
            </gp:geopriv>
          </status>
          <timestamp>2003-06-22T20:57:29Z</timestamp>
        </tuple>
      </presence>

   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]