# A Pervasive Promotion Model for Personalized Promotion Systems on Using WLAN Localization and NFC Techniques

Authors: Kam-Yiu Lam; Joseph Kee Yin Ng; Jiantao Wang; Calvin Ho Chuen Kam; Nelson Wai-Hung Tsang
Journal: Mobile Information Systems
 (2015)

---

## Abstract

In this paper, we propose a novelpervasive business model for sales promotion in retail chain stores utilizing WLAN localization and near field communication (NFC) technologies. The objectives of the model are to increase the customers’ flow of the stores and their incentives in purchasing. In the proposed model, the NFC technology is used as the first mean to motivate customers to come to the stores. Then, with the use of WLAN, the movements of the customers, who are carrying smartphones, within the stores are captured and maintained in the movement database. By interpreting the movements of customers as indicators of their interests to the displayed items, personalized promotion strategies can be formulated to increase their incentives for purchasing future items. Various issues in the application of the adopted localization scheme for locating customers in a store are discussed. To facilitate the item management and space utilization in displaying the items, we propose an enhanced R-tree for indexing the data items maintained in the movement database. Experimental results have demonstrated the effectiveness of the adopted localization scheme in supporting the proposed model.


---

## Body

## 1. Introduction

With the advances in electronic and wireless communication technologies, the design and development of novel mobile and pervasive computing applications have attracted great interests in both the industry and academia. Nowadays, people can easily use their smartphones as minicomputers to play computer games and retrieve various useful information, for example, shopping information, through cellular or wireless networks. It can be anticipated that pervasive computing applications will become one of the core computing applications in the coming future [1], and more and more smart electronic devices will be equipped with powerful computing capabilities to support novel and advanced mobile services to the users.One of the typical pervasive computing applications that is attracting tremendous attention in the business sector is thelocation-based services [2]. For location-based services, the services to be delivered to mobile clients depend on their current locations. For example, in a museum, different descriptions about the exhibits will be provided to the visitors depending on the current locations of the visitors. In general, location-based services can be classified into two main categories. Firstly, they are thesmart services for mobile users such as mobile control and navigation services, for example, Google map and smart cars. Secondly, it is the mobile information services. The business sector is exploring the locations and movements information of mobile users aiming at improving the business operations and the increase of sales volume, for example,mobile advertisement [3].A fundamental technology in providing effective location-based services is to have a good localization system to determine the current locations of mobile users accurately. Although GPS is a very successful technique for localization, it is mainly effective for outdoor localization. Even with the help of mobile phone technologies in localization, its accuracy may not be good enough for many indoor location-based applications which require an accuracy within a range of 1 to 2 m.Another common technology for localization is to use thewireless local area network (WLAN) which has been shown to be more suitable for localization in indoor environment [4, 5]. In addition, the coverage of WLAN is getting larger and larger in many big cities and various efficient techniques have been proposed to improve its accuracy and deployment [5]. Experimentally, it has been shown that the accuracy achieved from a WLAN in localization can be within one metre with good calibration [4].Another type of wireless communication technology that is receiving growing interests in recent years is thenear field communication (NFC). Functionally, NFC is not a communication device but an identification technique similar to RFID and smart cards. Currently, various studies are conducted to look into the feasibility of NFC for payment systems, object tracking, and logistic applications. Since more and more smartphones are equipped with NFC, its applications are growing rapidly. Unlike WLAN, NFC is for very short range communication, that is, within several centimetres. Although the close range of communication of NFC limits its communication capability, it can be used as a reliable and easy-to-use location indicator if the location of one of the NFC devices is known, that is, the presence of an NFC device next to another NFC device which has a known location.Although various novel location-based services are emerging, for example, counting people in a tour group and taking roll calls for class attendance in universities, the application potentials of the location information obtained from WLAN for location-based business applications still have a lot of room for further exploration especially when they are combined with NFC and other location-based technologies. According to behavioral studies in pervasive promotion systems [1, 6, 7], the information for the movements of customers within a store could be very useful for marketing and for planning promotion strategies in retail stores. In this paper, by exploring the advanced techniques in pervasive computing and localization using both WLAN and NFC, we formulate apervasive promotion model for the development of apersonalized promotion system for sales promotion in retail chain stores. Various technical issues in the design of the system are discussed in this paper.The remainder of the paper is organized as follows. In Section2, we briefly review the related work on location-based services and the different technologies for localization. In Section 3, we define the proposed pervasive promotion model. In Section 4, we discuss the details of the design of the personalized promotion system according to the proposed model. An illustrative example is presented in Section 5. In Section 6, we report the performance of the localization scheme in supporting the proposed system. We conclude the paper and briefly discuss the future works in Section 7.


## 2. Related Work and Background

In this section, we review the previous work on applying location-based services in business advertisement and customer behavioral prediction. Then, we present the latest technologies for localization using WLAN and the basic principles and performance characteristics of NFC.


### 2.1. Location-Based Business Services

With the popularity of smartphones, business companies are developing various novel location-based services for catching new business opportunities. One of the popular location-based services is mobile advertisement [2, 8]. In [8], the iMAS system was proposed. It uses GPS to provide location-based intelligent advertising services such that different advertising information is provided to clients at different locations. Similarly, in [2], a location-based mobile advertisement publishing system for vendors was proposed. The system allows the vendors to edit advertisements and publish advertisements to customers through a wireless infrastructure such as 3G networks or WiMAX. In addition, the advertisement data desired by the customers can also be viewed through QR code readers.In addition to mobile advertisements, some researchers studied how to provide user-adaptive advertisement. In [9], how to publish advertisements in a supermarket that can be adapted to the concerning information of a particular client from his own profile is presented. Then, specific advertising hints can be delivered as a navigation service to the client within the supermarket while he is shopping around.As demonstrated in [6], economic incentive is a very effective way for shaping consumer behavior. Yamabe et al. [6] studied various incentive mechanisms and how they alter the consumer behavior. They proposed four micropricing models to alter the behavior of consumers. In the micropricing models, different pricing systems are adopted for different services to be provided to a consumer. Similar to [6], Kanda et al. [10] studied the behavior of customers in particular their movements in a public area such as in a train station to identify the real customers. It uses a humanoid robot to identify the real customers based on the collected movement behavior information, for example, the movement speeds and paths of the real customers, in the monitored region. In [7], product involvement was applied for mobile advertising to study the effect of involvements on consumers’ purchase intention. It was shown that impulse buying tendency influences the degree that a customer may be engaged in a product purchase. You et al. [1] studied the relationship between shopping time and purchasing. It divides the time that a customer spends within a store to shopping time and entertainment time. Then, it proposed a phone-based system to sense physical shopping activities while tracking the shopping time of customers in a store.Similar to the previous work, for example, [1, 6, 10], in this paper, we explore the movements of customers to formulate personalized promotion strategies with the purpose to increase the incentives of customers for purchasing. However, unlike those mentioned above, we apply the latest localization method using WLAN to capture the movements of customers in a store to determine their interests in an item/items displaying in the store [4] and then formulate promotion strategies. Different from the work in [1], we combine NFC and WLAN in the personalized promotion system to increase the flow volume of customers into the stores. To the best of our knowledge, there is a lack of effective personalized promotion systems for retail sales. In addition, we combine the movement database with an enhanced R-tree index such that the data items maintained in the movement database can be retrieved efficiently and various spatial queries can be supported for enhancing the space management in a store. Although R-tree [11] has been shown to be effective for managing spatial objects and location information of moving objects, to the best of our knowledge, there is still lack of any research work on applying R-tree for tracking the movement behavior of mobile clients in business promotion and space management in retail stores.


### 2.2. Localization Using Wireless Communication

#### 2.2.1. Localization Using WLAN

The basic principle in localization is to use a set of sensors with fixed and known positions to collect radio signals from a mobile device carried by the mobile user [12–15]. With the obtained data, they perform location estimation such as using triangulation. Various estimation techniques have been proposed to improve the accuracy of the estimation such as the sequential monte carlo localization (MCL) method [16] and the sequential greedy optimization (SGO) method [17].According to the distance or a distance dependent parameter parameter between the sensors and the mobile device, localization techniques can be classified into range-based and range-free methods [18]. Although the range-free methods offer a straightforward and simple localization option for many wireless localization applications since they do not require any specific ranging devices, their accuracies are normally limited.Compared with the range-free methods, the range-based methods, in general, can achieve a higher accuracy for localization. They explore the measured values in wireless communication to estimate the location of a mobile user. Some of the commonly used physical measures are the time-of-arrival (TOA), time-difference-of-arrival (TDOA), angle-of-arrival (AOA), and received signal strength indicator (RSSI) [5, 16, 19, 20]. Amongst these measures, the RSSI-based localization techniques provide a class of low-cost and easy-implemented range-based localization schemes [13–15, 19]. Some popular techniques based on RSSI are the fingerprinting, aggregated signal layout, and center of gravity (CG) [4]. To further enhance the performance in using RSSI, the signal aggregated method was proposed in [21]. In [5], an efficient approach was proposed to reduce the manual calibration and to optimize the accuracy in indoor positioning using RSSI. In this paper, we also adopt RSSI together with the signal aggregated method as the basic measures for localization using WLAN to determine the movements of customers within a store.


#### 2.2.2. Localization Using NFC

Near field communication (NFC) [22–24] is a very short range of communication technology using radio frequency, that is, 13.56 MHz. When two NFC devices are brought within a close range, that is, less than 10 cm, they can determine each other automatically and establish a communication channel for data exchange. Basically, there are two types of NFC: active and passive. In passive NFC, a passive sensor/tag is activated when an active NFC device is within a close range of communication of the passive tag. Since we put the passive tag at a fixed location and it has a unique identifier, the location information of the passive tag and identifier can be transferred to the active NFC device. Similar to passive RFID, another benefit of a passive NFC is that the passive NFC tag can obtain power from the radio frequency generated from the active NFC device. Each active NFC device is self-powered and generates its own oscillating magnetic field for communication. In the proposed promotion system, we use passive NFC tags to issue some discount policies to attract customers to enter into the chain stores for promotion purpose.The emergency of NFC-enabled smartphones opens up a lot of new business opportunities to the smartphone operators [23, 24]. Nowadays, NFC can be used to replace smart cards for various identity checking purposes such as in taking attendances and even be used for e-payment to replace the Octopus system, the most popular e-payment system in Hong Kong. When the NFC works with other networks such as cellular networks and WLAN, its applications could be much wider since NFC and the networks supplement the limitations of each other. WLAN and cellular networks require a more complex system infrastructure and a higher security measure. On the other hand, although NFC has limited communication range, it has a simple “touch” interface to facilitate its operation. The close range of communication of NFC can also enhance the security of the communication and makes the transmission more difficult to be captured and attacked by malicious devices.


## 2.1. Location-Based Business Services

With the popularity of smartphones, business companies are developing various novel location-based services for catching new business opportunities. One of the popular location-based services is mobile advertisement [2, 8]. In [8], the iMAS system was proposed. It uses GPS to provide location-based intelligent advertising services such that different advertising information is provided to clients at different locations. Similarly, in [2], a location-based mobile advertisement publishing system for vendors was proposed. The system allows the vendors to edit advertisements and publish advertisements to customers through a wireless infrastructure such as 3G networks or WiMAX. In addition, the advertisement data desired by the customers can also be viewed through QR code readers.In addition to mobile advertisements, some researchers studied how to provide user-adaptive advertisement. In [9], how to publish advertisements in a supermarket that can be adapted to the concerning information of a particular client from his own profile is presented. Then, specific advertising hints can be delivered as a navigation service to the client within the supermarket while he is shopping around.As demonstrated in [6], economic incentive is a very effective way for shaping consumer behavior. Yamabe et al. [6] studied various incentive mechanisms and how they alter the consumer behavior. They proposed four micropricing models to alter the behavior of consumers. In the micropricing models, different pricing systems are adopted for different services to be provided to a consumer. Similar to [6], Kanda et al. [10] studied the behavior of customers in particular their movements in a public area such as in a train station to identify the real customers. It uses a humanoid robot to identify the real customers based on the collected movement behavior information, for example, the movement speeds and paths of the real customers, in the monitored region. In [7], product involvement was applied for mobile advertising to study the effect of involvements on consumers’ purchase intention. It was shown that impulse buying tendency influences the degree that a customer may be engaged in a product purchase. You et al. [1] studied the relationship between shopping time and purchasing. It divides the time that a customer spends within a store to shopping time and entertainment time. Then, it proposed a phone-based system to sense physical shopping activities while tracking the shopping time of customers in a store.Similar to the previous work, for example, [1, 6, 10], in this paper, we explore the movements of customers to formulate personalized promotion strategies with the purpose to increase the incentives of customers for purchasing. However, unlike those mentioned above, we apply the latest localization method using WLAN to capture the movements of customers in a store to determine their interests in an item/items displaying in the store [4] and then formulate promotion strategies. Different from the work in [1], we combine NFC and WLAN in the personalized promotion system to increase the flow volume of customers into the stores. To the best of our knowledge, there is a lack of effective personalized promotion systems for retail sales. In addition, we combine the movement database with an enhanced R-tree index such that the data items maintained in the movement database can be retrieved efficiently and various spatial queries can be supported for enhancing the space management in a store. Although R-tree [11] has been shown to be effective for managing spatial objects and location information of moving objects, to the best of our knowledge, there is still lack of any research work on applying R-tree for tracking the movement behavior of mobile clients in business promotion and space management in retail stores.


## 2.2. Localization Using Wireless Communication

### 2.2.1. Localization Using WLAN

The basic principle in localization is to use a set of sensors with fixed and known positions to collect radio signals from a mobile device carried by the mobile user [12–15]. With the obtained data, they perform location estimation such as using triangulation. Various estimation techniques have been proposed to improve the accuracy of the estimation such as the sequential monte carlo localization (MCL) method [16] and the sequential greedy optimization (SGO) method [17].According to the distance or a distance dependent parameter parameter between the sensors and the mobile device, localization techniques can be classified into range-based and range-free methods [18]. Although the range-free methods offer a straightforward and simple localization option for many wireless localization applications since they do not require any specific ranging devices, their accuracies are normally limited.Compared with the range-free methods, the range-based methods, in general, can achieve a higher accuracy for localization. They explore the measured values in wireless communication to estimate the location of a mobile user. Some of the commonly used physical measures are the time-of-arrival (TOA), time-difference-of-arrival (TDOA), angle-of-arrival (AOA), and received signal strength indicator (RSSI) [5, 16, 19, 20]. Amongst these measures, the RSSI-based localization techniques provide a class of low-cost and easy-implemented range-based localization schemes [13–15, 19]. Some popular techniques based on RSSI are the fingerprinting, aggregated signal layout, and center of gravity (CG) [4]. To further enhance the performance in using RSSI, the signal aggregated method was proposed in [21]. In [5], an efficient approach was proposed to reduce the manual calibration and to optimize the accuracy in indoor positioning using RSSI. In this paper, we also adopt RSSI together with the signal aggregated method as the basic measures for localization using WLAN to determine the movements of customers within a store.


### 2.2.2. Localization Using NFC

Near field communication (NFC) [22–24] is a very short range of communication technology using radio frequency, that is, 13.56 MHz. When two NFC devices are brought within a close range, that is, less than 10 cm, they can determine each other automatically and establish a communication channel for data exchange. Basically, there are two types of NFC: active and passive. In passive NFC, a passive sensor/tag is activated when an active NFC device is within a close range of communication of the passive tag. Since we put the passive tag at a fixed location and it has a unique identifier, the location information of the passive tag and identifier can be transferred to the active NFC device. Similar to passive RFID, another benefit of a passive NFC is that the passive NFC tag can obtain power from the radio frequency generated from the active NFC device. Each active NFC device is self-powered and generates its own oscillating magnetic field for communication. In the proposed promotion system, we use passive NFC tags to issue some discount policies to attract customers to enter into the chain stores for promotion purpose.The emergency of NFC-enabled smartphones opens up a lot of new business opportunities to the smartphone operators [23, 24]. Nowadays, NFC can be used to replace smart cards for various identity checking purposes such as in taking attendances and even be used for e-payment to replace the Octopus system, the most popular e-payment system in Hong Kong. When the NFC works with other networks such as cellular networks and WLAN, its applications could be much wider since NFC and the networks supplement the limitations of each other. WLAN and cellular networks require a more complex system infrastructure and a higher security measure. On the other hand, although NFC has limited communication range, it has a simple “touch” interface to facilitate its operation. The close range of communication of NFC can also enhance the security of the communication and makes the transmission more difficult to be captured and attacked by malicious devices.


## 2.2.1. Localization Using WLAN

The basic principle in localization is to use a set of sensors with fixed and known positions to collect radio signals from a mobile device carried by the mobile user [12–15]. With the obtained data, they perform location estimation such as using triangulation. Various estimation techniques have been proposed to improve the accuracy of the estimation such as the sequential monte carlo localization (MCL) method [16] and the sequential greedy optimization (SGO) method [17].According to the distance or a distance dependent parameter parameter between the sensors and the mobile device, localization techniques can be classified into range-based and range-free methods [18]. Although the range-free methods offer a straightforward and simple localization option for many wireless localization applications since they do not require any specific ranging devices, their accuracies are normally limited.Compared with the range-free methods, the range-based methods, in general, can achieve a higher accuracy for localization. They explore the measured values in wireless communication to estimate the location of a mobile user. Some of the commonly used physical measures are the time-of-arrival (TOA), time-difference-of-arrival (TDOA), angle-of-arrival (AOA), and received signal strength indicator (RSSI) [5, 16, 19, 20]. Amongst these measures, the RSSI-based localization techniques provide a class of low-cost and easy-implemented range-based localization schemes [13–15, 19]. Some popular techniques based on RSSI are the fingerprinting, aggregated signal layout, and center of gravity (CG) [4]. To further enhance the performance in using RSSI, the signal aggregated method was proposed in [21]. In [5], an efficient approach was proposed to reduce the manual calibration and to optimize the accuracy in indoor positioning using RSSI. In this paper, we also adopt RSSI together with the signal aggregated method as the basic measures for localization using WLAN to determine the movements of customers within a store.


## 2.2.2. Localization Using NFC

Near field communication (NFC) [22–24] is a very short range of communication technology using radio frequency, that is, 13.56 MHz. When two NFC devices are brought within a close range, that is, less than 10 cm, they can determine each other automatically and establish a communication channel for data exchange. Basically, there are two types of NFC: active and passive. In passive NFC, a passive sensor/tag is activated when an active NFC device is within a close range of communication of the passive tag. Since we put the passive tag at a fixed location and it has a unique identifier, the location information of the passive tag and identifier can be transferred to the active NFC device. Similar to passive RFID, another benefit of a passive NFC is that the passive NFC tag can obtain power from the radio frequency generated from the active NFC device. Each active NFC device is self-powered and generates its own oscillating magnetic field for communication. In the proposed promotion system, we use passive NFC tags to issue some discount policies to attract customers to enter into the chain stores for promotion purpose.The emergency of NFC-enabled smartphones opens up a lot of new business opportunities to the smartphone operators [23, 24]. Nowadays, NFC can be used to replace smart cards for various identity checking purposes such as in taking attendances and even be used for e-payment to replace the Octopus system, the most popular e-payment system in Hong Kong. When the NFC works with other networks such as cellular networks and WLAN, its applications could be much wider since NFC and the networks supplement the limitations of each other. WLAN and cellular networks require a more complex system infrastructure and a higher security measure. On the other hand, although NFC has limited communication range, it has a simple “touch” interface to facilitate its operation. The close range of communication of NFC can also enhance the security of the communication and makes the transmission more difficult to be captured and attacked by malicious devices.


## 3. Pervasive Promotion Model

In this section, we introduce apervasive promotion model for promotingselected items in retail sales to registered customers. The pervasive promotion model is for retail chain stores which have many stores distributed in a city such as the Park’N Shop Supermarket and the convenient store Mannings Company Limited in Hong Kong. The main entities in the system arecustomer,store,booth, anditem as shown in Figure 1. The model ispervasive in the sense that it integrates the promotion of items with the shopping movement of customers while they are shopping around in any one of the chain stores. In addition, the customers can also exchange promotion information with each other whenever they meet each other independent of their current locations or remotely through the internet.Figure 1
The ER model of the main entities.In retail sales, the first objective in promotion is to increase theflow volume of customers of the stores. Then, the second objective is to increase theincentives of the customers for purchasing. In the following sections, we will discuss how the proposed pervasive promotion model can achieve the two objectives effectively.As shown in Figure2, the pervasive promotion model consists of four main components:(i)
membership,(ii)
flow attraction,(iii)
movement tracking,(iv)
personalized promotion.Figure 2
The pervasive promotion model for promoting selected items in retail chain stores.


### 3.1. Membership

Membership is commonly adopted in retail stores to provide discount and rebate to registered customers for improving the relationships between customers and the stores. However, most of them arenot personalized to the customers such that the relationship is just defined between a group of customers and a store or a chain of stores; that is, the same promotion strategy is applied to the same group of registered customers as shown in Figure 3(b).Figure 3
Personalized promotion versus nonpersonalized promotion.
(a)
(b)Personalized relationships are not easy to be formulated as they require the identification of the items that the customers may be interested to purchase. A wrong guess could be annoying and generate negative impacts to the image of the stores and companies, for example, receiving a large number of uninterested promotion messages. In this proposed model, by exploring the movements of customers within the stores, we formulate the relationships between a customer and the items which may be interesting to the customer. Then, different promotion strategies can be applied to different customers based on the defined relationships specifically as shown in Figure 3(a). This not only can improve the relationships between the customers and the stores as the customers are treated specifically by the stores. This can also provide a higher flexibility in promoting the items; for example, different discount rates may be applied to different customers in promoting the same item.In addition to tracking the movements of customers within the stores, the purchase histories of the customers as well as their responses to the promotion messages are also maintained; that is, the promotion of an item is successful and the customer has taken the promotion and purchased the item. This information will also be considered in formulating the promotion strategies to improve the effectiveness of the promotion system.


### 3.2. Flow Attraction

The second component isflow attraction. It is how to increase the flow volume of customers of the stores. If more customers are walking around within a store, for either window shopping or real shopping, the sales volume of the store has a higher potential to be increased [1]. In the proposed pervasive promotion model, we make use of the close range communication of NFC to motivate the customers to visit the stores.Once a registered customer carrying an NFC-enabled smartphone, which is runningapps specially designed for the personalized promotion system, comes to a close range of a passive NFC tag in any one of the chain stores, the tag will be activated and its unique ID code and its location information will be transferred to theapps.In order to increase the incentive of a customer to go to check with the NFC tags installed in the stores, a simplediscount promotion strategy may be applied. For example, each checking with an NFC tag will give a bonus mark to the customer and a customer can accumulate up to a maximum mark in each day from the same store.To make the promotion scheme more attractive and to increase the number of customers to visit the stores, the accumulated bonus marks of a customer may betransferred to another customer if both of them have NFC-enabled smartphones and are the registered customers of the chain stores. In this way, they may be able to maximize the discount and purchase benefits that they can obtain according to the received promotion messages.


### 3.3. Movement Tracking

The third component of the pervasive promotion model is tracking themovements of customers within a store. This is a localization problem of the registered customers within a store. In our system, we adopt the WLAN for localization. A number of WLAN access points (APs) are installed at the ceiling of each store. They are used to determine which booth a customer is currently locating at. In a store, a set of nonoverlapping rectangular booths are conceptually defined as shown in Figure 4. The size of a booth may range from one to several square metres. Each booth is assigned a unique booth ID (BID) and a set of coordinates (e.g., x1, x2, x3, and x4) to represent the identity of the booth and its location in the store, respectively. The rectangular shape of a booth can facilitate the booth management using theR-tree index. This will be discussed in Section 4.3. Note that it is not necessary to have a WLAN access point for each booth for localization. The important issue in localization is to distinguish which booth a customer is currently locating at or he is locating in a nonbooth area. Within each booth, items are being displayed. It is assumed that the items displaying under a booth are of similar types, for example, watches or baby food. Some items are selected to be promotion items (IP) while the others are nonpromotion items (INP). IP are those items that are popular and promotion strategies have been defined for increasing their sales volumes.Figure 4
The booths in a store.In location tracking, it is not necessary to continuously monitor the location of a customer for every step. Otherwise, the localization cost in terms of processing cost and communication cost of the network could be expensive. Instead, we use anadaptive periodic scheme (to be discussed in next section) for checking the current location of a customer in a store.In localization, we determine the booth ID (BID) of the customer in the store. If the BID(t) of customer C at time t is different from the previous BID(t-s) and the total duration of the customer in a booth is larger than a predefined threshold Tupdate, a time-stamped record calledcustomer-item record will be generated for each promotion item, IP, in the booth. The generated customer-item records will be forwarded and inserted into themovement database which contains the information of the “customers’ interests” to the items centrally maintained for all the stores. Each customer-item record is an indicator to show that the customer may be interested in the item.


### 3.4. Personalized Promotion

The last component of the pervasive promotion model is thepersonalized promotion. Once the app running in the smartphone of a registered customer obtains the ID of an NFC tag, it will be activated and the personalized promotion component will be triggered. The interested items of the customer maintained in themovement database based on his previous visits to the stores will be searched using the customer ID obtained from his smartphone. If the store has the same items, promotion strategies will be formulated to determine how to promote the items such as the discount rates of the items to the customer. Then, time-stampedpromotion coupons will be forwarded and displayed in his smartphone through the installed mobileapps for the customer to consider. The time-stamp of the promotion coupon indicates the validity period of the coupon. It could be within the same day or week depending on the formulated promotion strategies. Therefore, by controlling the number of promotion items and the definitions of the conditions for formulating the promotion rules, the number of promotion messages can be controlled so that a customer will not be annoyed by a large number of uninterested promotion messages. Since this paper is concentrated on the business model and the design of the personalized promotion system, the discussion on the discount rules is out of the scope of this paper.It is expected that, through the pervasive promotion model, a mutual benefit can be achieved to both the stores and the customers; that is, the customers can purchase the items they find intersting using lower prices or with more benefits, for example, bonus items, while the sales volume of the stores can be increased. Furthermore, different promotion strategies can be applied to different customers according to their loyalties to the stores and their previous purchase histories (e.g., total sales purchased in a month). In addition, the personalized promotion can make the customers have a good feeling of being important as they are being treated specifically. Increasing the loyalty of customers to the stores may motivate further purchases from them.


## 3.1. Membership

Membership is commonly adopted in retail stores to provide discount and rebate to registered customers for improving the relationships between customers and the stores. However, most of them arenot personalized to the customers such that the relationship is just defined between a group of customers and a store or a chain of stores; that is, the same promotion strategy is applied to the same group of registered customers as shown in Figure 3(b).Figure 3
Personalized promotion versus nonpersonalized promotion.
(a)
(b)Personalized relationships are not easy to be formulated as they require the identification of the items that the customers may be interested to purchase. A wrong guess could be annoying and generate negative impacts to the image of the stores and companies, for example, receiving a large number of uninterested promotion messages. In this proposed model, by exploring the movements of customers within the stores, we formulate the relationships between a customer and the items which may be interesting to the customer. Then, different promotion strategies can be applied to different customers based on the defined relationships specifically as shown in Figure 3(a). This not only can improve the relationships between the customers and the stores as the customers are treated specifically by the stores. This can also provide a higher flexibility in promoting the items; for example, different discount rates may be applied to different customers in promoting the same item.In addition to tracking the movements of customers within the stores, the purchase histories of the customers as well as their responses to the promotion messages are also maintained; that is, the promotion of an item is successful and the customer has taken the promotion and purchased the item. This information will also be considered in formulating the promotion strategies to improve the effectiveness of the promotion system.


## 3.2. Flow Attraction

The second component isflow attraction. It is how to increase the flow volume of customers of the stores. If more customers are walking around within a store, for either window shopping or real shopping, the sales volume of the store has a higher potential to be increased [1]. In the proposed pervasive promotion model, we make use of the close range communication of NFC to motivate the customers to visit the stores.Once a registered customer carrying an NFC-enabled smartphone, which is runningapps specially designed for the personalized promotion system, comes to a close range of a passive NFC tag in any one of the chain stores, the tag will be activated and its unique ID code and its location information will be transferred to theapps.In order to increase the incentive of a customer to go to check with the NFC tags installed in the stores, a simplediscount promotion strategy may be applied. For example, each checking with an NFC tag will give a bonus mark to the customer and a customer can accumulate up to a maximum mark in each day from the same store.To make the promotion scheme more attractive and to increase the number of customers to visit the stores, the accumulated bonus marks of a customer may betransferred to another customer if both of them have NFC-enabled smartphones and are the registered customers of the chain stores. In this way, they may be able to maximize the discount and purchase benefits that they can obtain according to the received promotion messages.


## 3.3. Movement Tracking

The third component of the pervasive promotion model is tracking themovements of customers within a store. This is a localization problem of the registered customers within a store. In our system, we adopt the WLAN for localization. A number of WLAN access points (APs) are installed at the ceiling of each store. They are used to determine which booth a customer is currently locating at. In a store, a set of nonoverlapping rectangular booths are conceptually defined as shown in Figure 4. The size of a booth may range from one to several square metres. Each booth is assigned a unique booth ID (BID) and a set of coordinates (e.g., x1, x2, x3, and x4) to represent the identity of the booth and its location in the store, respectively. The rectangular shape of a booth can facilitate the booth management using theR-tree index. This will be discussed in Section 4.3. Note that it is not necessary to have a WLAN access point for each booth for localization. The important issue in localization is to distinguish which booth a customer is currently locating at or he is locating in a nonbooth area. Within each booth, items are being displayed. It is assumed that the items displaying under a booth are of similar types, for example, watches or baby food. Some items are selected to be promotion items (IP) while the others are nonpromotion items (INP). IP are those items that are popular and promotion strategies have been defined for increasing their sales volumes.Figure 4
The booths in a store.In location tracking, it is not necessary to continuously monitor the location of a customer for every step. Otherwise, the localization cost in terms of processing cost and communication cost of the network could be expensive. Instead, we use anadaptive periodic scheme (to be discussed in next section) for checking the current location of a customer in a store.In localization, we determine the booth ID (BID) of the customer in the store. If the BID(t) of customer C at time t is different from the previous BID(t-s) and the total duration of the customer in a booth is larger than a predefined threshold Tupdate, a time-stamped record calledcustomer-item record will be generated for each promotion item, IP, in the booth. The generated customer-item records will be forwarded and inserted into themovement database which contains the information of the “customers’ interests” to the items centrally maintained for all the stores. Each customer-item record is an indicator to show that the customer may be interested in the item.


## 3.4. Personalized Promotion

The last component of the pervasive promotion model is thepersonalized promotion. Once the app running in the smartphone of a registered customer obtains the ID of an NFC tag, it will be activated and the personalized promotion component will be triggered. The interested items of the customer maintained in themovement database based on his previous visits to the stores will be searched using the customer ID obtained from his smartphone. If the store has the same items, promotion strategies will be formulated to determine how to promote the items such as the discount rates of the items to the customer. Then, time-stampedpromotion coupons will be forwarded and displayed in his smartphone through the installed mobileapps for the customer to consider. The time-stamp of the promotion coupon indicates the validity period of the coupon. It could be within the same day or week depending on the formulated promotion strategies. Therefore, by controlling the number of promotion items and the definitions of the conditions for formulating the promotion rules, the number of promotion messages can be controlled so that a customer will not be annoyed by a large number of uninterested promotion messages. Since this paper is concentrated on the business model and the design of the personalized promotion system, the discussion on the discount rules is out of the scope of this paper.It is expected that, through the pervasive promotion model, a mutual benefit can be achieved to both the stores and the customers; that is, the customers can purchase the items they find intersting using lower prices or with more benefits, for example, bonus items, while the sales volume of the stores can be increased. Furthermore, different promotion strategies can be applied to different customers according to their loyalties to the stores and their previous purchase histories (e.g., total sales purchased in a month). In addition, the personalized promotion can make the customers have a good feeling of being important as they are being treated specifically. Increasing the loyalty of customers to the stores may motivate further purchases from them.


## 4. System Architecture and Technical Issues

In this section, according to the pervasive promotion model introduced in Section3, we present the design of thepersonalized promotion system.


### 4.1. System Architecture and Operations

Figure5 shows the architecture of the personalized promotion system. It consists of two subsystems: frontend and backend. Table 1 summarizes the set of databases maintained in the frontend and backend systems.Table 1
Details of the databases.
Database
Description of the database
Frontend
Store database
Store record contains the information about the stores such as store ID, booths' location, booth ID, and sale items ID.
Backend
Item database
Item records contain information about the items such as the location of an item in a booth in each store and its price.
Movement database
Booth records contain the information of the booth IDs and the associated list of customer-item records.
Customer database
Customer records contain the information of registered customers such as customer ID, the name, and telephone number.
Promotion database
Promotion records contain the information about the promotion rules for each promotion item.Figure 5
System architecture of the personalized promotion system.


#### 4.1.1. Frontend System

At the frontend system, each store has a passive NFC tag with a fixed location, a set of NFC-enabled smartphones carrying by the registered customers visiting the stores,apps for the personalized promotion system running on the customers’ smartphones, a set of fixed WLAN access points, and a local location server which maintains thestore database. The store database maintains information about the store such as store ID, store address, booth IDs, booth locations, and sales items in the store.The local location server connects to a set of WLAN access points (APs) installed at the ceiling of the store. Theapps running in an NFC-enabled smartphone communicate with the NFC tag when they are within a close range, that is, next to each other. Then, theapps get the tag ID and communicate with the WLAN access points installed in the store to establish a connection with one of them to acquire an IP address for the smartphone. Note that although a wireless connection can be established between a smartphone and the WLAN once the smartphone is within the store, in our system the connection is established “only” after a customer has checked with an NFC tag. The reason is that these are registered customers. Once a customer uses his smartphone to check with the NFC tag, it is an “agreement” between store and the customer that he is allowed to be connected and monitored in the store.The WLAN access points measure thereceived signal strength indicator (RSSI) from the smartphone of the customer periodically and pass the measured signal strengths to the local location server. The server then performs location estimation to determine the booth that the customer is currently staying at and to determine the period of time that the customer has been staying for in the booth by comparing with the previous location record of the customer. The details of the localization estimation method will be discussed in Section 4.2. Since the number of registered customers in a store could be large, we adopt an adaptive periodic scheme for setting the period for checking the locations of a customer such that the sampling period Pi,j for customer i in booth j is adaptive:(1)Pi,j=max⁡x+n∗m,Tcheck,where n is the number of consecutive times that the customer remains in the same booth while x and m are predefined tuning parameters to control the estimation period. Tcheck is the maximum period for localization with Tcheck smaller than Tupdate which is the time threshold for generating a location update. Larger values for m and x increase the estimation period and reduce the estimation cost at the local location server.If there is a change in location, that is, the latestBID being different from the previous one, and the period of time of the customer staying in the booth, Tperiod, is larger than Tupdate, acustomer-item record will be generated for eachpromotion item, Ip, displaying in the booth. Please be reminded that it is assumed that the items in a booth are assumed to be the same types. Therefore, the customer may be interested in all of them. Each record consists of the customer ID, booth ID, item ID, the date, the start time, and the period of time that the customer has stayed in the booth.


#### 4.1.2. Backend System

The backend system consists of two servers: the location database server and the promotion server. The backend system connects to the frontend system through a high-speed wired network. The location database server maintains the movement database for all the stores. It is indexed by an enhanced R-tree [11]. Each data item, called abooth record, maintains the information for a booth such as its identity and physical coordinates (e.g., x1, x2, y1, and y2) in the store. The details of the enhanced R-tree will be discussed in Section 4.3.Under each booth record, there is a list of items displaying in the booth sorted according to their IDs. In the movement database, an item in a booth may be pointed by a customer ID if the customer is interested at the item defined according to a customer-item record as shown in Figure6. In addition to the R-tree index, a key is maintained to sort the list of customer IDs. Note that a customer ID may point to a list of items as he may be interested in several items distributed in different booths. If there is a move of an item from a booth to another booth, the movement database and the item database will be updated accordingly. The item database contains the details of the items and the distribution of items in each booth and each store.Figure 6
Enhanced R-tree for a store in Figure4.Since the item lists pointed by a customer ID are linked together, we may use the customer ID to obtain the set of items the customer is interested in when he accumulates marks in a store using his smartphone. After identifying his items of interest (obtaining the list of items pointed by the customer ID), the promotion server searches thepromotion database which defines the promotion rules for each promotion item. Following the rules, the promotion server formulates the promotion strategies for the selected items and then promotion coupons will be generated and displayed through theapps in the customer’s smartphone.


### 4.2. Localization Using WLAN

From our previous studies on localization using WLAN, the fingerprinting approach is good and accurate in providing room-level or, in this case, booth-level localization services with an average accuracy of about 1.6 m [25]. However, the disadvantage is the difficulties in setup and heavy maintenance cost of the fingerprint database. Fortunately, this cost can be reduced by the aggregated signal layout technique where the accuracy is roughly maintained [21].Figure7 shows an example floor plan of a store. It is assumed that it is rectangular or consists of several connected rectangles. Access points are installed strategically within each rectangle and most of the time at the corner of each rectangle. These access points form a WLAN to support the communication with the smartphones as well as for location estimation of the customers within the booths.Figure 7
The floor plan of a store.Since we adopt using the aggregated signal layout approach [21] for location estimation, we have to find out the signal-distance relationship for the target operation environment. For this real-time calibration, access points act as sensors to capture the communication signals between the access points and the WiFi-enabled smartphone as well as among all the access points themselves. As these access points are installed at strategic points within the operation environment in such a way that the access points receive signals among each other from different distances, a real-time signal to distance relationship can then be obtained.With the average received signal strength of each communication between a pair of access points being detected, a (signal, distance) data point for each pair of access points can be obtained. Then we can use a linear equation y=a+bx that best fits the data points, with the y-offsets defined as(2)R2=∑‍yi-fa,b2,where yi is the distance in a (signal, distance) data point and f(a,b)=a+bx. a and b with minimum R2 are obtained by the linear least squares fitting. Then, the solutions to b and a are(3)b=ssxyssxx,a=y¯+bx¯,where(4)ssxx=∑‍xi-x¯2,ssxy=∑‍xi-x¯yi-y¯.With a real-time derivation of the signal-distance relationship, a signal map can be obtained for each access point. When a WiFi-enabled smartphone enters the operation environment, the WiFi signals can be picked up by the nearby access points and vice versa. If the area is marked by a grid of a certain size, each access point that detects the user’s WiFi signal can calculate the possible positions within the grid where the smartphone is currently locating. Then the aggregated signal layout method can perform location estimation by overlapping or stacking up the signal layouts of these access points. Considering a single access point, given the received signal strength from a WiFi-enabled smartphone, the distance between the phone and the access point could be obtained from the sensor’s signal layout; the interdistance draws the possible locations of the smartphone in a circular perimeter. By aggregating the signal layouts of all the access points, essentially locating the common points of the perimeters, the estimated location of the smartphone can be obtained.Since it is common that the received signal strength does not conform to an access point signal layout, we allow some errors to the distance estimation. For instance, we allow a search window of ±2 dbm to our aggregated signal layout method, such that when an access point receives signal strength of −68 dbm, the algorithm searches the sensor’s signal layout for position marker distances within the grid that falls between signal strengths −66 and −70 dbm. This search window we called signal spread is used to ensure more overlaps between layers of the signal layouts of the access points. With such a localization scheme, experimental results have shown that we can have a booth-level location estimation ranging from 0.9 m to 1.4 m. Please refer to [21] for the details of the aggregated signal layout method for localization within a wireless network. Since the accuracy may have error in estimation, the problem will be more serious if the booth size is small. In order to improve the location estimation accuracy, we use an adaptive rate measure (ARM) scheme to estimate the current booth ID of a customer. UnderARM, if the dimension of a booth is smaller (e.g., the length of edges of a rectangle), we repeat with more number of estimations to obtain the average value in localization for a customer in order to improve the accuracy in estimating the booth that the customer is currently locating.One of the problems in determining the booth that a customer is currently locating using the above location estimation method is thebing-bong effect. This is a customer locating at the connection line of two booths and moving back and forth between them. For this case, similar toARM, we increase the number of estimations as the problem may be due to estimation error and then take the average as a damping factor to determine the booth that the customer is currently locating. If the customer is always located between the two booths, that is, the average location being close by a threshold distance to both booths, two sets of customer-item records will be generated.


### 4.3. The Enhanced R-Tree Index

The R-tree index was proposed for indexing spatial data [11]. In an R-tree index, each node, except the root node, has M maximum number of entries and m minimum number of entries with m≤M/2. The root node has at least two entries. All the leaf nodes are at the same level; that is, it is a balanced tree. Each node in the R-tree contains a set of entries of the form (ptr, rect), where, for leaf node,ptr is a pointer to a record maintained in the database andrect is theminimum bounding rectangle (MBR) of the data item as shown in Figure 6. The MBR is used to represent the physical location and the size of a booth. For inner node,ptr is the pointer to a child node at the next lower level of the tree andrect is the MBR that bounds all the MBRs of the child node under it.An enhanced R-tree is proposed to index the booth records of the stores. They are maintained in the movement database. The enhanced R-tree can facilitate the management of the items and space utilization of the booths by supporting various types of spatial queries. As shown in Figure6, the index for the movement database consists of two parts. At the upper level, an R-tree is used to index the spaces covered by each booth in the stores. For example, the R-tree with fanout 3 in Figure 6 indexes the stores in Figure 4. The inner nodes cover the areas indexed by the booths pointed by their leaf nodes. Each leaf node points to the items under the booth. Under each item, if it is a promotion item, a list of customer-item records (called item list) is maintained according to the start time (e.g., time when the customer starts to stay in the booth) of the records. In addition, a set of array lists, C1,Ci,…,Cm (called customer list) sorted according to customer ID, is maintained for searching the items that are of interest to customer i according to the received customer-item records. Since the number of customers could be large, a hash table is used to search the customer list to obtain the list of items that are of interest to the customer. A newly arrived customer-item record is inserted into customer ID list according to the customer ID and its duration. In addition, it is inserted into the item list according to their start time and item ID. Since the customer-item records under each item list are time-stamped according to the start time of the records, old customer-item records may be removed periodically by searching the item lists.


## 4.1. System Architecture and Operations

Figure5 shows the architecture of the personalized promotion system. It consists of two subsystems: frontend and backend. Table 1 summarizes the set of databases maintained in the frontend and backend systems.Table 1
Details of the databases.
Database
Description of the database
Frontend
Store database
Store record contains the information about the stores such as store ID, booths' location, booth ID, and sale items ID.
Backend
Item database
Item records contain information about the items such as the location of an item in a booth in each store and its price.
Movement database
Booth records contain the information of the booth IDs and the associated list of customer-item records.
Customer database
Customer records contain the information of registered customers such as customer ID, the name, and telephone number.
Promotion database
Promotion records contain the information about the promotion rules for each promotion item.Figure 5
System architecture of the personalized promotion system.


### 4.1.1. Frontend System

At the frontend system, each store has a passive NFC tag with a fixed location, a set of NFC-enabled smartphones carrying by the registered customers visiting the stores,apps for the personalized promotion system running on the customers’ smartphones, a set of fixed WLAN access points, and a local location server which maintains thestore database. The store database maintains information about the store such as store ID, store address, booth IDs, booth locations, and sales items in the store.The local location server connects to a set of WLAN access points (APs) installed at the ceiling of the store. Theapps running in an NFC-enabled smartphone communicate with the NFC tag when they are within a close range, that is, next to each other. Then, theapps get the tag ID and communicate with the WLAN access points installed in the store to establish a connection with one of them to acquire an IP address for the smartphone. Note that although a wireless connection can be established between a smartphone and the WLAN once the smartphone is within the store, in our system the connection is established “only” after a customer has checked with an NFC tag. The reason is that these are registered customers. Once a customer uses his smartphone to check with the NFC tag, it is an “agreement” between store and the customer that he is allowed to be connected and monitored in the store.The WLAN access points measure thereceived signal strength indicator (RSSI) from the smartphone of the customer periodically and pass the measured signal strengths to the local location server. The server then performs location estimation to determine the booth that the customer is currently staying at and to determine the period of time that the customer has been staying for in the booth by comparing with the previous location record of the customer. The details of the localization estimation method will be discussed in Section 4.2. Since the number of registered customers in a store could be large, we adopt an adaptive periodic scheme for setting the period for checking the locations of a customer such that the sampling period Pi,j for customer i in booth j is adaptive:(1)Pi,j=max⁡x+n∗m,Tcheck,where n is the number of consecutive times that the customer remains in the same booth while x and m are predefined tuning parameters to control the estimation period. Tcheck is the maximum period for localization with Tcheck smaller than Tupdate which is the time threshold for generating a location update. Larger values for m and x increase the estimation period and reduce the estimation cost at the local location server.If there is a change in location, that is, the latestBID being different from the previous one, and the period of time of the customer staying in the booth, Tperiod, is larger than Tupdate, acustomer-item record will be generated for eachpromotion item, Ip, displaying in the booth. Please be reminded that it is assumed that the items in a booth are assumed to be the same types. Therefore, the customer may be interested in all of them. Each record consists of the customer ID, booth ID, item ID, the date, the start time, and the period of time that the customer has stayed in the booth.


### 4.1.2. Backend System

The backend system consists of two servers: the location database server and the promotion server. The backend system connects to the frontend system through a high-speed wired network. The location database server maintains the movement database for all the stores. It is indexed by an enhanced R-tree [11]. Each data item, called abooth record, maintains the information for a booth such as its identity and physical coordinates (e.g., x1, x2, y1, and y2) in the store. The details of the enhanced R-tree will be discussed in Section 4.3.Under each booth record, there is a list of items displaying in the booth sorted according to their IDs. In the movement database, an item in a booth may be pointed by a customer ID if the customer is interested at the item defined according to a customer-item record as shown in Figure6. In addition to the R-tree index, a key is maintained to sort the list of customer IDs. Note that a customer ID may point to a list of items as he may be interested in several items distributed in different booths. If there is a move of an item from a booth to another booth, the movement database and the item database will be updated accordingly. The item database contains the details of the items and the distribution of items in each booth and each store.Figure 6
Enhanced R-tree for a store in Figure4.Since the item lists pointed by a customer ID are linked together, we may use the customer ID to obtain the set of items the customer is interested in when he accumulates marks in a store using his smartphone. After identifying his items of interest (obtaining the list of items pointed by the customer ID), the promotion server searches thepromotion database which defines the promotion rules for each promotion item. Following the rules, the promotion server formulates the promotion strategies for the selected items and then promotion coupons will be generated and displayed through theapps in the customer’s smartphone.


## 4.1.1. Frontend System

At the frontend system, each store has a passive NFC tag with a fixed location, a set of NFC-enabled smartphones carrying by the registered customers visiting the stores,apps for the personalized promotion system running on the customers’ smartphones, a set of fixed WLAN access points, and a local location server which maintains thestore database. The store database maintains information about the store such as store ID, store address, booth IDs, booth locations, and sales items in the store.The local location server connects to a set of WLAN access points (APs) installed at the ceiling of the store. Theapps running in an NFC-enabled smartphone communicate with the NFC tag when they are within a close range, that is, next to each other. Then, theapps get the tag ID and communicate with the WLAN access points installed in the store to establish a connection with one of them to acquire an IP address for the smartphone. Note that although a wireless connection can be established between a smartphone and the WLAN once the smartphone is within the store, in our system the connection is established “only” after a customer has checked with an NFC tag. The reason is that these are registered customers. Once a customer uses his smartphone to check with the NFC tag, it is an “agreement” between store and the customer that he is allowed to be connected and monitored in the store.The WLAN access points measure thereceived signal strength indicator (RSSI) from the smartphone of the customer periodically and pass the measured signal strengths to the local location server. The server then performs location estimation to determine the booth that the customer is currently staying at and to determine the period of time that the customer has been staying for in the booth by comparing with the previous location record of the customer. The details of the localization estimation method will be discussed in Section 4.2. Since the number of registered customers in a store could be large, we adopt an adaptive periodic scheme for setting the period for checking the locations of a customer such that the sampling period Pi,j for customer i in booth j is adaptive:(1)Pi,j=max⁡x+n∗m,Tcheck,where n is the number of consecutive times that the customer remains in the same booth while x and m are predefined tuning parameters to control the estimation period. Tcheck is the maximum period for localization with Tcheck smaller than Tupdate which is the time threshold for generating a location update. Larger values for m and x increase the estimation period and reduce the estimation cost at the local location server.If there is a change in location, that is, the latestBID being different from the previous one, and the period of time of the customer staying in the booth, Tperiod, is larger than Tupdate, acustomer-item record will be generated for eachpromotion item, Ip, displaying in the booth. Please be reminded that it is assumed that the items in a booth are assumed to be the same types. Therefore, the customer may be interested in all of them. Each record consists of the customer ID, booth ID, item ID, the date, the start time, and the period of time that the customer has stayed in the booth.


## 4.1.2. Backend System

The backend system consists of two servers: the location database server and the promotion server. The backend system connects to the frontend system through a high-speed wired network. The location database server maintains the movement database for all the stores. It is indexed by an enhanced R-tree [11]. Each data item, called abooth record, maintains the information for a booth such as its identity and physical coordinates (e.g., x1, x2, y1, and y2) in the store. The details of the enhanced R-tree will be discussed in Section 4.3.Under each booth record, there is a list of items displaying in the booth sorted according to their IDs. In the movement database, an item in a booth may be pointed by a customer ID if the customer is interested at the item defined according to a customer-item record as shown in Figure6. In addition to the R-tree index, a key is maintained to sort the list of customer IDs. Note that a customer ID may point to a list of items as he may be interested in several items distributed in different booths. If there is a move of an item from a booth to another booth, the movement database and the item database will be updated accordingly. The item database contains the details of the items and the distribution of items in each booth and each store.Figure 6
Enhanced R-tree for a store in Figure4.Since the item lists pointed by a customer ID are linked together, we may use the customer ID to obtain the set of items the customer is interested in when he accumulates marks in a store using his smartphone. After identifying his items of interest (obtaining the list of items pointed by the customer ID), the promotion server searches thepromotion database which defines the promotion rules for each promotion item. Following the rules, the promotion server formulates the promotion strategies for the selected items and then promotion coupons will be generated and displayed through theapps in the customer’s smartphone.


## 4.2. Localization Using WLAN

From our previous studies on localization using WLAN, the fingerprinting approach is good and accurate in providing room-level or, in this case, booth-level localization services with an average accuracy of about 1.6 m [25]. However, the disadvantage is the difficulties in setup and heavy maintenance cost of the fingerprint database. Fortunately, this cost can be reduced by the aggregated signal layout technique where the accuracy is roughly maintained [21].Figure7 shows an example floor plan of a store. It is assumed that it is rectangular or consists of several connected rectangles. Access points are installed strategically within each rectangle and most of the time at the corner of each rectangle. These access points form a WLAN to support the communication with the smartphones as well as for location estimation of the customers within the booths.Figure 7
The floor plan of a store.Since we adopt using the aggregated signal layout approach [21] for location estimation, we have to find out the signal-distance relationship for the target operation environment. For this real-time calibration, access points act as sensors to capture the communication signals between the access points and the WiFi-enabled smartphone as well as among all the access points themselves. As these access points are installed at strategic points within the operation environment in such a way that the access points receive signals among each other from different distances, a real-time signal to distance relationship can then be obtained.With the average received signal strength of each communication between a pair of access points being detected, a (signal, distance) data point for each pair of access points can be obtained. Then we can use a linear equation y=a+bx that best fits the data points, with the y-offsets defined as(2)R2=∑‍yi-fa,b2,where yi is the distance in a (signal, distance) data point and f(a,b)=a+bx. a and b with minimum R2 are obtained by the linear least squares fitting. Then, the solutions to b and a are(3)b=ssxyssxx,a=y¯+bx¯,where(4)ssxx=∑‍xi-x¯2,ssxy=∑‍xi-x¯yi-y¯.With a real-time derivation of the signal-distance relationship, a signal map can be obtained for each access point. When a WiFi-enabled smartphone enters the operation environment, the WiFi signals can be picked up by the nearby access points and vice versa. If the area is marked by a grid of a certain size, each access point that detects the user’s WiFi signal can calculate the possible positions within the grid where the smartphone is currently locating. Then the aggregated signal layout method can perform location estimation by overlapping or stacking up the signal layouts of these access points. Considering a single access point, given the received signal strength from a WiFi-enabled smartphone, the distance between the phone and the access point could be obtained from the sensor’s signal layout; the interdistance draws the possible locations of the smartphone in a circular perimeter. By aggregating the signal layouts of all the access points, essentially locating the common points of the perimeters, the estimated location of the smartphone can be obtained.Since it is common that the received signal strength does not conform to an access point signal layout, we allow some errors to the distance estimation. For instance, we allow a search window of ±2 dbm to our aggregated signal layout method, such that when an access point receives signal strength of −68 dbm, the algorithm searches the sensor’s signal layout for position marker distances within the grid that falls between signal strengths −66 and −70 dbm. This search window we called signal spread is used to ensure more overlaps between layers of the signal layouts of the access points. With such a localization scheme, experimental results have shown that we can have a booth-level location estimation ranging from 0.9 m to 1.4 m. Please refer to [21] for the details of the aggregated signal layout method for localization within a wireless network. Since the accuracy may have error in estimation, the problem will be more serious if the booth size is small. In order to improve the location estimation accuracy, we use an adaptive rate measure (ARM) scheme to estimate the current booth ID of a customer. UnderARM, if the dimension of a booth is smaller (e.g., the length of edges of a rectangle), we repeat with more number of estimations to obtain the average value in localization for a customer in order to improve the accuracy in estimating the booth that the customer is currently locating.One of the problems in determining the booth that a customer is currently locating using the above location estimation method is thebing-bong effect. This is a customer locating at the connection line of two booths and moving back and forth between them. For this case, similar toARM, we increase the number of estimations as the problem may be due to estimation error and then take the average as a damping factor to determine the booth that the customer is currently locating. If the customer is always located between the two booths, that is, the average location being close by a threshold distance to both booths, two sets of customer-item records will be generated.


## 4.3. The Enhanced R-Tree Index

The R-tree index was proposed for indexing spatial data [11]. In an R-tree index, each node, except the root node, has M maximum number of entries and m minimum number of entries with m≤M/2. The root node has at least two entries. All the leaf nodes are at the same level; that is, it is a balanced tree. Each node in the R-tree contains a set of entries of the form (ptr, rect), where, for leaf node,ptr is a pointer to a record maintained in the database andrect is theminimum bounding rectangle (MBR) of the data item as shown in Figure 6. The MBR is used to represent the physical location and the size of a booth. For inner node,ptr is the pointer to a child node at the next lower level of the tree andrect is the MBR that bounds all the MBRs of the child node under it.An enhanced R-tree is proposed to index the booth records of the stores. They are maintained in the movement database. The enhanced R-tree can facilitate the management of the items and space utilization of the booths by supporting various types of spatial queries. As shown in Figure6, the index for the movement database consists of two parts. At the upper level, an R-tree is used to index the spaces covered by each booth in the stores. For example, the R-tree with fanout 3 in Figure 6 indexes the stores in Figure 4. The inner nodes cover the areas indexed by the booths pointed by their leaf nodes. Each leaf node points to the items under the booth. Under each item, if it is a promotion item, a list of customer-item records (called item list) is maintained according to the start time (e.g., time when the customer starts to stay in the booth) of the records. In addition, a set of array lists, C1,Ci,…,Cm (called customer list) sorted according to customer ID, is maintained for searching the items that are of interest to customer i according to the received customer-item records. Since the number of customers could be large, a hash table is used to search the customer list to obtain the list of items that are of interest to the customer. A newly arrived customer-item record is inserted into customer ID list according to the customer ID and its duration. In addition, it is inserted into the item list according to their start time and item ID. Since the customer-item records under each item list are time-stamped according to the start time of the records, old customer-item records may be removed periodically by searching the item lists.


## 5. Illustrative Example

In this section, we give an illustrative example to show how the personalized promotion system retrieves the items that a customer may be interested in and how the system can help to increase the sales volume of the retail chain stores. Table2 presents the promotion rule of some items. For example, if a customer has accumulated 15 marks, he can get 10% discount for item 1 in booth B2.Table 2
Example promotion rules for the sales items in booths B1 and B2 of Figure4.
Booths
Items
Marks
5
15
30
45
B1
1
0.05
0.1
0.12
0.2
2
0.05
0.1
0.15
0.2
3
0.05
0.05
0.1
0.15
B2
1
0.05
0.1
0.1
0.15
2
0.05
0.1
0.15
0.15
3
0.05
0.1
0.1
0.15
4
0.05
0.1
0.15
0.20Once a registered customer enters a store for accumulating mark using his NFC-enabled smartphone, his smartphone will acquire an IP address from the WLAN installed in the store. Then, the location database server will retrieve the customer’s customer-item records by invoking RetrieveCustRecord. If the corresponding sales items in the promotion database have discount rules defined at that time, the corresponding promotion information will be transferred to the customer by invoking IssueInfoToCustomer. At the same time, his identity and movement will be monitored periodically for further customer-item records generation. Meanwhile, if a customer does not know the location of a particular sales item that he wants to check with, he can submit a query RetrieveItem to obtain the location information from theItem database.The generated customer-item records maintained by the local location server will be forwarded to the location database server by AddCustRecord periodically. After inserting all the customer-item records, the location database server will exploit the received customer-item records. If a sales item appears in many customer-item records, the SetPromotion will be invoked to set the discount rate for that item according to thediscount rule defined by the chain stores. Meanwhile, the chain stores can retrieve the booth that contains the most booth records by invoking GetHottestBooth to identify which items are most popular to the customers. Other spatial queries may also be submitted for how to place the items in the booths so as to attract the customers’ attention. Table 3 shows some example queries of the promotion systems.Table 3
Example queries in the personalized promoted system.
Queries
Descriptions
SetPromotion(item,marks,discnt)
Set the discount rate asdiscnt for item item with the accumulated marks.
AddCustRecord(UID,BID)
Add the customer-item record with the customer IDUID to the booth record with BID to the movement database.
RetrieveCustRecord(UID,n)
Retrieve the topn items of the customer-item records that the customer UID is interested from the movement database.
IssueInfoToCustomer(UID,item)
Issue discount information of data itemitem to the customer with identity number UID.
RetrieveItem(item)
Retrieve the location of the given itemitem.
GetHottestBooth(date,BID)
Get the booth ID with the maximum number of customer-item records on a particular daydate.
GetColdestBooth(date,BID)
Get the booth ID with the minimum number of customer-item records on a particular daydate.
GetRecords(area,Ss,Se)
Get the number of customer-item records in the given areaarea for a given time period [Ss,Se].
GetHighTimeofBooth(BID,hour,record)
Given a booth ID, get the largest total stay period of the customer-item records for each hour.


## 6. Experimental Results

In this section, we report the experimental results of our study on theeffectiveness of the adopted localization scheme in identifying the booth in which the user device (a WiFi-enabled smartphone) is locating. We constructed and conducted experiments in the network labs FSC301C and FSC301D at Hong Kong Baptist University (HKBU). The two labs are rectangular in shape and adjacent to each other.


### 6.1. Experimental Setup

Figure8 shows the floor plan and the layout of the access points in the two labs FSC801C and FSC801D. All the access points were mounted at the ceiling forming a WLAN as well as a sensing network. The access points were programmable routers, Linksys WRT54G, which were burned with an open-source custom-made firmware, acting as the WiFi sensors to obtain information of the data packets transmitted within the WLAN. All the access points continuously listen to the packets sent and received by the user device and also among the access points themselves. Packet information such as the service set identifier (SSID), extended service set identifier (ESSID), received signal strength indicator (RSSI), noise level, traffic rate, and traffic frequency was measured by a custom-made wireless data acquisition application written for the Linksys WRT54G WLAN router. For transmission efficiency and the reduction of data traffic, this useful information was selected (filter), grouped, time-stamped, and sent via TCP sockets through the router to be stored into the database maintained in the location database server. Then, the location estimation process would perform the estimation to find out which booth the user was currently locating at.Figure 8
The locations of the access points in the test site.As shown in Figure8, the access points in FSC801C were placed at the four corners first and the remaining five access points were called signal calibrators. Each signal calibrator was placed at a position such that the distances between it and the access points at each corner were different. Similarly, in FSC801D, two access points were placed at the far end corners from FSC801C. Furthermore, as shown in Figure 9, we divided FSC801C into 42 marker positions (each with a marker number) with horizontal and vertical dimensions of 1.9 m and 1.4 m, respectively. They were the basic unit for location estimation.Figure 9
The floor plan and the layout of the access points in the test site (FSC801C).


### 6.2. Experimental Results and Discussions

In the first set of experiments, we studied the estimation accuracy of the adopted localization scheme when the size of test site was varied. We placed the user device at different arbitrary marker positions (e.g., marker numbers of 9, 13, 23, and 25) in lab FSC801C and turned off all the calibrators except one of them. As shown in Table4, the estimated accuracy of correctly identifying the marker number where the user device was locating was in a range of 0.584 to 0.832. It is interesting to see that the estimation accuracy is not significantly affected by the size of the test site and the number of access points used for localization. The average accuracies of using FSC801C and both FSC801C and FSC801D are similar, for example, 0.693 and 0.702, respectively. Therefore, to simplify the experimental setup, in the remaining experiments, we adopted the settings in lab FSC801C for testing and turned off all the access points in lab FSC801D.Table 4
Probabilities of the user location in a specific marker position estimated with different test sites.
Marker position
Test site
FSC801C
FSC801C + FSC801D
9
0.832
0.766
13
0.652
0.584
23
0.646
0.764
25
0.64
0.694
Average
0.692
0.702In the second set of experiments, different numbers of access points (e.g., 3, 5, 7, and 9) were used. The access points were first placed at the corners and the remaining access points were calibrators. The results, as shown in Table5, indicate that increasing the number of access points does not have serious impact on the estimation accuracy. Using more access points (or calibrators) does not always give better estimation accuracy. Using four access points at the corners and one signal calibrator gives an estimation accuracy similar to the performance of different numbers of access points.Table 5
Probabilities of the user location in a specific marker position estimated with different number of APs.
Marker position
Number of APs
3
5
7
9
9
0.658
0.815
0.628
0.641
13
0.591
0.575
0.575
0.583
23
0.741
0.84
0.901
0.783
25
0.725
0.445
0.442
0.527
Average
0.678
0.668
0.636
0.6335In the third set of experiments, we looked at the size of a booth on the effectiveness of the adopted localization scheme in localization, that is, the effectiveness to identify the current booth ID when the booth size was varied. Following the settings in the second set of experiments, we used five access points with one of them as the calibrator in FSC801C. In this set of experiments, we assumed that the booths were squares with equal size and their dimension was described by the radius of the circle that could include the square. Furthermore, we assumed that the user was at the center of the booth (center of the circle). Then we measured the probability that the user was estimated to be in that booth when the booth size was varied. Since we took signal strength data samples for location estimation, the more the samples, the better the accuracy (i.e., the adaptive rate measure (ARM)). Since we had 5 access points in the test site and each access point could generate 5–10 samples per second, it roughly took 10 to 20 seconds for collecting 500 samples for achieving a high accuracy for identifying the current booth ID. As shown in Table6, when the size of the booth is within a radius of 0.83 m, we need to collect more samples to have a higher probability to identify the booth ID. As the booth size increases to a circle of radius of 2.15 m, there is a high probability (0.875) to identify the booth ID correctly by collecting only 25 data samples, that is, around 0.5 to 1 second to complete the localization estimation. Our experimental result shows that if the booth size is 2.5 m or above in radius, we can correctly identify which booth the user is currently locating at.Table 6
The accuracy of the location estimation.
Within a radius of
500 samples
50 samples
25 samples
10 samples
0.83 m
0.973
0.738
0.503
0.258
2.15 m
0.995
0.954
0.875
0.62
2.50 m
1
0.987
0.977
0.908In the last set of experiments, we considered lab FSC801C consisting of Booth 1 and Booth 2 with the common border at the middle of the room. We moved the user within a booth to the common edge of the two booths instead of putting him at the center of the booth to test the localization scheme when the pingpong effect was serious. Table7 shows the results of the second set of experiments. It indicates that the probability of each estimated marker position being identified is the correct booth ID. That is, referring to Figure 9 and Table 7, for Marker 1 at the lowest left corner, the probability of Marker 1 estimated to be in Booth 2 is 0.952. Similarly, for Marker 22 which is nearby the booth border, the accuracy is only about 0.483 of guessing it right at Booth 1.Table 7
Probabilities of the user location estimated within the correct booth area.
Probabilities of estimated marker position falling in the correct booth
Average
Distance from border
Booth 1
0.789
0.827
0.871
0.772
0.82
0.861
0.724
0.809
3.5 m
0.619
0.741
0.588
0.888
0.857
0.854
0.952
0.786
2.1 m
0.483
0.425
0.357
0.459
0.997
0.571
0.588
0.554
0.7 m
Booth 2
0.799
0.898
0.673
0.929
0.718
0.697
0.408
0.732
0.7 m
0.884
0.983
0.721
0.966
0.895
0.939
0.701
0.87
2.1 m
0.952
0.823
0.956
0.963
0.769
0.867
0.942
0.896
3.5 mAs shown in Table7, indicated by the average probability for each row of markers, the accuracy of the estimation of getting the correct booth ID is lower if the user is closer to the booth border. On the contrary, if the user is far from the booth border, for example, 3.5 m away, the probability of correctly identifying the booth ID is around 0.809 to 0.896. We use a signal strength graphical icon of 5 ratings to show visually the pattern of correctly identifying the booth ID within our test site. Because of the positioning of access points installed, there may be some discrepancies among different markers. However, in general, if one is not too close to the border, that is, within 0.7 m, we can obtain the correct booth ID in most of the cases.


## 6.1. Experimental Setup

Figure8 shows the floor plan and the layout of the access points in the two labs FSC801C and FSC801D. All the access points were mounted at the ceiling forming a WLAN as well as a sensing network. The access points were programmable routers, Linksys WRT54G, which were burned with an open-source custom-made firmware, acting as the WiFi sensors to obtain information of the data packets transmitted within the WLAN. All the access points continuously listen to the packets sent and received by the user device and also among the access points themselves. Packet information such as the service set identifier (SSID), extended service set identifier (ESSID), received signal strength indicator (RSSI), noise level, traffic rate, and traffic frequency was measured by a custom-made wireless data acquisition application written for the Linksys WRT54G WLAN router. For transmission efficiency and the reduction of data traffic, this useful information was selected (filter), grouped, time-stamped, and sent via TCP sockets through the router to be stored into the database maintained in the location database server. Then, the location estimation process would perform the estimation to find out which booth the user was currently locating at.Figure 8
The locations of the access points in the test site.As shown in Figure8, the access points in FSC801C were placed at the four corners first and the remaining five access points were called signal calibrators. Each signal calibrator was placed at a position such that the distances between it and the access points at each corner were different. Similarly, in FSC801D, two access points were placed at the far end corners from FSC801C. Furthermore, as shown in Figure 9, we divided FSC801C into 42 marker positions (each with a marker number) with horizontal and vertical dimensions of 1.9 m and 1.4 m, respectively. They were the basic unit for location estimation.Figure 9
The floor plan and the layout of the access points in the test site (FSC801C).


## 6.2. Experimental Results and Discussions

In the first set of experiments, we studied the estimation accuracy of the adopted localization scheme when the size of test site was varied. We placed the user device at different arbitrary marker positions (e.g., marker numbers of 9, 13, 23, and 25) in lab FSC801C and turned off all the calibrators except one of them. As shown in Table4, the estimated accuracy of correctly identifying the marker number where the user device was locating was in a range of 0.584 to 0.832. It is interesting to see that the estimation accuracy is not significantly affected by the size of the test site and the number of access points used for localization. The average accuracies of using FSC801C and both FSC801C and FSC801D are similar, for example, 0.693 and 0.702, respectively. Therefore, to simplify the experimental setup, in the remaining experiments, we adopted the settings in lab FSC801C for testing and turned off all the access points in lab FSC801D.Table 4
Probabilities of the user location in a specific marker position estimated with different test sites.
Marker position
Test site
FSC801C
FSC801C + FSC801D
9
0.832
0.766
13
0.652
0.584
23
0.646
0.764
25
0.64
0.694
Average
0.692
0.702In the second set of experiments, different numbers of access points (e.g., 3, 5, 7, and 9) were used. The access points were first placed at the corners and the remaining access points were calibrators. The results, as shown in Table5, indicate that increasing the number of access points does not have serious impact on the estimation accuracy. Using more access points (or calibrators) does not always give better estimation accuracy. Using four access points at the corners and one signal calibrator gives an estimation accuracy similar to the performance of different numbers of access points.Table 5
Probabilities of the user location in a specific marker position estimated with different number of APs.
Marker position
Number of APs
3
5
7
9
9
0.658
0.815
0.628
0.641
13
0.591
0.575
0.575
0.583
23
0.741
0.84
0.901
0.783
25
0.725
0.445
0.442
0.527
Average
0.678
0.668
0.636
0.6335In the third set of experiments, we looked at the size of a booth on the effectiveness of the adopted localization scheme in localization, that is, the effectiveness to identify the current booth ID when the booth size was varied. Following the settings in the second set of experiments, we used five access points with one of them as the calibrator in FSC801C. In this set of experiments, we assumed that the booths were squares with equal size and their dimension was described by the radius of the circle that could include the square. Furthermore, we assumed that the user was at the center of the booth (center of the circle). Then we measured the probability that the user was estimated to be in that booth when the booth size was varied. Since we took signal strength data samples for location estimation, the more the samples, the better the accuracy (i.e., the adaptive rate measure (ARM)). Since we had 5 access points in the test site and each access point could generate 5–10 samples per second, it roughly took 10 to 20 seconds for collecting 500 samples for achieving a high accuracy for identifying the current booth ID. As shown in Table6, when the size of the booth is within a radius of 0.83 m, we need to collect more samples to have a higher probability to identify the booth ID. As the booth size increases to a circle of radius of 2.15 m, there is a high probability (0.875) to identify the booth ID correctly by collecting only 25 data samples, that is, around 0.5 to 1 second to complete the localization estimation. Our experimental result shows that if the booth size is 2.5 m or above in radius, we can correctly identify which booth the user is currently locating at.Table 6
The accuracy of the location estimation.
Within a radius of
500 samples
50 samples
25 samples
10 samples
0.83 m
0.973
0.738
0.503
0.258
2.15 m
0.995
0.954
0.875
0.62
2.50 m
1
0.987
0.977
0.908In the last set of experiments, we considered lab FSC801C consisting of Booth 1 and Booth 2 with the common border at the middle of the room. We moved the user within a booth to the common edge of the two booths instead of putting him at the center of the booth to test the localization scheme when the pingpong effect was serious. Table7 shows the results of the second set of experiments. It indicates that the probability of each estimated marker position being identified is the correct booth ID. That is, referring to Figure 9 and Table 7, for Marker 1 at the lowest left corner, the probability of Marker 1 estimated to be in Booth 2 is 0.952. Similarly, for Marker 22 which is nearby the booth border, the accuracy is only about 0.483 of guessing it right at Booth 1.Table 7
Probabilities of the user location estimated within the correct booth area.
Probabilities of estimated marker position falling in the correct booth
Average
Distance from border
Booth 1
0.789
0.827
0.871
0.772
0.82
0.861
0.724
0.809
3.5 m
0.619
0.741
0.588
0.888
0.857
0.854
0.952
0.786
2.1 m
0.483
0.425
0.357
0.459
0.997
0.571
0.588
0.554
0.7 m
Booth 2
0.799
0.898
0.673
0.929
0.718
0.697
0.408
0.732
0.7 m
0.884
0.983
0.721
0.966
0.895
0.939
0.701
0.87
2.1 m
0.952
0.823
0.956
0.963
0.769
0.867
0.942
0.896
3.5 mAs shown in Table7, indicated by the average probability for each row of markers, the accuracy of the estimation of getting the correct booth ID is lower if the user is closer to the booth border. On the contrary, if the user is far from the booth border, for example, 3.5 m away, the probability of correctly identifying the booth ID is around 0.809 to 0.896. We use a signal strength graphical icon of 5 ratings to show visually the pattern of correctly identifying the booth ID within our test site. Because of the positioning of access points installed, there may be some discrepancies among different markers. However, in general, if one is not too close to the border, that is, within 0.7 m, we can obtain the correct booth ID in most of the cases.


## 7. Conclusions and Future Work

Location-based services are receiving tremendous interests in the business sector and various novel location-based services are developing accordingly. However, most of them just use simple location technologies to get the current location of a mobile client to determine the services to be provided to the client. There is still lack of a good business model to show how the technologies can be integrated into the design of practical business systems. In this paper, we apply WLAN for localization and combine it with the NFC technology to propose apervasive promotion model for the design of an effective personalized promotion system for retail chain stores. The localization technique using WLAN is adopted to capture the movements of customers within the stores by assuming that the movements within a store are effective indicators of the customers’ interest in sales items. The architecture and operations of the personalized promotion system are discussed and various technical issues in localization using WLAN are studied for improving the accuracies in identifying the booth that a customer is currently locating. In addition, an enhanced R-tree index is proposed to support different types of spatial queries for better management of the items and booths in the stores. Experimental results have demonstrated the effectiveness of the adopted localization scheme in tracking the movements of customers in different booths. An important future work is to study the effectiveness of the proposed model and promotion system in retail sales in practices. A survey and questionnaire may be conducted to study how the customers respond to the system and the promotion strategies adopted in the model. The model may be applied to formulate promotion solutions for specific retail sale systems, for example, the convenient stores. Another important future work is to study the impacts of different placements of access points on the effectiveness of the adopted localization scheme.



---

*Source: 626070-2015-04-09.xml*