无线车辆检测系统能量高效分时分簇路由研究

雷　旭，丁　恒，闫茂德（.长安大学电子与控制工程学院，陕西西安　70064；.合肥工业大学交通运输工程学院，安徽合肥　30009）



无线车辆检测系统能量高效分时分簇路由研究

雷旭1，丁恒2，闫茂德1
（1.长安大学电子与控制工程学院，陕西西安710064；2.合肥工业大学交通运输工程学院，安徽合肥230009）

摘要：为了均衡地磁式无线车辆检测器网络的能量负载和延长系统生命周期，文章设计了无线通信分簇算法与路由协议。针对城市交通控制的应用场景，考察被测对象——交叉口交通流的运动变化规律，将日交通流变化划分为高峰时段、低峰时段和平峰时段3个阶段，提出按3个阶段分别设计的分簇算法，即高峰时段的节点主动式（proactive）分簇算法、低峰时段的节点被动式（reactive）分簇算法和平峰时段的主动分簇被动重构分簇算法；在此基础上，依据第1顺序无线电模型，引入中继簇首剩余能量作为权重因子，设计了单跳多跳自适应数据传输路由；最后，采用OMNeT＋＋对算法协议进行了建模仿真，以系统生命周期、死亡节点占有率和系统剩余能量作为性能指标进行对比分析。结果表明，算法协议能够提高系统的能量利用率，有效平衡节点能耗，延长了系统的生命周期。

关键词：交通信息物理系统；无线车辆检测器；无线传感器网络；能量负载均衡；分簇算法

闫茂德（1974-），男，陕西澄城人，博士，长安大学教授，硕士生导师.

车辆检测技术是交通信息物理系统（T-CPS）感知层的关键技术，主要包括对交通流量、交通密度、行驶速度和行驶时间等交通要素的信息感知［1］，为实施交通状况监控和交通管理提供重要依据。近几年，基于各向异性磁阻效应（AMR）的地磁传感技术成为研究热点［2］。地磁车辆检测器由于具有体积小、灵敏度高、成本低、不易受环境因素影响和安装方便等优点，已经在城市智能交通控制系统中得到了大量应用。为了最大限度发挥地磁传感技术的优势，检测系统通常采用无线传感器网络（WSN）作为主要数据通信方式。依托WSN的分布式、自组织、高容错等特性，无线地磁式车辆检测器提高了检测精度和识别率。节点能耗、系统生命期、网络传输实时性和通信质量是WSN重点关注的问题［3］，因此数据传输的路由技术直接影响WSN的性能。国内外对WSN的路由协议做了广泛的研究，文献［4］最早提出了LEACH（low-energy adaptive clustering hierarchy）路由协议，基于概率随机分配原则，达到降低网络能耗、延长生命周期的目的，从此WSN分簇思想开始成为研究重点；文献［5］提出了HEED（hybrid energy-efficient distributed clustering）协议，采用完全分布式的簇首选举机制，在更快分簇的同时产生更加均匀、合理的网络拓扑；文献［6］提出了由汇聚节点执行Mamdani模糊逻辑方法统一集中式的簇首选举机制；文献［7］提出一种区域中心式的分簇路由协议；文献［8］针对电磁传感器网络的特点提出了一种群规模约束分群算法；文献［9］针对矿井巷道的应用情况提出了基于动态路径损耗指数的最小能耗中继路由算法；文献［10］为建筑能耗监测系统设计了基于位置信息的数据汇聚路由策略。

WSN具有很强的应用相关性，不同应用中的路由协议可能差别很大，已有的研究大多集中在通用WSN路由协议方面，而针对实际WSN具体应用场景的特殊性来研究路由协议的还不多。本文针对无线车辆检测器在城市交通控制应用中的具体需求，设计了考虑交通应用特点的能耗均衡路由协议，在保证网络通信质量和实时性的前提下，解决网络整体能耗均衡问题。实际测试数据表明，路由协议能够有效平衡网络负载，提高系统的生命周期。

1　无线车辆检测系统网络特性

无线车辆检测系统（wireless vehicle detector system，WVDS）在城市交通控制（UTC）中大量应用于交叉口，作为T-CPS的感知层，为整个UTC系统提供基本交通数据，系统的安装位置示意图如图1所示。系统由感知节点（Sensor）和汇聚节点（Sink）组成，感知节点预埋在路口车道上由电池供电，用于获取固定车道上的交通参数信息，通过自组织网络传递数据；汇聚节点安装在交叉口道路旁，一般由固定电源供电，负责收集感知节点检测的信息、管理无线网络和向数据中心上传检测信息。感知节点一旦安装不易拆卸，由电池供电工作在低功耗模式，存在固定生命期；汇聚节点一般处理能力强，能够承担较复杂运算，具备与数据中心远程连接的功能。

图1　无线车辆检测系统示意图

由于具体应用需求与传统WSN不完全相同，WVDS还具有其自身的特殊性。

（1）传统WSN节点一般将监测数据简单处理之后直接通过网络发至汇聚节点，而WVDS中的感知节点为了较少的能耗和通信的高效，一般不直接传送检测的磁场扰动信息，而是先对原始数据做归一化处理后再向网络发送，供汇聚节点进一步处理。WVDS中有效感知信息已经过感知节点预处理，因此WVDS感知节点不需要周期性地与网络同步数据，只在有数据发送需求时才联网通信。

（2）系统中每个节点安装位置固定，因此在路由协议中每个节点的位置信息是常数，节省了通信的开销。

（3）为了获取车流速度等信息，感知节点一般在同一车道成对安装，其工作负载随着每天各时段交通量的不同而差异很大。

路由协议直接影响WSN整体网络的传输性能，决定着系统的生命期，因此路由协议对WVDS至关重要。路由协议在设计时应充分考虑系统网络的应用背景条件，目标是实现网络传输的高质量和系统性能的高效率。

2　考虑交通流因素的分簇路由协议

WVDS的检测对象是车辆通过信息和交通流，被测对象的运动规律对WVDS的工作模式有重要影响。为此，对普通交叉口交通流的动态变化规律进行了考察，西安市凤城八路-文景路交叉口的周小时交通量数据变化规律如图2所示。

图2　交叉口周小时交通量数据变化图

由图2可以看出，交叉口的交通流运行行为明显分为3个状态，即拥堵、正常和消散［11］。交通流运动变化的3个时段和WVDS中感应节点的平均触发时间见表1所列。

表1　交通流运行行为时段表

由于检测对象的动态变化特征直接影响WVDS工作的整体任务负载，网络路由协议的构建也应重点按照任务负载的3个阶段分别考虑。一般无线传感器网络的工作进程以“轮”为单位周期开展，每轮分簇包括1个建立期和n个稳定期［4］。其中，建立期即簇首选举阶段，稳定期完成簇内数据通信。本文根据网络负载的3个状态分别设计簇首的选举算法，在系统控制上，3个状态的切换由汇聚节点根据交通流经验数据得出的3个时段进行统一调配。

2.1高峰时段的节点主动式分簇路由

根据交通流数据，在高峰时段，系统感应节点平均1.0 s触发1次，在这种高负载工作状态下，系统整体能耗是需要考虑的第1因素。因此，应尽可能等概率地随机分簇，从而使系统整体达到负载平衡。为了降低感应节点与汇聚节点信息传递的频率，减少能量损耗，基于LEACH思想，采取分布式的分簇原则，即节点主动式成簇算法。

在进入高峰时段后的第1轮网络周期，汇聚节点收集完网络内所有节点信息，广播命令，网络切换至分布式分簇路由阶段。每个节点生成1个介于0～1之间的随机数，如果小于阈值T（n），则该节点在本轮中当选为簇首节点。簇首节点向临近节点广播当选消息，临近节点选择数据通信代价较小的簇首加入成簇。

本文结合WVDS在交叉口车流高峰时段系统运行的特点，考虑节点剩余能量和网络整体能耗因素，改进DCHS（deterministic cluster-head selection）［12］中T（n）的计算方法，即

其中，p为簇首节点占总节点数的比例；r为当前轮数；En-current为节点当前的能量；-Em为每次进入高峰时段汇聚节点计算的网络节点当天的初始平均能量；rs为节点连续未当选过簇首的轮次；G为前r个周期内未成为簇首节点的集合。一旦节点被选为簇首，rs则被设为0。

（1）式吸收了DCHS的核心思想，但WVDS在安装运行后的实际状态是一个感知节点相互异构的系统，且随着系统运行各节点剩余能量表现出不平衡；而在感知节点处理器运算能力有限的条件下，复杂算法会增加计算开销，反而消耗更多能量。因此，在DCHS中引入作为参考常数，用于每个节点计算阈值T（n），在选举簇首过程中引入节点剩余能量因素，增大剩余能量多的节点成为簇首的概率。设计算法在每天进入高峰时段前由汇聚节点统一计算系统节点平均剩余能量，在广播时发送给每个节点。

2.2低峰时段的节点被动式分簇路由

交通流在进入低峰时段后急剧减小，系统感应节点的平均感应触发时间为8.0 s。这种情况下，每个节点的数据通信负荷都很低，应尽量减少节点参与网络通信的频率，以减少节点能量损耗。最优的方式是采用集中式分簇路由算法，由汇聚节点根据各节点剩余能量和位置情况对整个网络进行统一分簇，即节点被动式成簇算法。这样可以最大程度发挥汇聚节点的计算性能，以生成接近最优的网络结构；同时，使非簇首节点在无车触发时关闭无线收发模块，节省能量。

由图2可知，每个交通量变化周期中只有1个连续的低峰时段，于前一天第2个平峰时段结束的20：00开始至第2天上午7：00结束。在进入低峰时段后，汇聚节点向当前簇首节点发布路由切换广播，簇首节点对簇内节点发布广播命令。

算法开始时，各节点向汇聚节点发送带有自身标志和当前剩余能量的短消息。汇聚节点根据所有节点的剩余能量计算系统节点平均能量值，并将该值设为门限值，剩余能量大于门限值的节点加入簇首节点集合，反之，则加入非簇首节点集合。从簇首节点集合中选出合适数量和数据通信代价最优的簇首集合是一个NP完全问题。汇聚节点运行模拟退火（simulated annealing）算法［13］解决该NP问题。

汇聚节点进行重复迭代运算，随机选择簇首节点集合C，随机且独立地扰动C中的坐标为（x，y）的节点c，得到新坐标（x'，y'），选择位置最靠近该坐标的点c'组成新的集合C'。定义包含节点c的集合C的代价为f（C），即

其中，di，c为节点i到节点c的距离。

分别计算f（C）和f（C'），若f（C'）＜f（C），则接收C'为下一状态的簇首集合；否则，按概率Pk判断C'是否成为下一状态的簇首集合，其中Pk定义如下：

其中，αk为控制参数，定义如下：

通过多次迭代运算，汇聚节点筛选近似最优簇首集合，把簇首集合和每个簇的结构信息向所有网络节点广播。

2.3平峰时段的主动分簇被动重构分簇路由

交通流量的2个平峰时段都在高峰时段过后的阶段，这期间感应节点的平均触发时间间隔在3.0 s左右，与高峰时段感应节点频繁触发状态相比，工作负荷相对减小。但此时系统整个网络的数据通信仍保持在一个相对频繁的水平，若采用集中式分簇算法，各节点会高频率地与汇聚节点进行数据传输，耗费节点剩余能量，降低系统整体生存时间。若继续延续高峰时段的分布式分簇路由，则会进行频繁的分簇切换，由于触发时间间隔较长，很多节点没有检测数据更新时也要参与分簇过程，使得能量效率降低。为了减小感应节点与汇聚节点的通信代价，提升节点剩余能量的使用效率，应对繁忙时段系统通信的特殊性，平峰时段采用集中与分布相结合的分簇路由算法。

进入平峰时段后的第1轮，系统继续按照高峰时段的分布式路由算法先由节点主动成簇。从第2轮起，汇聚节点执行类似低峰时段的集中式分簇路由。具体地，在每轮开始之前，将上一轮收集到的各节点剩余能量汇总并计算出Eavg作为阈值。将上一轮各簇首节点的剩余能量Ecurrent与阈值进行比较，若Ecurrent＞Eavg，则继续维持该簇首及簇结构不变；若Ecurrent＜Eavg，则维持簇结构，重新选取簇内剩余能量最高者为簇首节点，并向全网进行广播。之后，网络进入稳定通信阶段。

当执行至第r轮，满足条件：

其中，λ为小于1的经验调节系数，值的大小由平峰时段与高峰时段感应节点综合响应时间的比值决定。此时，汇聚节点向全网广播，解散之前r轮的各簇首和簇结构，各节点重新运行前述的分布式分簇算法对网络簇首进行重选。汇聚节点将r清零重新计数。

3　数据传输的路由协议

3.1能耗模型

采用第1顺序无线电模型［14］，节点在距离d上发送和接收1条长度l bit消息的能耗分别为：

其中，Eelec为传输电路中处理1 bit数据所需要的能量；efs为自由空间模型中的能量消耗系数；emp为多径衰落模型中的能量消耗系数。

由能量模型可知，信号在无线信道传输中的能量消耗与d有关。当d小于阈值d0时为自由空间模型，能量消耗与距离的平方成正比；当d大于阈值d0时为多径衰落模型，能量消耗与距离的四次方成正比。假设信道是双向对称的，即节点A传送数据到节点B的能量消耗与B传送到A是相同的。

3.2路由的单跳与多跳选择

WVDS的网络属于中小型规模的无线传感器网络，在现有硬件条件下分簇后的各簇首都具备直接与汇聚节点通信的能力，但单跳通信不一定是最优的通信路由方式。以自由空间模型为例，能量消耗与距离的平方成正比，如图3所示，若簇首节点i通过中继簇首节点j传输到汇聚节点s，则传输过程所消耗的能量为：

若簇首节点i直接将数据传输到汇聚节点s，则能量消耗为：

图3　路由的单跳与多跳选择图

3.3多跳路由中继节点选择

在数据传输的多跳路由中，考虑各簇首的剩余能量因素，引入簇首权重Wi，代表簇首节点i通过一跳范围内的簇首节点j转发数据时能量耗散权重。Wi定义如下：

其中，Ei为簇首节点i的剩余能量；e-为所有簇首节点剩余能量的平均值；di为簇首节点i到汇聚节点的距离；di，j为簇首节点i到簇首节点j的距离；dj为簇首节点j到汇聚节点的距离；ρ为调节系数。

根据贪婪算法，簇首节点以簇首权重定义式计算出与相邻簇首节点间的权重值。将权重值小于0的簇首节点排除，生成按大小排列的中继候选列表。当簇首节点i需要发送数据至汇聚节点时，在中继候选表中选择权重值最大的相邻簇首节点作为中继簇首节点j，然后中继簇首节点j会按与簇首节点i一样的原则进行数据传输。如果在列表中没有合适的中继节点，簇首节点则将数据直接发送给汇聚节点。

3.4补充机制

上述路由算法长时间运行后，临近汇聚节点的簇首节点承担过重的数据转发工作，导致能量快速消耗。为了平衡系统各节点能耗，将系统簇首节点剩余能量的均值设为门限阈值。在每轮建立期，各簇首节点将剩余能量Ei与相比较，若则向其他簇首节点发送1个“退出转发中继”的广播。其他簇首节点收到广播后，核对内部中继候选列表，若存在该节点，则将其删除。

4　仿真与实验数据分析

本文针对无线车辆检测系统设计了以能量均衡为目标的分时段分簇算法的无线数据通信路由协议DPEE（divided period energy-efficient distributed clustering）。为了对所提出的算法和协议进行充分验证和实验，选用OMNeT＋＋软件作为仿真平台。实验设计对WVDS中车辆检测的能耗进行简化，重点关注其网络传输部分，将WVDS常用的传统ad-hoc平面路由协议和不考虑车流量因素的单一LEACH分簇协议作为比对参照，通过仿真实验结果的对比和分析，对本文提出的算法和协议的有效性进行评估。

实验按照图1中节点布设的相对位置，在100 m×100 m的分布区域内建立了无线车辆检测系统仿真模型，网络环境参数见表2所列。

仿真实验对比分析的3个性能指标如下：

（1）系统生命周期。网络生命周期将从出现第1个死亡节点和最后1个死亡节点的时间2个方面考察，评估算法和协议对无线车辆检测系统整体的能量利用效率。

（2）死亡节点占有率。比较死亡节点占网络总节点数的百分比随网络运行的变化情况，评估算法和协议对系统能量的平衡性。

（3）系统整体剩余能量。考察系统各节点剩余能量的总和随网络运行时的变化情况，评估算法和协议的节能性。

表2　仿真模型环境参数

网络生命周期的仿真结果对比如图4所示。由图4可看出，本文算法协议直至1 137轮才出现第1个死亡节点，至3 276轮最后1个节点死亡；而ad-hoc协议和LEACH协议分别在643轮和829轮出现第1个死亡节点，分别在1 306轮和1 781轮最后1个节点死亡。因此，本文DPEE算法协议在节点的能量利用效率上具有优势。

图4　网络生命周期仿真结果对比

死亡节点占有率随网络运行的变化曲线如图5所示。由图5可以看出，在同一死亡节点占有率下，本文DPEE算法的节点生存时间明显比其他2种算法长，而且死亡节点增长缓慢，体现了其对网络整体生命周期的延长作用。另外，曲线的变化率在3 000轮之前都保持较低水平，体现出本文算法协议较好地平衡了网络节点的能量。

全网总剩余能量的对比曲线如图6所示。仿真分别运行1 000轮时，3种算法协议的系统总剩余能量分别为28.1、20.7、11.9 J。从变化趋势上看，本文算法协议的系统总剩余能量变化平缓，而ad-hoc平面路由协议下降最快。原因在于本文算法对系统节点的剩余能量进行了较好的平衡，单独LEACH算法由于存在分簇不均匀的问题，并且与ad-hoc平面路由一样都没有考虑交通流变化的影响因素，因此导致整体能耗不平衡和过快的耗能速度。

图5　死亡节点占有率变化曲线

图6　全网总剩余能量的对比曲线

5　结束语

本文针对无线车辆检测系统的应用场景特点，结合分析交通流运动变化规律，考虑工程应用需求的情况，设计了均衡无线车辆检测节点能耗的分簇算法和无线通信路由协议。采用OMNeT＋＋建立仿真模型，仿真实验结果表明，本文算法和协议能够有效地节省系统能量、均衡负载和系统的能量分布，对系统运行的生命周期有较好的延长作用。然而，实际应用中交叉口交通流变化规律在空间和时间上都是动态的，因此，以本文研究为基础，在无线通信路由协议中考虑适应交通流动态变化的算法是进一步研究的重点。

［参考文献］

［1］孙棣华，李永福，刘卫宁，等.交通信息物理系统及其关键技术研究综述［J］.中国公路学报，2013，26（1）：144-155.

［2］雷旭，侯莹莹，武奇生.地磁车辆检测器车型分类算法设计［J］.长安大学学报：自然科学版，2013，33（5）：118-123.

［3］Cheng C T，Tse C K，Lau F C M.A delay-aware data collection network structure for wireless sensor networks［J］.IEEE Sensors Journal，2011，11（3）：699-710.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks ［C］//Proceedings of the 33rd Annual Hawaii International Conference on System Sciences.IEEE，2000：3005-3014.

［5］Younis O，Fahmy S.HEED：a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3（4）：366-379.

［6］Gupta I，Riordan D，Sampalli S.Cluster-head election using fuzzy logic for wireless sensor networks［C］//Proceedings of the 3rd Annual Conference on Communication Networks and Services Research.IEEE，2005：255-260.

［7］高腾.能量高效的无线传感器网络分簇路由协议研究［D］.大连：大连理工大学，2011.

［8］李鑫，张霞，于宏毅.一种电磁传感器网络的群规模约束分群算法［J］.电路与系统学报，2013，18（2）：457-465.

［9］Qiao G Z，Zeng J C.Power saving route algorithm on underground wireless sensor networks［C］//International Conference on Future Information Technology and Management Engineering.IEEE，2010：394-398.

［10］周俊青，汪鹏，刘国栋，等.基于区域划分的WSN数据汇聚路由算法［J］.合肥工业大学学报：自然科学版，2012，35 （12）：1648-1651，1713.

［11］庄斌，杨晓光，李克平.道路交通拥挤事件判别准则与检测算法［J］.中国公路学报，2006，19（3）：82-86.

［12］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection ［C］//IEEE Conference on Mobile and Wireless Communications Networks.IEEE，2002：368-372.

［13］卢建中，程浩.改进GA优化BP神经网络的短时交通流预测［J］.合肥工业大学学报：自然科学版，2015，38（1）：127-131.

［14］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.

（责任编辑胡亚敏）

Research on divided-period energy-efficient clustering routing protocol for wireless vehicle detector system

LEI Xu1，DING Heng2，YAN Mao-de1

（1.School of Electronic and Control Engineering，Chang’an University，Xi’an 710064，China；2.School of Transportation Engineering，Hefei U-niversity of Technology，Hefei 230009，China）

Abstract：In order to balance energy consumption and prolong the lifetime of the geomagnetic wireless vehicle detector system，a design of clustering algorithm and routing protocol for wireless communication is proposed.According to the application scenarios of Urban Traffic Control（UTC），the motion feature of traffic flow of urban road intersection is investigated.The daily process of the traffic flow is divided into three parts，including peak period，low peak period and flat peak period.The clustering algorithm is designed respectively in accordance with the three periods，namely the proactive clustering algorithm for peak period，the reactive clustering algorithm for low peak period，and the proactive clustering and reactive reconfiguration algorithm for flat peak period.According to the first order radio energy dissipation model，the adaptive protocol about single-hop to multi-hop is provided.In the protocol，the remaining energy of relay cluster heads is introduced as weight factor.Finally，the protocol is simulated on OMNeT＋＋.The life cycle，death nodes occupancy and remaining energy are selected as measurement indexes.The results show that the protocol is able to improve the energy efficiency，balance the energy consumption and prolong the life cycle of the system.

Key words：traffic-cyber physical system（T-CPS）；wireless vehicle detector；wireless sensor network （WSN）；balance of energy consumption；clustering algorithm

作者简介：雷旭（1981-），男，河南三门峡人，长安大学高级工程师；

基金项目：国家自然科学基金资助项目（61304195）；中央高校基本科研业务费基础研究资助项目（2014G1321037）；安徽省自然科学青年基金资助项目（1408085QF111）和西安市科技计划资助项目（CXY1436（10））

收稿日期：2015-05-21；修回日期：2015-07-14

Doi：10.3969/j.issn.1003-5060.2016.01.004

中图分类号：U495

文献标识码：A

文章编号：1003-5060（2016）01-0020-07