Proceedings of ICCTA20 11
`
`SPACEANNOTATOR: A HIGH PRECISION
`LOCATION BASED ASSET MANAGEMENT SYSTEM
`IN INDOOR ENVIRONMENT
`2
` Yongcai Wang
`
`Lei Song
`
`l,
`
`1 NEC Labs China
`2 IllS, Tsinghua University, Beijing 100876, China
`
`
`
`
`
`songJei@nec.cn, wangyc@tsinghua.edu.cn
`
`Abstract
`
`
`
`LBS (retrieval & navigation)
`
`Camera and radio signal intensity (RSI) indicator
`
`
`
`
`
`are involved to provide positioning ability in indoor
`
`
`environment for LAMS. D. Chen[3] proposed a
`Asset management is urgently needed in supply
`
`
`
`
`method to sample the related position of each book
`
`
`chain which requires to solve two basic problems I)
`
`in shelf by snapping photos with Smartphone,
`what assets do we have; and 2) where they are?
`
`
`whose application scene is limited. BlueBot [4]
`
`Existing methods exploit barcode and RFID
`
`
`using robot equipped RFID-reader to achieve
`
`
`
`technologies to retrieve the information and
`
`
`indoor location-sensing, but meter level precision is
`
`
`
`
`quantity of assets. However, the location of asset is
`
`
`
`not suitable for fine-grained asset application. RSI
`
`still hard to obtain for the lack of suitable location
`
`based positioning methods are widely used in
`
`technologies. In this paper, a high precision
`
`
`wireless sensor network (WSN) such as [5][6].
`
`
`location based asset management system named
`
`
`However lack of stability and precision are its
`
`
`
`SpaceAnnotator is proposed. SpaceAnnotator is
`
`
`major limitation for asset management. A more
`
`implemented based on TOA positioning
`method
`
`
`accurate and universal LAMS is desired.
`
`
`using Ultrasound and RF signals. Leveraging the
`
`
`
`
`centimeter level positioning accuracy provided by
`
`
`
`the positioning system, SpaceAnnotator maps the
`
`
`IDs of objects to their locations. Based on the
`
`
`
`
`location information, location based service (LBS)
`
`
`in provided for asset management. Compared with
`
`
`conventional location based asset management
`
`system, SpaceAnnotator works well even in
`managing small volume objects for its high
`accuracy.
`
`Location-ID
`
`mapping I E
`
`Location ID of Database
`of objects objects
`
`Keywords: LBS; Asset management
`system;
`
`
`LAMS; high precision positioning.
`
`Figure 1 System architecture of SpaceAnnotator
`
`1 Introduction
`
`In this paper we proposed SpaceAnnotator, a high
`
`
`
`
`
`precision location based asset management system
`
`in indoor environment. The overall system
`Location, as the most essential context of object,
`
`
`
`
`architecture is shown in Fig. I. Accurate
`
`
`
`can be exploited to provide context-aware services
`
`positioning result is provided by ultrasound
`
`to users, which is called Location Based Services
`
`
`
`
`positioning subsystem [7][8]. SpaceAnnotator is
`
`
`(LBS). Location based Asset Management System
`
`
`
`
`designed for fine-grained ID-position mapping. By
`
`
`(LAMS) is an important instance of LBS, in which,
`
`
`integration with asset database, it provides
`
`
`
`the type, quality, and positions of massive amount
`
`
`foundation for various LBS.
`
`assets are managed in real-time, forming
`SpaceAnnotator contains four components as
`
`
`
`
`fundamental for supply chain and warehouse
`
`
`shown in Fig.2. A PDA with RFID/Barcode reader
`
`
`applications. So far, there are already research
`
`
`
`and positioning accessory is used for sensing asset
`
`
`
`
`results and engineering implementation focusing on
`
`
`
`information. A ultrasound positioning subsystem,
`
`LAMS. Since how the ID of an object is mapped to
`
`which captures data from PDA and then outputs
`
`
`its corresponding location plays key role in LAMS,
`
`position-ID mapping for the asset that the PDA is
`
`
`positioning technologies are the basic need of
`
`
`
`sensing. A server provides navigation and query
`
`LAMS. The most well known positioning system is
`
`
`service to users for asset management. Detail
`
`
`GPS[I]. However due to its dependence of satellite,
`
`information of assets such as name, manufactory
`
`
`GPS is not functional in indoor environment and
`
`
`
`and picture are obtained from a database by using
`
`
`lack of high positioning accuracy [2]. RFID,
`the ID as index.
`
`RFC - Exhibit 1013
`
`1
`
`

`
`
`
`POSITIONING SUBSYSTEM
`
`Server
`
`(EKF) is run by the host-device
`to
`
`calculate and
`
`output the position of the POA.
`
`S �
`
`101 : (x1,y1,zl)
`102 : (x2,y2,z2)
`103 : (x3,y3,z3)
`
`RF
`
`PDA
`
`
`
`Figure 2 Components in SpaceAnnotator
`
`Compared with conventional LAMS, there are two
`
`
`main advantages:
`
`Figure 4 Asset registration
`
`With this positioning subsystem, workflow of asset
`
`
`precision, I) Centimeter level posItIoning
`
`
`
`registration is shown in Figure 4. Warehouseman
`
`therefore, small volume object such as book
`and CO can be managed by SpaceAnnotator.
`
`holds the POA to read the RFIO/Barcode on the
`
`object. Assuming IDi is read, then positioning
`
`
`2) Using RFID/Barcode as identifier makes
`
`
`SpaceAnnotator good compatibility and cost­
`
`
`
`routine is triggered to measure the position X, of
`
`PDA. Finally, server builds (IDi. X,) mapping to
`effective.
`
`record the asset ID and position. To simplify this
`The rest part of this paper is organized as follows.
`
`
`
`
`process, transferring ID and positioning are merged
`
`
`The system structure of Space Annotator will be
`
`to one step by encoding the ID into sync packet in
`
`
`
`described in Section 2; followed by key algorithms
`positioning.
`
`
`of SpaceAnnotator in Section 3; Prototype in
`
`
`Section 4;the performance of the SpaceAnnotator
`The workflow of navigation is shown in Figure 5.
`
`
`
`
`will be shown by adequate experiment in Section 5;
`
`When warehouseman wants to seek an object with
`
`
`Section 6 gives the conclusion of this paper and
`
`
`
`IDa, a self-positioning process is started on himlher
`
`discussion of future work.
`
`
`PDA to get current position Xo. Then a query
`
`
`
`The to the server. contain (IDa, Xo) is submitted
`
`server sends back an optimal path to the PDA,
`which is shown on the POA screen to guide the
`Location sensing is the foundation of LAMS. In
`
`
`
`
`warehouseman.
`
`
`SpaceAnnotator, ultrasound TOA based positioning
`
`
`
`
`subsystem is employed to provide location stream
`
`with centimeter-level precision[8].
`
`2 System overview
`
`s
`
`
`
`Figure 3 Structure of positioning subsystem
`
`
`
`Figure 5 Navigating mode.
`
`
`Figure 3 shows the structure of positioning
`
`
`
`
`subsystem. Reference nodes are installed in fixed
`Based on (id, pos) mapping, LBS such as asset
`
`
`
`positions of room. 40Khz ultrasound sensor and
`
`
`
`retrieval and asset displaying are also provided. For
`
`radio modules are embedded in each node. In each
`
`
`convenience, in SpaceAnnotator, these LBS are
`
`
`positioning routine, ID of object is read through
`
`presented on web. User can use any device with a
`
`RFID/Barcode reader in POA. Then POA sends a
`
`
`
`browser to get the latest status of warehouse. By
`
`radio sync packet and a ultrasound pulse
`
`
`
`using Ajax push technology, positions of assets and
`
`
`
`simultaneously. Each reference node measures its
`
`
`
`warehouseman can be updated in real-time. Figure
`
`
`
`distance to POA by counting arrival time difference
`6 shows the web page of an online asset
`
`
`between sync packet and ultrasound pulse. Then aIJ
`
`
`management demo. Left-half shows the real time
`
`
`
`
`measured distance are collected by a host-device in
`
`
`status of warehouse. Right-half shows list of
`
`
`
`the subsystem. Finally, An Extended Kalman Filter
`
`registered assets.
`
`2
`
`

`
`.. ... .............. ..
`
`''''-_ ........ ..
`
`Figure 6 Web based asset manage interface
`
`3 Key algorithms
`
`In order to solve this problem a novel algorithm
`
`
`
`named Fake-spot are proposed. Fake-spot is an
`
`
`
`
`iterative linear regression algorithm. The flowchart
`
`
`of fake-spot algorithm is shown in Figure 8. First
`
`
`all measured distances are copied to the valid
`
`distances set (VDS), which are input to EKF
`
`
`
`
`positioning algorithm to calculate a fake-spot. Then
`
`
`Fake-distances could be calculated from fake-spot.
`
`
`All distances in VDS and its corresponding fake­
`
`
`
`distances are compared. If their difference exceeds
`
`
`a threshold, this distance is judged as an outlier.
`
`
`The loop will continue until no outlier is found in
`
`
`one loop; then all distances in VDS are outputted as
`valid distances.
`
`Previous system structure gives a general design of
`
`
`
`
`
`SpaceAnnotator. To make the system work in
`
`
`
`practical scene, some algorithms are proposed to
`
`
`solve challenges existing in real Warehouse.
`
`Input:
`
`Measured Distances
`
`\'ES
`
`Output:
`Valid distance
`SOl
`
`3.1 Zone matching algorithm
`
`
`In warehouse, asset is stored with two modes. They
`can be either stacked freely or put into some
`
`predefined small zone, such as shelf, drawer or
`
`
`cabinet. For previous mode, people always want to
`
`
`
`know the precise position. For the later mode, to
`
`know which small zone it is occupying is more
`
`
`useful. So in SpaceAnnotator, a zone calibration
`
`
`
`and detection algorithm is exploited[lO]. The
`
`
`location features of the small zones are calibrated
`
`
`offline by K Nearest Neighbor (KNN) method and
`
`
`the online zone detection is carried out by Least
`Square Estimation.
`
`
`
`Figure 8 Flowchart of Fake-spot algorithm.
`
`
`
`600
`
`500
`
`400
`
`� 300 .,
`
`o
`
`200
`
`100
`
`0
`
`I_ calCUlated
`c::::JRe"
`
`10
`
`Figure 9 Distances measured in warehouse with
`
`3.2 NLOS filtration algorithm
`
`High precision location stream is the foundation of
`
`
`
`
`
`LAMS. Because of obstacles in warehouse and
`
`
`poor penetration of ultrasound, Non Light of Sight
`
`(NLOS) interference happens easily in warehouse
`
`
`
`when ultrasound positioning subsystem is used. As
`
`
`
`a result the measured distances are often longer
`
`than the real distances. Figure 7 shows average
`
`value of measured distances at 10 different
`
`
`positions in a warehouse. The solid bars stand for
`
`
`calculated distances, while the hollow bars stand
`
`for the real distance. It is found that one third of the
`
`
`
`
`
`
`
`measured distances are invalid. Similar experiment
`fake-spot
`
`result could be found in [9]
`Figure 9 shows measured distances from same
`
`
`800
`
`
`condition as Figure 7. The only difference is the
`
`
`
`employing of fake-spot algorithm. It is found that
`
`almost all NLOS interferences are eliminated,
`
`which verified the effectiveness of fake-spot
`algorithm.
`
`1_ Calculated
`
`c:=JRe al
`
`700
`
`600
`
`500
`8
`� 400
`B
`300
`
`200
`
`100
`
`0
`
`
`
`I� �
`
`10
`
`4 System prototype
`
`To verity system design and algorithms, prototype
`
`
`
`of SpaceAnnotator is implemented. Top subfigure
`
`in Figure 10 shows receivers, cables and host in
`Figure 7 Distances measured in warehouse without
`
`positioning subsystem. The bottom one in figure
`
`
`
`
`fake-spot.
`
`3
`
`

`
`shows how they are instaIIed in experiment
`5 Performance evaluation
`
`
`warehouse.
`
`
`
`Figure 10 Prototypes of positioning subsystem.
`
`
`
`Using this prototype, adequate experiments are
`
`
`
`
`carried out to show the performance of the
`SpaceAnnotator.
`40 points in the warehouse are selected as
`
`
`
`
`
`experiment points. Positions of aII the points are
`
`
`measured manually by Laser range finder as ground
`
`truth. Then SpaceAnnotator is used to measure
`
`
`positions of all these points. The 3D-view of
`
`
`contrast is shown in Fig 14. Red points stand for
`
`real position while the green points stand for
`
`
`positioning result. We can find out that in center of
`
`
`
`the room positioning results are close to the real
`
`
`position. While in comer the positioning error are
`much bigger.
`As figure 11 shows, industrial PDA and dual screen
`
`
`
`
`
`android PAD are selected as handhold devices. The
`left one is PDA with smaII weight and long battery
`
`
`life, which is suitable for asset operation such as
`
`
`registering and position updating. The right one is a
`
`PAD with big screen which is suitable for
`
`
`navigation and status checking. In both of the
`
`
`
`
`is accessory devices, a ultrasound & radio emitter
`
`
`plugged into the USB-host port.
`
`10
`
`
`
`Figure 1 1 Prototype ofPDA
`
`100
`
`200
`
`Y(cm)
`
`X(cm)
`
`Figure 13 Deployment of receivers in positioning
`
`Fig. 12 shows experiment scene of SpaceAnnotator,
`
`
`
`whose size is a 6m * 4m *3m. In this experimental
`subsystem.
`
`warehouse, Shelf and tables are set up for holding
`
`
`assets. CDs, books and bottles are used as
`
`250 /
`I :
`
`240
`
`real oo5.:lon I
`pos tlc"mQ res_it I
`
`/
`
`220
`
`, 200
`
`80
`
`·40 / 500 400
`
`I L 500
`v o
`-:00
`300 200 100 o -100
`
`
`
`
`
`Figure 12 Experiment scene
`
`
`
`Figure 14 3D view of positioning error
`
`Top view of same experiment is shown in Figure 15.
`
`
`Figure 13 shows the positioning subsystem
`
`
`
`Positioning error in x-y planet is much smaller than
`
`
`
`installed in this room. 15 ultrasound receivers are
`
`in 3D space. The cause is that all receivers are
`
`mounted on the ceiling of this room to work as
`
`
`
`deployed in x-y planet, so resolution in z-axis is
`
`
`reference point for position calculation.
`
`
`smaller than in x-y planet. Like 3D view, error in
`
`comer is bigger than in the center of the room.
`
`4
`
`

`
`of a warehouse. Hybrid location methods and
`
`
`
`
`location based complement method would be the
`
`research focus of next step to solve this problem.
`
`References
`
`� 0.., % % �
`�
`� � � <b
`0() <b � <b � � 0()
`Gl (10 � <l> 0 � S
`e <II � Q (j) <II
`
`e (10 @ Gl (10 0 Ge
`Gl I!! \ll Gl 0 6 Q)
`6 $ Gl 6> '& <II
`50 S S � % % <b �
`
`50
`
`150 200
`X(cm)
`
`
`
`subsystem.
`
`l00I'--C� � � � � � �7r _�_�oom���
`
`- - - 08 ntef
`
`-
`
`s \'era(Je
`
`[ 1] P. Enge and P. Misra, "Special Issue on Global
`
`
`
`
`Positioning System", Proceedings of the IEEE,
`vol. 87, Jan. 1999, pp. 3-15.
`
`[2] K. Hassy, R. Narsim, E. Drury, R. Vandenberg,
`
`D. Sen, C. Grooby, and 1. Bernhard, "Spatially
`
`
`Enabling Data With GIS for Utility Waterways
`
`
`and Watershed Asset Management Program",
`
`Proceedings of the Water Environment
`
`Federation, vol. 2009,2009, pp. 6854--6870.
`Figure 15 Deployment of receivers in positioning
`[3] D. Chen, S. Tsai, K.H. Kim, C.H. Hsu, J.P.
`
`Singh, and B. Girod, "Low-cost asset tracking
`Figure 16 gives the CDF of positioning result. The
`
`
`
`
`using location-aware camera phones", SPIE
`
`
`error is defined as the Euclidean distance between
`
`
`Workshop on Applications of Digital Image
`
`
`
`real position and positioning result. We can find
`
`Processing (ADIP), San Diego, California,
`
`
`that in average, 90% of the error is smaller than 10
`2010.
`
`centimeter, which means that all object bigger than
`
`[4] A. Patil, 1. Munson, D. Wood, and A. Cole,
`
`
`10 centimeter is supported in SpaceAnnotator.
`
`
`
`"BlueBot: Asset tracking via robotic location
`
`
`
`crawling", Computer Communications, vol. 3 1,
`2008,pp. 1067�1077.
`
`[5] P. Bahl and V.N. Padmanabhan, "RADAR: an
`
`and in-building RF -based user location
`
`
`
`tracking system", IEEE INFOCOM 2000.
`
`
`Nineteenth Annual Joint Conference of the
`IEEE Computer and Communications
`
`
`Societies. Proceedings, IEEE, 2000, pp. 775-
`784 vol.2.
`[6] A. Mason, A. Shaw, and A.I. AI-Shamma'a,
`
`
`
`"Inventory Management in the Packaged Gas
`
`
`Industry Using Wireless Sensor Networks",
`
`Advances in Wireless Sensors and Sensor
`
`
`Networks, S.C. Mukhopadhyay and H. Leung,
`
`
`Eds., Berlin, Heidelberg: Springer Berlin
`
`Heidelberg, 2010, pp. 75-100.
`[7] lunhui Zhao and Yongcai Wang,
`
`
`"Autonomous Ultrasonic Indoor Tracking
`Location based asset management is a promising
`
`
`
`
`
`System", International Symposium on Parallel
`
`
`application of loT. In this paper, we proposed a
`
`
`and Distributed Processing with Applications,
`
`novel LAMS named SpaceAnnotator, by exploiting
`2008. ISPA '08, IEEE, 2008, pp. 532-539.
`
`
`ultrasound TOA positioning and barcode ID
`
`[8] L. Song and Y. Wang, "3D Accurate Location
`
`
`
`scanning technologies. Position and asset 10 is
`
`
`Stream Tracking and Recognition Using an
`
`mapped and LBS such as asset retrieval and
`
`
`Ultrasound LocalizationSystem", 201 1.
`
`
`navigation are provided. To solve practical
`
`[9] K. Lferd, lR. Martinez-de Dios, A. de San
`
`
`problems from real warehouse, NLOS algorithm
`Bernabe, and A. Ollero, "Experimental
`
`
`
`and shelf matching algorithm are involved. In order
`
`comparison of RSSI and TOF measurements
`
`
`to evaluate the performance of SpaceAnnotator
`for localization".
`
`
`
`protocol, some experiments are carried out, which
`
`[ 10] J.Zhao, Y. Wang, PosPush: A Highly Accurate
`
`
`shows that SpaceAnnotator can provide centimeter
`
`
`
`Location based Information Delivery System,
`
`
`level positioning resolution. But because of the
`
`In proceedings of The Third International
`
`
`
`poor penetration ability and short valid distance of
`
`
`Conference on Mobile Ubiquitous Computing,
`
`
`ultrasound, location precision of current
`Systems, Services and Technologies,
`
`
`
`SpaceAnnotator varied greatly in different position
`
`(UBICOMM09),2009.
`
`eo
`
`�!O "
`
`40
`
`30
`
`,\ 20 21 30 35
`LocatJ'lg arror(cm)
`
`Figure 16 CDF of positioning error.
`
`'0
`
`6 Conclusions
`
`5