基于QoS和分簇机制的WMSNs路由算法研究

杜佳轩,马利亚,杨 军

(1.宁夏大学 信息工程学院， 银川 750021; 2.宁夏医科大学 总医院，银川 750021;3.宁夏大学 计算机网络管理中心， 银川 750021)

基于QoS和分簇机制的WMSNs路由算法研究

杜佳轩1,马利亚2,杨 军3

(1.宁夏大学 信息工程学院， 银川 750021; 2.宁夏医科大学 总医院，银川 750021;3.宁夏大学 计算机网络管理中心， 银川 750021)

针对无线多媒体传感器网络中如何设计具有服务质量保证的路由算法问题，综合考虑的了节点间标准化后的丢包率、延迟、剩余能量、可用存储四个参数，提出算法ED-ACO(Energy and best distribution of Cluster Head Distance-Ant colony optimization);ED-ACO算法采用基于剩余能量和簇首最佳距离分布的分簇结构，均匀划分网络，将节点的丢包率，延迟，剩余能量，可用存储标准化为具体参数，考虑到蚁群算法的状态转移概率公式中，利用该公式去选择下一跳路径传送感知数据，同时满足了服务质量要求;NS2仿真结果表明，与经典的AODV算法相比，在丢包率，延迟上保证了服务质量要求。

无线多媒体传感器网络；服务质量；最佳簇首分布；蚁群优化算法

0 引言

基于分簇的无线传感器网路(WSNs)[1-2]的路由协议具有良好的扩展性，能更好的节省传感器结点的资源，便于数据融合和传输。基于分簇的路由协议是将网络划分为若干簇，在一个簇内有一个簇头结点和若干簇成员结点，簇头对簇内成员进行信息采集，对数据进行融合转发。LEACH[3]协议是一种经典的分簇协议，周期性的等概率选举簇头，使网络的能量消耗相对均匀，从而延长网络的生存期。但是LEACH由于等概率的选择簇头，所以网络中簇头分布不均匀，在选择簇头的过程中没有考虑剩余能量和数据融合。EBUCBS[4]是一种基于扇形的能量均衡的非均匀分簇路由协议，采用固定分簇的方式减少重复分簇，且靠近基站的簇由于使用率高缩小簇的范围，远离基站的簇的范围较大。QoS(Quality of Service)需求是区别于传统传感器网络的一个重要特征，传统WMSNs常以牺牲QoS来降低功耗.而无线多媒体传感器网络(WMSNs)则更加注重QoS，对于不同应用为多媒体数据流提供实时性、可靠性、带宽、分组丢失等保障。REAR[5]是一种将链路带宽和能量作为服务质量参数来设计的多媒体路由协议，使用元数据建立多路径路由减少能量消耗，用一个代价函数来评估传输链路。Akkaya 等人[6]提出的由图像传感器节点组成的实时能量感知QoS路由协议，使用最小路径代价找到多条网络路由，但是算法的收敛性不高。HE[7]等人提出一种QoS路由协议SPEED，该方法提供了实时的端到端的时间保证，每个节点需要保存邻居节点信息和利用地理信息转发去寻找路径。但是该算法没有提供数据包的可靠传输保证。Felemban[8]等人提出一种多路径多速度的MMSPEED算法，该算法将实时性和可靠性考虑到到路由算法上来作为QoS条件，但是因为没有把能量效率考虑进来，所以只能适应于生存期较短的网络。通过对蚁群算法的研究[9-10]，基于分簇思想，将结点的剩余能量，数据包频率考虑作为参数，计算下一跳结点的转发概率，在一定程度上也提高了数据的传输效率。

本文在结合分簇策略和服务质量保障机制下，将节点的丢包率，延迟，剩余能量，可用存储标准化为具体参数，考虑到蚁群算法的状态转移概率公式中，利用该公式去选择下一跳转发路径传送感知数据，有效地保证了不同应用数据流的服务质量，增强了网络的适用性。

1 网络模型和问题描述

1.1 网络模型

对于每路径P的服务质量参数值计算如下：

(1)

(2)

(3)

(4)

对于具体环境下不同的应用有不同的服务质量要求，所以对于一条可行路径PQoS∈P，目标函数:

为了简化网络模型，我们采取一些合理的假设如下：

1)有N个感知节点随机地分布在M×M的方形区域。

2)基站位于网络的外部且有无限的能量供应。

3)所有节点部署后没有移动能力且有唯一的ID标识，均匀的部署在监测区域内。

4)所有节点初始能量相同，节点可以根据距离自适应的调整发射功率。

本文采用文献[11]一致的无线电能耗模型，发送端的能量主要消耗在无线电发送元件和功率放大器，接收端的能量主要消耗在无线电发送元件，实验采用自由空间(d2功耗损失)多径衰减(d4功耗损失)信道模型，主要与发送端和接收端之间的距离有关。

传感器节点发送l-bit数据耗能：

(5)

传感器节点接受1-bit数据耗能：

(6)

1.2 问题描述

能量高效的分簇路由算法设计时应注意以下几点：1)应该使用分布式的设计思想，可以有效利用节点的能量和提高网络的生存期；2)簇的规模要适中，要考虑节点的负载均衡；3)要根据实际来设计应用相关的协议；4)感知节点之间的数据传送应该采取分布式传送，避免单跳传送，应设计最短路径的簇头节点之间的数据传输协议，扩大网络的生存期。分簇路由拓扑结构如图1所示。

图1 分簇路由拓扑结构

2 ED-ACO路由算法

ED-ACO是一种针对WMSNs设计的路由协议，是一种基于分簇结构的网络，利用蚁群算法在源节点和Sink节点之间传输数据，在不同的应用环境下满足不同服务质量要求。分簇阶段我们采用剩余能量和最佳簇首距离的分簇方法，数据传输阶段我们利用前向蚂蚁和回溯蚂蚁来寻找路径和更新信息素轨迹，在这个过程中，我们将剩余能量、端到端的延迟，数据包的丢失率，可用的存储空间作为服务质量参数来设计信息素更新公式，在选择下一跳节点时，根据概率转移公式，选择具有最大概率的节点作为下一跳节点。在F-ant到达Sink节点后，Sink节点产生B-ant来更新节点的路由表和信息，当B-ant节点到达源节点后，开始传输数据，数据传输之后根据具体要求进行簇的调整和路由维持。具体的方案下文给出。

2.1 基于蚁群算法的路径搜索

ED-ACO协议基于蚁群优化算法(AntColonyOptimization)去发现和维持簇头节点到Sink节点或基站之间的路由。在分簇过程结束后路由发现算法开始执行。在提出路由发现算法之前，我们提出以下定义：

2.1.1 人工蚂蚁结构

1)Ant.ID蚂蚁的ID

2)Ant.Type在路由发现过程中的蚂蚁类型。有转发蚂蚁F-ant,回溯蚂蚁B-ant,路由维持蚂蚁M-ant,数据蚂蚁D-ant.

3)Ant.AllowedNode蚂蚁节点，允许访问的节点

4)Ant.hop蚂蚁从簇头源节点开始经过节点的条数，代表蚂蚁的TTL。

5)Ant.info:各种类型的蚂蚁使用此数据域存储路由或节点的特殊信息，包括以下几个子域：蚂蚁所经过节点的最小剩余能量蚂蚁经过的节点的累积队列延迟、包的丢失率、节点的可用存储。

在第一阶段分簇之后，数据传输阶段开始。首先簇首首先对簇内数据进行融合，然后数据以多跳的方式发送至目的节点，随后非簇首节点进入休眠状态以节约能量。多路径搜索算法是基于蚁群算法模型，簇首节点产生前向蚂蚁寻找到Sink节点的有效路径，每个蚂蚁都有自己的内存表，用禁忌表来记录已经访问过的节点，用Ant.AllowedNode域来记录允许访问的节点。ED-ACO算法中，前向蚂蚁携带以下信息：数据包类型Type、所有的簇首节点ID、产生前向蚂蚁的簇首节点ID、已访问节点字段VisitedNode、蚂蚁从源节点出发的时间SrcTime、跳数(蚂蚁经过簇首节点个数)。后向蚂蚁要携带数据包类型Type、已访问节点字段VisitedNode，此后向蚂蚁对应的前向蚂蚁从源节点出发的时间SrcTime、链路最小剩余能量Emin、链路平均消耗能量Eavg。

表1 前向蚂蚁携带的报文格式

表2 后向蚂蚁携带的报文格式

2.1.2 信息素表

蚂蚁信息素表是一种特殊的数据结构，存储节点i经过簇头邻居j到Sink节点的路由信息素轨迹信息。存储到节点的内存中，数据的组织结构如表3所示。

表3 节点i的信息素表

在表3中每一行表示对应特定的流量类型，由具体的应用实例定义。每一列是节点i的邻居节点信息，主要包括四个值，每一个值是对于不同排队类型下的信息素轨迹。分别是流量类型k下当前节点的剩余能量，延迟率，丢包率和可用存储。

2.1.3 路由发现阶段

当一个常规节点需要发送数据到Sink节点，这样的信息要立即发送到它的簇头，ED-ACO算法描述如下：当一个簇头节点有感知数据需要发送，簇头节点查找它的路由表为了找到合适的路径传送数据。在发起传送数据开始时，簇头源节点查找它的信息素表为了找到一个任意的没有失效的节点信息。如果这个节点的时钟大于一个截止时间那么这个信息失效，如果所有信息素表中的信息都失效，那么一个新的路由探测阶段开始。大量的前向蚂蚁需要被发送在路由探测阶段。在路由发现过程结束后，缓存数据被立即发送到它的目的地。为了减少路由发现阶段的延迟，ED-ACO算法在分簇阶段后发起一个全路由探测阶段，一个簇头节点接受一个蚂蚁过程如图2所示。

图2 ED-ACO的路由发现过程

ED-ACO算法有三个阶段：转发蚂蚁阶段、回溯蚂蚁阶段、路由维持阶段。

转发蚂蚁阶段：如果一个簇头节点发现没有期望的到达Sink节点的路径，它将产生具体数量的转发蚂蚁(F-ants)去寻找通向Sink节点的路径。转发蚂蚁作为一种代理去建立从CH节点到Sink节点的信息素轨迹，转发蚂蚁的结构上文中已经定义，F-ants的信息域携带：蚂蚁经过的节点的最小剩余能量；每个蚂蚁经过的节点的累积的队列延迟，数据包的丢失率，可用的存储空间。

这些参数作为服务质量(QoS)度量被用来在路由发现阶段。为了找到一条源节点到Sink节点的路由，簇头源节点广播一个F-ant。蚂蚁数据包在发送前必须预先定义，比如：ant.type=F-ant。ant.hopcount=0。簇头源节点放入Ant.nallowed-nodes中，当中间的一个簇头节点收到一个F-ant后，首先判断接收到的F-ant 的Ant.nallowed-nodes域中是否存在回路，导致路由回路的蚂蚁则被丢弃。在发送F-ant到下一个簇头节点之前，F-ant的node.info关于当前簇头的局部信息必须更新。更新规则如下：

energy←min(energy,re(ch))

delay←delay+del(ch)

packetloss←packetloss×pkl(ch)

memory←min(memory,mea(ch))

其中：re(ch)表示簇头节点的剩余能量，dl(ch)表示链路的延迟率，pl(ch)表示簇头节点之间的丢包率，ma(ch)表示簇头节点的可用存储空间。

(8)

式(8)中，启发信息采用如下公式计算:

(9)

为了计算转移概率值，必须计算下面这些概率值：

1)标准化的能量概率：

2)标准化的延迟概率：

3)标准化的包丢失概率：

4)标准化的可用内存的概率值：

最终，在流量类型k下从簇头节点i到节点j的标准化的信息素值计算公式如下：

(10)

公式(8)计算了通过F-ant收集到了相关的QoS参数，能量，延迟，带宽，数据包的丢失率，和可用存储。标准化多个信息素值并转化为相同的维度，以便计算转移概率。路由发现过程中选择下一跳通过参数alpha来控制不同信息素的权重达到不同的服务质量要求。

2.2 回溯蚂蚁阶段

当一个转发蚂蚁到达Sink节点，开始实施路由评估系统，通过将转发蚂蚁收集到的信息与具体应用设置的舒服质量参数值进行比较。例如，相关应用需要的路由是这样的：包损失率小于1%，剩余能量高于80%。Sink节点来评估F-ants收集到的路由参数来决定路由是否有效。如果路由不满足应用的服务质量要求，这个F-ants被丢弃。具体使用的应用必须调整这些参数为了获得有效的路由，如果参数是不真实的或者不可能取得的在当前的网络下，那么，Sink节点会丢弃这些蚂蚁发现的所有路径。

当一个F-ant被Sink节点接收，满足当前应用的要求，Sink节点结束F-ant生命,一个B-ant产生。B-ant将F-ant收集到的信息以及路径中的中间节点的ID用与F-ant相反的路径发送。当中间簇头节点i接收到一个B-ant,信息存储在B-ant中用来更新相关路径上的信息素，一轮结束后，增加已有路径上的信息素，减少无关路径上的信息素，使用信息素更新公式，计算公式如下：

1)能量信息素：

2)延迟信息素：

3)包丢失信息素：

4)可用内存信息素：

最优路径上的信息素轨迹被增加，通过给一个信息素增量。此外，减少不好路径上的信息素，使得蚂蚁都远离最坏的路径。B-ant被发送到下一个簇头通过与F-ant的相反路径。当B-ant到达F-ant的源簇头节点，在更新信息素轨迹后被丢弃。数据之后开始经过最大概率路径传送。

2.3 数据传输阶段

在ED-ACO算法中，簇头节点选择具有最大信息素值的路径转发数据。对于一个给定的流量类型k，当一个节点有多个下一跳节点可以转发数据，选择具有最大ψ值的节点。这个ψ值的计算公式如公式(10)。这种策略可以让数据根据预估计的链路质量有效的传输。当预估计的链路是良好的，接下来的工作由F-ant来完成，正如之前部分描述，具有负载均衡保证。当一个链路的质量比其他链路差，减少这条链路上的负载。其他的链路路径则承担更多的负载任务，为了避免拥塞，我们相应的调节QoS服务参数，使节点的能耗更加均匀，延长网络生存期。

2.4 簇内调整

在第一轮数据传输结束后，要判断路由经过的各簇首节点的能量水平，若簇首节点能量高于簇内平均剩余能量，保持原簇首不变；反之，进行簇内调整，根据公式选取高于平均剩余能量的节点当选簇头，低于平均剩余能量的节点进入休眠状态。新选出的簇首广播原簇首ID、自身ID、自身剩余能量的消息通知簇内成员及其他簇首成员，所有簇首节点收到簇头调整信息后更新各自对应的路由表信息。

3 仿真与分析

3.1 仿真实验环境

本实验采用NS2进行路由发现过程分析，我们从数据包的转发率，端到端的延迟，路由开销三个方面与AODV[12]协议进行对比，分析算法性能。实际仿真参数和文献[13]基本相同如表4所示。

表4 仿真实验的各个参数

3.2 路由过程

我们将改进的ED-ACO协议与经典的AODV协议相比较，在实验中，使用参数如表1，主要从3个方面来对比算法的性能：数据包的转发率、端到端的延迟、路由开销。为了验证算法的有效性，采用CBR流量模型产生32bytes到1024Bytes的数据包、多媒体数据包(1024Bytes)、标量数据包(32Bytes)。一个簇内的不同类型传感器仅仅发送一次数据包到Sink节点。视频节点的优先权高于标量节点。图10所示为AODV协议的包转发率，ED-ACO协议标量数据的转发率和多媒体数据包的转发率。不同的参数设置如下：

对于ED-ACO-S(标量数据)α=0,αe=1，最小剩余能量必须大于0，ED-ACO-M(视频数据)α=0,αε=1，对于视频数据包的损失率必须最小。

在所有流量类型下信息素的蒸发率ρ都为0.7。

从图3中可以发现，在实验开始时候，ED-ACO-S与AODV转发率都比较高，但是运行一段时间后，ED-ACO-M转发率远远高于ED-ACO-S和AODV。这是因为在开始阶段ED-ACO-M缺少足够的信息去发现有效的路径，但是经过一段时间，随着算法收敛，有效路径上的信息素增多，找到最优路径传输数据，数据包的转发因而提高。因此实验结论与我们的假设是一致的。

图3 数据包的转发率对比图

在图4中我们观察两个协议端到端的平均时延，在实验中，我们设置参数如下，α=0,αδ=1(αδ为累计队列延迟参数)。通过图4我们可以观察到ED-ACO-M和ED-ACO-S的端到端的延迟要比AODV协议要小，因为多路径的发现，当到达Sink节点的路径失效，数据包会立即使用其他路径传输而不用进行路由发现阶段，因此有效地减少了短刀段的延迟。在ED-ACO-S中，路由发现阶段主要考虑了剩余能量，所以不会把数据包都转发到最好的路径上，所以ED-ACO-S的延迟要比ED-ACO-M要高。

图4 端到端的延迟对比图

如图5所示，因为要周期性的去监测和维持路由所需条件产生了大量的F-ANT和B-ANT，所以ED-ACO的路由开销要大于AODV协议。

图5 路由开销对比图

4 结束语

无线传感器网络是应用相关的网络，数据采集是其主要的功能，采用分簇路由技术可以均衡的减少能量消耗，扩大网络生存期。本文采用分簇结构，利用蚁群优化算法在各簇头之间找到一条最短路径多跳传输数据，减少了数据传送距离。通过大量的模拟实验证明了ED-ACO协议在分簇方面良好的性能，有效地减少了因数据传送消耗的能量，最终在一定程度上延长了网络的生存期，保证了服务质量。

[1] Abbasi A A, Younis M. A survey on clustering algorithms for wireless sensor networks[J]. Computer Communications, 2007, 30 (14/15): 2826-2841.

[2] 张军强, 王汝传, 黄海平. 基于分簇的无线多媒体传感器网络数据聚合方案研究[J]. 电子与信息学报, 2014, (01): 8-14.

[3] Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on wireless communications, 2002, 1 (4): 660-670.

[4] 刘同来, 刘伟强. 无线传感器网络中基于扇形的非匀均分簇路由协议[J]. 微电子学与计算机, 2015(2): 100-104.

[5] Lan Y, Wenjing W, Fuxiang G. A real-time and energy aware QoS routing protocol for multimedia wireless sensor networks[A].IEEE[C]. 2008: 3321-3326.

[6] Akkaya K, Younis M. Energy and QoS aware routing in wireless sensor networks[J]. Cluster computing, 2005, 8 (2/3): 179-188.

[7] He T, Stankovic JA, Lu C,et al. SPEED: A stateless protocol for real-time communication in sensor networks[C]: IEEE, 2003: 46-55.

[8] Felemban E, Lee C G, Ekici E. MMSPEED: Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[J]. IEEE transactions on mobile computing, 2006, (6): 738-754.

[9] 邓 达, 周激流, 林 锋. 基于蚁群算法的无线多媒体传感器网络路由研究[J]. 北京理工大学学报, 2011(4): 456-460.

[10] 刘 逵, 刘三阳, 冯海林,等. 一种基于分簇蚁群策略的无线传感器网络路由算法[J]. 控制与决策, 2012(6): 929-932,936.

[11] Khediri S E, Nasri N, Wei A,et al. A new approach for clustering in wireless sensors networks based on LEACH[J]. Procedia Computer Science, 2014, 32: 1180-1185.

[12] 周德荣. 基于蚁群算法改进的AODV路由协议研究[J]. 西南师范大学学报(自然科学版), 2014(11): 75-80.

[13] 李芳芳, 王 靖. 一种基于LEACH协议的无线传感器网络路由算法[J]. 传感技术学报, 2012(10): 1445-1451.

Research on Wireless Multimedia Sensor Networks ant Colony Routing Algorithm Based on QoS and Clustering

Du Jiaxuan1，Ma Liya2，Yang Jun3

(1.School of Information Engineering， Ningxia University，Yinchuan 750021，China;2.General Hospital, Ningxia Medical University, Yinchuan 750021，China;3.Network Administrator Center, Ningxia University，Yinchuan 750021，China)

Aiming at the wireless multimedia sensor networks of QoS routing problem, this paper proposed a ED-ACO(Energy and best distribution of Cluster Head Distance-Ant colony optimization ) taking nodes statistics parameters ,packet loss, delay ratio, remain energy and available memory into consideration. ED-ACO used the clustering structure based on energy and best distribution of cluster head distance to partition networks uniformly, selecting the next hop to transmit sensor data according to the equation of state transition, in the same time it met the QoS requirements in WMSNs. NS2 simulation results indicates that ED-ACO compared with AODV satisfies the QoS requirements in packet loss ratio and delay ratio.

WMSNs；QoS；best cluster head distribution；ACO

2016-09-17；

2016-10-10。

国家自然科学基金项目(61261001)。

杜佳轩(1990-)，男，宁夏吴忠人，硕士，主要从事无线传感网方向的研究。

杨 军(1972-)，男，宁夏银川人，博士，教授，CCF会员，主要从事无线传感网方向的研究。

1671-4598(2017)02-0196-05

10.16526/j.cnki.11-4762/tp.2017.02.054

TP393.1

A