摘要：目前，全国大小超市星罗棋布，几乎所有的超市都会出现大量顾客排队等待结账的场面，这不仅会浪费顾客的时间，也不利于超市的经营与盈利。本文基于超宽带室内定位技术（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.

分享让更多人看到