Expressions for search time and energy consumption
In the coming decades, an increasingly larger number of baby boomers will grow into old age. This trend has led to an increasing demand for devices and services (e.g., [1-8]) that can help elderly individuals to live well and independently.
Existing object locators are not ideal in many aspects: The number of buttons on the interrogator and tags is fixed, and the number is small. Extending the locator to track more objects is impossible. – If the user were to use more than one tag of the same color, the tags would all respond to the search signal for tag(s) of the color from the interrogator. This situation is clearly not desirable. – When a tag breaks, the user must purchase a replacement tag of the same color as the broken one. Tags are battery-powered. A tag might become a lost object itself after it runs out of battery. More seriously, the interrogator itself can be misplaced. Obviously, these are serious shortcomings.
This chapter describes three designs and a proof-of-concept prototype of object locators based on the
This chapter makes two contributions: The first is the object locator designs presented here. The designs use different hardware components and have different hardware-dependent software requirements. The information provided by the chapter on these aspects should enable a developer to build a suitable object locator platform, or an extension to one of the commonly used computer and smart mobile device platforms. The functionality of hardware-independent object locator software is well defined, and a C-like pseudo code description can be found in .
The hardware capabilities and object search schemes used by the designs lead to differences in search time and energy consumption. We provide here a numeric model that can be used to determine the tradeoffs between these figures of merit. Developers of RFID-based object locators can use the results of the analysis as design guides. Today, object locators based on all designs are too costly: Typical RFID readers have capabilities not needed by our application and cost far more than what is suitable for the application. Through this analysis, we identify the design that is the most practical for the current state of RFID technology and project the advances in the technology required to make RFID-based object locators affordable (i.e., with prices comparable with some of the locators one can now find in stores.) This is the second contribution of the chapter.
The rest of this chapter is organized as follows. Section 2 describes closely related works. Section 3 describes use scenarios that illustrate how a RFID-based object locator may be used. Section 4 presents three designs of RFID-based object locators. Section 5 describes the implementation of a proof-of-concept prototype based on one of the designs. It also describes the reader collision problem  encountered in the prototype and the solution we use to deal with the problem. Section 6 describes a numeric model for computing energy consumption and search time and compares the merits of the designs. Section 7 concludes the chapter and discusses future works.
2. Background and related work
This section first presents a brief overview of RFID technology as a way to state the assumptions made in subsequent chapters on state-of-the-art readers and tags. Our object locator resembles location detection systems in its goal: assisting users to locate objects. The section describes existing location systems and compare and contrast them with our object locators.
2.1. RFID technology
RFID technology is now applied to a wide spectrum of applications. As an example, personal identification application is used to provide authentication and authorization to individuals carrying their RFID tags so that they can be automatically identified by a central computer. Card-like RFID tags used as smart cards in public transports is another example: Information on money stored in a tag is automatically deducted when the card holder presents the card in front of a reader while getting on or off a transporter. Other applications include using RFID tags as markings of books for more efficient library management, shipping containers for tracking them by retail industry, and so on.
Figure 2 shows a typical system that uses RFID technology. The host machine uses one or more RFID readers to retrieve digital information stored in RFID tags and processes the information according to the needs of one or more applications. In general, a RFID tag contains a globally unique identification (UID) as well as data fields organized in a standard way . A RFID-based object locator only needs the UID information; other data fields are not used.
There are three types of RFID tags: passive, semi-passive and active. A
Each message sent from a reader to tags contains a command code. Among the sets of commands defined by ISO15693 , our object locators use only
The command used to read UID of a tag is the
2.2. Location detection systems
Many different location detection systems are available today. Global Positioning System (GPS)  is the most well known. Priced at about $ 100 US each, GPS navigators are widely used in cars, buses and so on. However GPS has its limitations. Reflection, occlusion and multipath effects seriously interfere with distance measurement and make GPS ineffective indoors. For this reason, indoor location detection systems use a variety of other technologies.
Active Badge  is representative of infrared-based location detection systems. A badge containing an infrared transmitter is attached to each object to be tracked by the system. The transmitter sends periodically messages containing the unique identification of the badge. The messages are caught by some infrared receivers at fixed known locations and relayed by the receivers to a central computer. The central computer resolves the position of the badge based on the locations of the receivers. Shortcomings of systems such as Active Badge arise from the fact that infrared signals cannot penetrate most materials in a building and are easily interfered by other infrared sources.
Ultrasound is used to assist with distance measurement in Bat  and Cricket . These systems use both ultrasound and RF signals to measure distances between beacons (transmitters) and listeners (receivers): When a beacon at a known location transmits an ultrasound signal and a RF signal concurrently, a listener can calculate the distance to the beacon from the difference between the arrival times of the signals.
Many indoor location detection systems use RF-based technology to take advantage of the fact that RF signals penetrate most non-metallic materials. RADAR  is an example. The system estimates distance by estimating the strength of RF signals. Specifically, the system measures in the initialization phase at a set of fixed locations the strengths of a RF signal sent by a location-known transmitter. The measured strengths are stored in a database to be used later as yardsticks during the working phase. In the working phase, each receiver measures the strength of a RF signal transmitted from a tracked object and sends the strength to a central computer. The computer compares the measured strengths with the information stored in the database and then resolves the possible position of the transmitter (i.e., the tracked object). MoteTrack , similar to RADAR, uses empirical distance measurement to estimate positions of objects. WLAN (wireless local area network) can be used to build location detection systems also. SpotON  and Nibble  are examples.
Compared with the above mentioned location detection systems, an object locator must be a far more low cost solution and must be ultra easy to set up and use. Many indoor location detection systems (e.g. Bat and Active Badge) rely on a big infrastructure or a pre-computed database (e.g. RADAR) to support location estimation. These systems are too costly to deploy and maintain and hence, unsuitable for home use. Cricket system provides a low cost location-aware service. An object with a receiver can determine its location. This is not what an object locator does. A misplaced object does not need to know its own location; the user looking for it needs to know.
3. User scenarios
The routine usage of an object locator requires only three operations: Add, Delete and Query. We describe these operations here to illustrate how a locator may be used. Without loss of generality, we assume that a new object locator kit contains a portable interrogator, a dozen of RFID tags and agents. As illustrated by Figure 3, the interrogator resembles a smart phone. It has a small non-volatile storage and a RF transceiver together with a network address. We will return in the next section to describe how the RF transceiver is used, as well as what agents are and do. Unlike common smart phones, however, the interrogator has a RFID reader. The reader is used for the Add operation described below.
Specifically, Figure 3 shows parts of the user interface on an interrogator with a LCD touch screen and two buttons. The LCD touch screen is used as both input and output user interface. A user can select an item among the items displayed on the screen, the button at the bottom left corner to confirm a selection, and the button at the bottom right corner to cancel the selection. Some operations need text input. The virtual keyboard shown on right is for this purpose.
Figures 4 and 5 illustrate Add and Query operations, respectively. Add operation works in a similar way as the address book of a smart phone. Using this operation, the user can add the registration of an object to be tracked into the interrogator. By registration, we mean a mapping between the id of the tag attached to an object and the name of the object. The user queries the locations of objects by their names. In response to a query, the interrogator uses the object-name-tag-id mappings to resolve which one of the registered objects to search. Figure 4 shows a scenario: The user picks an unused tag and attaches it to an object to be tracked as shown in Figure 4(a) and (b). Then, the user puts the tag close to the interrogator and selects Add object. This step is shown in Figure 4(c). In response to Add object command, the interrogator reads the id of the tag, displays a new text field and prompts the user to enter a name (e.g., Key). When the user confirms the name, the interrogator creates a mapping associating the name with the id of the tag attached to the object, and stores the mapping in its local non-volatile memory. This is illustrated in Figure 4(d). The user repeats the above steps to register each object until all objects to be tracked are registered.
Query operation is the work horse of the object locator. The user presses Query object on the touch screen, as illustrated by Figure 5(a), to invoke this operation for assistance in finding misplaced objects. When the names of registered objects are displayed, the user selects the object to be searched; in this example, it is Key. After the user confirms the selection, as shown in Figure 5(b), the interrogator retrieves from its local storage the id of the tag attached to the object with the selected name and starts a search for the tag with that id. Hereafter, we call the tag being searched the
Object locators of different designs present the result of Query operation in different ways. As examples, Figure 5(c) and (d) shows two different responses. In Figure 5(c), the interrogator directs the user to the place (e.g. bedroom 1) where the queried object is found. In Figure 5(d), the queried tag beeps, allowing the user to look for it by following the sound. This version works like the existing locator described in Section I.
Delete operation removes the registration of an object, i.e., the object-name-tag-id mapping stored in the interrogator: The user can invoke the operation by pressing Delete object on the touch screen. In response, the interrogator displays the list of registered objects, allowing the user to select the object (e.g. Key) to be deleted. The interrogator deletes the mapping after the user confirms the selection. Delete operation frees the tag attached to the now unregistered object and makes the tag free for use to track some other object.
4. Alternative designs
The three designs of object locator are called Room-level Agents, Interrogator and Tags (RAIT) locator, Desk-level Agents, Interrogator and Tags (DAIT) locator and Desk-level and Room-level Agents, Interrogator and Tags (DRAIT) locator. As their names imply, each of the locator consists of tags, agents and at least one interrogator. The adjectives room-level and desk-level describe the ranges of RFID readers used by the designs. The ranges of room-level readers and desk-level readers are sufficiently large to cover a typical-size room or desk, respectively.
The term tag refers specifically to RFID tags. Each tag has a unique id, hereafter called
4.1. RAIT locator
A disadvantage of the existing locator is that a user needs to walk around the house when searching an object and the interrogator needs to repeatedly send the query signal until the user hears the queried tag or gives up the search. RAIT locator is designed to eliminate this disadvantage.
RAIT locator uses one or more agents to cover each room, and the house is fully covered by agents as shown in Figure 6. When the user invokes a Query operation, the interrogator sends a query message containing the TID of the queried tag to agents and thus requests the agents to search the queried tag on its behalf. Each agent broadcasts an addressed mode read request with the TID retrieved from the query message to read the tags within range. The tag with id matching the TID beeps upon receiving a read request, in addition to responding to the agent. The agent finding the queried tag reports its network address to the interrogator. This information enables the interrogator to display the results illustrated by Figure 5(c), telling the user to go to the specified room where the queried object has been found.
Obviously, the agents must be set up before a RAIT locator can be used. Figure 7 lists the steps carried out by the user and work done by the system during the set up process. The goal of Steps 3-5 is to make sure that there is no blind region. A
The Register Agent operation in Step 6 is similar to Add operation described in Section 3. Its goal is to assign a human-readable location name to an agent, so that the interrogator can later generate query results illustrated by the example in Figure 5(c). During the operation, the interrogator prompts the user to provide a unique name for the location of each agent. For example, if the living room needs two agents, Living Room R(ight) and Living Room L(eft) are good names for them.
The interrogator also assigns a unique network address to the agent being registered. The id of the tag in an agent is the product serial number of the agent. The interrogator uses the id to distinguish the agent from previously registered agents. By assigning successive network addresses to agents as they are registered and initialized one by one, successive Register Agent operations enable each initialized agent to join the WLAN and later compute the addresses of other agents by adding or substituting some number from its own address.
Figure 8 depicts the format of messages in a RAIT locator. This format supports multiple interrogators: The src_addr allows agents to identify the interrogator issuing the query message. The dest_addr allows them to address their responses to a specified interrogator. Data field allows interrogators to synchronize their databases created by Add and Register Agent operations. We will discuss how the other fields are used shortly.
4.2. DAIT and DRAIT locators
DAIT locator, shown in Figure 9, is an extension of RAIT locator. The designs are similar in how the Query operation is handled by the interrogator and agents. DAIT differs from RAIT primarily in the required read ranges of agents. The read range of agents used in a DAIT locator is less than one meter. Agents with such a small range offer higher accuracy in locations of queried tags. Information on the agent that finds the queried tag tells the user the location of the searched object within a small vicinity of the agent. Tags in DAIT locators are passive; they do not beep because a user can easily find the misplaced object even though the tag does not beep. Because tags do not need to beep, they can be battery free. This is a major advantage of DAIT locator.
However, it is significantly more complicated to set up desk-level agents. Blind regions of RAIT locator are easy to detect and eliminate because a blind region is typically created by walls and is near the read boundary of an agent. In the case of DAIT locator, a room cannot be fully covered by one or two agents. Any three adjacent agents may create a blind region. Our solution is to give a user a circular thread whose circumference is less than (i.e., the circumference of a regular triangle whose center is one unit away from its corners) times their read range and instruct a user to set any three adjacent agents within the circular thread. By doing so, blind regions never occur.
DRAIT locator has a hybrid design that aims to extend the lifetime of semi-passive tags. A DRAIT locator contains both room-level and desk-level agents. Its interrogator asks desk-level agents to search first. The interrogator asks room-level agents only when no desk-level agent finds the queried object. We set up desk-level agents on furniture in addition to setting up room-level agents as described above. Because misplaced objects are often on furniture or in vicinities of them, the queried object can often be found by a desk-level agent, and the tag on it does not need to beep.
4.3. Search schemes
A queried object can be searched in three ways: broadcast, relay and polling. The
The knowledge on the agent network addresses and the number of agents enables an interrogator to request assistance from agents one at a time using the
According to the
5. Prototype implementation
We implemented a proof-of-concept prototype of DAIT locator, the design that does not require customized semi-passive tags. Indeed, all components used in our prototype are readily available today. Parts (a) and (b) of Figure 10 show an agent and the portable interrogator of our prototype, respectively. The agent is composed of a microcontroller, a RF transmitter, a RF receiver and a RFID reader module. The microcontroller is ATMEL ATmega128. It runs at 8MHz and has 128k bytes flash / 4k bytes EPPROM. The RF transmitters and receivers interconnecting interrogator(s) and agents are LINX TXM(RXM)-433-LR, which use 433MHz ASK. RFID reader modules are MELEXIS EVB90121, which is ISO15693-compliant and uses a directional antenna. We use TI OMAP5912 and NEC Q-VGA to implement the portable interrogator. The current version of our prototype supports the three operations described in Section II and uses the polling search scheme.
The lack of customized antenna design for tags and readers and the reader collision problem seriously affects the performance of our prototype. Our DAIT prototype uses only tags with directional antennae. (Again, the reason is that such tags are readily available.) When the antennae of tags and readers are directional, the read performance of agents depends on the orientation of the antennae. Clearly, tagged objects may be placed in arbitrary orientations. As a consequence, it is impossible to ensure optimal or near optimal alignment of the tag antennae towards the agents covering their locations. This is the reason that tags in a DAIT object locator should have omni-directional antennae. Agents with omni-directional antennae can be simply set on furniture as shown in Figure 11(a). Agents with directional antennae should be attached to the ceiling as shown in Figure 11(b). This arrangement requires a read range of 2-3 meters. With readers of a sufficiently large read range, RAIT locators can use tags with directional antennae without performance concern.
Close proximity of readers (i.e., agents) is necessary in order to avoid blind regions. Our DAIT prototype is no exception. When RFID readers have overlap coverage areas, signals sent at the same time from them to tags in the overlap region interfere with each other. This is called the
A DAIT locator that uses the broadcast scheme can circumvent the reader collision problem in many ways. For example, the DAIT prototype can let each agent delay transmitting its query signal by an amount of time that is a function of its network address. In this way, agents try to avoid transmitting query signals at the same time. This solution is practical and easy to implement.
Another solution requires each agent to know the network addresses of its neighbors. Each agent can be viewed as a node in a connected graph. There is an edge between two nodes when the agents represented by them have overlapping coverage regions. A graph coloring algorithm can be used to assign different colors to adjacent nodes. The reader collision problem never occurs as long as agents labeled by different colors do not transmit query signals concurrently. This solution is likely to have a better response time than the solution mentioned above or the relay and polling schemes. However it requires additional hardware for each agent to automatically detect its neighbors or connectivity information entered by the user manually. The additional hardware makes agents more costly, and complicated operations by the user make an object locator hard to use.
6. Relative merits
We use search time and energy consumption of a single query to measure the relative merits of object locator designs. Search time and energy consumption per query depend on many factors including the number of agents, search scheme, search sequence and locations of misplaced objects.
6.1. Search time and energy consumption
The expressions of energy consumption and search time per query according to broadcast, relay and polling schemes are listed in Table 1. The expressions assume that agents and interrogator(s) are battery powered and communicate in the manners described in Section 4. The notations used in the expression are defined in Table 2.
The total energy consumed by the object locator for processing a Query operation according to the broadcast scheme is the sum of the three terms in the first row of Table 1. In this case, the interrogator transmits only one query message per Query operation. The energy it consumes is
In the expressions,
The expression of the expected time taken by the locator using the broadcast scheme to respond to a Query operation assumes that agents search the queried tag in sequence in order to avoid the reader collision problem. The first term in the expression is the time taken by the query message from the interrogator to reach all the agents. If the first agent finds the queried tag, which occurs with probability
The average search time of an object locator that uses the relay and polling scheme are estimated by the expressions in the fourth and sixth rows in Table 1, respectively. Relay and polling scheme also lets all agents search the queried tag in sequence. This is why the coefficients in these expressions are the same as the coefficients in the expression of
As stated earlier, Table 1 is based on the assumption that agents and the interrogator are battery powered. Hence, the total energy consumption includes energy consumptions of agents and an interrogator. However, agents can be connected to wall plugs, especially when the number of agents is small, as in the case of RAIT locators. The interrogator using relay and broadcast scheme consumes exactly
6.2. Model of object locality
We call the probability of finding a queried object at
Figure 12 gives an illustrative example. The figure is not drawn scale, and each unit square in this example is 10 cm by 10 cm in dimension. Two agents
We call the area where a misplaced object might be placed an
6.3. Evaluation environment and results
The environment we used to evaluate the relative performance of our designs has a 10m by 10m search space, containing 1000 × 1000 unit squares of size 1 cm by 1 cm. Agents are placed according to the arrangement in Figure 13(a). The number of agents is
In Section 4, we said that the agent with the smallest network address is the first agent and the other agents are asked one by one in order of agent ids to search for the queried object. We call this search order
Our evaluation program assumes that object regions are circular for the sake of simplicity. The center and radius of an object region are randomly generated. The variables
Figure 14(a) and (b) show the average search time for broadcast scheme, relay scheme, and polling scheme (i.e., polling in sequential order), as well as polling scheme with profiling. The search time of relay and polling schemes is higher than broadcast scheme for all values of DRatio. The search time of polling scheme with profiling is less than that of broadcast scheme when DRatio is less than about 1 (100) for
Figure 15 shows the average energy consumption consumed by agents when
Table 3 gives a summary. The table suggests the broadcast scheme when DRatio is high and search time is more important than energy consumption. When DRatio is low, the differences among the search times of all search schemes are small. Energy consumption becomes the dominant factor for comparison. It is possible for agents in a RAIT locator to connect to power source. For energy saving on interrogators, we suggest polling scheme with profiling for stationary interrogators and relay or broadcast scheme for portable interrogators. As for DAIT locators, we consider energy consumption of an interrogator and agents. We suggest polling scheme with profiling when ERatio is low and the same suggestions as that for a RAIT locator if ERatio is high.
We described here three alternative designs for RFID-based object locator. These object locators are extensible, reusable and low maintenance. They are easy for users to set up and use. Our analysis shows that search time and energy consumption for all designs and search schemes depend the capabilities of RFID readers and RF transceivers used by agents. Roughly speaking, polling and relay schemes are competitive to broadcast scheme only when DRatio or ERatio are less than 10.
We implemented a proof-of-concept DAIT prototype object locator to demonstrate the object locator concept and designs. The prototype uses only readily available hardware components, including readers and tags with directional antennae. The performance of the prototype is far from ideal, primarily for this reason. Because it is impossible to control the orientation of tag antennae, omni-directional antennae are better suited for our application.
The total cost of an object locator depends on many factors. The total hardware cost of a minimum object locator is the sum of the costs of an interrogator and required number of agents and tags. Compared with the costs of interrogator and agent, the hardware cost of tags is significantly lower and, for the discussion here, can be neglected.
Currently, the total hardware cost of an object locator is dominated by the total cost of agents, and the cost of an agent is dominated by the RFID reader in the agent. The number of agents required to fully cover a house depends on dimensions
This work is partially supported by the Taiwan Academia Sinica thematic project SISARL (Sensor Information System for Active Retirees and Assisted Living (http://www.sisarl.org).