软件学报  2014, Vol. 25 Issue (8): 1729-1742   PDF    
面向IPv6物联子网的轻量级树型转发模型
肖融1,2, 陈文龙3, 孙波1    
1. 北京师范大学 信息科学与技术学院, 北京 100875;
2. 北京师范大学 教育学部, 北京 100875;
3. 首都师范大学 信息工程学院, 北京 100048
摘要:在IPv6 物联网中,RPL 路由模型已得到广泛的认可.然而对于规模较大的多跳网络结构,RPL 面临着部分转发节点路由容量较大的问题.而且物联子网中扁平化的地址结构使得这一问题更为突出.设计了支持IPv6 地址自动分配的轻量级树型转发模型TFAD(tree forwarding model with address automatically distributed),将物联子网中的节点构造成一棵层次转发树,树节点的IPv6 地址在子树范围内高度聚合.各节点只需存储与其子节点数相当的转发项,即可完成TFAD 模型的数据转发.此外,设计了TFAD 模型的备份父节点机制,当网络出现故障时能够以子树为单位进行网络拓扑重构,实现物联子网的快速路由恢复.实验验证了TFAD 模型的高效路由存储性能以及快速的路由学习能力和故障后路由恢复能力.
关键词物联网     转发树     子树地址范围     层次比特位    
Light Weight and Tree-Based Forwarding Model in IPv6 IoT Subnet
XIAO Rong1,2, CHEN Wen-Long3, SUN Bo1    
1. College of Information Science and Technology, Beijing Normal University, Beijing 100875, China;
2. Faculty of Education, Beijing Normal University, Beijing 100875, China;
3. College of Information Engineering, Capital Normal University, Beijing 100048, China
Corresponding author: CHEN Wen-Long, E-mail: wenlongchen@sina.com
Abstract: RPL has received universal acceptance in IPv6 routing of the Internet of things (IoT). However, for large-scale multi-hops networks, the RPL routing model is faced with the problem that some IoT nodes heavily consume routing table storage. Besides, the flattened address architecture in IoT subnet makes this problem more prominent. In this paper, TFAD (tree forwarding model with address automatically distributed), a light-weight and tree-based forwarding model, is proposed to support automatic IPv6 address assignment. TFAD constructs a forwarding-level-tree for all the IoT nodes that make the IPv6 addresses of nodes aggregate highly in each sub-tree. In TFAD, each node only needs to maintain a few forwarding entries, the number of which is equivalent to the number of its direct son-nodes. Moreover, the backup mechanism of parent node in TFAD is designed. This mechanism supports the network topology reconstitution based on the whole sub-tree, achieving fast route-recovery from network failure. The experiments based on real sensor nodes prove that TFAD model possesses not only high performance on routing table storage but also rapidity on routing table learning and routing recovery from failure.
Key words: Internet of things     forwarding tree     address range of sub-tree     lay bit    

物联网被视为现有互联网的延伸和扩展[1],它将在环境监测、健康医疗、智能家居等各个领域被广泛实施.物联网节点的海量部署及其与传统互联网系统直连直通的诉求,都希望物联网能有一种普适的、开放的节点标识机制.显然,IP技术是最佳选择.由于互联网IPv4地址即将耗尽[2],学术界普遍认为:物联网必定与IPv6技术相结合,通过IPv6地址来标识各种传感器节点[3,4].IETF已成立多个工作组研究IPv6物联网技术,其中,ROLL工作组专门针对物联网路由问题设计了RPL协议[5].然而在规模较大的多跳网络结构中,RPL协议会给部分路由节点带来较大的转发项存储及处理开销.另外,物联网节点操作系统普遍使用SLAAC(stateless address auto configuration)地址分配机制[6],易形成扁平化、难聚合的子网地址结构,对网络路由性能的提升造成障碍.

针对IPv6物联网的路由转发问题,本文提出了一种支持地址自动分配的轻量级树型转发模型(tree forwarding model with address automatically distributed,简称TFAD).TFAD模型主要适用于网络拓扑相对稳定的物联网环境,它以物联子网网关节点为树根,将所有节点构建成一棵层次转发树.在转发树中,每个节点都按照指定规则从其父节点继承一块IPv6地址块,并将地址分配给它的子节点.这样,转发树中任何一棵子树都拥有一个高度聚合的子树地址范围.当然,如果某个节点获得了一个子树地址范围却又没下连足够多的子孙节点,就会出现地 址空间的浪费.尽管TFAD模型会消耗略多的地址空间,但这种IPv6层次地址结构非常规整,转发树中的节点只需存储极少的转发条目,即可实现物联子网节点的双向转发通信.而且,节点的转发项存储容量只与其直连子节点数相关.

TFAD模型具有如下特点:1) 路由协议交互简单,节点间父子关系构建后,根据父节点的所辖前缀完成子节点的IP配置,与上下游其他节点无关,能够确保较快的路由收敛能力;2) 节点转发项数量较少,每个节点的转发项数与直连子节点数相当,极大地减少了树节点的内存消耗,具有很好的路由可扩展性;3) 快速路由恢复,以子树为单位进行拓扑重构以及事先选择备份父节点,可实现链路故障后物联子网路由体系的快速稳定.

本文第1节介绍相关研究工作.第2节介绍TFAD模型的核心思想及相关定义.第3节介绍TFAD转发树的构建方法.第4节介绍节点的转发信息存储方法及报文转发处理流程.第5节对TFAD模型进行组网实验及性能分析.第6节总结全文.

1 相关研究

IPv6物联网结构有如下主要特点:1) 资源受限.不仅是计算机系统的3大传统资源(处理器、存储、带宽)在物联网环境中大幅受限,无源供电环境导致节点的供电能力也极为有限[7].因此,轻量级协议机制成为物联网体系的研究重点.2) 节点的多重角色.不同于传统互联网,物联网的节点还需具有自路由能力[8],为其他节点提供数据转发等功能.3) 新型链路层协议.IPv6物联网的链 路层主要基于802.15.4低功耗协议[9]实现,它使用8个字节的链路层MAC地址.802.15.4协议具有复杂度低、成本小、功耗小等特点.此外,IETF专门成立了6LoWPAN工作组[10],为IEEE 802.15.4设计适配层使其支持IPv6.所以,IPv6物联网转发模型面临着新的挑战,本文的轻量级转发模型也是基于上述特点展开研究.

互联网中任何一套路由转发体系都与其网络节点标识机制密不可分,节点标识是网络路由转发的前提和基础.传统传感器网络部署时,常在所辖范围内自主设置节点标识,文献[11,12]就研究了树型ID标识分配及标识压缩方法.自主标识机制简单易实施,但却无法支持传感器网络节点与互联网系统的端到端通信.文献[3]从多个角度阐述了物联网节点使用IP地址作为节点标识的优势,包括良好的开放性和可扩展性、支持轻量级协议栈实现、支持多样的上层应用、已得到广泛实施、支持端到端通信等等.文献[13]也强调物联网设计与实现的统一性,IP技术则可为该目标提供统一的标识支撑.可见,物联网必将与IP技术相结合.同时,由于互联网的大规模发展导致IPv4地址即将耗尽,互联网本身也正从IPv4向IPv6过渡.所以,物联网环境使用IPv6地址作为节点标识是必然趋势.

现有IPv6网络主要通过ND协议或DHCPv6协议实现端系统的地址自动配置.IPv6设计了邻居发现协议(ND)进行全局地址的无状态自动配置,由节点的第1跳路由器通过路由器公告(RA)消息向网络节点发布64位前缀,各节点将其与EUI-64链路层地址结合生成全局IPv6地址[6].另外,IPv6网络还可利用DHCPv6机制实施节点的有状态全局地址分配[14].通过DHCP和ND机制进行地址分配,逻辑上都要求端系统与地址分配设备(网关路由器或DHCP服务器)直连通信.并且,子网中节点的地址是扁平结构,没有任何层次性,非常不利于物联子网中多跳寻径.可见,DHCP和ND协议都无法直接施用于现有物联网典型树型结构.针对上述问题,本文面向物联网结构设计了特定的地址分配机制,为轻量级转发模型提供支撑.

作为无线传感器网络的最核心技术,路由及转发模型一直是学术研究的重要关注点.文献[15,16]对无线传感器网络路由协议进行了归纳和总结,包括层次结构和数据中心等多种路由转发模型.

层次结构路由是无线传感器网络中广泛研究的路由技术[17].它将节点分为不同层次的若干组,每组只有组头节点代表一个组与外部进行路由交互,并严格遵循层次隶属关系[18].层次路由的典型代表是分簇路由[19].它根据不同方法将传感器节点分成相应的簇,并在各节点簇中选举一个簇头节点,通过节点的多跳通信和分层路由来节约能耗,从而实现较大规模无线传感器网络节点的分级通信.TEEN(threshold sensitive energy efficient sensor network protocol)[20]还通过簇头在簇内设置阈值,减少传感信息的发送次数.然而,分簇路由需要节点支持专门的簇头选举协议.而且,如果无法解决节点标识的聚合问题,簇间路由协议交互及节点存储仍较为复杂.

数据中心路由协议围绕着传感信息到sink节点的传递方式进行描述.SPIN(sensor protocols for information via negotiation)[21]定义了元数据,对传感信息进行描述,并在节点间协商元数据,减少冗余信息的传递.LEACH (low-energy adaptive clustering hierarchy)[22]很好地与分簇路由思想结合在一起,传感节点向着sink节点发送信息,簇头节点会依据特定规则进行数据的聚集,从而减少数据传递并降低网络能耗.在近期研究中,文献[23]还介绍了一种新型的基于移动人员的物联网数据采集方法.它依据移动人员所在位置,不断构 建或更新数据转发树实施传感信息采集.当然,它只适用一些特定的物联网场景.汇聚树协议(collection tree protocol,简称CTP)[24,25]面向数据汇报场景提供了一种传感节点向根节点的数据通信方法,它与节点地址无关,每个节点根据路径链路质量选择最优父节点.节点发现父节点失效后,会按照同样的方法重新选择新的父节点.而且,CTP只关注上行消息,本文TFAD模型可关注双向通信,并由于节点地址在子树范围高度聚合,TFAD还可支持链路故障时以子树为单位切换父节点.AODV(ad hoc on-demand distance vector routing)是无线网络领域较为经典的一种路由协 议[26],它专为无线自组织网络设计,也可归为数据中心路由协议.AODV协议由源节点以组播形式发送路由请求,接收到请求的节点继续转发该组播路由请求,一直洪泛到目标节点或是某个已知去往目标节点路由的节点.AODV协议还通过定期广播Hello报文来维护路由.AODV协议的交互开销很大,并不适合大多数物联网 场景.

目前,针对IPv6无线传感器网络,最为业界认可的路由协议当属IETF的ROLL工作组为低功耗有损网络设计的RPL路由协议[5].现有典型物联网操作系统Contiki[27]和TinyOS[28]都能很好地支持RPL协议.该协议将物联网节点构建成树状有向无环结构,并简单地将数据传递分为上行和下行两个方向.其中,下行数据传递支持存储模式和非存储模式.在存储模式中,每个节点会存储以其为根的子树所辖节点的路由,并以此完成路由转发.在非存储模式中,sink节点之外的其他节点不存储路由信息,下行数据通过源路由IP选项头指定转发路径.由于IP源路由并不受业界广为接纳,现有实现主要通过存储模式进行下行数据转发.此外,该路由协议基于邻居发现机制(ND)实施网络节点的IPv6地址配置,网络地址仍然是扁平状结构,这使得转发树中sink节点或靠近树根的节点要存储大量的路由信息,导致了较 低的存储性能.本文的TFAD模型在这方面有了明显的改善.

上述研究成果为本文工作提供了重要参考.然而,现有路由转发模型都没有很好地与节点标识研究融合,也没有解决节点标识的聚合问题.在IPv6物联网中,不可聚合或没有层次关系的地址结构将导致网络需要交互并存储大量的路由信息.本文设计了基于子树可聚合的地址结构,进而构建轻量级树状路由转发模型.

2 支持地址自动分配的树型转发模型

网络节点的标识体系总是与整个网络的路由转发体系密不可分,一个合理、高效的地址分配体系有利于高效转发体系的构建.我们认为,IPv6物联子网的地址管理及路由转发应满足如下基本目标:低负载的路由交互、轻量级转发引擎、支持网络节点IPv6地址的简单配置管理.

面向IPv6物联子网的特定网络环境,并针对上述地址管理和转发机制的基本目标,本文设计了支持地址自动分配的树型转发模型TFAD.该模型中,所有物联网节点以网关节点为根,构造成一棵层次转发树.树型转发模型中的节点都具有明确的层数属性,用以描述该节点到根节点的跳数距离.例如,根节点的层数为0,根节点的直连子节点的层数为1,其他节点的层数是其父节点的层数加1.每一节点都按照指定规则从其父节点继承一块IPv6地址块,并根据同样规则分配给其所辖子节点 ,节点地址都可在节点所属子树范围内高度聚合.由于节点地址在层次转发树中高度聚合,父、子节点间进行简单的协议交互即可完成转发信息的学习,每个节点只需存储少量的转发条目即可完成数据转发.

定义1(层次比特位(lay bit,简称LB)). 层次比特位是128位IPv6地址中除去网络位之外的若干连续bit位,TFAD模型中,利用层次比特位标识树型结构中同一层的不同兄弟节点及其所辖子树.

为不失一般性,本文以特定64位子网地址范围进行分析,即假设整个物联子网分得一个“2500::/64”IPv6网络地址段,每层的层数比特位都为16位,共有5层.此时,层次比特位是IPv6地址中第65位~第128位间的某16个连续bit位.图 1就是TFAD模型在该物联子网构建的树型网络拓扑,节点地址中,带下划线部分就是该节点的层次比特位取值.例如,节点2~节点4是同层兄弟节点,拥有相同的16位层次比特位(第65位~第80位),它们通过层次比特位的不同取值来标识各自的节点子树.同理,节点5、节点6也拥有相同位置的16位层次比特位(第81位~第96位),并且取值各不相同.此外,图 1中各节点标有对应的IP前缀,表示该节点所辖子树的地址范围.例如,节点3所辖子树的地址范围是2500::0002:0:0:0/80,节 点 5~节点10的地址都属于该范围.图 1中,不同层节点管辖不同大小的地址范围,对应地址范围的掩码长度分别为64,80,96,112,128,其中,最底层叶子节点管辖地址范围的掩码长度为128,即只管辖自身1个节点.需要说明的是,TFAD模型实际部署时,可根据具体情况设置不同的物联子网地址范围、层数和各层的层次比特位数.为便于描述,本文有如表 1所示的符号定义.

Fig. 1 An example of network topology for TFAD图 1 TFAD网络拓扑示例

Table 1 Symbols definition of TFAD model 表 1 TFAD模型符号定义

定义2(底层节点). 在层次转发树中,层数为Lmax的节点称为底层节点,否则称为非底层节点.

一个节点只要它的层数小于Lmax,即使没有子节点,仍被称为非底层节点.显然,底层节点不能再连接子节点,而非底层节点可以下连子节点.图 1中,实心节点为底层节点,空心节点为非底层节点.例如,节点2虽然并未下连子节点,但其层数小于Lmax,属于非底层节点,它可以下连子节点.

定义3(叶子节点). 在层次转发树中,没有下连子节点的节点为叶子节点.

叶子节点与底层节点不是同一概念.图 1中,节点4和节点6都是叶子节点,但却不是底层节点.

定义4(子树地址范围(address range of sub-tree,简称ARST)). 在TFAD模型中,任一树节点Ni都拥有一个特定的子树地址范围ARST[i],以Ni为根的子树中所有节点的IP地址都属于ARST[i].子树地址范围是一个IPv6网段,具体描述为ARST[i].IP/ARST[i].len.例如,图 1中节点3的子树地址范围是2500::0002:0:0:0/80.另外,底层节点的子树地址范围只辖一个IPv6地址,即节点自身的地址,此时& lt; /span>ARST[i].len=128.

定义5(子树地址范围派生Inherit). 父节点根据自身地址范围ARST[f]及子节点层次比特位取值Ns.val,派生出子节点的子树地址范围ARST[s],记作ARST[s]=Inherit(ARST[f]).有:ARST[s].len=ARST[f].len+LB[Ns.lay].n,并且ARST[s].IPARST[f].IP在对应层次比特位上补上子节点Ns的层次比特位取值Ns.val而得.

TFAD模型中的节点都有对应的子树地址范围,是其父节点的地址范围与自身的层次比特位取值结合而得.以图 1为例,节点N5的子树地址范围为“2500::0002:0001:0:0/96”,是由父节点N3的子树地址范围“2500::0002: 0:0:0/80”与N5自己的层次比特位“::0001:0:0”(下划线所指即为层次比特位)结合而得.

TFAD模型以物联子网网关为根节点,构造一棵层次转发树.树中节点根据其所在的层次位置,拥有特定的IPv6子树地址范围.由于树节点IPv6地址具有严格的层次隶属关系,TFAD模型各节点能够以极少的转发信息完成物联子网的数据转发过程.基本思想描述如下:

1) 节点IPv6地址自动配置.

物联子网中所有节点的子网掩码都为64位,节点IPv6地址根据其子树地址范围生成.如图 1中,节点3的子树地址范围为“2500::0002:0:0:0/80”,则节点3的地址为“2500::0002:0:0:0/64”.由于IP地址在主机部分不能全为0和全为1,所以对转发树部分节点的地址配置需要有特殊考虑.树根节点地址设置为子树地址范围加1,图 1中节 点1的IPv6地址为2500::1/64.另外,IP地址主机位全为1的节点不允许接入层次转发树,如图 1网络拓扑中,不能接入1个IP地址为2500:FFFF:FFFF:FFFF:FFFF/64的底层节点.

2) 数据转发.

物联子网节点的数据处理可分为上行转发过程(向着树根节点方向)和下行转发过程(向着树叶节点方向),这两个转发过程可覆盖物联子网内部节点间通信、物联子网节点与互联网节点间的通信.节点Ni收到一个待转发的数据报,若报文目的IPv6地址属于节点Ni所辖的子树地址范围ARST[i],则将向其子树中某个直连子节点转发,即为下行转发;否则,向其父节点转发,则为上行转发.

3) 路由学习与转发信息存储.

转发树中,任意父子节点间都有明确的子树地址范围隶属关系,构成天然的寻径体系.所以,TFAD模型路由协议交互简单,建立好单跳父子节点关系并分配好IP地址,转发路径也就随之建立.网络节点的转发信息包括各直连子节点的层次比特位和链路层MAC地址的对应项,还包括父节点的链路层MAC地址.图 1中,节点3的转发信息包括层次比特位“0001”对应链路地址为 M5、层次比特位“FFFF”对应链路地址为M6等等.此外,节点3还需存储父节点的链路地址M1.

定义6(路由恢复时间). 在TFAD模型中,无线网络拓扑变化会导致若干节点到根节点的短暂数据传输中断,从传输中断到传输恢复正常的时间段称为路由恢复时间.路由恢复时间与特定网络结构、特定网络状态相关.需要强调,节点间的正常传输包括双向可达.

TFAD模型支持以子树为单位进行拓扑重构,从而实现网络故障后的快速路由恢复机制.在层次转发树中,每一节点都会预先设置备份父节点,备份父节点的层数必须不大于父节点的层数,并且尽可能地接近父节点的层数.这样,节点或链路故障时即可实施子树整体迁移,实现节点路由的快速恢复.快速恢复机制详见第3节.

3 转发树构建方法

首先,需要对物联子网根节点进行初始化配置.根节点实际还充当物联网节点与传统互联网通信的网关.根节点与其子节点的通信接口称为下连接口,与互联网相连的接口为上连接口.需要给根节点指定该物联子网的64位IPv6地址前缀PFX64,根节点下连接口的IPv6地址为PFX64+1,掩码长度为64.显然,根节点的子树地址范围就是PFX64.另外,根节点上连 接口以传统方式接入IPv6互联网,并向外发布PFX64对应的物联子网路由.

接着,物联子网各节点按照指定规则依次加入层次转发树.在TFAD模型中,物联子网中新增节点会通过广播“Hello请求报文”探测直连邻居节点,已加入转发树的节点收到“Hello请求报文”后会发送“Hello应答报文”.两种Hello报文主要字段包括:“层数”描述报文发送节点Ni的层数,即& lt; span lang="EN-US" style='color:black' xml:lang="EN-US">Ni.lay;“剩余连接数”描述报文发送节点Ni还可接收的子节点数,即Ni.rem字段.对于尚未加入转发树的节点,其Hello报文中节点层数设置为-1.当一个新节点Nn准备加入层次转发树时,它会通过Hello报文搜寻其一跳可达的邻居节点,确定一个尽量 靠 近转发树根(即层数较小)的邻居节点作为父节点Nf.新节点Nn通过节点Nf加入物联子网的层次转发树中.

TFAD模型的核心思想是:将物联子网中的节点构造成一棵层次转发树,并且树节点的IPv6地址在子树范围内高度聚合,使得节点根据子节点地址信息就可完成数据转发.层次转发树的构建过程主要考虑两个较为典型的度量参数:子节点数和到网关的转发跳数.下连子节点数的限制是为了各节点的转发负载均衡,转发跳数最少是为了数据快速到达网关.实际部署中,可根据特定环境及需求选择其他度量参数来决定层次转发树的构造方法.

节点Nn加入物联子网的过程,即Nn发现父节点的过程,描述为PROC_1,具体步骤如下:

1) Nn启动邻居搜寻超时定时器TM1,超时时间为t1.

2) 在t1时间段内,新节点Nn通过Hello报文搜寻其能够一跳连接的所有邻居节点集合S1.

3) TM1超时后,如果S1为空,则重新跳转到步骤1;否则,在S1中挑选已连入层次转发树(即该节点层数不为负数)且子节点数尚未达到最大值(即还可接收子节点数大于0)的节点,令此集合为S2,满足:S2={Ni| Ni.lay≥0ÙNi.rem>0};如果集合S2为空,则重新跳转到步骤1).

4) 如果节点Nn没有父节点,则执行步骤5);如果节点Nn已有父节点Nf但没有备份父节点,则跳转到步骤7).

5) 在S2中挑选层数最小的节点集合(可能有多个节点同时为层数最小),令此集合为S3,满足:S3={Ni| Ni.layNj.lay,"NjÎS2};显然,由于S2不为空,则S3必定不为空.

6) 如在S3中只有1个节点,则它成为新节点Nn的接入父节点Nf,重新跳转到步骤1)(寻找备份父节点);否则,表示有多个节点共同满足层数最小,则选择子节点数最少的两个节点,这两个节点的子节点数可能相同,也可能不同.在这两个节点中,选择子节点数最小的节点(如果两个节点的子节点数相同,则任选一个)为父节点Nf,选择另一个节点作为备份父节点Nb,备份父节点Nb.rem减1.然后删除定时器TM1,算法结束.

7) 在S2中挑选出层数小于或等于父节点层数,且与父节点层数尽量接近的节点组成集合S4.满足:S4= {Ni|(Ni.layNf.lay)Ù(Nf.lay-Ni.lay)≤(Nf.lay-Nj.lay),"NjÎS2}.

8) 如果S4为空,则重新跳转到步骤1);否则,转到步骤9).

9) 如在S4中只有1个节点,则它成为节点Nn的备份父节点Nb;否则,选择子节点数最小的节点(如果有多个子节点数最小的节点,则任选一个)为备份父节点Nb,备份父节点Nb.rem减1.然后删除定时器TM1,算法结束.

父节点发现过程利用邻居搜寻定时器TM1,基本能够确保节点Nn通过最优的父节点接入层次转发树.此后,考虑拓扑的稳定性以及父节点切换代价,节点在能正常工作的情况下不会再寻找更优父节点.当然,如果父节点及备份父节点全部失效,节点Nn将重新启动PROC_1过程,寻找新的最优父节点并加入转发树.

新增节点Nn确定父节点后,将向父节点发送“节点加入请求报文”,父节点回送“节点加入应答报文”,相互获得路由转发所需信息.具体步骤描述为PROC_2.

1) 新增节点Nn向父节点发送“节点加入请求报文”,通告自身的MAC地址.

2) 父节点Nf接收到Nn的“节点加入请求报文”后,将可接入子节点数Nj.rem减1.

3) Nf为新增子节点Nn分配层次比特位Nn.val;若NnNf的第k个子节点,则新增节点的层次比特位取值:Nn.val=k.

4) 父节点增加一条转发项,即子节点Nn的层次比特位以及对应子节点的MAC地址所组成的转发信息项:(Nn.val,Mn).

5) 父节点计算新增子节点Nn的子树地址范围ARST[n],并向Nn发送“节点加入应答报文”通告Nn对应的子树地址范围,有:ARST[n]=Inherit(ARST[f]).

6) 新增节点Nn获取自己处于转发树的层数:Nn.lay=Nf.lay+1,并根据协议报文存储父节点的链路层地址为Mf.

7) Nn设置自身IPv6地址为ARST[n].IP/64.

在TFAD模型中,节点加入到层次转发树的过程涵盖了节点的地址分配及转发信息生成,整个过程涉及4种协议报文:Hello请求、Hello应答、节点加入请求、节点加入应答.TFAD转发树构造过程包含了节点地址分配机制,能确保节点IP地址总能在子树范围聚合成一个网络前缀,这使得节点的转发项数很少,是直连子节点数加1.而且,TFAD的路由收敛时间相对较短,新节点的加入只对其直连父节点产生影响,无需向根节点层层通告.反之,在RPL模型中,新节点加入到树型拓扑时必须由其父节点向着根节点的方向层层通告,构建新增节点的下行路由通道.

TFAD模型备份父节点机制可有效实现网络故障时的快速路由恢复,每个节点都会尽力寻找备份父节点.当节点Ni发现与父节点的无线链路失效时,若有备份父节点Nb,则会将Ni为根的转发子树整体移动到备份父节点的子树中.当然,若Ni无下连子节点,则会以单个节点实施父节点切换.对于TFAD模型中的任一节点Ni,其备份父节点的层数总是不大于父节点的层数,该特性确保了链路失效时以Ni为根的转发子树整体移动的可行性.需要说明:拥有同一父节点的兄弟节点可能拥有不同的备份父节点,当父节点失效时,它们会选择各自的备份父节点作为自己新的父节点.

节点与备份父节点确定父子关系后,参照PROC_2完成信息交互,不同的是:Nb.rem不需要减1,因为在PROC_1中Nb.rem已经减1.这样可以保证当备份父节点Nb切换为Ni的父节点时,以Ni为根的转发子树一定能连接到Nb节点.另外,由于此时Ni是带着一棵子树加入到Nb子树,还需从Ni开始,朝着树叶方向依次向各自的子节点通告新的子树地址范围和各节点所在层数.最重要的是:受影响子树中各节点的转发表项,在子树迁移过程中无需修改.所以,以子树为单位的拓扑重构过程极为简单,能够实现故障时的快速路由恢复.

假设图 2(a)为前期稳定状态时的某个转发树拓扑.当节点N5发现与节点N3的无线链路发生故障,则会将以N5为根的子树整体切换到备份父节点的子树中.有两种可能的切换结果:第1种情况是备份节点与父节点在同一层,第2种情况是备份节点比父节点的层数要小.情况1如图 2(b)所示 ,若N5的备份父节点为N2,则N2N5参照PROC_2交互信息,构建新的转发项.此外,N2还需向N5子树层层发布新的子树地址范围.不过,由于N5子树的 层次比特位分配没有变化,所以整个N5子树节点的转发表无需改变.情况2如图 2(c)所示,若N5的备份父节点为N1,除了完成情况1所述工作,还需将N5子树中各节点的层数减1.

Fig. 2 Rapid routing recovery after link failure图 2 链路故障后的路由快速恢复

Ni没有备份父节点,则需通知其子树中所有节点解散,让它们各自重新寻找新的父节点.当然,在这种情况下,也可以设计其他优化算法来实现该子树某一部分整体移动.另外,还可以设计预留资源方法确保转发树中各节点都能拥有一个备份父节点.限于篇幅,本文不对上述机制详细描述.

对于子节点Ni的离开,其原父节点Nf需要完成资源回收及信息更新.主要行为描述为PROC_3.需要说明:若离开的节点Ni下连一个子树,父节点的行为也是如此.

1) 父节点Nf的可接入子节点数Nf.rem加1;

2) Nf回收子节点Ni对应的层次比特位,可供以后的新增子节点使用;

3) 父节点删除Ni对应的转发项:(Ni.val,Mi).

此外,TFAD模型能够方便地实施规模扩展.如图 3所示,对于规模更大的物联子网环境,可构造基于TFAD的层次路由体系.整个物联子网包括多个网关,每个网关都是一个TFAD层次结构的根节点,各网关可按照传统域内路由协议互连,并与互联网连接.当然,层次路由体系中每个根节点需要发布其转发树标识以相互区分,协议交互更为复杂,本文专注于单棵转发树的路由转发分析,对多层路由体系不做细述.

Fig. 3 Hierarchical routing architecture with multi-gateway based on TFAD图 3 基于TFAD的多网关层次路由体系
4 表项存储及转发处理

对于TFAD模型转发树中的任一节点Ni,其转发项结构为

(LB[j],MACj),0≤jNUMson.

该转发项用于存储Ni的第j个子节点的层次比特位及其MAC地址.当j为0时,该转发项对应LB[j]的值为0,MACj存储了Ni的父节点MAC地址.根据前文所述,层次比特位位数最多为16,占2Bytes,加上8Bytes的MAC地址,一条转发项只需占用10Bytes.典型IPv6路由系统中,一条IPv6转发项的长度至少为25Bytes(16字节的目的网段、1字节的掩码长度、8字节的下一跳链路地址).本文设计的TFAD转发项的长度为10个字节,只是原来的40%,极大地节省了节点存储资源.除主体转发项外,节点Ni还要存储其子树地址范围ARST[i],可据此判断一个报文的目的端是否属于Ni子树.

图 4是层次转发树中,某节点Ni的报文转发处理过程.由于TFAD模型中各节点IP地址是严格按子树聚合,所以可根据目的地址是否属于Ni的子树地址范围来判断上行流量和下行流量.上行流量转发给Ni的父节点,下行流量通过转发表查询发送给Ni的某个子节点.具体步骤如下:

Fig. 4 Packets forwarding procedure图 4 报文转发过程

1) 通过无线接口收到一个IPv6报文,取其目的IPv6地址IPdest.

2) 若IPdest属于节点Ni的子树地址范围ARST[i],则说明目标节点处在以Ni为根的子树中,跳转至步骤4);若IPdest不属于ARST[i],则执行步骤3).

3) 若此报文源MAC地址为Ni父节点的链路层地址,则说明发生路由环,丢弃报文,转发结束;否则,转发报文给Ni的父节点,父节点链路层地址为转发表中的(0,MAC0)转发项的MAC0,转发结束.

4) 若IPdest为本节点地址,则提交上层协议处理,转发结束;否则,执行步骤5).

5) 取IPdest中对应Ni节点层次比特位的值,即IPdest中从第LB[Ni.lay].b位开始,到第(LB[Ni.lay].b+ LB[Ni.lay].n-1)位的取值,并在转发表中查找匹配项;若查找失败,则丢弃报文,结束;若匹配成功,则将报文转发到匹配项对应的链路层地址.

TFAD转发模型有如下特点:1) 3层路由转发与2层链路地址查找集成在一起,可快速完成整个转发处理过程;2) 转发表项简单、实用,只存储“层次比特位”与对应的MAC地址;3) 可支持链路故障时转发系统的快速恢复,子树整体切换时无需修改大多数节点的主体转发表项.

5 实验及性能分析

在TFAD模型中,由于节点只存储各子节点层次比特位和对应的链路层地址,存储性能有较大的优化.为了方便分析,令构建的转发拓扑为满m叉树,即,除了底层节点以外,每个节点都有m个子节点,共有n层.其中,第0层有1个根节点,第1层有m个节点,第i层有mi个节点.为了便于分析,我们不考虑第2节所述的IP地址主机位全为1的节点.令转发树中节点总数为Numnodes,则有:

TFAD模型中,每个非底层节点存储的转发项数为(m+1),即,m项子节点和1项父节点的转发信息;另外,底层节点只需存储1项父节点的转发信息.因此,可计算TFAD模型所有非底层节点转发项数共为所有底层节点转发项数共为mn-1.所以,转发树所有节点转发项数为

本文以RPL转发模型为比较对象,对TFAD转发表存储性能进行分析.RPL模型中,每个节点也需存储1项父节点的转发信息;另外,还需为其所有的子孙节点存储转发信息.第0层根节点转发项数为第1层共有m1个节点,每个节点转发项数为以此类推,第j层共有mj个节点,每个节点转发项数为满足j<n-1.另外,共有mn-1个底层节点,它们只需存储1项父节点转发信息.所以,RPL模型中所有节点转发项数为

显然,TFAD模型中整个转发树的转发项数量相对于RPL模型有大幅减少.继续分析单节点转发项数量,令转发树中各节点的子节点数m分别为1,2,3,针对5层树结构比较RPL模型与TFAD模型的单节点转发表容量,如图 5所示.两种模型的底层节点,都只需存储去往父节点的1条转发项.当m等于1时,即物联子网为线型连接拓扑.对于靠近树根的节点,RPL模型转发项数比TFAD模型略多,并且越往叶子节点靠近,转发项数差异越小.然而随着子节点数m的增长,RPL模型中靠近树根的节点转发项数却急剧增长.但TFAD模型中各节点存储的转发项数只与其直连子节点数相当,不会随着层数减小而增长.此外,TFAD模型节点的小容量转发表,还可提高报文转发过程中表项的匹配速度.所以,与RPL模型相比,TFAD模型对物联网节点的转发性能也有较大提高.

Fig. 5 Analysis of forwarding items number of one node in TFAD model图 5 TFAD模型单节点转发项数分析

本文通过真实物联网节点组网,测试了TFAD模型的路由性能,节点参数描述见表 2.

Table 2 Parameters of IOT nodes 表 2 物联网节点参数

实验在各个节点的链路层实施MAC地址过滤,构建图 6(a)所示的典型网络拓扑结构.通过同类型无线节点集成串口,与普通主机连接,形成报文监控节点.监控节点可捕获802.15.4协议报文,并在Wireshark工具中显示抓包信息.实验中,设置各节点加入路由树后会定时向节点1发送类似PING机制的echo request报文,节点1收到后会回送echo reply报文.那么,各节点路由学习成功后会在图 6椭圆范围出现相应的双向通信报文.实验通过各节点首次与节点1正常双向通信来判定其路由学习完成时间.所以,实验中只需部署一个监控节点,对图 6中的椭圆范围进行报文捕获,即可获得各节点路由学习时间.

Fig. 6 Topology of network with real nodes图 6 真实节点网络拓扑

分别在各节点中实施RPL模型和TFAD模型,RPL协议是Contiki操作系统自带功能,并且节点加入方式为主动请求方式.图 7介绍了两种模型在Contiki中实现的功能结构图,给出了与本文相关的主要功能函数.图 7(a)描述了RPL的主要功能模块.控制层面:RPL协议收到DAO报文[5]后,生成路由项并添加到全局路由表中.数据层面:底层接收报文后进行分析,将目的IP地址为本地的报文交由应用层处理,也包括路由协议报文.对于其他报文实施转发处理,查找路由获得下一跳地址,继续查找邻居MAC地址并通过6LoWPAN封装发送.图 7(b)是本文设计的TFAD模型基本实现,浅灰色的模块与RPL不同,其他模 块的实现与RPL相同.控制层面:收到新的子节点加入请求则增加转发项,转发项包含子节点的层次比特位及该节点的MAC地址.数据层面:转发处理与RPL有明显差异,由于转发项包含MAC地址,则无需再查找邻居MAC地址.

Fig. 7 Contiki-Based implementation of two forwarding models图 7 两种转发模型基于Contiki的实现

图 8是两种模型下不同层数节点多次实验的路由学习时间分析,每层节点取20次实验数据.对于第1层节点,两种模型的路由学习时间相差无几;但对于2层及2层以上节点,TFAD模型中节点路由学习速度明显优于RPL模型.而且,随着节点所处层数的增加,两种模型中节点的路由学习时间差更为明显.所以,对于无线节点构成的层次拓扑树,其层数越大,则TFAD模型的快速路由学习优势就更为明显.实验中发生的无线传输偶尔丢包,会导致路由学习时间的延长,表现为图 8中折线的突然升高.

Fig. 8 Time for achieving routes of nodes with different layers 图 8 不同层数节点获取路由时间

本文还基于图 6(a)拓扑进行了两种模型网络状态变化后的路由恢复实验.基于图 6(a)拓扑的网络稳定后,将节点2和节点4关闭,网络拓扑变化为图 6(b).其中,节点5为根的子树(子树1)将以节点1为自己新的父节点,该子树所有节点的层数都发生了变化;节点6为根的子树(子树2)将以节点3为自己新的父节点,该子树所有节点的层数都未发生变化.在TFAD实验中,图 6(a)拓扑稳定时节点5的备份父节点为节点1,节点6的备份父节点为节点3.整个实验仍通过监控节点捕获报文,当节点Ni能与节点1正常双向通信,才认为节点Ni的路由恢复 正常.

在上述网络拓扑变化情况下,TFAD模型和RPL模型中不同层数节点的路由恢复时间如图 9所示.受影响子树的第0层节点在TFAD模型与RPL模型中的路由恢复时间相差不大,如图 9(a)所示,这是因为切换过程涉及的协议控制报文数量相当.然而对于受影响子树的其他节点,TFAD模型的路由恢复时间却有较为明显的优势,如图 9(b)和图 9(c)所示.而且,无论备份父节点与父节点层数是否相同,路由恢复实验中所有节点在TFAD模型中的路由恢复时间都较短并且变化不大.此外,针对受影响子树部署监控节点,捕获协议报文进行分析,可以发现:TFAD模型在子树整体迁移过程中,只需要极少的控制消息,主要用于通告子树地址范围和各节点所在层数的变化;而且,TFAD模型的网络拓扑变化不用像RPL模型那样层层向上通告,而只需向新的父节点通告即可.这也是TFAD模型快速路由恢复的一个关键因 素.

Fig. 9 Routing recovery time of nodes with different layers in the influenced sub-tree图 9 受影响子树中不同层数节点路由恢复时间

综上可知:在多跳(2跳以上)路由结构中,TFAD模型的路由学习速度和网络状态变化后的路由恢复速度都比RPL模型有较大的优势;而且随着网络路由跳数增大及各节点子节点数增多,TFAD比RPL具有更好的路由存储性能.TFAD模型付出的代价是IPv6地址空间的低利用率,具体的利用率与实际部署情况相关.TFAD和RPL路由模型的各项性能比较见表 3.

Table 3 Performance comparison for two models 表 3 两种模型的性能比较
6 总 结

RPL协议是IPv6物联网中最广为认可的路由机制,但在规模略大的多跳网络结构中,面临着转发节点存储及处理负载过重的问题.而且,物联网中扁平化IPv6地址体系使得这一问题更加突出.本文设计了节点地址可基于子树聚合的轻量级转发模型TFAD,将物联网节点构造成一棵层次转发树,每一子树中的节点地址总能汇聚为一个IPv6网段.各节点只需存储与其子节点数相当的转发项,即可支持TFAD模型的数据转发,极大地减少了树节点的存储消耗,具有很好的路由可扩展 性.性能分析表明:随着网络规模的逐渐增大,TFAD模型相对于RPL模型具有更好的存储性能和路由收敛速度.TFAD模型的协议交互简单,只需极少的父子节点信息交互即可实现子网内节点的路由信息生成.每一子树都有对应的IP网段,子树内部的拓扑结构信息对上层节点透明.另外,还设计了TFAD模型的备份父节点机制,支持节点或链路故障后以子树为单位进行网络拓扑重构,从而实现物联子网的快速路由恢复.基于真实物联网节点的组网实验,验证了TFAD模型节点的路由学习速度较RPL模型占优;而对于网络故障后的路由恢复,TFAD模型也更为快速.

当然,TFAD模型层次地址结构可能会导致物联子网内IPv6地址的少许浪费,但可以优化TFAD地址分配机制以节约地址.另外,虽然TFAD模型可根据部署情况设置不同的层数和层次比特位数,但本文方案仍有“同层节点总是具有相同的层次比特位”的约束.可对TFAD模型优化,使得各子树能够根据实时连接状态,调整单个子树范围内的层数及层次比特位,从而有效提升TFAD模型的灵活性.而且,IPv6较大的子网地址范围能够为该思想提供有力的支撑.本文的后续工作将对上述问题展开研究.

参考文献
[1] Commission of the European Communities. Internet of things——n action plan for Europe. 2009.
[2] Meyer D, Zhang L, Fall K. Report from the IAB workshop on routing and addressing. RFC 4984, 2007.
[3] Dunkels A, Vasseur JP. IP for Smart Objects. ISPO Alliance White Paper, 2008.
[4] Ma YW, Lai CF, Huang YM, Chen JL. Mobile RFID with IPv6 for phone services. In: Proc. of the 13th IEEE Int' Symp. on Consumer Electronics. Kyoto: IEEE Press, 2009. 169-170 .
[5] Winter T, Thubert P, Hui J, Kelsey R, Levis P, Pister K, Struik R, Vasseur JP, Alexander R. RPL: IPv6 routing protocol for low-power and lossy networks. RFC 6550, 2012.
[6] Narten T, Nordmark E, Simpson W, Soliman H. Neighbor discovery for IP version 6 (IPv6). RFC 4861, 2007.
[7] Akkaya K, Younis M. A survey on routing protocols for wireless sensor networks. Ad Hoc Networks, 2005,3(3):325-349 .
[8] Atzori L, Iera A, Morabito G. The Internet of things: A survey. Computer Networks, 2010,54(15):2787-2805 .
[9] IEEE.802.15.4. http://www.ieee802.org/15/pub/TG4.html
[10] Kim E, Kaspar D, Gomez C, Bormann C. Problem statement and requirements for IPv6 over low-power wireless personal area network (6LoWPAN) routing. RFC 6606, 2012.
[11] Jobin J, Krishnamurthy SV, Tripathi SK. A scheme for the assignment of unique addresses to support self-organization in wireless sensor networks. In: Proc. of the IEEE 60th Vehicular Technology Conf. Los Angeles: IEEE Press, 2004. 4578-4582 .
[12] Lin JL, Liu YH, Ni LM. SIDA: Self-Organized ID assignment in wireless sensor networks. In: Proc. of the IEEE Int' Conf. on Mobile Adhoc and Sensor Systems. Pisa: IEEE Press, 2007. 1-8 .
[13] Chen HM, Cui L, XIE KB. A comparative study on architecture and implementation methodologies of Internet of things. Chinese Journal of Computers, 2013,36(1):168-188 (in Chinese with English abstract).
[14] Droms R, Bound J, Volz B, Lemon T, Perkins C, Carney M. Dynamic host configuration protocol for IPv6 (DHCPv6). RFC 3315, 2003.
[15] Villalba LJG, Orozco ALS, Cabrera AT, Abbas CJB. Routing protocols in wireless sensor networks. Sensors, 2009,9(11):8399-8421.
[16] Singh SK, Singh MP, Singh DK. Routing protocols in wireless sensor networks——A survey. Int' Journal of Computer Science & Engineering Survey (IJCSES), 2010,1(2):63-83 .
[17] Estrin D, Govindan R, Heidemann J, Kumar S. Next century challenges: Scalable coordinate in sensor network. In: Proc. of the 5th ACM/IEEE Int' Conf. on Mobile Computing and Networking. New York: ACM Press, 1999. 263-270.
[18] Singh SK, Singh MP, Singh DK. A survey of energy-efficient hierarchical cluster-based routing in wireless sensor networks. Int' Journal of Advanced Networking and Application, 2010,2(2):570-580.
[19] Shen B, Zhang SY, Zhong YP. Cluster-Based routing protocols for wireless sensor networks. Ruan Jian Xue Bao/Journal of Software, 2006,17(7):1588-1600 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/1588.htm
[20] Manjeshwar A, Agrawal DP. TEEN: A routing protocol for enhanced efficiency in wireless sensor networks. In: Proc. of the 15th Int' Parallel and Distributed Processing Symp. (IPDPS). San Francisco: IEEE Press, 2001. 2009-2015 .
[21] Kulik J, Heinzelman W, Balakrishnan H. Negotiation-Based protocols for disseminating information in wireless sensor networks. Wireless Networks, 2002,8(2/3):169-185 .
[22] Heinzelman WB, Chandrakasan AP, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks. IEEE Trans. on Wireless Communications, 2002,1(4):660-670 .
[23] Li ZJ, Liu YH, Li M, Wang JL, Cao ZC. Exploiting ubiquitous data collection for mobile users in wireless sensor networks. IEEE Trans. on Parallel and Distributed Systems, 2013,24(2):312-326 .
[24] Fonseca R, Gnawali O, Jamieson K, Kim S, Levis P, Woo A. TEP 123: The collection tree protocol. 2006.
[25] Gnawali O, Fonseca R, Jamieson K, Moss D, Levis P. Collection tree protocol. In: Proc. of the 7th ACM Conf. on Embedded Networked Sensor Systems. New York: ACM Press, 2009. 1-14 .
[26] Perkins C, Belding-Royer E, Das S. Ad hoc on-demand distance vector (AODV) routing. RFC 3561, 2003.
[27] Contike. http://www.contiki-os.org/
[28] TinyOS. http://www.tinyos.net/
[13] 陈海明,崔莉,谢开斌.物联网体系结构与实现方法的比较研究.计算机学报,2012,36(1):168−188.
[19] 沈波,张世永,钟亦平.无线传感器网络分簇路由协议.软件学报,2006,17(7):1588−1600. http://www.jos.org.cn/1000-9825/17/1588.htm [doi: 10.1360/jos171588]