一种基于聚类算法的ETX辅助无人机AODV路由协议

郭少雄,宋志群,李 勇,刘玉涛

(1.中国电子科技集团公司第五十四研究所,河北石家庄 050081;2.通信网信息传输与分发技术重点实验室,河北石家庄 050081)

无人机被广泛应用于交通管理[1-2]、监控[3]、边境巡逻[4]、灾难救援[5-6]等领域。由于无人机的高移动性、拓扑变化的周期性、能量约束和通信范围有限,其通信网络内链路断裂和数据包丢失现象较其他无线通信链路更加频繁。在飞行自组网(flying ad hoc network,FANET)中,需要稳定的数据传输路径来保证网络内高效可靠的通信。因此,路由协议设计是FANET中的一个重要问题,开发低开销、低延时的高效路由协议成为研究的热点和难点[7]。

无线自组网按需平面距离向量(ad hoc on-demand distant vector,AODV)路由协议以其方便高效的性能被广泛应用于无人机自组织网络[8],网络中的节点并不存储网络整体的拓扑结构,仅当需要发送信息时才会寻找路由路径,但在发现、生成路由时会产生较高的延迟,跳数最短路由机制也存在一定的弊端。

针对上述问题,许多学者基于AODV路由协议提出了更加稳定高效的改进协议。SARKAR等[9]提出了一种基于增强蚁群优化算法的Enhanced-Ant-AODV路由协议,利用信息素判别最优路径,提供了有效的QoS保障;LI等[10]提出了一种基于模糊逻辑辅助的FL-AODV路由协议,提高了路径的可靠性;BAMHDI等[11]提出了一种基于节点密度的DP-AODV路由协议,通过动态调整传输数据包所需的功率,从而减少网络的功率总需求;SHAFI等[12]提出了一种基于机器学习的ML-AODV路由协议,用来检测泛洪黑洞攻击,提高了网络的安全性。

期望传输次数(expected transmission count,ETX)度量是目前使用率较高的路由度量值之一。MALNAR等[13]最早基于网络仿真平台NS3实现了AODV路由协议的ETX机制改进,并在P-AODV路由协议的基础上结合ETX机制提出了一种ND-AODV-ETX路由协议,在端到端延迟和丢包率方面提高了协议的性能,但也带来了较大的路由开销;HUANG等[14]提出了一种AODV-NLS-AODV路由协议,但是也没有考虑控制开销的问题。事实上,ETX机制能够很好地平衡以最小跳数选取路径带来的链路质量问题,提高网络的吞吐量,但因增加了探测包,导致传输时延和路由开销也随之增加,AODV路由协议的泛洪广播更是加重了这一问题。如图1所示,当源节点S寻找到达目的节点D的路径时,网络中每个节点都广播路由请求消息,这对于有限的无线资源是一种浪费。

图1 泛洪广播Fig.1 Flooding broadcast

本文在AODV-ETX路由协议的基础上,结合K-means聚类算法,提出了K-AODV-ETX路由协议,通过聚类特征选择RREQ消息转发的最佳集群,减少盲目泛洪广播带来的资源浪费,缩短路径发现时间,有效降低协议的路由开销与端到端时延。

为了验证性能,将K-AODV-ETX路由协议与AODV路由协议、AODV-ETX路由协议、ND-AODV-ETX路由协议进行比较,其中AODV-ETX路由协议与ND-AODV-ETX路由协议是分别在AODV路由协议、ND-AODV路由协议的基础上改进而来的。

1 算法设计

1.1 ETX机制原理

AODV-ETX路由协议、ND-AODV-ETX路由协议均采用ETX机制。ETX机制通过一种消息探针来监控链路上的数据包预期传输数。为了找出传播值最小的传播链路,AODV路由协议中传统的跳数最短路径选择机制将被ETX机制取代。当源节点和目的节点之间的通信链路建立时,通过计算链路正向传输成功的概率和反向重传成功的概率来得到节点链路中的ETX值。

ETX定义为

(1)

式(1)中:R为网络2个节点之间的路由;η为路由R的一跳;φ(η)为转发接收比;ρ(η)为反向接收比,即对应ACK报文被成功接收的概率。

接收比常由链路探测报文(link probe packet,LPP)估计:

(2)

式(2)中:

(3)

α为链路质量老化参数,α越大,接收比的平均时间越长,从而产生更稳定、可靠的估计。

链路的ETX值由在该链路上发送数据包所需的预期传输数表示,包括重传。如果pf表示报文成功传输的概率,pr表示ACK报文成功接收的概率,那么报文成功发送并确认的概率为pf×pr,则链路l的ETX值可以表示为

ETXl=1/(pf×pr)。

(4)

网络中节点以平均周期τ广播链路探测消息报文LPP,概率Pf和Pr都可以通过LPP来测量,周期τ内最大抖动设置为10%来避免意外同步的产生。每个节点将在最近w秒内接收到的LPP数量记录在自己的路由表中,并根据式(5)计算任意时刻t下的概率:

(5)

式(5)中:count(t-w,t)为在窗口w期间实际接收到的LPP数量;w/τ为在此窗口期间应该接收的LPP数量。如在链路X→Y上,X通过计算从Y成功接收到的LPP来测量pr,节点Y发送的每个LPP都包含最近w秒内从X接收到的LPP数量。节点X根据w秒内接收到的LPP数量来计算pr,路由r的度量为路由中每个链路l的ETX值的和:

(6)

1.2 K-means聚类算法

相比于AODV路由协议的跳数最小路径选择机制,ETX机制提供了一种有效提高自组织网络吞吐量的方法,但由于探测包LPP的存在,增加了网络的控制报文,从而增大了路由开销和时延,基于这一问题,本文考虑采用聚类算法思想控制开销,减小时延。

聚类算法是一种有效的特征分类方法[15],并已被应用到路由协议中,许多基于聚类算法的路由协议被提出[16-17],现阶段大部分的聚类算法都应用于分簇协议的设计与应用,而本文旨在基于聚类算法的分类思想将FANET中的节点进行特征分类。

执行聚类算法后,分布在一定范围内的节点根据特征被分类,如图2、图3所示,其中图3中不同颜色代表不同的类,当路由发现过程触发时,改变RREQ消息泛洪广播机制,沿着特定无人机节点集群传播。

图2 节点分布情况Fig.2 Node distribution

图3 K-means聚类后节点分布情况Fig.3 Node distribution after K-means algorithm

算法选择初始聚类数量K,目标是将1≤j≤N的点集合Kj重新组织成K个聚类。为此,采用K-means聚类算法随机选取点xi作为质心,其中1≤i≤K,每个质心属于一个聚类C。然后,算法将数据集中的每个点分配到最近的质心,该过程基于距离目标函数,该函数计算所有聚类中所有距离的平方和,利用式(7)进行计算:

(7)

式(7)中:d(xj,ui)=|xj-ui|2,其为该点到聚类质心的距离;xj为该点的位置;ui为i=1,2,…,K时质心的位置,K是簇的个数。

如图2所示,在分配完每个聚类中的点后,K-means算法使用式(8)更新每个质心的位置:

(8)

在本文中,K-means聚类中使用的聚类特征有3个,网络中源节点基于邻居的聚类特征来选择最优聚类进行消息转发。

1)到目的节点的跳数 到目的节点的跳数越小,路由越短,路由发现的时间越短。

2)错误传输次数 节点错误传输的次数越少,节点的传输越可靠,则经过此节点的链路质量高,有助于提高吞吐量和数据投递率。

3)节点可用缓冲空间 节点的可用缓冲空间越大,表示节点处的网络拥塞情况越轻,数据包经过此处不容易发生拥塞,有助于提高网络的吞吐量。

2 协议工作流程

K-AODV-ETX路由协议的工作流程主要分为2步:第1步,在网络中执行K-means聚类算法对节点进行分类处理,选择合理的集群进行源节点与目的节点之间的消息报文转发;第2步,执行路由发现过程,与AODV-ETX路由协议相同。

2.1 转发集群选择

K-means聚类算法的伪码如下。

输入:质心数量K;节点集合N;随机分配给质心的列表Ck

输出:具有质心的集群

Begin

1.Repeat

2.ForN个数据点,do

3.使用式(7)计算数据点和每个聚类的质心之间的距离

4.将数据点指定给最近的质心

5.Endfor

6.ForCk中的每个集群do

7.使用式(8)计算新的质心位置

8.Endfor

9.Until所有数据点都属于一个集群或达到最大迭代次数

End

K-means聚类算法流程如图4所示。

图4 K-means聚类算法流程Fig.4 Process of K-means clustering algorithm

为了收集网络内节点信息从而确定转发集群,利用网络仿真软件NS3,向AODV协议类中添加新字段,具体如下:

在“RREPHeader”和“RoutingTableEntry”类中增加m_txErrorCount(错误传输计数),m_freeSpace(缓冲空间),m_positionX(节点横坐标),m_positionY(节点纵坐标)字段,同时在执行文件中新增协议文件aodvKmeans-routing-protocol.h和路由表文件aodvKmeans-rtable.h来进行K-AODV-ETX路由协议的实现。

2.2 路径选择

K-AODV-ETX路由协议的路由发现与维护过程与AODV协议基本相同,不同的是采用ETX机制进行路由选择与判别,为此,对协议的RREQ与RREP消息报文进行修改,如图5和图6所示。

类型JRGDU保留跳数RREQ ID目的节点序列号路由请求RREQ源节点的IP地址寿命ETX

类型RA保留前缀长度多跳转发计数器目的节点IP地址目的节点序列号路由请求RREQ源节点的IP地址寿命ETX

从图5、图6可知,相比于原RREQ和RREP包格式,改进的RREQ和RREP均增加了ETX项,用以路径判别。

首先,每个路由表项都使用ETX字段展开。在AODV路由协议中,路由表项是按目的地分类的。如果到某个目的地有多条路由,则按跳数对路由进行分类,跳数最小的路由为最佳路由。在AODV-ETX路由协议中,根据路由的ETX值对路由进行分类,ETX值最小的路由为最佳路由。如果存在多个具有相同ETX值的路由,则再以跳数最小的路由为最佳。

当源节点S进行路由发现过程广播RREQ消息时,ETX的初始值设置为0,此后ETX字段的处理方式与跳数类似。即RREQ转发到目的节点时,每个节点的ETX字段按照式(6)进行更新。发送RREP报文的原理与之相同。ETX值是累积的,通过比较不同路径的ETX值之和选择路径。

原AODV路由协议中的最小跳数机制下的RREQ和RREP消息传播方式和本文提出的K-AODV-ETX路由协议ETX机制下的RREQ和RREP消息传播方式分别如图7、图8所示:

图7 最小跳数机制下的消息传播Fig.7 Message propagation with minimum hop count mechanism

图8 ETX机制下的消息传播Fig.8 Message propagation under the ETX mechanism

如图7所示,AODV路由协议采用跳数最小机制选择路径,RREQ消息每转发1次,其路由表项中的跳数项则加1,节点A广播RREQ消息报文,节点C和节点B均收到,随后节点C和节点B广播,节点B收到来自节点C的RREQ消息,与自身路由表更新过的跳数进行比较,对节点C的RREQ消息进行舍弃,直至目的节点D收到RREQ消息,并发送RREP消息建立正向传输路径,S—A—C—B—D跳数较大,采用S—A—B—D进行数据传输。

在ETX机制下,链路的ETX值之和越小,链路的质量越好,因此K-AODV-ETX路由协议选择ETX值之和最小的链路进行数据传输,如在图8中,当链路A—C—B的ETX值之和小于A—B链路的ETX值时,虽然A—B链路的跳数较小,但节点B仍会舍弃来自节点A的RREQ消息,采用链路S—A—C—B—D进行数据传输。

3 仿真设置与分析

3.1 仿真环境和仿真参数介绍

本文采用网络仿真软件NS3进行仿真,仿真参数设置如表1所示。

表1 仿真参数设置

为了衡量K-AODV-ETX路由协议的网络性能,选取了以下3个仿真指标。

1)数据包投递率(packet delivery ratio,PDR) PDR为目的节点接收到的数据包个数与源节点发送的数据包个数之比,反映了网络传输的可靠性,投递率越高,协议的可靠性越大。

(9)

2)端到端的平均时延 它包括路由查找时延、数据包在接口队列中的等待时延、传输时延及MAC层的重传时延,其反映了路由有效性,尤其对语音消息来说,时延太大会严重影响通信质量。

(10)

3)路由开销 路由开销指网络中用于路由寻找和路由维护的控制数据包个数与目的节点接收到的数据包个数的比值。

(11)

4)吞吐量 吞吐量指单位时间内通过链路成功传输的平均数据量,吞吐量越大,网络性能越好。

3.2 仿真结果分析

为评估K-AODV-ETX路由协议的性能,设置节点速度为20 m/s,在节点数为10,20,30,40,50个时对协议分别进行仿真分析,并与AODV路由协议、AODV-ETX路由协议、K-AODV-ETX路由协议和ND-AODV-ETX路由协议进行对比。

图9显示了节点速度为20 m/s时,4种路由协议的PDR随节点数的变化情况。从图中可以看出,采用ETX机制可以明显提高协议的数据包投递率,AODV-ETX路由协议相比于AODV路由协议,其PDR最大可提升7%左右,而ND-AODV-ETX路由协议相比于AODV-ETX路由协议在PDR上没有明显的优势。本文提出的K-AODV-ETX路由协议的PDR略小于AODV-ETX路由协议,这是由于K-means机制路由发现过程中的选择性转发,结合路径选择时候的ETX机制,容易引起节点处数据包的溢出丢失。

图9 4种路由协议PDR随节点数的变化Fig.9 Variation of PDR with number of nodes for four routing protocols

图10展示了4种路由协议的时延随节点数的变化情况。从图中可以看出,ND-AODV-ETX路由协议和AODV-ETX路由协议的时延均明显高于AODV路由协议与K-AODV-ETX路由协议。这是由ETX机制的重传导致的,K-AODV-ETX路由协议采用K-means聚类算法,有目的地转发RREQ数据包,实现了路径的快速发现,很好地平衡了ETX机制带来的高延迟问题,其时延性能和AODV路由协议相当。

图10 4种路由协议的时延随节点数的变化Fig.10 Variation of delay with number of nodes for four routing protocols

图11展示了4种路由协议的路由开销随节点数的变化情况。由于ETX机制本身在路由控制包中占用了字节,随着节点数的增加,为维持稳定链路需要更多的控制包,导致路由开销较大且不断增加。本文提出的K-AODV-ETX路由协议,在路由发现广播环节选取了最优集群进行转发,有效控制了无效的路由广播,开销小于AODV-ETX路由协议和ND-AODV-ETX路由协议。从图11中还可以看出,在节点数大于40个后,在相应速度下网络内的节点间信息交换较为充分,趋于一种稳定状态,使得路由开销出现下降的趋势。

图11 4种路由协议的路由开销随节点数的变化Fig.11 Variation of routing overhead with number of nodes for four protocols

图12展示了4种路由协议的吞吐量随节点数的变化情况。从图中可以看出,采用ETX机制有效提高了AODV路由协议的吞吐量;在K-AODV-ETX路由协议中,在聚类特征中的节点缓冲项,能够有效减少网络拥塞,增大了协议的吞吐量,比AODV路由协议最大可提高11.3%。

图12 4种路由协议的吞吐量随节点数的变化Fig.12 Variation of routing throughput with number of nodes for four protocols

4 结 语

本文提出了一种基于K-means聚类算法的ETX辅助无人机K-AODV-ETX路由协议。通过研究得到如下结论。

1)利用K均值聚类算法,协议根据相应的聚类特征选择最优集群转发RREQ消息报文,有效降低了节点泛洪广播带来的额外开销,同时RREQ消息的选择性转发可以加快邻居发现的速度,降低了路径发现时延。

2)数据传输采用ETX值较小的路径,保证了链路的传输质量。

3)NS3仿真结果表明,与AODV路由协议、AODV-ETX路由协议和ND-AODV-ETX路由协议进行比较,K-AODV-ETX路由协议虽然在端到端投递率方面有所下降,但是仍保持了高于AODV路由协议的投递率水平,在保证一定吞吐量的同时,在时延和路由开销性能方面也具有明显优势,是一种有效降低开销与路径发现时延的路由协议。

对于提出的K-AODV-ETX路由协议,本文主要对不同网络密度下的协议性能进行了研究,未对不同速度下的协议性能进行讨论,而实际中无人机集群在执行不同任务时可能采取不同的飞行速度,同时由于电池能量限制,亟需提高高速移动下的协议性能并保障协议的能量效率,因此,今后将对不同速度下的协议性能做进一步的研究。