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]