物联网环境下的物品标签有序化
袁行船*
作者简介：袁行船，(1980-)，男，工程师，主要研究方向：物联网，网络通信. E-mail: yuanxcs@163.com
（武汉数字工程研究所，武汉 430073）
5 摘要：文章提出了在物联网环境下标签的有序化组织。由于网络的层次特征，必然使得网络
拓扑结构的物理结点可以向树形结构转换，然后将物品标签向物理标签以及虚拟标签进行转
换。文章然后给出了带*管理节点特征，基于它的特征，给出了物理标签树向逻辑标签树转
换方法。然后通过生成新的上层管理节点的办法，对下层节点进行新的归并，新的管理节点
之间是有序的，从而让一个无序标签树向一个有序标签树转换。然而，这种转换存在被管理
10 节点庞大的可能，文章通过修改带*管理节点的描述，来对这种树形结构进行调整。文章紧
跟着讨论了标签注册、跟踪和注销问题以及实现这些问题的NAPTR 的方法。讨论了这种模型
的搜索复杂度。
关键词：物联网；标签；注册；跟踪；定位
 0 引言
国际电信联盟(International Telecommunication Union，简称ITU)在其名为物联网(the
Internet of things，简称IOT)的2005 年年终报告中指出，利用RFID 和Internet 可以构造一个
覆盖世界上万事万物的网络，从而实现物品的自动识别和物品信息的互联与共享[1]。如果说
35 RFID 为物品提供自我表达的能力，那么这个新型的物联网将为物品提供交流平台。
物联网尚处于萌芽阶段，当前相关研究者主要关注闭环物联网研究，重点集中在RFID
硬件设备(芯片设计[2]、天线设计[3]等)、RFID 中间件[4]等方面。关于开环的研究涉及到RFID
信息服务[5]、寻址服务[6][7]以及发现服务[8][9]等方面。
RFID 识别物品的时候，是通过物品编码来获取的，它实际上经过全球统一规划管理,
40 用于唯一标识物品编码所属编码标准的号码,就好像给每个物品贴了一个标签，本文后面用
“标签”来表示物品的编码。
参考互联网，如果物联网通过输入一个标签，然后就可以获取与标签有关的服务信息，
那么将非常适合于物品流通。于是，有人基于物联网的相关研究结果[5][6][8]，给出了物联网
的资源寻址应用可划分为5 层[10]：即物品标准寻址层、物品编码寻址层、物品发现寻址层、
 45 物品信息寻址层和物理地址寻址层。并且给出了相关概念。
将标签进行动态、有序的管理，并维护着它，是一项具有挑战的工作。文章试图从这个
角度，提出了一种物品标签组织模型及其生成方法。
1 物联网标签组织模型
从搜索的角度，作者认为标签可以根据它在形成中的不同阶段的作用，可以定义为物理
50 标签、虚拟标签、逻辑标签以及排序标签。首先介绍这几个概念：
物理标签：指一切标签在实际物联网基于互联网的结构分割形成的关系。标签之间物理
上是关联的，此空间仅仅提供物理上的查找，由于它们在逻辑上是毫无关联，将会使得标签
的查找过程相当复杂，甚至不可能进行搜索。该空间标签的查找是一个基于网络的查找。对
任何一个标签的定位都好像大海捞针。
55 虚拟标签：由于网络的VPN 技术使得结点之间即使不是一个物理区域的结点，但形成
一个虚拟专用网，那么虚拟组织之间的所有标签成为该组织的虚拟标签。对于一个物联网系
统，如果不存在VPN 组织，那么虚拟标签就不存在。相对于物理标签，虚拟标签的查找减
少了一定的查找困难，这是因为标签根据VPN 组织进行了一些划分，从而让查找简单一些，
但是对于物联网来说，虚拟标签所能提供的方便就是满足VPN 内部节点的需求，对外而言，
60 还是无法满足要求。
逻辑标签：从独立的物理标签经过映射，而转化为逻辑上有一定关联，易于管理的资源。
该标签对外可以通过一个代表向外提供标签搜索。这个代表在后文中就是管理节点，后文称
之为带*节点，将在后文详细论述。
排序标签：所有标签经过逻辑资源的演变，最终形成一个有序的层次结构，就可以依据
65 这个有序层次化结构进行匹配，不断缩小查找范围，从而迅速的进行定位和查找。
现在，我们知道物联网物品编码可以按照标签划分为物理标签、虚拟标签、逻辑标签、
排序标签，物理标签和虚拟标签基于物联网所在的互联网进行的划分，逻辑标签基于标签本
身特征进行划分，外部查找可以有借鉴和参考。排序标签是将这些个体资源按照其参数和描
述进行层次化划分。这里，主要讨论的是基于网络物理结构划分的基础上而进行的划分，从
70 而实现快速定位和查找。
下面给出一个物联网的定义：
定义1： ( , , , , , , , , , ) 1 2 G= L N E P Q C rf rq Π Π ，其中，L 为物联网中的所有标签的集合；N 和
E 是对应的网络描述，N 为网络中所有信息服务结点集合；E 表示信息结点间的邻接关系；
P 为物联网中所有最初产生标签集合，属于物理标签和虚拟标签范畴；Q为对标签的参数
75 和描述的集合，从后文可以知道，它属于逻辑标签的范畴，有了这个描述，就可以依照策略
进行定位和搜索；由于物品还会流通，定义C 为物联网中对所有被跟踪物品标签的集合（均
来自于P ，即将被消费的东西）。rf 表示标签刚产生后加入到物联网进行注册，注册函数
为rf : P → N ； rq 表示标签在异地请求获得跟踪函数，rq :C → P ； 1 Π 为所有标签基于
物联网覆盖区域和VPN 技术进行划分的，物理标签和虚拟标签基于1 Π 划分的； 2 Π 是基于
1 80 Π 划分的基础上，依据不同的策略进行新的划分，并最终具有一定的含义，逻辑标签和排
序标签基于2 Π 划分。如果一个标签资源经过2 Π 的划分，且这样建立起的模型有一定规律，
便可依据这样的规律进行标签搜索和定位。
 2 网络节点树形化
从网络最基本的域的组织关系来看，计算机与计算机之间可以按照全平、蜂窝和层次3
85 种方式组织[11]，全平是指所有结点完全对等，对于内部的每个结点的信息，外界可以看到
里面所有结点的信息。蜂窝是一个自治域，就是所有的结点分成多个小组，这些结点之间互
不相交，每个小组有一个或者多个结点作为边界，负责跟外部进行交互，外界只能看见边界
上的结点信息，而对于自治域内部的信息透明的。层次结构就是一个树型结构，结点之间是
父子关系和兄弟关系，其对孙子节点具有透明性。
90 这三种网络组织方式之间往往交错在一起，形式化的描述就是网络可表示成一个图
G' = (V ' ,E') ，其中V ' 表示路由节点集，E' 表示连接节点的通信链路集。如果对G' 进行适
当的划分，分割成多个子网络' ( ' , ' )
i i i G = V E ，对任意1 ≤ i, j ≤ n 且对于任意i ≠ j 有
' ' = ∅ ∨ ' ' = ∅
i j i j V IV E I E ，所有的子网络'
i G 之间按照全平、蜂窝或者层次方式进行组织，
如此继续对'
i G 进行划分，直到最终划分的子网只有一个节点为止。
95 关于计算机网络路由，也是按照层次的方式路由的。如果需要寻找某个自己看不到的结
点，它就通过要查找的结点的IP 地址，首先定位某个子网，再继续对子网进行定位到下一
级子网，这样，通过一层层定位，最终找到相应的结点。
2.1 基于三个基本组织方式的节点层次化
全平、蜂窝和层次结构形成计算机网络的三种基本结构，其中，关于层次结构本身就是
100 层次化，就不谈了。这里主要研究一下全平和蜂窝结构的层次化转换。
2.1.1 全平、蜂窝结构向层次结构的转换
全平是指所有结点之间的信息完全公开，蜂窝结构的网络是自治域结构网络，它的内部
节点之间路由信息是共享的，对外有一个或者多个结点作为边界，负责跟外部进行交互，外
界只能看见边界上的结点信息，而自治域内部结点对外界是透明的。对于全平结构的节点，
105 随便选择一个节点作为根节点，其它所有节点都是该节点的子节点，同时，该树结构为包含
该结构、范围更大的上一层结构的子树。对于蜂窝结构，则选择一个边界节点作为所有其它
节点的根节点。如图1 所示，对于全平结构，节点1、2、3 或4 均可作为根节点；对于蜂窝
结构，节点1、2、3 和4 作为边界节点，内部还存在其它的节点，只能选择边界节点作为根
节点。
110
图1 以结点1 为根树形结构
Fig. 1 The Tree-structed Based on Node 1
 115 2.1.2 特殊组织的物理资源树的生成
网络资源的划分，不仅仅要考虑到具体的物理拓扑结构，还要考虑虚拟组织之间资源的
共享，对于虚拟组织的层次化，各虚拟组织可以看作一个自治域蜂窝结构，单独列出来，依
然按照蜂窝模式生成自己的生成树进行层次化。
2.2 网络结构向树形结构转换算法
120 由于网络结构总体上的层层细化分割关系，使得属于任何一个辖区内的任何一个节点，
必然也是该辖区对应子树的根节点或者子孙节点，转换的方法有很多种。下面针对一个给定
的连通图G ，作者给出一种转换方法：
(1) 令G 为1 G ，置i 为1；
(2) 对i G 内部的每一个最基本的结构：这里最基本的结构指的是内部节点不再存在子
125 域。如果是树形结构，直接作为生成树；如果是全平和蜂窝结构，将其转化为一棵生成
树，取根结点代表该结构整体，这样直接包含该结构的上层结构就认为该域不存在，而
将其看作一个节点，所有与该域互连的结点变成与该根结点的互连。从而形成新的连通
图i G
(3) 重复步骤(2)，直到最终得到的i G 成为一棵树形结构1 T ；
130 (4) 置i 为1；
(5) 对i T 内所有在步骤(2)中任何子结构中，所有取代某个最基本结构整体的根结点，
按照该基本结构生成相应的生成树，而保持已有在i T 中的根节点的父子连接关系不变。
将其对应的域中以其作为根结点的所有子树整体接入该结点；
(6) 重复步骤(5)，直到所有的标签资源都在该树形结构上，记为T 。
135 3 物联网环境下排序标签的形成
对于物联网环境下的物品标签，由于每个服务节点产生出多个标签，因此所有这些标签
都是以该节点为根节点，从而形成层次化的标签结构。因此，所有的划分都是基于网络结构
划分的，属于定义1 种的1 Π 划分范畴。下面讲解以下如何对1 Π 做一个进一步的划分，使
学术论文网Tag：代写论文 代写代发论文 代发论文 职称论文发表