顾昊伦, 赵国荣, 韩 旭, 高 超

(1.海军航空大学岸防兵学院, 山东 烟台 264001; 2.中国人民解放军第91001部队, 北京 100854)

0 引 言

无线网络技术的发展与推广使得各导航平台可以借助平台间的组网与信息协同,在不大幅度增加单个平台硬件负载的前提下,完成单个平台难以实现的各类任务[1]。组网导航系统(networked navigation systems, NNSs)正是以导航体传感器网络为中心,依托于组网节点间导航信息的协作量测,通过无线交互及信息共享实现网络内整体导航性能的提升。

实现组网导航的基础是针对导航体传感器网络设计一套高效的组网通信协议。其中,路由协议位于网络层,是实现NNSs从小尺度网络与短距传输迈向大范围组网与长距传输的关键机制。与传统Ad-hoc网络相比,NNSs路由协议的设计难点为[2]:① 通信服务类型多种多样;② 服务质量(quality of service, QoS)传输需求;③ 节点能量受限更为明显;④ 低通信时滞需求。

针对问题①和问题②,文献[3-5]综合协作通信和QoS路由,分别以不同目标设计了相应的协作QoS路由协议,实现了差异化服务的策略,提高了带宽利用率并降低了干扰/串听等。但文献[3-5]并未在路由协议的设计中量化QoS指标,且并未建立协作传输和多跳传输对空间复用率及吞吐量的影响模型等。文献[6]则针对上述缺点,以三维地理栅格和受控虚拟节点为基础,将Ebbinghaus记忆原理引入路由搜索的效能优化,设计了一种基于三维地理栅格的衰减记忆协作QoS路由协议(fading memory cooperative QoS routing protocol based on three-dimensional geographic grid,FMCQR),实现了对先验路由信息的高效利用。但文献[6]主要解决的仍是问题①和问题②,并未将节点能量受限考虑到设计目标中。因此,尽管其考虑了低通信时滞需求,但当其算法应用至NNSs这种大范围多节点组网的情形时,网络能量的迅速衰减使得通信时滞问题反而更加严重。

针对问题③和问题④,文献[7]在低功能耗自适应集簇分层型(low energy adaptive clustering hierarchy,LEACH)协议的基础上,提出了一种LEACH-DCHS算法,仅从剩余能量多的节点中选取簇头。但随着网络的运行,该种算法将会导致簇头的数量急剧下降,影响网络稳定性。文献[8]考虑文献[7]中的缺陷,重新构造阈值函数,优先选取剩余能量高的节点为簇头。但在网络运行的初始阶段,该种算法将会导致簇头数量爆炸。因此,从控制簇头数量的变化相对平稳这一角度,文献[9]和文献[10]分别提出了集中式LEACH协议和基于窗口滑动和动态节点数目的改进LEACH协议算法控制簇头期望数目始终在最优范围内。文献[7-10]在分簇路由协议的基础上,从簇头选取的角度对问题③提出解决方案,优化了网络的整体运行效率。但均普遍存在簇头分布过于集中、过于偏向,动态分簇引入额外开销以及汇聚节点附近的能量空洞等问题。文献[11]针对上述问题提出了节能非均匀分簇(energy-efficient uneven clustering,EEUC)协议,优化了簇头分布,缓解了能量空洞问题。但成簇能耗过大,且随着网络的运行会导致远离汇聚节点的簇群能量加速衰减,因此并未从本质上解决能量空洞问题。

针对文献[7-11]暴露出的问题,文献[12]证明了具有随机或受控移动汇聚节点的Ad-hoc网络负载更加均匀、能耗更低、生命周期更长。文献[13]提出了一种基于随机移动汇聚节点的准集中式分簇(quasi centralized clustering approach,QCCA)协议。该协议首先将网络划分为不同区域,区域内高能量节点优先成为簇头,仅当汇聚节点移动至某一区域时由该区域内的簇头将信息融合发送至汇聚节点。但该种算法极有可能导致某一轮中汇聚节点无法访问所有区域,通信时滞问题反而加剧。文献[14]则通过选取代理节点的方式,提出了一种移动基站汇聚(sink mobility support,SMS)协议,但若代理节点死亡,路由重构将会造成较大时滞。文献[15]综合中继跳数,移动汇聚节点的行程长度和节点剩余能量提出了一种能量感知自界跳数算法(energy aware bounded hop count algorithm,EABHCA)协议,该算法具有时滞低的特点,但其能耗和吞吐量方面性能均一般,不适用于NNSs这种大规模网络。

本文综合考虑上述文献中的优缺点,以随机移动汇聚节点为基础,将整个网络区域分为汇聚节点为中心的交叉区域和非交叉区域。交叉区域内的节点为骨干节点,通过构建路由树将数据传递给汇聚节点;非交叉区域内的节点通过链式分簇实现数据传递并与骨干节点建立联系。CRTCC路由协议旨在解决以下4个问题:① 通过移动汇聚节点的方式提高网络内节点的利用率及能量节省率;② 通过建立路由树的方式提高网络运行效率,降低通信时滞;③ 通过链式分簇的方式进一步降低通信时滞;④ 通过优化链式分簇算法降低混合层次链式分簇可能带来的能耗过大的问题。

1 问题描述

1.1 网络模型

设NNSs共有N个节点及1个汇聚节点。节点主要用于收集、处理和传递测距信息和导航信息,具有有限的能量、存储空间,通信能力一般;汇聚节点主要用于收集并向用户传递节点的导航信息,其能量供应不受限制,存储空间足够,通信能力较强。节点获取测距信息的方式为基于信号到达时间(time of arrival,TOA)法的组网测距[16],解算导航信息包括解算位置信息和姿态信息,分别采取DMDG-3D球面定位算法[17]和四元数UKF姿态估计算法[18]。

设初始时刻之前,网络内所有节点通过文献[19]设计的NNSs通信协议均获取了初始导航信息并建立了网络空间局部坐标系。设局部坐标系下x轴范围为[0,X],y轴范围为[0,Y],z轴范围为[0,Z]。

基于移动汇聚节点的交叉路由树构建及链式分簇相结合的路由算法(routing algorithm combining cross routing tree construction based on mobile sink and chain clustering, CRTCC)协议采取了“轮”的概念,每一轮包括一个设置阶段和一个稳态阶段。在设置阶段,首先构建一个以移动汇聚节点为中心的交叉区域,区域内的节点为骨干节点,然后根据距离和剩余能量建立路由树,最后通过链式分簇算法将非交叉区域内的节点分为多个簇群。在稳态阶段,普通节点将信息传递给对应的簇头,由簇头将收集到的信息融合处理后传递给骨干节点,最后骨干节点通过路由树将信息传递给汇聚节点。与此同时,稳态阶段刷新所有节点的导航信息,作为下一轮设置阶段的信息基础。图1即为某一轮中CRTCC构建的网络结构示意图,其中以汇聚节点为中心的正方体向6个边界面延拓后得到的3个长方体区域的并集即为交叉区域。

图1 CRTCC构建的网络结构

1.2 能量模型

与Ad-Hoc网络类似,NNSs节点在传输数据的过程中消耗的能量远远大于计算所消耗的能量,因此采取一阶无线电模型[20]计算节点消耗的能量。能耗计算公式如下所示：

(1)

式中:ET(k,d)表示某一节点将k-bits数据包发送到d以外另一节点的能耗;ER(k)表示某一节点接受k-bits数据包的能耗;Ee表示某一节点驱动和控制其电子元件的能耗;Ea表示某一节点维持无线电可靠传输的能耗。Ea表达式如下所示:

(2)

式中:εf代表自由空间模型下的信号衰减因子;εm代表多径模型下的信号衰减因子;d0表达式如下所示:

(3)

2 CRTCC路由协议算法

CRTCC路由协议将网络运行时间分为多轮,在每一轮的设置阶段包含5个步骤。

步骤 1汇聚节点路径规划及各节点邻居库更新。

步骤 2交叉区域构建。

步骤 3交叉区域节点生成路由树。

步骤 4非交叉区域节点簇头选取。

步骤 5构建簇结构及路径选择。

在随后的稳态阶段,各节点收集的测距信息及导航信息根据设置阶段的路由转发到相应节点进行计算与融合。稳态阶段除了完成向汇聚节点发送用户指定的导航信息外,还需要完成各节点导航信息的刷新,作为下一轮设置阶段的信息基础。

2.1 汇聚节点路径规划及各节点邻居库更新

算法 1汇聚节点路径规划

(4)

图2 式(4)中各角定义图

(5)

算法 2邻居库更新

由算法1、算法2可知,算法1的时间复杂度为T(1),空间复杂度为O(1);算法2的时间复杂度为T(n2),空间复杂度为O(1)。

2.2 交叉区域构建

记以汇聚节点为中心的正方体边长为l,0

算法 3交叉区域构建

记φ为交叉区域内节点(骨干节点)坐标的集合。根据点到平面距离公式可得dsBk表达式如下：

(6)

情景 1∀k∈{1,2,…,6},dsBk≥0.5l

此情景对应的交叉区域示意图如图3所示。

图3 情景1对应交叉区域

定义U(x,δ)为x的δ领域,U(x,δ)的具体含义为U(x,δ)=[x-δ,x+δ],则根据图3可知φ的表达式如下所示：

(7)

情景 2∃k∈{1,2,…,6},s.t.dsBk<0.5l

此情景共有6种情况,图4为k=1(即汇聚节点与y=0平面距离小于0.5l)时情景2对应的交叉区域示意图。

图4 情景2对应交叉区域(k=1)

k取其余值时可类比推得。因此,k=1,2,…,6时，φ的表达式分别如下所示：

(8)

(9)

(10)

(11)

(12)

(13)

情景 3当汇聚节点与两个相邻边界面的距离同时小于0.5l。不防设这两个相邻边界面为Bk和Bp。

此情景共有12种情况,分别为k=1,p=2;k=1,p=4;k=1,p=5;k=1,p=6;k=2,p=3;k=2,p=5;k=2,p=6;k=3,p=4;k=3,p=5;k=3,p=6;k=4,p=5;k=4,p=6。图5为k=1,p=2时情景3对应交叉区域示意图。

图5 情景3对应交叉区域(k=1,p=2)

当k=1,p=2时:

(14)

当k=1,p=4时:

(15)

当k=1,p=5时:

(16)

当k=1,p=6时:

(17)

当k=2,p=3时:

(18)

当k=2,p=5时:

(19)

当k=2,p=6时:

(20)

当k=3,p=4时:

(21)

当k=3,p=5时:

(22)

当k=3,p=6时:

(23)

当k=4,p=5时:

(24)

当k=4,p=6时:

(25)

情景 4当汇聚节点与3个两两相邻边界面的距离同时小于0.5l时。不防设这3个两两相邻边界面为Bk、Bp和Bq。

此情景共有8种情况,分别为k=1,p=2,q=5;k=1,p=2,q=6;k=2,p=3,q=5;k=2,p=3,q=6;k=3,p=4,q=5;k=3,p=4,q=6;k=4,p=1,q=5;k=4,p=1,q=6。图6为k=4,p=1,q=6时情景4对应交叉区域示意图。

图6 时情景4对应交叉区域(k=4,p=1,q=6)

k,p,q取其余值时可类比推得。沿用情景3中的定义,情景4下φ的表达式如下所示。

当k=1,p=2,q=5时:

(26)

当k=1,p=2,q=6时:

(27)

当k=2,p=3,q=5时:

(28)

当k=2,p=3,q=6时:

(29)

当k=3,p=4,q=5时:

(30)

当k=3,p=4,q=6时:

(31)

当k=4,p=1,q=5时:

(32)

当k=4,p=1,q=6时:

(33)

综上易知算法3的时间复杂度为T(n),空间复杂度为O(1)。

2.3 路由树生成

算法 4路由树生成

路由树的构建过程一共分为5个步骤。

(34)

重复上述所有步骤直至路由树所有分支构造完毕。上述步骤是以图3所示交叉区域为例,算法3中生成的其他类型交叉区域均可采用类似算法4的方法得到相应的路由树。算法4的时间复杂度为T(n),空间复杂度为O(1)。

2.4 簇头选取

算法 5簇头选取

CRTCC协议进入成簇阶段后,非交叉区域内各节点随机产生一个0到1之间的数字,随机数小于阈值τ(η)的节点选为簇头。

CRTCC协议在LEACH协议的基础上,在簇头选取时综合考虑节点剩余能量以及节点和簇头之间的位置关系。阈值函数τ(η)表达式如下所示：

(35)

(36)

θ角的引入是为了避免路径选择时,多个簇头与汇聚节点的连线重叠或者夹角很小,导致这些簇头向汇聚节点派出的蚂蚁进行寻优的路径重合率较高,最终导致重合路径上的节点能耗过大、快速死亡。设θ角定义为:① 当网络内没有簇头时,θ=0;② 当网络内仅有一个簇头时,候选簇头与汇聚节点的连线同已选簇头与汇聚节点的连线之间的夹角的倒数为θ;③ 当网络内存在两个及两个以上簇头时,若候选簇头与汇聚节点的连线在某两个已选簇头与汇聚节点的连线构成的平面内,且在这两根连线构成的锐角区域范围内没有第3根已选簇头与汇聚节点的连线,则这两根已选簇头与汇聚节点连线的角平分线同候选簇头与汇聚节点连线的夹角为θ。否则取候选簇头与汇聚节点的连线同所有已选簇头与汇聚节点的连线夹角的最小值的倒数为θ。

2.5 构建簇结构及路径选择

簇头选取完成后,开始构建簇结构。为增强网络稳定性,提高鲁棒性,簇结构采取混合层次网络拓扑结构。具体算法如下。

算法 6构建簇结构

步骤 4重复上述步骤1～步骤3,直到所有簇头全部完成初步的簇结构构建。

步骤 6重复步骤5,直到所有普通节点均能以单跳形式入簇。在此过程中,若有某个普通节点连续ω次寻找到同一个与自身距离最近的簇节点,则令该普通节点直接以单跳方式与此簇节点连接入簇。

步骤 7依次遍历六条路由树分支上所有骨干节点(包括汇聚节点)的邻居库,将其中属于非交叉区域的节点找出并令其以单跳方式与自身建立连接。若有同一个非交叉区域内的节点与多个骨干节点建立连接,则选取距离最小的。至此链式混合层次簇群结构与路由树建立连接。

由上述步骤可知,ω可以用来控制成簇收敛速度。由于是混合层次网络拓扑结构,普通节点之间、簇头与普通节点之间均可以进行通信,路径选择具有多样性。因此，通过算法7改进蚁群算法给出路径选择的依据。

算法 7路径选择

(37)

(38)

(39)

(40)

(41)

(42)

由式(40)～式(42)可知,CRTCC协议在信息素更新前,蚂蚁先按照自身路径长度进行排名,路径短的排在前面,且由于系数加权,排在前面的蚂蚁会释放更多信息素,加快路径选择速度。

综上算法1～算法7构成了CRTCC路由协议。

3 算例仿真

本文应用Matlab平台,共分4种不同的场景进行仿真,分别记为NNS#1、NNS#2、NNS#3、NNS#4,网络区域大小为50 m×50 m×50 m、50 m×50 m×50 m、100 m×100 m×100 m、200 m×200 m×200 m.节点数量为50、100、100、150,各节点初始能量均为1 J,Ee=40 nJ/bit,εf=20 pJ/bit/m2,εm=0.002 pJ/bit/m4,导航信息数据包大小为4 096 bit,其余数据包(包括测距包、控制包、广播包等)大小为196 bit。假设节点剩余能量小于1%时死亡,节点随机散布在网络空间。

本文采取文献[21]中提及的树型链式非均匀分簇路由协议(tree-chain uneven cluster hybrid multi-hop routing algorithm,TUCHM)以及文献[20]中提及的基于簇树的节能路由协议(cluster-tree-based energy-efficient routing protowl for wireless sensor network,CTEER)进行比较。文献[21]提出了一种链式分簇结构,但并没有考虑移动汇聚节点;文献[20]考虑了移动汇聚节点并提出了路由树的构建方法,但其分簇仅是最简单的均匀分簇。

同场景下3种路由协议的节点存活数随轮数的变化图如图7所示。

图7 4种场景下节点存活数的变化

不同情景下3种路由协议的首个节点死亡轮数(first node death, FND),一半节点存活轮数(half nodes alive, HNA),最后一个节点死亡轮数(last node death, LND),如表1～表3所示。

表1 4种场景下采取THCUM的网络生命周期指标

表2 4种场景下采取CTEER的网络生命周期指标

表3 4种场景下采取CRTCC的网络生命周期指标

根据图7及表1～表3可知:① THCUM路由协议下的NNSs生命周期短,节点能耗大,死亡速度快,这是因为THCUM路由协议是假设移动汇聚节点固定的,能量空洞问题较其他两种算法而言比较明显。② THCUM路由协议下节点数目的增大对其生命周期影响不大,而网络区域的扩大却影响很大。这是因为THCUM也是采用链式分簇方法,网络空间内远离汇聚节点的普通节点或者簇头增多,链路增长,链路上节点能耗增大,加速节点的死亡。而由于THCUM采取的是混合层次拓扑结构并设计了寻优路径算法,节点数目的增多不会导致生命周期的明显降低。③ CTEER协议由于采用了基于移动汇聚节点的路由树,其网络生命周期相对较长,且由于其采取的是均匀分簇,配合路由树可以取得较好的节能效果。④ CRTCC协议无论是从FND、HNA还是从LND的角度其生命周期都较长,性能高于另外两种协议。

本文利用每轮传输数据包产生的跳数总和来衡量3种路由协议下网络的通信时滞,并通过前200轮的数据进行仿真分析。不同场景下3种路由协议的每轮跳数总和变化图如图8所示。

图8 4种场景下每轮跳数总和的变化

由图8可知:① CRTCC协议尽管在生命周期性能方面的表现比较突出,但随着网络规模的增大,其通信时滞越来越明显,在NNS#4情景下超过了TUCHM协议;② TUCHM协议每轮跳数总和并不稳定,这与其混合层次非均匀分簇结构及寻优路径算法中的启发因子有关;③ CRTCC协议每轮跳数总和相对比较稳定、通信时滞较低,性能高于另外两种协议。

4 结 论

本文重点设计了7个算法来构成CRTCC路由协议。以移动汇聚节点为中心的交叉路由树增加了网络生命周期,其分支延拓到了网络的6个临界面,有效降低了通信时滞的影响;非交叉区域的节点完成链式分簇,进一步降低通信时滞;同时改善簇头选取策略并采用混合层次网络拓扑结构,优化路径选择算法,有效防止了链式分簇可能导致的能耗过大、生命周期减小。最后通过与TUCHM协议和CTEER协议在4种场景下的仿真比较,验证了算法的有效性。