关键词：UWB；RFID；图像识别；关键规则挖掘算法；协同滤波算法；智能购物车
第一章绪论
1.1课题研究的背景和意义
物联网是新一代信息技术的重要组成部分。目前，与物联网技术结合的超市智能购物系统已经得到了广泛的发展，但由于其用户操作繁琐、成本较高，未得到期望中的广泛应用，因此智能购物车系统并未受到新技术发展的促进。
物联网关键技术包括传感器技术、RFID标签、嵌入式系统技术等。将这些与室内定位技术、图像识别技术以及人工智能算法相结合，应用到超市智能购物车系统中，进行NovelCart智能购物车系统的研究与搭建，在提升用户购物体验的还帮助超市节省了人力成本，同时还能引起社会对这些先进技术的重视，推动整个领域的发展。
对于超市来说，智能购物车的推行至关重要；对于购物车本身来说，除了产品的损耗，还有技术的更新迭代。所以智能购物车是一项可持续发展的产业。
1.2国内外研究现状
智能购物车是近两年才兴起的产业，热度很高，需求量大。然而从顾客使用体验和技术角度看，现有智能购物车的解决方案仍然存在很多不完善的地方。
目前绝大多数智能购物车都没有包含的室内导航功能。对于大中型超市，如果顾客不熟悉超市的布局又没有地图的话，购物非常耗时，常常需要为了一个商品搜寻很久，极大影响了顾客的用户体验。同时，目前世面上的智能购物车基本上全部需要客户手动扫描商品。这不仅让顾客承担了收银员的扫描工作、增加了劳动量，还可能因为错扫、漏扫而造成超市的直接损失。且目前广受认可的、功能尚还齐全的购物车，成本价大概在一万元左右。这样的高成本导致很多超市对智能购物车望而却步，严重推缓了购物智能化的进程。
第二章NovelCart系统设计方案
2.1系统总体方案设计
2.2方案论证
2.2.1室内定位方案选择
DWM1000模块完美符合NovelCart高精度、低成本、小型化的设计需求。安装在NovelCart上的DWM1000模块通过测量与超市中布设的坐标已知的DWM1000基站之间的距离，进行三点定位，即可提供30cm精度的室内定位服务。据估算，DWM1000基站的布设成本约为0.5元/平米。
2.2.2商品识别方案选择
NovelCart采用KLM400UHFRFID模块用于自动识别购物车内的商品。KLM400模块对于标签的识别灵敏，稳定。识别距离可达2米，且可以实现多标签（>50张）识别，速度可达每秒50张以上。该模块无需外接散热装置，其性能受外壳、电磁环境等外界影响较小。将KLM400模块放置在购物车尾部，该模块的RFID标签识别范围正好可以覆盖整个购物车。同时50张标签/秒的识别速度可以快速结算购物车内的商品，十分快捷高效。
2.2.3主处理器选择
NovelCart的主处理器主要负责控制触摸屏显示用户界面与用户进行交互、控制RFID模块实时识别购物车内商品信息和使用算法智能推荐商品，具有较强的计算能力和图像处理能力。
树莓派(RaspberryPI)是一个采用ARM处理器的开放式嵌入式系统，外形小巧，却具有强大的系统功能和接口资源。第三代树莓派(Model3B)是以ARMCortex-A53架构、主频1.2GHz、64位4核心BroadcomBCM2837处理器为核心的单板计算机，具有USB接口、SD卡插槽、HDMI输出接口等等。树莓派有极强的图形能力，能室内用板载的HDMI接口提供1080p全高清影像输出。树莓派还板载了40个可编程GPIO接口，具有强大的外设控制能力。树莓派可运行Debian、Ubuntu等Linux系统，并可充分利用Linux大量开源资源。
采用三代树莓派作为主控制器，可直接使用HDMI连接高清触摸屏流畅运行用户交互界面，并且剩余的计算性能还足以运行人工智能算法，符合NovelCart的设计需求。
2.2.4协处理器即UWB基站主处理器选择
使用STM32F103RCT6作为NovelCart的协处理器和UWB定位基站的主处理器可以保证室内定位服务精准稳定的运行，并且有利于整体系统的低成本、小型化实现。
第三章硬件设计
NovelCart硬件设计主要包含两部分：NovelCart智能购物车系统主体以及UWB定位基站。NovelCart智能购物车系统主体部分采用模块化设计，整体结构小巧可靠，可直接安装在普通购物车上。UWB定位基站采用了低功耗、小型化设计，电路板大小仅55mm×35mm。
3.1NovelCart主体硬件设计
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所示：
UWB模块天线的位置会影响定位的精度。为了保证定位性能，尽可能减少NovelCart上其他电子元器件的干扰，DWM1000并未和协处理器设计在一块电路板上，而是采用了一块单独的电路板，通过排线和协处理器部分电路相连，以便把DWM1000模块布设在最利于定位的位置。
协处理部分和DWM1000模块的PCB设计和实物图如图3-4所示：
3.2UWB定位基站硬件设计
3.2.1UWB室内定位原理
NovelCart采用单边双向测距(Single-sidedtwo-wayranging,SS-TWR)方向计算购物车与UWB定位基站之间的距离。SS-TWR定位方式的原理如图3-5所示：
3.2.2UWB基站设计
其中电路的设计与主体硬件设计中所介绍的基本一致，在此不做赘述
UWB基站的PCB基站实现了尽可能的小型化，大小仅35mm×45mm：
第四章软件设计
4.1图形界面设计
NovelCart搭载的用户图形界面(GUI)是基于Kivy设计开发的。Kivy是一套Python语言下的跨平台快速应用开发框架，对于多点触控有着良好的支持。Kivy依据允许商业使用LGPLv3协议发布，支持Linux、Windows、MacOSX、Android和iOS平台，原生支持包括多点触控的各个平台的输入设备协议，其图形核心围绕OpenGLES2构建，可以充分利用目标平台的GPU进行加速。
在使用Kivy设计NovelCart用户交互GUI的过程中，模块化与抽象化的思想至关重要。NovelCart的软件构架把各种基本的任务进行抽象，比如打开窗口、显示图像和文本、拼写校正等等。
Kivy使NovelCart的GUI具有着极高的可扩展性与可移植性。Kivy的API接口调用简单，扩展容易，通过简单的代码一面与操作系统间进行通信，另一方面与接口完成信息交互，可以实时而高效率地调用各个硬件组成部分以及存储当中的数据信息，完成所需的任务；Kivy在运行过程中，所使用的API皆用自各运行平台所提供的API，同一端程序可以编译后在不同操作系统下的运行，也使得NovelCart的GUI在不同设备上的移植能力，以便后续升级。
NovelCart搭载的GUI共有八个界面：等待界面、主界面（如图4-2所示）、地图界面、推荐界面、购物车界面以及提醒界面、警报界面、和支付界面。其主要关系结构与业务逻辑线程之前的关系如图4-3所示。
4.2RFID标签的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模块通过FT232RLUSB转串口模块连接，波特率为115200bps，校验位一位。设置每隔2s进行一次单次轮询。假设进行单次轮询时车内有n个商品，则ARM主控制器会收到一个由n个以“BB0222”开头、“7E”结尾的子帧构成的通知帧。RFID信号的EPC解算流程图如图4-4所示。
第五章算法设计
5.1关联规则挖掘算法Apriori
表3给出了一个交易数据集的例子通常称其为购物篮交易记录(MarketBasketTransaction)。图中每一行对应一个交易，包含一个唯一标识TID和特定顾客购买的商品集合。
关联规则挖掘任务：对于给定的交易记录列表,寻找其中存在的固有的项目之前的联系：
支持度≥minsupthreshold
置信度≥minconfthreshold
因此，将关联规则挖掘任务分解为频繁项集产生和强规则产生两个子任务。格结构(LatticeStructure)常被用来枚举所有可能的项集。如图5-1所示。
图5-1为I={a,b,c,d,e}的项集格。一般来说，排除空集后，一个包含k个项的数据集可能产生2k1个频繁项集。在实际情况下k的值可能非常大，需要探查的项集搜索空集可能是指数规模的。结合Apriori所利用的第一条先验原理，利用支持度对候选项集进行剪枝。
Apriori定律1：如果一个集合是频繁项集，则它的所有子集都是频繁项集。
Apriori定律2：如果一个集合不是频繁项集，则它的所有超集都不是频繁项集。
图5-2表示{A,B}是非频繁集时，其超集也是非频繁集，可以将它们都剪除。
5.2协同滤波算法
协同过滤推荐算法分为两类，分别是基于用户的协同过滤算法(User-basedCollaborativeFiltering)，和基于物品的协同过滤算法(Item-basedCollaborativeFiltering)。算法通过对用户历史行为数据的挖掘发现用户的偏好，基于不同的偏好对用户进行群组划分并推荐品味相似的商品。可利用Apriori算法所得的关联规则挖掘结果，采用基于用户的协同滤波算法对相似用户进行匹配并预测推荐。
欧几里德距离评价是一个较为简单的用户关系评价方法。原理是通过计算两个用户在散点图中的距离来判断不同的用户是否有相同的偏好。5个用户相互间的欧几里德系数，也就是用户间的距离如表4所示。系数越小表示两个用户间的距离越近，偏好也越是接近。如表5所示，用户偏好关系与图5-4一致。
第六章系统测试与误差分析
6.1UWB定位测试
在实验室环境内对UWB定位系统进行测试。三个UWB基站使用三脚架架设在15mx10m室内环境中，如图6-1所示，三个基站的布局如图6-2所示。
从图中可以看出，定位结果基本准确。由于UWB定位标签在测试过程中是由测试人员手持，在行走过程中会有上下、左右的轻微晃动，对定位结果造成了一定干扰。而实际使用中，精度会有略微提升。
6.2RFID商品识别测试
由于KLM400模块的工作频谱范围为840~960MHz，属于高频无线电波频段（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；基于KLM400UHFRFID进行标签识别技术优化，识别速度可达63张/秒，识别范围可达1.2㎡，完全覆盖一个购物车；通过Apriori算法和基于用户的协同滤波算法（User-basedCollaborativeFiltering）获得频繁项集，并通过关联规则挖掘结果进行商品推荐。采用基于Kivy设计的用户交互界面，在Linux、Windows系统下运行顺畅。
虽然按照预期完成了整个系统，但是系统仍存在一些需要改进的部分。我们也会在后期为UWB室内定位增加卡尔曼滤波算法，从而进一步提升定位精度；我们还会应用SipeedMaixGo开发板，加入图像识别，优化商品识别的解决方法，同时使成本更低。
参考文献
[1]GuanW,ChungCY,LinLJ.Collaborative-filteringcontentmodelforrecommendingitems:US,US7584171[P].2009.
[2]BodonF.AfastAPRIORIimplementation[J].ProceedingsoftheIEEEIcdmWorkshoponFrequentItemsetMiningImplementations,2003.
[3]GibertK,Sànchez-MarrèM,CodinaV.ChoosingtheRightDataMiningTechnique:ClassificationofMethodsandIntelligentRecommendation[J].2010,165(1):52.
[4]陆丽娜,陈亚萍,魏恒义,等.挖掘关联规则中Apriori算法的研究[J].小型微型计算机系统,2000,21(9):940-943.
[5]张雪文.智能推荐系统中协同过滤算法的研究[D].上海交通大学,2008.