伴随着现代物流市场的迅速发展, 客户对于快速准确的物流服务要求越来越高, 对流通中货物的定位需求也不断增长。随着计算机网络技术、无线通信技术的发展, 定位技术主要分为室内定位和室外定位两种类型, 目前室外定位系统中, 发展和应用最为普遍的是GPS全球定位系统, 但由于货物仓库内部货架位置布局复杂且有多种非视距的噪声干扰, 使得传统定位技术并不适应于大型综合化立体仓库的定位环境。本文提出了一种基于普适计算环境的物流仓库定位算法[1]。

普适计算思想是由Mark Weiser于1991年在《Scientific American》的“The Computer for the 21st Century”中提出的[2], 指信息空间与物理空间相互融合, 可以随时随地、透明地获得数字化的服务, 而无需端坐在一个专门的计算机面前[3]。随着无线通信和计算机技术的快速发展, 无线传感器网络 (Wireless Sensor Network, WSN) 和无线射频识别RFID (Radio Frequency Identify) 得到了广泛的应用, 成为普适计算中的两大关键技术[4,5]。无线射频识别是一种自动识别技术, 通过无线射频方式进行非接触的双向数据通信, 无须人工干预, 可识别快速移动的物体和识别多个标签[6,7]。但RFID阅读器获得的数据必须有网络作为传输载体, 这限制了它的应用[8]。而WSN可以较好地弥补RFID的缺点, 是一种特殊的Ad-hoc网络[9], 是由大量传感器节点自组织形成的, 并将数据传送到网络中的特定位置[10,11]。因此, WSN与RFID融合将扩展原有的功能, 并给普适计算带来了大量新的应用[12]。本文利用RFID和WSN融合技术, 构建了一个适合仓库需求的物流定位与追踪系统。

采用RFID阅读器与WSN的融合技术组成信标节点, 将定位算法中的定位向量格式设计为 (Tag_ID, Node_ID, T) , 其中Tag_ID表示货物所携带的电子标签, 且具有唯一的EPC-Global码, Node_ID表示信标节点ID号, T表示货物进入信标节点范围内被监测到的时间。根据采集的定位向量进行分组排序, 其中, 标签Tag1分组排序后定位向量见表1。

根据表1可以看出, 通过货物在某一时刻被哪个信标节点监测到, 从而判断货物所在仓库的位置。但存在某些时刻未被信标节点监测到的情况, 从而导致大量的盲区出现, 造成网络覆盖范围的减少。如图1所示, 将表中记录的时间属性投影在时间轴上, 空白时间段表示未被任何信标节点监测到, 则该时间段内无法确定该货物所在的区域, 而一味的增加信标节点, 则会增加成本和算法的复杂程度。在本文改进的算法中, 主要解决空白时间段货物的位置信息。

表1 标签Tag1定位向量  下载原图

表1 标签Tag1定位向量

图1 标签Tag1的运动轨迹在时间轴上的投影  下载原图

将仓库空间划分为不同的区域。根据仓库不同位置设置不同的信标节点, 例如根据进出口的节点可以判断货物的运动方向, 而存储区域内的节点仅用来定位和采集信息, 因此在仓库部署的信标节点有两种: (1) 无向设备不能判断货物运动方向, 只能监测到某货物进入到了其阅读范围之内, 如图2的N5、N6和N8等节点。 (2) 有向设备一般部署在出入口的位置, 因为有向信标节点的阅读器拥有两个不同方向的天线, 根据标签被两个天线读取到的先后顺序就可以判断货物的移动方向。如货物携带的电子标签先被天线1监测到, 然后被天线2监测到, 说明货物进入到存储区域。反之说明货物离开了存储区域, 如图2所示, N1和N1'就是一个有向节点。

图2 仓库部分区域平面示例图  下载原图

将布置在仓库的信标节点抽象为无向图, 根据这些区域的连通性和可达性构成基本图。如图3所示, 区域1、区域2都被抽象为一个点, 而边则表示了这两个点之间是联通的。定义V是图中顶点的集合, 每一个顶点对应仓库的一个区域。E是边的集合, 每条边可以定义为向量 (vi, vj) , 其中vi, vj∈V, 并且vi≠vj。

图3 仓库区域拓扑图  下载原图

为了能够计算出空闲时间段货物的位置, 将原算法中定位向量中信标节点分量Node_ID设置为Nid和Nid', 分别表示阅读器的两个不同方向的天线, 时间分量T设置为Ts和Te, 改进后的定位向量的格式为: (Tag_ID, Node_ID, Ts, Te) , 其中Ts表示货物进入到节点的采集区域被监测到的时间, Te表示货物最后一次被节点监测到的时间, 其表示在Ts到Te时间段的每一刻货物都被同一信标节点监测到。

对定位向量进行改进后, 依据以下步骤进行货物定位:

Step1:对定位向量分组和排序, 其中Tag1处理后得到的定位向量表, 见表2。

表2 改进后的定位向量表  下载原图

表2 改进后的定位向量表

Step2:将预处理所获得的每一个定位向量转换为基本图的对应元素。首先建立属性为 (Tag_ID, Node1, Node2, Ts, Te, Elment) 的表格。其次对某一个货物移动所产生的所有的定位向量的集合按照时间排序后进行处理, 如果每两个定位向量的Te与Ts的差值小于或者等于一个采样周期, 说明这两个向量是连续的, 即这两条向量是由一个有向设备产生的, 可以得到图中的一条边, 相关数据被插入;如果两个定位向量是不连续的, 即Te与Ts的插值大于一个采样周期, 说明该定位向量是由无向设备产生的, 那么就转换为基本图的一个顶点, 处理结果见表3。

Step3:根据第2步的结果来确定空闲时间段该货物的所在区域。首先建立一个属性为 (Tag, Ts, Te, Region) 的表格。其中属性Ts和Te表示空白时间段, Region表示在空白时间段内货物所在的区域。该步对表3中每相邻两个记录做以下处理:如果当前记录的前一条记录中的Elment属性值是一条边, 则将该边的尾节点加入到集合V1中, 如果是顶点, 则将该顶点加入到集合V1;如果当前记录的Elment属性值是一条边, 则将该记录的头节点加入到集合V2中, 如果是顶点, 则将顶点加入到集合V2中。然后对集合V1和集合V2取交集, 如果它们的交集不为空, 则可以得到该货物在空白时间段所处的区域。如果V1与V2没有交集, 则说明货物有可能在这两个区域内的盲区中, 需要进一步判断。经步骤3处理后的定位向量表见表4。

表3 处理后得到的定位向量表  下载原图

表3 处理后得到的定位向量表

表4 第3步处理后得到的定位向量表  下载原图

表4 第3步处理后得到的定位向量表

Step4:假设测量货物在仓库移动的最大速度为vmax, 根据这一速度来精确货物在空白时间段所在的区域。由于RFID阅读器的覆盖范围都是以自身为圆心, 以其识别距离为半径的圆。以表4中第四条记录为例, 在该条记录中得到在空白时间段T41-T46货物所处的位置在区域7或区域6。根据图4所示, 假设Tx是空白时间段T41到T46中的任一时刻, 设△t1=TxT40, △t2=T47-Tx。由于货物在T40时刻被节点N7最后一次监测到, 可知在T40时刻后货物离开了N7的监测区域, 以信标节点N7所在的圆点O7为出发点, 以R7为半径, 根据最大移动速度Vmax可以确定货物在T41到Tx时间段的移动距离为R'=vmax×△t1。

同理, 由于在T47时刻货物被节点N6首次监测到, 可得货物在Tx到T46时间段的移动距离为R''=vmax×△t2。根据以上两个半径条件R'+R7和R''+R6可以判断货物在空白时间段T41-T46所处的位置应该为环形区域1和环形区域2的交集区域3处。

图4 空白时间段移动轨迹图  下载原图

利用Matlab7.0进行仿真实验, 将仓库监测区域抽象为200m×200m的长方形区域, 信标节点150个, MAC协议采用802.15.4, 实际环境下的路径衰落指数η=3.5, 参考距离d0=1m, 高斯分布随机变量Xσ的标准差取值为4.0[13]。实验结果是重复30次运行的平均值。实验主要对传统的定位算法和本文改进的定位算法的覆盖率进行性能评估。如图5所示, 随着信标节点数量的增加, 改进算法的定位覆盖率明显高于传统定位算法。

图5 定位覆盖率  下载原图

随着现代物流的发展, 流通中货物的定位需求也不断增长。本文利用RFID与WSN融合技术, 提出了一种基于普适计算环境的物流仓库定位算法。并针对定位向量进行改进, 将货物的最大移动速度引入到定位算法中, 有效的弥补了空白时间段的定位, 提高了定位的覆盖范围。