基于无线传感网NB-IoT分簇RPL组播路由算法的研究

高江军,洪 锋

(1.池州职业技术学院 电子信息与传媒系,安徽 池州 247000;2.池州学院 智能感知与计算研究中心,安徽 池州 247000)

路由算法是指用于计算网络中数据包传输路径的算法。当一个数据包从源节点发送到目标节点时,需要通过一系列的中间节点进行转发,路由算法就是根据网络拓扑结构、链路状态、流量负载等信息,计算出数据包传输的最佳路径。

路由算法是网络协议栈中非常重要的一部分,不同的网络协议栈可能采用不同的路由算法来实现数据包的传输和路由选择。以基于openFlow/SDN控制器的路由算法[1]为例,该算法利用openFlow的SDN控制平面与数据平面分离,在制定路由策略时考虑全网流量信息和网络状态,并以网状网和胖二叉树网络为基础,制定网络转发策略。

RPL(低功耗有损网络路由协议)是一种可以不依赖定位系统自行组网的无线传感网路由协议,主要在LLN(低功耗有损网络)网络中应用,该网络中的节点以无源节点为主。节点之间通过RPL协议自行构建由父子节点组成的有向无环图,根节点通过广播收集全网节点的数据[2]。但在实际的无线传感网中,如果只是收集指定区域或者指定节点的信息时,全网发送数据就会造成数据的冗余转发,对于节点能量有限的无源节点就会减少网络的生存时间。

加入组播机制后的网络可以解决传统RPL路由算法中存在的数据转发冗余问题,延长网络的生存时间。随着无线网络规模的逐渐扩大,虽然组播技术已经大大减少了节点转发数据量,但是由于网络结构是树形结构,关键节点的转发资源消耗依然很大。传统的算法设计主要围绕中小型网络进行算法改进,当网络规模不断扩大后,关键转发节点就会快速消耗殆尽。

目前关于RPL分簇组播路由算法的国内外研究并不多,研究的方向主要有基于位置的路由算法和基于消息报文设计的路由算法。

基于位置的算法主要是通过定位系统将各个节点的地理信息发送给根节点或者关键转发节点,如SenCast算法[3]和HGMR算法[4]。其中,SenCast算法思想主要是在大规模无线传感网中建立一个强大的基站,根据网络功能需求和各个节点的路由信息建立最优组播树,再对该组播树进行分簇。在转发数据时,基站首先与各个簇首进行数据交互,簇首再将数据以无状态的方式发送给各组播接收节点。该算法的优势是利用强大的基站来维护所有节点的路由信息,承担了大多的路由计算,但是簇首的能量消耗较大,而且无状态的组播会因为路由无法固定,容易导致部分数据的转发路径复杂甚至丢失。HGMR算法思想首先将网络划分成多个子树,网络中有一个能量充足的sink节点(根节点),各子树根据地理哈希算法选取一个簇首,数据的发送从sink节点和簇首开始,再由簇首转发到各个子树的接收节点。该算法的优点是大量的路由信息由sink节点和簇首分担,分散了关键转发节点的能量消耗。但是存在两个问题,一是sink节点和簇首的位置难以固定,如果距离较远,可能导致信号接收不到或者不稳定现象;二是簇首的能量消耗较大,没有较好的轮换机制,很容易导致网络频繁重构、数据转发延迟或者丢失。

基于修改消息报文的组播主要有DODAG(以目的节点为导向的有向无环图)组播[5]和EBMR组播[6]。其中,DODAG组播是通过修改RPL组网消息中的option选项的内容,在各接收节点消息option选项中增加组播地址并根据RPL算法建立组播树,每个组播接收节点都有一个父节点和备份父节点。该算法的优点在于当转发节点失效时,可以通过备份节点完成转发,增加了网络传输的可靠性。而该算法的缺点是每次发送数据都会经过父节点和备份父节点,这种冗余发送会造成父节点能量多余消耗。EBMR算法前期的研究主要是通过在option选项中增加剩余能量计算机制,并设定节点的能量阈值,建立能量均衡最优转发节点集合,数据的传输选择能量剩余大于阈值的节点进行转发。当节点能量小于阈值,从节点集合中更换大于阈值的节点进行转发。该算法能很好地平衡各关键转发节点的能耗,但在大规模无线传感网中,由于节点数量较多,组播地址和路由数据也会不断增大,远距离的传输会加快节点因计算过多导致的能量消耗,网络生存时间会大幅减少[7]。

1 研究思路

大规模无线传感网中,已有基于位置和消息报文设计的算法都还存在很多问题,若要有效地提高网络的生存周期和传输效率,应该结合多种协议算法的优缺点,合理优化网络算法。本研究主要是通过固定节点分簇和最优转发节点轮换机制来降低大规模网络节点的存储压力和数据转发冗余率。

1.1 固定节点分簇

大规模无线传感网的节点数量庞大,仅仅使用RPL组播是不实际的,节点存储和转发量过大都会造成节点能量快速消耗殆尽。在网络密度相同时,将大规模网络根据覆盖区域和节点数量分成若干大小相近的簇,网络的簇首选择NB-IoT基站模式,簇首按照蜂窝结构排列,所有簇首之间通过NB-IoT协议[8]进行数据通信。各个簇首负责本簇内的节点组播通信,簇内采用RPL组播路由协议,根据前期研究的EBMR算法构建基于能耗均衡的最优转发集合进行组播分组转发。

1.2 簇内DODAG的构建

簇内通过构建DODAG完成所有节点的自行组网。簇首先向邻居节点广播DIO消息,所有邻居节点处于监听状态,收到DIO消息后根据目标函数和度量值考虑是否加入DODAG,如果邻居节点符合加入条件则以簇首作为其父节点添加路由,并向父节点回复包含自己rank值(在DODAG中的深度)的DAO消息。加入DODAG的邻居节点继续向下定期发送DIO消息,直到所有节点按照上述方法完成注册和rank值计算,并在rank值与父节点相近的邻居节点中选择一个备份父节点,在构建DODAG过程中同时完成环路检测,确保网络没有环路。最后簇首完成所有簇内节点的路由信息更新。

1.3 簇内RPL组播树构建

在投放无线传感器之前,所有节点都存储了组播地址,根据收集数据的不同进行分组。簇首通过构建DODAG已存储所有组播接收节点的路由信息,组播分组转发会选择最优的转发路线进行转发。

1.4 簇内最优转发节点选取

簇首的由于采用NB-IoT基站,可以确保无线信号覆盖簇内的所有节点,组播分组在组播树中转发,会出现rank值小的节点成为关键转发节点,长时间的数据收发,会造成这类节点能量比其他节点更快地消耗,即使有备份节点的轮换,也不会维持太长时间。因此,当部分节点能量耗尽时,很容易触发DODAG重构,能量耗尽的节点区域则无法采集数据。因此,在节点轮换时,要合理考虑网络中各节点的能耗均衡,确保节点无意外损害的情况下,可以维持更长的时间。本文研究的RPL-CMRA算法,主要是通过在各节点消息的option中增加能量计算机制和节点轮换能量阈值,让节点能够根据阈值进行轮换。由于各节点都可以与簇首建立邻居关系,可以让网络中所有节点都可以参与轮换,最大限度的提高整个簇内网络节点能耗均衡性能。

2 RPL-CMRA最优转发节点组播路由算法描述

RPL-CMRA算法思想核心是NB-IoT基站模式和簇内最优节点转发算法。NB-IoT基站相比前期研究中的RPL节点,具有3个优势,一是信号覆盖范围广可以达到10km;二是支持海量连接,可以支持10万个连接,非常适合WSN(无线传感网)低功耗节点的部署需求;三是低功耗,普通的电池供电可以拥有10年寿命。为了能实现NB-IoT和WSN网络有效融合,需要在NB-IoT簇首协议栈进行修改和添加移动通信网关硬件模块,确保能将无线传感网收集的信息转发到移动通信网络中。簇内最优转发的核心是建立最优转发节点轮换机制,设定簇内节点总数为n,各组播节点编号为N,rank值为R,组播编号为M,记录节点剩余能量为E,节点剩余能量上报定时器为T,设计节点轮换阈值为S,用i表示节点序号。

2.1 簇内节点维护信息表设计

簇首组播信息如表1所示。

表1 簇首组播信息表

组播成员信息如表2所示。

表2 组播成员信息表

NB-IoT基站簇首,存储了本簇内的所有组播组地址和成员信息,RPL协议建立组播树之后,每当需要收集指定组播组的数据时,簇首会向各个组播成员发送收集数据消息。收到簇首的消息后,各个成员将采集的数据回送给簇首,并将转发过程中各个节点的剩余能量值Si一并发送给簇首。当在T时间内没有收到簇首消息时,节点会主动发送自身的能量剩余值给簇首。簇首比较父节点和备份节点的剩余能量阈值,判断是否存在能量不足的转发节点,如果存在,将转发父节点替换成备份节点。如果备份节点能量也不足,则根据能量不足的父节点和备份父节点的数量以及rank值,判断是否需要重构RPL和组播树。

转发节点组播信息如表3所示。

表3 转发节点组播信息表

在RPL组播簇内,各节点都有可能是本组播树的成员节点和转发父节点,同时也可能是其他组播树的父节点。因为离簇首越近,rank值越小,负责的转发量也就越大。当这些rank值小的转发节点能量低于能量剩余阈值时,首先进行备份节点替换,但是往往这些节点也会是其他组播树的父节点。本研究主要根据能量剩余不足的节点数和对应的rank值判断是否要重构组播树,主要依据为相同rank值的节点能量不足占比是否大于指定值,若大于则重构RPL,并对能量不足的节点进行标记,再将它的rank值设置到最大值,促使这些节点暂时不会成为父节点。

2.2 算法实现过程设计

首先,针对DAO消息格式进行改进。节点根据RPL路由算法通过发送组网消息来构建DODAG组播树,DAO消息中包含有组播编号、组播组地址、剩余能量阈值、父节点地址、备份父节点地址、簇首地址等信息。RPL-CMRA组播消息DAO选项如表4所示。当RPL建立DODAG时,DAO消息携带了本节点的编号、剩余能量阈值、所属组编号以及该节点在DODAG中的类型。RPL组播树构建完成后,组播消息负责传送采集信息,并上报剩余能量情况。

表4 RPL-CMRA组播DAO选项

其次,设计PL组播树重构算法。当DODAG组播构建完成后,组播分组就会根据簇首指令发送数据,并上报节点的剩余能量。当簇首发现同一个子节点的父节点和备份父节点都出现剩余能量不足时(小于阈值),发送通告该子节点下次转发数据到该父节点时,直接与簇首节点通信。簇首统计所有剩余能量不足节点数量为P。当P达到簇内总节点一半时,将这些节点rank值设置为最大值,并进行RPL重构组播树。重构RPL组播树如式(1)-式(3)所示。

(1)

P=crad(F)

(2)

(3)

3 剩余能量阈值设置

RPL-CMRA算法要求簇首根据簇内各节点的剩余能量S确定重构组播树的时间,S的取值直接决定RPL组播树的生存时间,根据多次仿真实验的数据,簇内节点数n、分组长度L、节点射频传输距离r、节点密度ρ直接决定网络的生存时间。根据这些参数可以计算节点收发一次组播分组的能耗Z,前期已经完成此项研究[9],因此剩余能量阈值可以通过式(4)和式(5)得出:

Z=L(2E+Kr2)

(4)

S=Sc-Zn

(5)

式(4)和式(5)中,Sc表示传感器节点的初始能量。

在仿真实验中,通过计算不同节点数和密度的情况,发现节点收发次数等于节点数时,此时的剩余能量值为阈值,刚好可以维持到第二次网络重构。

结语

针对基于NB-IoT基站模式RPL组播路由算法的研究,发现已有的RPL组播路由算法在大规模无线传感网中的应用中还存在很多问题。为了能不使用定位系统来降低能耗,利用新型的NB-IoT基站技术,可以充分发挥无源节点高接入和低消耗的优势。NB-IoT基站替换传统无线传感器簇首,可以大幅降低复杂环境的节点安装问题。另外,通过在簇首完成大量的剩余能量替换和网络重构计算,可以降低其他节点因计算带来的能耗,有利于延长网络生存周期。但该算法还存在其他问题,比如复杂环境下簇首位置的选择、传感器信号传输等。因此,该算法在后期研究中还需要进一步地改进和完善。