交通信息采集中WSN拥塞控制算法研究

曹 洁，郁 鑫

(兰州理工大学计算机与通信工程学院，甘肃 兰州 730050)

0 引言

交通信息采集在智能交通系统中占有很重要的地位，它是交通状态判断和预测、对交通流控制以及对紧急事件快速反应的依据［1］。由于无线传感器网络具备成本低，便于本地管理，易扩展等优良特性［2］，可以为智能交通系统的信息采集提供一种有效手段。然而，现有的无线传感网络仍然存在一些待解决的问题:无线传感网络的大规模部署、多跳或多对一的传输方式以及突发事件导致的数据流突发等原因容易引起网络拥塞，导致信息传输延时增大、数据丢失以及能量消耗过快，严重影响网络的服务质量。因此，若要提高交通信息采集监测数据的可靠性和实时性，就必须缓解无线传感网络的拥塞，另外网络能耗也是需要考虑的问题。

国内外学者针对无线传感器网络的特点提出了多种拥塞控制算法。ESRT［3］协议是第一个基于速率调节的拥塞控制协议，它综合考虑了网络对于可靠性和能耗的要求，通过对报告速率的适当调整，达到了减轻拥塞的同时提高可靠性和节省能量的目的。但是其需要网关具有覆盖整个网络的通信能力，使用简单的包数量统计的方式来衡量可靠性，且不区分数据源对信息逼真度的贡献能力，对所有节点采用统一的调整方案。CODA［4］能够调节局部节点造成的拥塞并采用逐跳控制信息减少能耗。但由于涉及网关和多个节点的反馈交互，在大规模网络中闭环控制调整速度相对较慢。基于流量调度的ARC［5］协议通过创建多元路径，增加传送的分组精度，同时避免冲突和重传能够节约大量的能量。CAR［6］协议提出了和ARC协议相近的方法，较适用于存在多种不同传输优先级的数据流的网络中。但是它对高移动数据源支持不足和为高优先级的数据流建立路由花费开销较大。BGR［7］协议同样结合了多径路由协议。与其它协议相比其实现机制较为简单，但随机选择的方式缺乏对邻居节点当前状况如能耗等的综合考虑，另外也存在将部分流量转发到周围其它拥塞区域的可能性。Gulluccio L等人提出CONCERT［8］采用数据聚合的方法减少网络中传输的数据量以减轻拥塞，达到延长网络周期的目的。PREI［9］协议还引入了多级聚合的思想，对相邻网格的数据进行再次聚合，以进一步减少传输的数据量，保证监测数据量突增情况下的传输效率。近几年，一些学者尝试根据系统控制和优化的方法，提出了适用于无线传感器网络的主动队列管理机制［10］。主动队列管理技术可以根据网络当前的状态预见可能出现的拥塞情况，并以丢弃或者标记分组的方式预先通知源端降低分组发送率，从而达到避免拥塞的目的。

基于以上分析考虑，为保证交通信息采集监测数据的实时性和可靠性，本文提出一种高性能拥塞控制HPCC(High-PerformanceCongestionControlAlgorithm)算法。实验表明:该算法在准确检测拥塞的同时有效地控制网络吞吐量、减少丢包数，进一步提升了交通信息采集系统的性能。

1 问题描述及算法的提出

无线传感网络作为一种新型技术，部署和维护十分方便，它被广泛用于智能交通信息采集系统中。如图1所示，基于WSN的道路交通监测系统具有以下特点:(1)传感器节点被大量地部署在道路两旁用来实时监测交通流数据;(2)节点需要将监测到的道路交通数据例如车流量、车速等以多跳或多对一的传输方式快速准确地传输到汇聚节点;(3)传感器节点和汇聚节点在部署后一般不发生位置的变动;(4)在突发性事件产生时，传感器网络中将会产生大量的数据。面向交通信息采集的无线传感网络与一般的监测网络有一定的区别，在交通信息采集时，一些数据相当重要，不允许降速，需要立刻传输到监测中心;同时传感器覆盖范围广，传输的数据流多样，有很多冗余节点。这些特性使得一般拥塞控制难以满足它的需求，而流量调度控制方法能够在不降低速率的同时对进入拥塞区域的数据流进行调度，通过绕路、分流等方式缓解拥塞，从而保证原有传输线路的畅通。但已有的流量调度算法存在以下问题:(1)拥塞检测方法比较单一，没有考虑网络状态特性，对网络拥塞程度估计不足;(2)分流路径选择时，简单综合各因素选择下一跳节点，忽略了具体环境对网络的影响。

图1 无线传感网络交通信息采集系统

针对以上问题，本文在流量调度算法的基础上，提出一种面向交通信息采集的高性能WSN拥塞控制算法。该算法通过引入拥塞预知状态指数准确检测拥塞，克服了传统检测方法的单一化、精确度不高的缺点;在产生拥塞时，对拥塞节点周围建立临时最佳路径进行分流调节，通过加入信道接入率这一参数保证了监测信息能够准确及时地传到汇聚节点，同时基于TOPSIS［11］理论思想构建选择模型，并将节点拥塞程度、剩余能量、距离原路径跳数以及信道接入率作为下一跳节点选择依据。

2HPCC算法

本算法分为拥塞检测和分流调节2个阶段。网络中的每个节点维护一个邻居节点信息表，该信息通过监听邻居节点发送的RTS帧获得。邻居节点信息表包含该节点通信范围内所有邻居节点的唯一标识号ID、拥塞程度、剩余能量、距离原路径跳数和信道接入率。拥塞程度，即节点缓存占用率，表明节点当前的拥塞度，在选择下一跳节点时尽量选择拥塞程度低的节点，以避免建立新路径后形成新的拥塞。新建路径既不能距离原始路径太远也不能距原始路径太近，太远会增大网络延时，而距离太近则可能导致更严重的拥塞，故将节点距离原路径跳数作为选择下一跳节点的依据。节点剩余能量的多少决定着节点使用周期，周期越长说明节点利用率越高。信道接入率反映了该节点无线链路质量的好坏，选择信道接入率高的节点有利于该节点快速接入信道。

2.1 拥塞检测

有效的拥塞检测是网络拥塞控制机制的一个关键部分。传统的拥塞检测方法均采用单一状态检测，没有考虑网络状态特性，这显然不符合实际情况。因此需要设计一种更为合理的拥塞检测方法。本文综合考虑了拥塞检测的精确性和实效性，定义拥塞预知状态指数(Congestion Predict State Index，CPSI)，利用队列缓存占有率与拥塞持续时间相结合的方法更新CPSI，预测网络拥塞发生趋势。C为拥塞预测状态指数且 C∈{0，1，2}，设队列缓冲区占有率为 r，2 个门限值为Rmin和Rmax，Th作为拥塞状态持续时间，门限值为Tc。表1为拥塞预知状态指数表。

表1 拥塞预知状态指数表

在HPCC算法中，具体的检测规则如下:

规则1 当r＜Rmin且Th=0时，C=0。说明节点的传输速率过低，导致节点缓存利用率过低，缓存资源利用不足，出现缓存空闲状况。

规则2 当 Rmin＜r＜Rmax且 Th＜Tc时，C=1。说明节点处于正常传输状态，无需改变当前传输状态。

规则3 当 r≥Rmax或 Rmin＜r＜Rmax且 Th＞Tc时，C=2。说明节点的传输速率过高，导致缓存利用率过高，本节点处将发生拥塞，缓存队列出现溢出状况，拥塞会导致最优路径失效，造成网络瘫痪。

2.2 分流调节

为了避免最优路径失效，当检测到拥塞时，本文将原始路径拥塞区域上游第一个非拥塞节点作为发起者(即为流量调度器)开始创建分流路径。为了选择最佳下一跳节点，HPCC基于TOPSIS理论构建选择模型，建立分流路径。TOPSIS思想是以靠近理想解和远离负理想解的程度作为评价指标。

2.2.1 节点属性归一化

定义节点 i的状态为 Di={xi1，xi2，xi3，xi4}分别代表节点的i的拥塞程度、剩余能量、跳数和信道接入率。发起节点首先在n个邻居节点中排除拥塞节点，从而将无拥塞节点作为备选节点，设备选节点有m个。在计算备选节点距离原路径跳数时，新建路径既不能距离原始路径太远也不能距原始路径太近，所以把备选节点距离原路径跳数的绝对偏差作为衡量节点属性的状态值，即每个备选节点距离原路径跳数与平均跳数的差值。由于备选节点的4个属性度量单位不一致，故采用归一化处理，生成备选节点规范矩阵如(1)式所示:

式(1)中vij为节点属性的归一化值，归一化过程如(2)式所示:

在备选节点的4个属性中，拥塞程度和距离原路径跳数绝对偏差是越小越好，为成本型指标;剩余能量和信道接入率是越大越好，属于效益型指标，根据式(3)和式(4)选出理想最优节点f*i和理想最差节点f'i，理想最优节点是成本效益指标最小和效益指标最大的节点;理想最差节点是成本效益指标最大和效益指标最小的节点。

理想最优节点:

理想最差节点:

其中，J*为效益型指标，J'为成本型指标，(fij)为参考节点加权判断矩阵。

2.2.2 节点属性度量

在选取下一跳节点时，希望所选取的备选节点的属性均是各属性最优的，即成本指标是最小而效益指标是最大的，但在实际中，这样的节点存在的可能性很小。在基于TOPSIS思想的选择模型中，为了综合考虑节点的各个属性，对所有属性进行加权处理。权向量的选择根据序关系分析法，在文献［7］中分析研究了节点的各个属性重要性，认为拥塞程度更为关键。本文同样基于该思想，认为节点拥塞水平更重要，所以权向量(w1，w2，w3，w4)可以选择为(0.4，0.2，0.2，0.2)，确定权向量后可以生成加权判断矩阵Z，综合度量节点属性信息，加权矩阵如式(5)所示:

2.2.3 节点综合贴近度

在实际选择中如果效益指标(剩余能量、信道接入率)比较高，成本(拥塞度、距离原路径跳数)也相对较高，就不属于最优的节点，或者成本和效益都比较低也不属于最优节点。在综合考虑成本指标和效益指标时，采用度量欧式距离的方法，即计算备选节点与理想最优和理想最差节点的欧式距离，再综合考虑节点贴近度，选择出贴近度最大节点即为最优节点。

备选节点离理想最优节点的距离:

备选节点离理想最差节点的距离:

备选节点贴近度的计算:

根据备选节点贴近度的大小对其进行排列，贴近度最大的节点就是需要查找的下一个节点。从此节点开始采用同样的方法继续寻找下一跳节点，直到新路径创建完成。

3 仿真实验与分析

为了验证算法的有效性，本文设计了基于NS2的仿真实验对算法性能进行分析与评价。设仿真场景部署在500 m×500 m的监测区域内，节点通信半径为50 m。MAC协议为802.11DCF，所有节点初始能量为1J，缓存大小为80个数据包，拥塞阈值为0.8，数据包大小为512 bytes。

数据传输的实时性和可靠性是WSN的重要性能评价指标，吞吐量反映网络的可靠性程度。端到端时延则反应了网络的实时性。图2对CODA、CAR和HPCC的网络吞吐量进行对比。从图中可以看出，0～30 s内，三者吞吐量基本一致，这是由于源速率比较低，网络中原路径能够承载此时的数据流量，因此，没有拥塞发生。30 s之后，增大源节点发包速率，源通信量增多，网络中发生拥塞，此时，HPCC和CAR迅速调整资源供应，建立新路径，为原始路径分担流量，吞吐量得到提升。而CODA通过调整上游节点和源节点速率缓解拥塞，从而使其吞吐量没有随着源数据量的增加而升高。HPCC的吞吐量高于CAR，这是由于本文算法添加信道接入率作为选择下一跳节点的依据，同时通过TOPSIS多属性决策模型进行选择最佳下一跳节点，所以，创建的新路径优于CAR所建路径，故吞吐量性能得到了提升。

图2 CODA、CAR和HPCC的网络吞吐量对比

图3 CODA、CAR和HPCC的平均端到端时延对比

图3为CODA、CAR和HPCC的平均端到端时延对比图。开始阶段，缓存器内数据包不断累积导致数据包排队等待时间增加，所以3种算法的延时均迅速增大。CAR和HPCC在拥塞后，均创建一条新路径为原始路径分担流量，降低节点缓存队列长度，从而减少了数据包在节点队列中的排队等候时间。而CODA通过抑制上游节点转发速率，虽然缩短了拥塞节点的队列长度，但上游节点中数据包传输延时增大，所以，其平均端到端延时变大，延时高于CAR和HPCC。在50 s后，延时趋于稳定，这是由于源通信量稳定，新路径建立后为原始路径分担流量使网络负载状态趋于稳定。图中HPCC的延时较CAR降低了20%左右，因为采用了拥塞预知状态指数来快速准确判断网络状态，所以HPCC延时性能优于CAR。

考虑节点能量受限是WSN的最大特点，在保证数据传输可靠性的前提下尽可能减小通信路径上的能量消耗，将有利于提高能量利用率，最大化网络生命期。由图4可以看出HPCC消耗能量的速率慢于CODA和CAR。这主要是由于CODA涉及网关和多个节点的反馈交互，消耗的能量较大，CAR建立分流路径消耗了大量的能量，而HPCC通过TOPSIS模型选择快速分流的同时周期性扫描缓存队列，消耗的能量相对较小。网络资源能够有效利用，表现出更好的节能性。

图4 CODA、CAR和HPCC的能耗对比

4 结束语

结合面向交通信息采集的无线传感器网络特点，针对已有流量调度算法的不足，本文提出了一种基于流量调度的HPCC拥塞控制算法。本算法通过准确有效的拥塞检测对网络拥塞状态进行预测。在分流调节时，将节点拥塞程度、剩余能量、距离原路径跳数以及信道接入率作为下一条节点选取依据，根据TOPSIS模型来合理选择下一跳节点，从而创建分流路径为原始路径分担流量。实验表明:本算法能保证网络吞吐量，降低延迟，减小网络能耗。

:

［1］齐楠，韩波，李平.智能交通系统中无线传感器网络的应用［J］.机电工程，2007，24(10):225-234.

［2］张玉鹏，刘凯，王广学，等.基于无线传感器网络的跨层拥塞控制协议［J］.电子学报，2011，39(10):2258-2262.

［3］Sankaasubramaniam Y，Akan B，Akyidiz O.Event-to-sink reliable transport in wireless sensor networks［C］//Proc.of the 4th ACM Int’l Symp.on Mobile Ad Hoc Networking and Computing.2003:177-188.

［4］Wan C，Eisenman S，Campbell A.CODA:Congestion detection and avoidance in sensor networks［C］//Proc.of the 1st Int’l Conf.on Embedded Networked Sensor Systems.2003:266-279.

［5］Kang J，Zhang Y，Nath B.Adaptive resource control scheme to alleviate congestion in sensor networks［C］//Proc.of 1st Workshop on Broadband Advanced Sensor Networks(BASENETS).2004.

［6］Kumar R，Rowaihy H，Cao G H，et al.Congestion Aware Routing in Sensor Networks［R］.PSU Technical Report，2006.

［7］Popl L，Raiciu C，Stoica I，et al.Reducing congestion effects in wireless networks by multipath routing［C］//Proc.of the 14th IEEE Int’l Conf.on Network Protocols(ICNP).2006:96-105.

［8］Gulluccio L，Campbell A T，Palozzo S.CONCERT:Aggregation-based congestion control forsensornetworks［C］//Proc.of the 3rd ACM Conf.on Embedded Networked Sensor Systems(SenSys).2005:274-275.

［9］Ngai E，Zhou Y F，Lyu M R，et al.Reliable reporting of delay-sensitive events in wireless sensor actuator networks［C］//Proc.of the 3rd IEEE Int’l Conf.on Mobile Adhoc and Sensor Systems(MASS).2006:101-108.

［10］Lachlanl H，Sthphen V，Rami G.Active queue management for fair resource allocation in wireless networks［J］.IEEE Transactions on Mobile Computing，2008，7(2):231-246.

［11］梁昌勇，戚筱雯.一种基于TOPSIS的混合多属性群决策方法［J］.中国管理科学，2012，20(8):109-117.