摘要：目前，全國大小超市星羅棋布，幾乎所有的超市都會出現大量顧客排隊等待結賬的場面，這不僅會浪費顧客的時間，也不利於超市的經營與盈利。本文基於超寬帶室內定位技術（UWB）、射頻識別技術（RFID）以及一些人工智能算法，從技術上解決了傳統超市人工收銀台結賬效率低下、用戶長時間排隊影響用戶體驗的問題，同時也解決了現有智能購物車需要用戶手動掃描已購商品的問題，實現了功能比較完善並可直接安裝在傳統購物車上的智能購物車系統NovelCart。

NovelCart智能購物車系統搭載的UHF-RFID模塊用於實時獲取車內商品信息，同時將信息通過串口發送至ARM主控制器﹔UWB室內定位模塊配合定位基站與STM32協處理器通過串口與樹莓派連接，進行室內實時定位，實現固定區域自動結算﹔與ARM主控制器通過HDMI連接的觸摸顯示屏可以用來與用戶進行交互和AI廣告推送﹔整個系統的核心ARM主控制器依靠強大的計算能力對整個系統進行信息處理，同時根據收集到的用戶購物信息，運用關聯規則挖掘算法Apriori進行數據挖掘，實現精准的廣告推送。NovelCart智能購物車系統的實現，在提升用戶購物體驗的同時還幫助超市節省了人力成本﹔且對比現有的一些智能購物車，成本更低，功能更加齊全，設備更加智能，有利於后續推廣。

關鍵詞：UWB﹔RFID﹔圖像識別﹔關鍵規則挖掘算法﹔協同濾波算法﹔智能購物車

第一章 緒論

1.1課題研究的背景和意義

物聯網是新一代信息技術的重要組成部分。目前，與物聯網技術結合的超市智能購物系統已經得到了廣泛的發展，但由於其用戶操作繁瑣、成本較高，未得到期望中的廣泛應用，因此智能購物車系統並未受到新技術發展的促進。

物聯網關鍵技術包括傳感器技術、RFID標簽、嵌入式系統技術等。將這些與室內定位技術、圖像識別技術以及人工智能算法相結合，應用到超市智能購物車系統中，進行NovelCart智能購物車系統的研究與搭建，在提升用戶購物體驗的還幫助超市節省了人力成本，同時還能引起社會對這些先進技術的重視，推動整個領域的發展。

對於超市來說，智能購物車的推行至關重要﹔對於購物車本身來說，除了產品的損耗，還有技術的更新迭代。所以智能購物車是一項可持續發展的產業。

1.2國內外研究現狀

智能購物車是近兩年才興起的產業，熱度很高，需求量大。然而從顧客使用體驗和技術角度看，現有智能購物車的解決方案仍然存在很多不完善的地方。

目前絕大多數智能購物車都沒有包含的室內導航功能。對於大中型超市，如果顧客不熟悉超市的布局又沒有地圖的話，購物非常耗時，常常需要為了一個商品搜尋很久，極大影響了顧客的用戶體驗。同時，目前世面上的智能購物車基本上全部需要客戶手動掃描商品。這不僅讓顧客承擔了收銀員的掃描工作、增加了勞動量，還可能因為錯掃、漏掃而造成超市的直接損失。且目前廣受認可的、功能尚還齊全的購物車，成本價大概在一萬元左右。這樣的高成本導致很多超市對智能購物車望而卻步，嚴重推緩了購物智能化的進程。

第二章 NovelCart 系統設計方案

2.1系統總體方案設計

NovelCart智能購物車系統主要針對大型綜合超市，致力於為超市用戶提供更好的購物體驗，為超市商家提供更精確、有效的廣告推送平台。其總體系統設計方案如圖2-1所示。

NovelCart採用ARM主處理器加STM32協處理器設計：ARM處理器的計算能力保証整體系統的流暢運行，STM32協處理器協助處理實時性要求較高的室內定位相關任務。傳感器方面，NovelCart主要配備了UHF RFID模塊和UWB室內定位模塊。UHF RFID模塊可以實時、准確地識別購物車內商品的信息。UWB室內定位模塊提供高達30cm精度的實時定位服務，從而可以建立電子圍欄，設置自動結賬區域。需要注意的是，NovelCart的室內定位功能需要配合UWB定位基站一同使用。此外，NovelCart還搭載一塊7英寸1024x600分辨率高清觸摸屏，用於用戶交互。

2.2方案論証

2.2.1室內定位方案選擇

精確的室內定位對於商業應用、公共安全等都具有非常重要的意義。然而室內環境非常復雜,信號傳播會受到各種各樣的影響。發射信號經過多條路徑、以不同的時間到達接收端,出現多徑傳播現象和非視距效應，使得室內定位極具挑戰性。超寬帶技術UWB (Ultra-wideband)擁有極寬電磁頻譜,在穿透能力、精細分辨、精確測距、抗多徑和抗干擾等方面具有獨特的優勢，其系統實現具有低復雜度、低功耗、低成本的潛力，成為室內定位最有前景的技術方案之一。DWM1000模塊的優點如表1所示。

DWM1000模塊完美符合NovelCart高精度、低成本、小型化的設計需求。安裝在NovelCart上的DWM1000模塊通過測量與超市中布設的坐標已知的DWM1000基站之間的距離，進行三點定位，即可提供30cm精度的室內定位服務。據估算，DWM1000基站的布設成本約為0.5元/平米。

2.2.2商品識別方案選擇

RFID作為一種非接觸式無線自動識別技術，其原理是通過射頻信號自動識別對象目標而獲取相關數據。工作在UHF頻段的RFID系統，具有識別距離遠、數據傳輸快等優點。在部分無人便利店中，已經採用了RFID的方式進行商品的結算，但由於其識別區域固定，並沒有解決結算效率低下的問題。

NovelCart採用KLM400 UHF RFID模塊用於自動識別購物車內的商品。KLM400模塊對於標簽的識別靈敏，穩定。識別距離可達2米，且可以實現多標簽（>50張）識別，速度可達每秒50張以上。該模塊無需外接散熱裝置，其性能受外殼、電磁環境等外界影響較小。將KLM400模塊放置在購物車尾部，該模塊的RFID標簽識別范圍正好可以覆蓋整個購物車。同時50張標簽/秒的識別速度可以快速結算購物車內的商品，十分快捷高效。

2.2.3主處理器選擇

NovelCart的主處理器主要負責控制觸摸屏顯示用戶界面與用戶進行交互、控制RFID模塊實時識別購物車內商品信息和使用算法智能推薦商品，具有較強的計算能力和圖像處理能力。

樹莓派(Raspberry PI)是一個採用ARM處理器的開放式嵌入式系統，外形小巧，卻具有強大的系統功能和接口資源。第三代樹莓派(Model 3B)是以ARM Cortex-A53架構、主頻1.2GHz、64位4核心Broadcom BCM2837處理器為核心的單板計算機，具有USB接口、SD卡插槽、HDMI輸出接口等等。樹莓派有極強的圖形能力，能室內用板載的HDMI接口提供1080p全高清影像輸出。樹莓派還板載了40個可編程GPIO接口，具有強大的外設控制能力。樹莓派可運行Debian、Ubuntu等Linux系統，並可充分利用Linux大量開源資源。

採用三代樹莓派作為主控制器，可直接使用HDMI連接高清觸摸屏流暢運行用戶交互界面，並且剩余的計算性能還足以運行人工智能算法，符合NovelCart的設計需求。

2.2.4協處理器即UWB基站主處理器選擇

Linux是非實時操作系統，實時性較差。而UWB定位需要系統具有較高的實時性，所以需要為樹莓派配備一個協處理器，用於協助完成UWB定位相關任務。同時，UWB定位基站也需要微控制器來驅動DWM1000模塊。

使用STM32F103RCT6作為NovelCart的協處理器和UWB定位基站的主處理器可以保証室內定位服務精准穩定的運行，並且有利於整體系統的低成本、小型化實現。

第三章  硬件設計

NovelCart硬件設計主要包含兩部分：NovelCart智能購物車系統主體以及UWB定位基站。NovelCart智能購物車系統主體部分採用模塊化設計，整體結構小巧可靠，可直接安裝在普通購物車上。UWB定位基站採用了低功耗、小型化設計，電路板大小僅55mm×35mm。

3.1 NovelCart主體硬件設計

NovelCart智能購物車系統主體系統硬件框圖如圖3-1所示：

硬件方面，NovelCart的ARM主控制器主要負責控制KLM400模塊實時識別購物車內商品信息、與協處理通信獲取室內定位信息、用戶超出結賬區域報警和使用板載的HDMI接口向觸摸屏輸出用戶交互界面。原理圖如圖3-2所示：

ARM主處理器通過板載的USB口連接FT232RL芯片，FT232RL芯片將USB口的232電平轉換為TTL電平串口與KLM400模塊相連。ARM主處理器的GPIO8和GPIO10分別為UART外設的RX引腳和TX引腳，GPIO8連接至協處理器的串口發送引腳、GPIO10連接至協處理器的串口接收引腳，ARM主處理器即可通過串口與協處理器通信，獲取室內定位信息。GPIO7為協處理器的使能引腳，GPIO7高電平時協處理器以1Hz頻率向ARM主處理器發送定位信息﹔GPIO低電平時，協處理器和UWB模塊處於休眠狀態，降低系統功耗。GPIO11負責控制蜂鳴器進行超出使用區域限制報警。考慮到蜂鳴器工作時最大電流可達300mA，遠大於ARM主處理器GPIO的最大輸出電流，所以驅動電路增加了S8050三極管，以低電流控制蜂鳴器的工作。

協處理器部分，為了使NovelCart硬件電路足夠緊湊，外形足夠小巧，協處理器部分採用STM32F103最小系統設計，部分原理圖如圖3-3所示：

STM32F103RCT6協處理器採用8M無源晶振作為時鐘輸入，經過內部鎖相環倍頻，工作在72MHz主頻。P1接口引出了與DWM1000通信相關的引腳，通過排線與DWM1000模塊相連﹔P2接口引出了與ARM主處理器通信相關的引腳，通過排線與ARM主處理器電路板相連。協處理器部分電路還保留了啟動模式選擇接口BOOT0，用於下載程序和后期維護、調試。電源使用AMS1117-3.3穩壓芯片將5V輸入電源轉換為3.3V。

UWB模塊天線的位置會影響定位的精度。為了保証定位性能，盡可能減少NovelCart上其他電子元器件的干擾，DWM1000並未和協處理器設計在一塊電路板上，而是採用了一塊單獨的電路板，通過排線和協處理器部分電路相連，以便把DWM1000模塊布設在最利於定位的位置。

協處理部分和DWM1000模塊的PCB設計和實物圖如圖3-4所示：

3.2 UWB定位基站硬件設計

3.2.1 UWB室內定位原理

NovelCart採用單邊雙向測距(Single-sided two-way ranging, SS-TWR)方向計算購物車與UWB定位基站之間的距離。SS-TWR定位方式的原理如圖3-5所示：

3.2.2 UWB基站設計

UWB基站採用了與NovelCart系統主體硬件相似的設計。UWB基站需要安裝在超市中，所以要盡可能的小巧、美觀。所以在UWB基站上隻保留了定位所需的相關最小電路。UWB基站硬件系統框圖如圖3-6所示：

其中電路的設計與主體硬件設計中所介紹的基本一致，在此不做贅述

UWB基站的PCB基站實現了盡可能的小型化，大小僅35mm×45mm：

第四章 軟件設計

4.1圖形界面設計

NovelCart搭載的用戶圖形界面(GUI)是基於Kivy設計開發的。Kivy是一套 Python語言下的跨平台快速應用開發框架，對於多點觸控有著良好的支持。Kivy 依據允許商業使用LGPLv3協議發布，支持Linux、Windows、MacOS X、Android 和iOS平台，原生支持包括多點觸控的各個平台的輸入設備協議，其圖形核心圍繞OpenGL ES2構建，可以充分利用目標平台的GPU進行加速。

在使用Kivy設計NovelCart用戶交互GUI的過程中，模塊化與抽象化的思想至關重要。NovelCart的軟件構架把各種基本的任務進行抽象，比如打開窗口、顯示圖像和文本、拼寫校正等等。

Kivy使NovelCart的GUI具有著極高的可擴展性與可移植性。Kivy的API接口調用簡單，擴展容易，通過簡單的代碼一面與操作系統間進行通信，另一方面與接口完成信息交互，可以實時而高效率地調用各個硬件組成部分以及存儲當中的數據信息，完成所需的任務﹔Kivy在運行過程中，所使用的API皆用自各運行平台所提供的API，同一端程序可以編譯后在不同操作系統下的運行，也使得NovelCart的GUI在不同設備上的移植能力，以便后續升級。

NovelCart搭載的GUI共有八個界面：等待界面、主界面（如圖4-2所示）、地圖界面、推薦界面、購物車界面以及提醒界面、警報界面、和支付界面。其主要關系結構與業務邏輯線程之前的關系如圖4-3所示。

4.2 RFID標簽的EPC解算

產品電子代碼（EPC編碼）是下一代產品標識代碼，它可以對供應鏈中的對象（包括物品、貨箱、貨盤、位置等）進行全球唯一的標識。EPC存儲在RFID標簽上，這個標簽包含一塊硅芯片和一根天線。NovelCart識別購物車內物品的原理就是通過RFID模塊接收購物車內RFID標簽的信號，解算出各個RFID標簽的EPC，根據EPC查詢數據庫從而獲取購物車內所有商品的各種信息。

KLM400模塊通訊協議內定義的單次輪詢指令的通知幀為：“BB00220000227E”。芯片接收到單次輪詢指令后，如果能夠讀到CRC校驗正確的標簽，KLM400返回包含RSSI、PC、EPC和CRC的數據。讀到一個標簽EPC就返回一條指令響應，讀到多個標簽則返回多條指令響應。如表2所示。

上表中“Header”代表幀頭，“Type”代表幀類型，“Command”代表指令，“PL”代表指令參數長度，“RSSI”代表信號強度，“PC”代表PC碼，“EPC”代表EPC碼，“CRC”代表循環校驗碼，“Checksum”代表校驗位，“End”代表幀尾。

ARM主控制器與KLM400模塊通過FT232RL USB轉串口模塊連接，波特率為115200bps，校驗位一位。設置每隔2s進行一次單次輪詢。假設進行單次輪詢時車內有n個商品，則ARM主控制器會收到一個由n個以“BB0222”開頭、“7E”結尾的子幀構成的通知幀。RFID信號的EPC解算流程圖如圖4-4所示。

第五章  算法設計

5.1關聯規則挖掘算法Apriori

NovelCart針對超市採集到的用戶歷史購買數據進行預處理，並使用關聯規則挖掘算法Apriori進行數據挖掘。Apriori算法是一種用於關聯規則挖掘(Association Rule Mining)的代表性算法，採用Apriori算法能夠有效獲得頻繁項集，並根據數據特征設置相應的閾值，向用戶推薦相關度高的商品。

表3給出了一個交易數據集的例子通常稱其為購物籃交易記錄(Market Basket Transaction)。圖中每一行對應一個交易，包含一個唯一標識TID和特定顧客購買的商品集合。

關聯規則挖掘任務：對於給定的交易記錄列表, 尋找其中存在的固有的項目之前的聯系：

支持度 ≧ minsup threshold

置信度 ≧ minconf threshold

因此，將關聯規則挖掘任務分解為頻繁項集產生和強規則產生兩個子任務。格結構(Lattice Structure)常被用來枚舉所有可能的項集。如圖5-1所示。

圖5-1為I={a,b,c,d,e}的項集格。一般來說，排除空集后，一個包含k個項的數據集可能產生2k−1個頻繁項集。在實際情況下k的值可能非常大，需要探查的項集搜索空集可能是指數規模的。結合Apriori所利用的第一條先驗原理，利用支持度對候選項集進行剪枝。

 Apriori定律1：如果一個集合是頻繁項集，則它的所有子集都是頻繁項集。

Apriori定律2：如果一個集合不是頻繁項集，則它的所有超集都不是頻繁項集。

圖5-2表示{A,B}是非頻繁集時，其超集也是非頻繁集，可以將它們都剪除。

5.2 協同濾波算法

協同過濾推薦算法分為兩類，分別是基於用戶的協同過濾算法(User-based Collaborative Filtering)，和基於物品的協同過濾算法(Item-based Collaborative Filtering)。算法通過對用戶歷史行為數據的挖掘發現用戶的偏好，基於不同的偏好對用戶進行群組劃分並推薦品味相似的商品。可利用Apriori算法所得的關聯規則挖掘結果，採用基於用戶的協同濾波算法對相似用戶進行匹配並預測推薦。

基於用戶的協同過濾算法是通過用戶的歷史行為數據發現用戶對商品或內容的喜好(如商品購買，收藏，內容評論或分享)，並對這些喜好進行度量和打分。根據不同用戶對相同商品或內容的態度和偏好程度計算用戶之間的關系。在有相同喜好的用戶間進行商品推薦。

我們模擬了5個用戶對兩件商品的評分，來說明如何通過用戶對不同商品的態度和偏好尋找相似的用戶。在示例中，5個用戶分別對兩件商品進行了評分。這裡的分值可能表示真實的購買，也可以是用戶對商品不同行為的量化指標。例如，瀏覽商品的次數，向朋友推薦商品，收藏，分享，或評論等等。這些行為都可以表示用戶對商品的態度和偏好程度。將5個用戶對兩件商品的評分用散點圖表示。

歐幾裡德距離評價是一個較為簡單的用戶關系評價方法。原理是通過計算兩個用戶在散點圖中的距離來判斷不同的用戶是否有相同的偏好。5個用戶相互間的歐幾裡德系數，也就是用戶間的距離如表4所示。系數越小表示兩個用戶間的距離越近，偏好也越是接近。如表5所示，用戶偏好關系與圖5-4一致。

在數據復雜的情況下採用皮爾遜相關度評價算法進行處理，皮爾遜相關系數的計算結果是一個在-1與1之間的數，用於體現相關性。0.8-1.0為極強相關，0.6-0.8為強相關，0.4-0.6為中等程度相關，0.2-0.4為弱相關，0.0-0.2為極弱相關或無相關。處理結果如表7所示。最終的推薦結果如表8所示。

第六章 系統測試與誤差分析

6.1 UWB定位測試

在實驗室環境內對UWB定位系統進行測試。三個UWB基站使用三腳架架設在15m x 10m室內環境中，如圖6-1所示，三個基站的布局如圖6-2所示。

從圖中可以看出，定位結果基本准確。由於UWB定位標簽在測試過程中是由測試人員手持，在行走過程中會有上下、左右的輕微晃動，對定位結果造成了一定干擾。而實際使用中，精度會有略微提升。

6.2 RFID商品識別測試

由於KLM400模塊的工作頻譜范圍為840 ~ 960 MHz，屬於高頻無線電波頻段（UHF），其波長較短，較易被液體所吸收，因此液體商品會對RFID信號的接收產生不利的影響，該影響主要表現在兩方面：（1）液體商品的RFID識別﹔（2）液體商品對其他商品RFID信號的阻隔。

經測試，在敞口金屬容器內普通商品（如紙抽）的RFID識別范圍為1.5 ~ 2m（不必要求RFID標簽面正對RFID模塊天線面），而液體商品的RFID識別范圍大幅降低。經測試，液體商品在RFID標簽面正對RFID模塊天線面時，RFID識別范圍約為15cm，而標簽面與天線面呈一定夾角時，RFID識別范圍則會降低至5 ~ 10cm。

當RFID模塊與貼有RFID標簽的紙抽如圖6-4左圖所示放置時，RFID模塊接收信號的強度為-35dBm，而當如圖6-4右圖所示在兩者中間放置一大瓶水時，RFID模塊對該標簽接收信號的強度降至-45dBm，同時在此距離下水瓶上RFID標簽的接收信號強度為-50dBm。

6.2.3金屬物品對RFID標簽的影響

當RFID電子標簽靠近金屬時，由於金屬對電磁波具有強烈的反射性，所以會伴隨著信號減弱，讀卡距離也會變得更近，嚴重干擾則會出現讀卡失敗的現象。

將如圖6-5所示的商品靠近RFID模塊時，隻有當商品貼有RFID標簽的一面貼近RFID模塊時（2cm以內），RFID模塊才會檢測到該物品。

此外，金屬制的購物車也會對RFID標簽識別產生一定影響。但比起對購物車內商品RFID信號的反射衰減，金屬購物車會對購物車外的商品RFID標簽產生更多的屏蔽作用，因此從綜合意義上講，金屬制購物車對於購物車內RFID標簽的識別是有益的。

總結

NovelCart是一款集合超寬帶室內定位技術(UWB)、射頻識別技術(RFID)和關聯規則挖掘算法和協同濾波算法，並可直接安裝在傳統購物車上的智能購物車系統。其中，基於UWB的DWM1000定位模塊精度可達20cm﹔基於KLM400 UHF RFID進行標簽識別技術優化，識別速度可達63張/秒，識別范圍可達1.2㎡，完全覆蓋一個購物車﹔通過Apriori算法和基於用戶的協同濾波算法（User-based Collaborative Filtering）獲得頻繁項集，並通過關聯規則挖掘結果進行商品推薦。採用基於Kivy設計的用戶交互界面，在Linux、Windows系統下運行順暢。

雖然按照預期完成了整個系統，但是系統仍存在一些需要改進的部分。我們也會在后期為UWB室內定位增加卡爾曼濾波算法，從而進一步提升定位精度﹔我們還會應用Sipeed MaixGo開發板，加入圖像識別，優化商品識別的解決方法，同時使成本更低。

參考文獻

[1] Guan W, Chung C Y, Lin L J. Collaborative-filtering content model for recommending items: US, US7584171[P]. 2009.

[2] Bodon F. A fast APRIORI implementation[J]. Proceedings of the IEEE Icdm Workshop on Frequent Itemset Mining Implementations, 2003.

[3] Gibert K, Sànchez-Marrè M, Codina V. Choosing the Right Data Mining Technique: Classification of Methods and Intelligent Recommendation[J]. 2010, 165(1):52.

[4] 陸麗娜, 陳亞萍, 魏恆義,等. 挖掘關聯規則中Apriori算法的研究[J]. 小型微型計算機系統, 2000, 21(9):940-943.

[5] 張雪文. 智能推薦系統中協同過濾算法的研究[D]. 上海交通大學, 2008.

分享讓更多人看到