基于WSNs智能交通系统的非均匀分簇路由

游子毅，章俊华，陈世国，王 义

（1.贵州省机械电子产品质量监督检验院，贵州 贵阳550081；2.贵州师范大学 物理与电子科学学院，贵州 贵阳550001；3.贵州省教育厅汽车电子技术特色重点实验室，贵州 贵阳550001）

0 引 言

路由协议对于交通信息采集中的网络传输性能尤为关键。由于分簇路由协议具有节能性好等特点，现已成为重点研究的一 类 无 线 传 感 器 网 络 （WSNs）路 由 协 议［1，2］。LEACH［3］是最早出现的均匀分簇路由协议，但是该类分簇结构也带来了一些问题。研究结果表明，随机选择簇头和簇内单跳路由会增加节点能耗并限制网络规模。此外，在规模较大的WSNs中，簇头间采用多跳通信方式与Sink节点 通 信，从 而 造 成 “热 区”问 题［4，5］。Heed 是 基 于LEACH 改进的成簇协议，主要在簇首选举中加入能量因素考虑［6］；TEEN［7］的主要框架和LEACH 一致，是一种应对时间紧急事件的响应式路由协议。LEACH，Heed 和TEEN 协议都没考虑到 “热区”问题。EEUC 是一种非均匀成簇路由协议［8］，其根据距离Sink节点的远近由近至远构造由小到大的簇半径，使靠近Sink节点的簇的成员数少于远离Sink节点的簇，从而减轻靠近Sink节点的簇头能量的消耗。然而，EEUC算法适合分布较均匀的情况。如果在实际的应用环境中节点分布不均匀，EEUC 还是无法缓解 “热区”问题。

在智能交通场景中，传感器节点多，采集的原始数据量较大。此外，车辆节点具有高移动性，使得车辆传感网的节点分布情况比静态传感器网络具有更频繁的变化。因此，现有的分层WSNs路由协议都不太适合智能交通环境。本文提出了一种能量均衡的非均匀分簇路由协议 （UCSNP）用于智能交通系统。该协议着重对非均匀成簇、簇间路由以及簇半径调整进行讨论。结合智能交通的特点，UCSNP建立链式结构［9］和分簇结构混合的通信方式，并在这种通信方式下，通过混合蛙跳算法［10］对簇间路由进行优化，动态调整簇通信半径。UCSNP 使网络拓扑更加合理，提高网络的生存周期并且减短了网络的收敛时间。本文在文献 ［11］基础之上解决基于WSNs的交通信息传输的“热区”问题。

1 混合蛙跳算法

首先，随机生成F 个解 （青蛙）作为初始种群。第i个解可表示为d 维问题的解Xi＝｛xi1，xi2，...，xid｝。其适应度可表示为Yi＝f（Xi），其中Yi为目标函数。F 只青蛙按Y值降序排列，并记录具有最好适应度的解Xg为整个种群中的最好解。然后把整个种群平均划分到m 个包含s 个解的子种群：F ＝m×s。在每个子种群中，将适应度最好的解和最差的解分别记为Xb和Xw。由每个子种群通过局部搜索对最差解Xw进行更新

式中：dj表示分量j 上移动的距离；rand（）是0到1之间的随机数；Dmax是青蛙允许移动的最大距离。当本轮局部搜索完成后，所有簇群的青蛙重新混合、排序并划分新簇群，开始下一轮的局部搜索。不断循环直到达到迭代次数。

2 UCSNP协议

2.1 网络模型与分簇策略

在智能交通的应用中无线传感器网络结构设计由车辆之间组成的移动的、分布式自组织形式与公路设施上传感器间组成的固定无线网络结构相结合［12］。存在两种信息通信 类 型，一 种 称 为 车—车 协 同 系 统 Vehicle－to－Vehicle（V2V），即车辆配备传感器以进行车辆之间的信息交互，这对于避免如交通堵塞等严重情况至关重要，另一种称为车—路协同系统Vehicle－to－Infrastructure（V2I），即车辆与安装在公路固定设施上的传感器之间进行信息传输，这对于在道路特别是高速公路上交通情况的及时反馈尤为重要。

假定在二维平面区域：Z2＝｛（x，y），0≤x，0≤y｝，所有的传感器节点 （车辆和固定设施）随机分布。该区域可通过具体的原则和方法网格化［13，14］，其格状网每个正方形小区域为α×α，边长α根据应用任务的求解精度而定。假设两个节点的位置分别为LP（xi，yi）和LQ（xj，yj），则两个位置之间的距离为

将该区域划分成n个区，n的数量由该区域的长度和分区节点的通信半径确定。Sink节点部署在区域外的一个固定位置。为了实现能耗均衡，距离Sink节点近的分区内的簇数目应多于远的分区。由于交通环境下车辆节点的高移动性，每个簇的簇头由Sink节点指定为该簇区内的一个固定设施。其它节点与簇头之间单跳通信，簇头可通过调整通信半径控制成员数以减小通信负载。对于相邻的两个簇簇头CHi和CHj，则D（CHi，CHj）≥RCHi＋RCHj，其中D（CHi，CHj）表示CHi与CHj之间的距离，RCHi和RCHj表示相应的半径。此外，不在任何一个簇通信半径覆盖下的传感器节点可采用链式结构［9］的多跳通信，基于贪婪算法选择信号强度最好的中继节点传送感知数据，以此方式将数据传递至距离最近的簇内的成员节点。该节点作为链首进行一次数据融合后，将数据包发送至簇头，如图1所示。

图1 链式和分簇混合的网络结构

网络中的每一个传感器 （车辆和路边设施）都有一个唯一的标志ID，由可信中心 （trusted authority）负责对节点认证、注册并授权。节点可通过ID 号和TA 签发的数字证书相互验证身份。

节点能量模型描述如下，节点发射l比特数据到距离为d 的位置，则发送端的能量为

接收端的能量为

其详细说明参见文献 ［8］。

2.2 簇间路由初始化参数

簇区内簇头CHi周期性地向其他成员节点发送询问报文REQ 以同步时间。每一轮采样l（1≤l≤N），簇头CHi将接收到的感知数据进行融合，生成新的数据包传送至Sink节点。传送时，CHi会选择相邻簇头作为中继节点转发数据包。因此，从源点CHi到Sink节点之间可生成一条或多条不同的路径。除与Sink节点一跳距离的簇外，簇头CHi可随机生成F 只青蛙，每只青蛙个体表示一条从CHi到Sink节点的可行路径，即P ＝｛P1，P2，...，Pd｝，其中d表示解空间的维数，Pi＝｛CHi，...，CHx，Sink｝。P 即为生成的初始群体。

青蛙个体的适应度主要依据传输数据的能耗和可靠性来计算。定义适应度函数为

式 （7）中，α1＋α2＋α3＝1；CHi∈Pi表示CHi是路径Pi上的一个节点；nk∈ci表示nk是簇ci内成员节点；ERX（CHi，nk）／ETX（CHi，nk）表示簇头CHi对成员节点nk接收／发送数据所消耗的能量；CHj∈adj（CHi）表示CHj是CHi的相邻簇头；ERX（CHi，CHj）／ETX（CHi，CHj）表示CHi对CHj接收／发送数据所消耗的能量；EDA（CHi）表示CHi融合数据所消耗的能量；Ecomput（CHi）表示CHi进行相应计算所消耗的能量。

函数fi描述路径Pi的总体能量消耗，包括该路径上各节点的计算代价和通信负荷。每一轮数据采样，簇头CHi接收簇内成员节点和来自相邻簇头的消息，计算出各能耗参数并更新从该簇头到Sink 节点的每条路径的代价。其中，系数α1，α2，α3为各种参数在节点总体能耗中的比重。可见，簇间最优路径问题等于青蛙最优解的问题。最优解问题是目标函数E（Pi）取最小值，即fi取最大值。

CHi将生 成 的 青 蛙 适 应 度 按 降 序 排 列 成P1，P2，...，PF，并划分成m 个种群Y1，Y2，...，Ym，构造子种群。m 的数值由P 中源点的下一跳节点的个数来决定。每个子种群包含s只青蛙，满足下列关系

2.3 簇间路由优化

（1）局部优化

将青蛙种群划分的多个子种群分别进行局部搜索。

步骤1 在第l轮（1≤l≤N），计算子种群Yi的适应度f（i）k，以概率p 一一进行更新，并找出最优解Pb和最差解Pw。

步骤2 Pb与Pw进行交叉替换操作，即查找两条路径中的相同节点，从选中的一个公共节点开始到下一个公共节点对Pw进行链路替换。如果两条路径仅有一个相同节点，则取Sink节点为下一个公共点。

例如：Pw＝｛CHs，CH2，CH3，CH5，CH7，Sink｝

Pb＝｛CHs，CH3，CH5，CH6，Sink｝

经过交叉后，Pw变为

Pw＝｛CHs，CH3，CH5，CH6，Sink｝

步骤3 计算交叉后最差解Pw的适应度newf（i）w，如果newf（i）w大于替换前最差解适应度f（i）w，则替换成功，否则，交叉失败。如果交叉失败，则再选用全局最优解Pg对Pw进行交叉替换。如果newf（i）w仍没有得到改进，则随机产生一个新的青蛙来代替原Pw。

（2）全局优化

步骤1 本轮搜索结束后，进行新一轮局部搜索。

步骤2 重复步骤1，经过N 轮局部优化后，将所有子种群的解重新混合在一起，按适应度f（i）降序排列，重新划分簇群。

步骤3 重复步骤2，直到满足目标函数E（Pi）值最小为止。

2.4 簇半径的动态调整

每一轮采样l（1≤l≤N），簇头CHi可计算其竞争半径如下［8］

簇内成员节点与簇头采用单跳通信方式通信。成员节点除了发送自身采集的数据，还需转发来自簇外其它节点的通过链式结构传送的数据。如果簇头节点承担过重负担，将消耗更多的能量，这样会使得簇头过早失效或丢弃数据包，从而造成感知空洞。为此，UCSNP采取一种动态的簇半径优化策略以调整节点间负载均衡。设置权值Wi计算公式如下

式中： ——0－1之间的参数；E（nk）——簇ci内成员节点nk在本轮采样中所消耗的能量；E（CHi）——簇头CHi在本轮采样中所消耗的能量；R0——簇头CHi在本轮的通信半径。从式 （9）可得出，权值Wi由成员节点总能耗与簇头能耗之比和成员节点到簇头距离总和与到簇头通信半径之比来决定。

3 性能分析

在下面实验中，通过仿真网络中节点的通信和节点能耗［15］，主要从能耗和收敛时间方面与EEUC 进行对比分析。设置一个200m×200m 的监测区域，区域内通过分簇算法形成1个Sink节点和若干个簇，每个簇内有1个融合节点，其中，Sink节点和融合节点为固定位置，其余节点成随机分布 （random waypoint）。

节点总的个数为100，普通节点的最大通信半径为10m，簇头的最大通信半径为20m。普通节点初始能量为1J，Sink节点和融合节点则为40J，数据包的最大值为128B，节点间传输带宽为0.5Mbps。设置节点周期性地感知和发送数据，各节点的采样周期为0.5－1.0s，发送数据的周期为0.2－0.5s，青蛙群体总数最大值为50，全局优化的迭代次数为N＝10，每次仿真持续时间为300s。

实验总共进行300 轮。图2 为UCSNP 协议和EEUC协议在网络运行期间除簇头和Sink节点以外的普通节点平均能耗比较。由图2分析得出，UCSNP协议和EEUC协议网络分区合理，能耗曲线都比较平稳，即相同的仿真时间内，能耗消耗均衡。UCSNP协议由于引入了簇半径优化策略，使得网络中有较多的簇规模接近最优，相比EEUC 协议减少了能耗。簇头和Sink节点都为路边固定设施，所以其能耗问题的影响相比普通节点要小很多。

图2 UCSNP和EEUC协议能耗比较

图3为UCSNP协议和EEUC 协议的存活节点数目对比图。从图3中可以看出，EEUC 协议第一个节点的死亡轮数是第88轮，而UCSNP 协议第一个节点的死亡轮数是123轮，比EEUC协议推迟了35 轮。在第300 轮时，EEUC协议存活节点数为29，而UCSNP协议的存活节点数为57。从以上分析得出，UCSNP协议由于引入了基于混合蛙跳算法的簇间路由优化，从而延长了网络生命周期。

图3 UCSNP和EEUC存活节点数目

图4显示为UCSNP 协议和EEUC 协议端到端平均收敛时间的对比。当网络拓扑发生变化时，EEUC 协议在簇内重新选举簇头，并通过簇间协商建立簇通信半径。当网络规模较大时，该协议由于收敛时间的大幅度增加而使得性能迅速下降。然而，在UCSNP 中，由固定簇头CHi或其备用簇头CH′i重新建立簇通信，无需选举簇头。此外，某些成员节点连接来自簇外的链式结构以分担簇头的负荷。从图4中可以看出，当两簇头间路由跳数增加时，EEUC协议近似于线性变化，而UCSNP协议呈凹形曲线。可见，相比EEUC，UCSNP协议在收敛时间方面明显减少。

图4 UCSNP和EEUC平均收敛时间比较

4 结束语

路由协议对于提高WSNs的整体性能及服务质量尤为关键。本文提出了一种非均匀分簇的路由优化协议UCSNP，用于缓解基于WSNs的智能交通系统的 “热区”问题。UCSNP协议考虑了智能交通环境下车辆传感网络的特点，采用链式结合非均匀分簇的混合网络结构。在该网络中，簇头间存在多路径路由传送采集的数据到基站。如果确定一条从源点到Sink节点的固定路径进行传输，当某个簇通信负载增大时，就会出现因簇头失效或负荷过重导致数据包丢失和传输时延增大，为此重新更新路由，将进一步增大能耗。因此，UCSNP协议采用混合蛙跳算法来全局优化簇间路由。此外，簇半径优化策略的引入避免了集中式成簇机制的一些弊端，在一定程度上平衡了网络负载。仿真实验结果表明，UCSNP协议在网络模型中相比EEUC协议能更有效地延长网络生命周期并且减短网络收敛时间。

［1］WANG Ruchuan.The technology and application of WSNs［M］.Beijing：People’s Posts and Telecommunications Publishing House，2011：8－20 （in Chinese）. ［王汝传.无线传感器网络技术及其应用 ［M］.北京：人民邮电出版社，2011：8－20.］

［2］LI Ye，WANG Jingbo，DONG Libo，et al.Research on applications of the internet of things in ITSs［J］.Journal of Mobile Communication，2010，15 （1）：30－34 （in Chinese）.［李野，王晶波，董利波，等.物联网在智能交通中的应用研究 ［J］.移动通信，2010，15 （1）：30－34.］

［3］Bani Yassein M，Al－zou＇bi A，Khamayseh Y，et al.Improvement on LEACH protocol of wireless sensor network（VLEACH）［J］.International Journal of Digital Content Technology and its Applications，2009，3 （2）：132－136.

［4］Gong Bencan，Xu Shouzhi.Unequal density－based node deployment and clustering routing protocol in wireless sensor networks［J］.Journal of Networks，2012，7 （11）：1892－1899.

［5］LIU Haolin，ZHU Min，ZHANG Zhihong.An uneven layered－based routing algorithm in wireless sensor network［J］.Journal of Sichuan University （Natural Science Edition），2011，4 （1）：803－807 （in Chinese）. ［刘昊霖，朱敏，张志宏.一种基于非均匀分层的WSN 分簇路由算法 ［J］.四川大学学报 （自然科学版），2011，4 （1）：803－807.］

［6］Sasikumar M，Dr R Anitha.Performance evaluation of heterogeneous－HEED protocol for wireless sensor networks［J］.International Journal of Advanced Research in Computer and Communication Engineering，2014，3 （2）：5555－5558.

［7］ZHANG Juntao，LI Yuan，CHEN Xiaoli.A novel improved data fusion algorithm based on TEEN ［J］.Journal of Shaanxi University of Science and Technology （Natural Science Edition），2013，31 （4）：110－113 （in Chinese）. ［张俊涛，李媛，陈晓莉.基于TEEN路由协议的改进型数据融合算法 ［J］.陕西科技大学学报（自然科学版），2013，31 （4）：110－113.］

［8］TANG Jiashan，WANG Yan.Improved EEUC routing protocol for wireless sensor networks ［J］.Journal of Chongqing University of Posts and Telecommunications （Natural Science Edition），2013，2 （1）：172－177 （in Chinese）.［唐加山，王燕.无线传感器网络中改进的EEUC 路由协议 ［J］.重庆邮电大学学报 （自然科学版），2013，2 （1）：172－177.］

［9］XU Dongdong，CHEN Guangting，TAN Lixing，et al.Routing protocol based on non－uniform clustering for wireless sensor networks ［J］.Journal of Hangzhou Dianzi University，2012，32 （3）：61－63 （in Chinese）.［徐冬冬，陈光亭，谭立兴，等.基于非均匀分簇的无线传感网络路由协议 ［J］.杭州电子科技大学学报，2012，32 （3）：61－63.］

［10］LUO Jianping，CHEN Minrong.Study on trajectory and convergence analysis of shuffled frog leaping algorithm and its improved algorithm ［J］.Signal Processing，2010，26 （9）：1428－1433 （in Chinese）.［骆剑平，陈泯融.混合蛙跳算法及其改进算法的运动轨迹及收敛性分析 ［J］.信号处理，2010，26 （9）：1428－1433.］

［11］YOU Ziyi，ZHANG Junhua，CHEN Shiguo.A data aggregation scheme based on wireless sensor networks and its application research in intelligent transportation system ［J］.Application Research of Computers，2014，31 （6）：1719－1722 （in Chinese）.［游子毅，章俊华，陈世国.基于无线传感网络的数据融合方法及其在智能交通系统中的应用 ［J］.计算机应用研究，2014，31 （6）：1719－1722.］

［12］Hussein T Mouftah，Mounib Khanafer，Mouhcine Guennoun.Wireless sensor network architectures for intelligent vehicular systems［EB／OL］.http：／／www.mcit.gov.sa／nr／rdo nlyres／08880e2f－f4c9－4029－988f－05bf1379516d／0／paper2.pdf，2010.

［13］Ossenbruggen P，Laflamme E.Time series analysis and models of freeway performance［J］.Journal of Transportation Engineering，2012，138 （8）：1030－1039.

［14］Shin－Ting Jeng，Tok YCA，Ritchie SG.Freeway corridor performance measurement based on vehicle reidentification［C］／／IEEE Transactions on Intelligent Transportation Systems，2010，11 （3）：639－646.

［15］Singh Y，Chaba Y，Jain M，et al.Performance evaluation of on demand multicasting routing protocols in mobile ad hoc networks ［C］／／International Conference on Recent Trends in Information， Telecommunication and Computing，2010：298－300.