交通信息采集中WSN分簇算法研究

曹 洁,马忠彧,侯 亮,王进花

(兰州理工大学,a.计算机与通信学院;b.电气工程与信息工程学院,兰州730050)

交通信息采集中WSN分簇算法研究

曹 洁*a,马忠彧b,侯 亮a,王进花b

(兰州理工大学,a.计算机与通信学院;b.电气工程与信息工程学院,兰州730050)

无线传感网是采集实时交通信息的重要工具.因其节点能量有限,必须设计高能效的分簇路由算法以延长网络周期.本文通过建立一种智能交通中无线传感器网络的应用模型,根据其特点和要求分析LEACH协议的优缺点并提出一种能量负载均衡的分簇算法.该算法对LEACH协议当中的簇首机制进行改进,综合考虑候选节点的剩余能量和簇首节点的分布位置;建立簇间多跳路由机制以避免单跳通信的大能量消耗;创造一种簇重构方法,避免过于频繁的簇重构引起的不必要能量消耗.仿真结果表明,能量均衡算法可有效平衡节点能量消耗分布,延长网络生命周期,可很好的应用于基于WSN的ITS当中.

智能交通;能量负载均衡;LEACH;无线传感网;分簇算法

1 引 言

城市交通智能化是减少交通拥堵、提高道路吞吐量和利用率的重要手段之一[1].为了克服传统智能交通实施成本高、部署难度大的问题,将无线传感网络(WSN)引入智能交通系统(ITS).利用传感器网络成本低廉、部署方便、适应性强和灵活的特点将其布置在固定区域范围内[2].这种网络一旦部署完毕就需要在固定区域内进行长期的交通参数采集与监测工作,而且在此期间一般不会更换节点电池,因此延长节点与网络生命周期成为将无线传感器网络运用于智能交通领域的热点问题之一.高能效的路由协议对提高节点的能量效率及延长网络生命周期有十分重要的意义.

目前,无线传感器网络的路由协议可以分为平面路由协议和分层路由协议两种.在平面路由协议中,所有网络节点的地位是平等的,不存在等级和层次差异,通过相互之间的局部操作和信息反馈来生成路由.典型的平面路由算法有定向扩散协议、SAR(Sequential Assignm-ent Routing)等[3].平面路由的最大缺点在于:网络中无管理节点;缺乏对通信资源的优化管理;自组织协同工作算法复杂;对网络动态变化的反应速度较慢等.

典型的分层路由协议包括:LEACH(Low Energy Adaptive Clustering Hierarchy)、TEEN (ThreshoId Sensitive Energy Efficient Protocols)[4]、PEGASIS( PowerEfficientGatheringin Sensor Information Systems)[5]、HEED( Hybrid Energy-Efficient Distributed Clustering)[6]等,其中LEACH协议是无线传感器网络中第一个分层路由算法,也是一种具有代表性的分层路由协议,它的思想引发了很多的分层路由协议的产生.

LEACH分簇协议概念被提出之后使得在网络节点节能及网络寿命延长方面得到了很大提高,然而将LEACH协议运用在智能交通领域下的无线传感器网络中,有其自身不可忽略的局限性.本文在LEACH协议的基础上,介绍一种基于能量和位置的能量均衡分簇路由算法 EAPBCP(Energy And Position-Based Clustering Protocol),该算法在簇首选举机制上充分考虑节点的能量及位置因素,避免剩余能量较低及地理位置不佳的节点被选为簇首节点.

2 基于WSN的ITS场景模型

如图1所示,基于无线传感器网络的智能交通系统是由布置在城市或高速公路的路边节点(位置已知的节点)、车载移动节点和Sink节点构成.

图1 基于WSN的ITS模型图Fig.1 ITS model based on WSN

(1)路边节点采用电池供电,其工作强度大、储存和处理能力较弱.具体功能有对路面湿度、温度、能见度及车流量进行信息采集;协同其他路边节点测量车距、车速等信息;经简单的数据融合处理后将数据传至Sink节点;接收并处理来自Sink节点的预警、更换任务等信息.

(2)车载节点(也可和RFID电子标签绑定)内部继承有车辆“身份证”信息,如车牌号、车辆类型和车主身份等信息.具体功能为车辆驶入公路以后周期广播自己的固有信息;接收来自其他节点的安全预警信息(如道路能见度差、路面光滑等).该类节点采用有源供电的方式,其存储及处理能力相对较强.

(3)Sink节点一般采用有源供电方式,且有存储能力大、运算能力强等特点.具体功能为收集来自路边节点的信息;将数据进行融合以后传至监控中心;管理及控制范围内的路边节点;接收监中心的各种控制指令等.

在智能交通系统中,用于实时获取交通信息的无线传感器网络节点数据采集量、处理量大,并要求簇头产生速度快、网络健壮性好、扩展性好.通过合理的分簇方式使全网能量均衡消耗已成为WSN在ITS运用中的研究热点.

3 LEACH算法及性能分析

3.1 算法描述

LEACH算法[7]是Chandrakasan等人为无线传感器网络设计的不同于平面路由协议的算法,全称是低功耗自适应集群分层协议.LEACH算法在运行过程中每个簇重构过程可以用“轮(Round)”来描述.每“轮”可以分为两个阶段:簇的建立阶段和传输数据的稳定阶段.

簇首节点的具体选举办法是:每个传感器节点随机产生一个0-1之间的一个值,如果产生的随机值小于某个阈值T(n)[8],那么该节点当选为簇首节点,阈值T(n)的产生方法如下:

式中,p是网络中簇头占所有节点的比例,r是目前正在进行的第r轮,n表示某节点,G是到第r轮之前尚未当选过簇头的节点集合,符号mod是求模运算符.

簇首节点选举结束以后,簇头节点广播自己当选为簇头的消息.网络中普通节点根据接收到信息的信号强度决定加入哪个簇,并向簇首节点发送自己的入簇请求,簇首节点返回确认信息,以此完成簇的建立[9].

3.2 算法能量模型分析

本文使用Heinzelman博士论文中的能耗模型[10],现假设一个簇内有n个节点,则每处理一帧数据,簇首所消耗的能量Ech为

某一簇首转发其他簇首数据所消耗的能量Ech-ch为

而每个非簇首节点消耗的能量Enon-CH为

上述式(2)—式(4)中:Eelec为发送或接收每比特数据时的电路能量消耗,与距离无关;ξfs为临界距离内发送电路的功耗系数;ξamp为临界距离外发送电路的功耗系数;dcrossover为临界距离;l为本簇内数据报的比特流数;EDA为数据融合消耗能量系数.

比较分析上述能量公式可知:簇首节点能耗远大于簇成员节点能耗,要使簇首节点不因大量消耗能量而过早死亡,则必须时时选举剩余能量大且地理位置较佳的节点当选为簇首节点,这对均衡全网能量、延长网络生命周期很有至关重要的意义.

3.3 算法特点分析

LEACH算法采用层次结构,打破了常规平面路由算法的路径选择难、路由信息存储量大的界限.该算法自适应随机选取簇首节点,采用TDMA技术解决信道征用问题,这有利于全网的负载均衡和能量控制.但是,LEACH协议存在以下两方面的问题制约着网络能量的均衡消耗:

(1)节点担任簇首概率是严格意义上的等概率选择,剩余能量较低的节点一旦当选为簇首节点会过早的耗尽能量而死亡;簇首以单跳形式向汇聚节点传送数据,导致地理位置不佳的簇首节点能量消耗过大.

(2)每轮通信结束后都要重新进行簇首选择和簇间、簇内的路由建立,簇重构轮数过于频繁导致大量能量消耗.

4 改进的算法EAPBCP

4.1 簇首节点的选择

在上述基于WSN的ITS场景当中,车载节点和Sink节点均为有源供电,不涉及分簇问题.因此,本算法仅针对电源能量有限的路边节点.分簇前,Sink节点计算出所有路边节点中距离自己最大距离Dmax和最小距离Dmin并广播至全网.在每一轮簇重构之前,所有的路边节点将自身剩余能量Ecurren及采集到的交通参数发送至上轮选出的簇首节点,簇首节点简单融合收到的数据后附加自己的Ecurren发送至Sink节点,收到数据后的Sink节点将有用的数据传送至网关、计算全网平均剩余能量值Eavg并发送至全网.各节点接收到簇首选举命令后比较Ecurrent和Eavg,仅当Ecurrent＞Eavg才能参与簇首选举.改进后的簇首选择阈值为

式中 p是网络中簇头占所有节点的比例;r是目前正在进行的第r轮;n表示某节点;G是到第r轮之前尚未当选过簇头的节点集合;符号mod是求模运算符;Dmax是所有路边节点到Sink节点距离的最大值;Dmin是所有路边节点到Sink节点距离的最小值;d是参加簇头选择的路边节点到Sink节点的距离;Eavg是全网平均能量;Ecurrent是节点当前剩余能量;G′是所有Ecurrent＞Eavg的路边节点集合.

4.2 簇内、簇间的路由建立

簇首节点选出以后,簇首节点向全网广播自己当选为簇首的消息,消息中含有自身地理位置信息、身份标识及所采用的CDMA扩频码.其他路边节点根据收到簇首广播消息的信号强弱判断出加入哪个簇并发送入簇请求.簇首在收到入簇请求以后将该路边节点加入自己的路由表,随后为簇内每个路边节点分配一个时间片并通知该簇中的所有节点.

簇首节点在收到其他簇首节点的广播消息后,根据自己的位置信息找到自己的前向簇首节点,具体判断方法如下:

(1)簇首节点计算出与Sink节点的距离:

式中 tx和ty、sx和sy分别是簇首节点this和汇聚节点Sink的横、纵坐标.

(2)其他簇首节点计算出自己与Sink节点的距离

式中 cx和cy、sx和sy分别是簇首节点clusteri和汇聚节点Sink的横、纵坐标.

(3)选择出D(this,sink)＞D(clusteri,sink)的簇首节点,并计算这些簇首节点与自己的距离:

式中 tx和ty、cx和cy分别是簇首节点this和簇首节点clusteri的横、纵坐标.

(4)若没有其他节点满足 D(this,sink)＞ D(clusteri,sink),则当前节点的下一跳为sink节点,否则从 D(clusteri,this)中选出最小值Dmin(clusteri,this),若Dmin(clusteri,this)＜D(this,sink),则Dmin(clusteri,this)对应的节点为当前簇首节点的下一跳.

由上文给出的节点发送数据的能量模型可知:这样选择下一跳簇首可以保证每一个簇首以较低的能耗将数据发送出去;由上文给出的簇首节点之间发送数据的能量模型可知:簇首节点将数据发送至离自己最近的簇首节点并使其转发,可以保证每一个簇首节点以最低的能量消耗将数据发送出去.

4.3 下一轮簇重构

簇内、簇间路由建立完成以后,Sink节点向全网发送传输指令开始进入本轮的数据传输阶段.所有路边节点在自己的时间片内将采集到的数据传输和Ecurrent传至簇首节点,其余时间片内节点将进入休眠状态;簇首节点将数据发送至下一跳簇首节点,最终发送至汇聚节点.

下一轮通信开始之前,Sink节点汇总收到的数据,重新计算当前全网节点的Eavg,并设置一个动态阈值Emin=Eavg/2.Sink节点将簇首节点的能量与Emin进行比较,如果Emin＜Ecurren,则维持当前簇结构不变,否则进入下一轮簇内重选,即选举当前簇内节点剩余能量最高的节点为簇首节点.Sink节点将新簇首的节点向全网进行广播,同时簇内节点及时更新自己的路由、簇首节点及时更新自己的下一跳节点.

每执行一次簇重构,Sink节点将轮计数器cluster-round加1,当 cluster-round＞n·p·25%时,Sink节点向全网广播重新按照前文所述的簇首选择机制在全网内实行大选,然后更新簇内、簇间路由,否则只在本簇内重新选择簇首,公布新簇头,更新簇内、簇间路由.整个流程图如图2所示.

图2 每轮通信后的处理流程图Fig.2 Processing flow chart of each round communication

5 算法的仿真分析

本文用MATLAB仿真了两种算法.首先比较分析首轮分簇仿真结果以验证EAPBCP在节点入簇时的就近原则,其次比较分析两种算法的网络生命周期以验证EAPBCP在延长网络周期方面的优越性.为研究方便,用100个节点随机分布在100 m×100 m的正方形区域内,具体仿真参数如表1所示:

表1 仿真参数设置Table1 Simulation parameters settings

图3、图4显示了两种算法在首轮选举结束后整个网络的分簇情况.从图3中可以看出并非所有节点加入距离自己最近的簇首节点,且各簇头与汇聚节点仅为单跳通信而不经过路由;从图4中可以看出每个节点都加入了离自己距离最近的簇首节点所在的簇,簇首节点也按照上文所述的方法建立起以sink节点为终点的多跳链路,这有利于延长网络生命周期.

图5描述了网络在运行两种算法时节点在各轮存活的个数.从图5中可以看出,两种算法在开始运行的前几轮当中,存活节点个数相差不大.这是因为各节点的初始能量相等,在EAPBCP算法中改进阈值中能量因素没有发挥优势作用.在随后的算法运行当中改进后的EAPBCP算法相对LEACH算法而言,将网络的生命周期延长了20%以上.一方面这是由于EAPBCP算法在阈值产生过程当中加入能量和距离因素,使簇首节点筛选严格,避免节点因过早消耗能量而死亡;另一方面这也是由于通过设置全网选举参数,避免频繁地在全网范围内进行簇头选举以减少网络能量消耗.

图3 LEACH首轮分簇结果图Fig.3 The first round clustering figure for LEACH

图4 EAPBCP首轮分簇结果图Fig.4 The first round clustering figure for EAPBCP

6 研究结论

本文给出了基于WSN的ITS场景并在此场景下提出了一种EAPBCP算法.该算法在簇首选择阈值当中将各路边节点的剩余能量和距离因素考虑进去,避免了剩余能量低、距离Sink节点远的路边节点当选为簇首节点;在簇首建立多跳路由时依据位置信息选择能耗代价最少的簇首节点为当前节点的下一跳节点;簇首通过多跳方式与Sink节点通信,弥补了远距离单跳通信能量消耗大的不足;一旦网络分簇结构确定,这一分簇结构在一定时间内不变,避免了频繁簇重构引起的能量消耗.

实验表明,该算法在给定模型下能有效均衡网络负载、延长生命周期;实现对城市道路或高速公路环境不间断安全监控,提高交通信息采集效率;减少更换传感器节点次数,提升经济效益.本文下一步研究包括:簇首节点的选举中综合考虑能量、位置、节点度因素,保证簇首节点在地理位置上分布均匀.

[1]王笑京,沈鸿飞,汪林等.中国智能交通系统发展战略研究[J].交通运输系统工程与信息,2006,6 (4):9-12.[WANG X J,SHENG H F,WANG L,et al. Study on development strategy of Chinese intelligent transportation[J].Journal of Transportation Systems engmeering and Information Technology,2006, 6(4):9-12.]

[2]潘振兴,杨晓光,潘玉琪,等.基于WSN的公交车辆信息采集系统网络性能评价方法[J].武汉理工大学学报(交通科学与工程版),2009,33(5):903-906.[PAN Z X,YANG X G,PAN Y Q,et al. Network evaluating method for bus vehicle information acquisition system based on WSN[J].Journals of Wuhan university of Technology(Traffic Science and Engineering Edition),2009,33(5):903-906.]

[3]胡静,沈连丰,宋铁成,等.新的无线传感器网络分簇算法[J].通信学报,2009,29(7):20-26.[HU J, SHENG L F,SONG T C,et al.The new clustering algorithm for wireless sensor network [J]. Communication Journal,2009,29(7):20-26.]

[4]姜华,刘海涛,等.无线传感器网的系统建模与仿真实现[J].系统工程与电子技术,2007,29(1):92-95.[JIANG H,LIU H T,et al.Modeling and simulating of wireless sensor network[J].Systems Engineering and Electronic Technology,2007,29(1):92-95.]

[5]任丰原,黄海宁,林闯,等.无线传感器网络[J].软件学报,2003,14(7):1282-1291.[RENG F Y, HUANG H N,LIN C,et al.Wireless sensor network [J].Journal of Software,2003,14(7):1282 -1291.]

[6]张豫鹤,黄希,崔丽,等.面向交通信息采集的无线传感器网络节点设计[J].计算机研究与发展, 2008,45(1):110-118.[ZHANG Y H,HUANG X, CUI L,et al.Design of wireless sensor network node facing the traffic information collection[J].Computer Research and Development,2008,45(1):110-118.]

[7]Heinzelman WB,Balakrishnan H.An specific application protocol architecture for wireless microsensor networks [J].IEEE Transactions on Wireless Communications. 2002,l(4):660-670.

[8]Melodia T,Pompili D,Akyildiz I F.On the interdependence of distributed topology control and geographical routing in Ad hoc and sensor networks[J].IEEE JSAC, 2005,23(3):520-532.

[9]Dimokas N,Katsaros D,Manolopoulos Y.Energyefficientdistributed clustering in wireless sensor networks[J].Journal of Parallel and Distributed Computing,2010,70(4):371-383.

[10]Youssef M,Youssef A,Younis M.Overlapping muhihop clustering for wireless sensor networks[J].IEEE Trans on Parallel and Distributed Systems,2009,20 (12):1844-1856.

Clustering Algorithm of WSN in Traffic Information Collection

CAO Jiea,MA Zhong-yub,HOU Lianga,WANG Jin-huab
(a.College of Computer and Communication;b.College of Electrical and Information Engineering,Lanzhou University of Technology,Lanzhou 730050,China)

Wireless sensor network is an important tool to collect real-time traffic information.Because of the limited node energy,it is essential to design an energy-efficient clustering routing algorithm to prolong the network cycle.This paper establishes an intelligent transportation model in the application of wireless sensor network.According to the characteristics and requirements,the paper analyzes both the advantages and disadvantages of LEACH agreement and proposes an improved clustering algorithm with energy loading balance.The algorithm considers the residual energy and position of cluster head node and then improves cluster head electing mechanism of LEACH agreement.It establishes multiple hops routing mechanism between clusters to avoid energy consumption as for single jump.A method for cluster's reconstruction is also presented to avoid unnecessary energy consumption as for frequent reconstruction.The results show that the proposed algorithm can effectively balance the consumption distribution of node energy,extend node and network life cycle.It can perform well in the intelligent transportation systems(ITS)based on WSN.

ITS;energy loading balance;LEACH;wireless sensor network;clustering algorithm

TN915

A

TN915

A

1009-6744(2013)01-0069-07

2012-09-07

2012-11-13录用日期:2012-11-20

亚行贷款兰州城市交通项目先进的交通控制系统(ATCS)工程(设计)(H1114aa004).

曹洁(1966-),女,安徽宿州人,教授,博导.

*通讯作者:caoj@lut.cn.