基于树状拓扑的智能交通传感网调度算法

基于树状拓扑的智能交通传感网调度算法

1智能交通传感网随着社会经济的不断发展，人们生活水平的普遍提高，整个社会对运输经济发展的需求不断增加，运输对经济发展的制约作用在不同程度上是普遍适用于不同国家和地区的。解决交通拥挤和封锁的问题几乎是国家政府最难解决的问题之一。通过增加技术含量的方法提高现有道路的利用率、道路交通的安全程度以及道路使用的舒适程度成为目前研究热点,智能交通系统(IntelligentTransportationSystems,ITS)应运而生,并且已成为公认的有效地解决交通运输领域问题,特别是交通拥挤、交通阻塞、交通事故和交通污染问题的最佳途径。ITS主要由信息采集、数据中心和信息分析处理三个子系统构成。其中,信息采集子系统负责检测、传输原始交通数据,并且对原始交通数据进行实时预处理后提供给数据中心,为整个智能交通系统提供基础数据支持;数据中心对实时交通数据进行不同类型的存储,并为信息分析处理子系统提供查询支持和Web服务;信息分析处理子系统对交通数据进行统计、分析、显示,提供交通状况信息及出行指导信息。目前国内外智能交通系统中多采用地埋式感应线圈进行交通信息的采集,以有线通信的方式传输至管理中心,设备成本高昂、需人工维护、易磨损、受气候和光线条件影响大,不易维护。随着传感器技术、嵌入式技术以及低功耗无线通信技术的发展,集信息采集、处理和传输功能于一身的无线传感器网络在智能交通中的应用越来越广泛。采用图像传感器的智能交通传感网无需地面施工、布局成本低、无需电缆联接、维护费用低,成为智能交通的发展趋势。如图1所示,智能交通传感网由图像传感器节点、汇聚节点和控制中心组成。图像传感器节点散布在指定的感知区域内,获取车辆数目、车位占用率等交通数据;自组树形网无线多跳传输至SINK汇聚节点,最后通过Internet网络或通信卫星到达控制中心。用户通过控制中心对传感器网络进行配置和管理,可以实现对公路交通情况的实时监控、获取停车位推荐以及最佳行车路线推荐等。智能交通传感网引入了信息量丰富的图像媒体,要能够实时同步的处理大量传感器节点采集到的数据,数据量大并且对实时性要求较高。如文献中指出传感器节点的采样频率至少要为100Hz,数据采集速率高达2kbps。因而相比一般的无线传感器网络应用,用于ITS的传感网通信的数据量非常庞大;除了对实时性要求较高,还有高吞吐量的要求。对于智能交通传感网来说,系统对吞吐量的要求为几百到几千个kbps的实时处理。而无线传感器节点的资源受限,因而需要高吞吐量、低时延的智能交通传感网为WSN提出了新的挑战。2基于tdma/fda调度的无线传感技术介质访问控制(MediumAccessControl,MAC)协议在节点间分配有限的无线信道资源,是保证网络高效通信的关键协议之一。目前广泛应用的MAC协议可以分成:随机竞争类和固定资源分配类。随机竞争类MAC协议如CSMA,S-MAC,T-MAC,节点在需要发送数据时通过竞争使用无线信道。固定资源分配类MAC协议如DMAC和LEACH,将无线信道资源分为多个子单元,节点在通信时使用固定的子单元,有效地避免碰撞冲突。固定资源分配类MAC协议主要有基于TDMA(时分复用)类和基于综合TDMA/FDMA(时分复用和频分复用)类。固定资源分配类的MAC协议保证节点在空闲时隙及时地进入睡眠状态,避免碰撞并且减少空闲侦听,相对于竞争类MAC协议能耗更低,更适用于实际智能交通传感网。基于TDMA的MAC协议给每个传感器节点分配固定的无线信道使用时隙,从而避免节点之间的相互干扰。与此同时,采用CC2420射频芯片的硬件节点如MICAZ、TMOTE都支持多信道传输,IEEE802.15.4将2.4G-2.48GHz频段的无线信道资源划分为16个信道。因而基于综合TDMA/FDMA调度的MAC协议,对有限的无线信道资源进行时间和频率的两维分配,通过引入多个信道的并行传输,充分利用多信道资源,能提供更高的网络吞吐量,更适用于智能交通传感网。大量基于综合TDMA/FDMA调度的通信协议被提出,但是这些协议均假定硬件节点能够同时工作在多个信道上。而每个无线传感器节点仅配备有一个射频收发模块,不能同时进行数据的收和发,也不能同时工作在多个信道上。所以上述协议不适用于无线传感器网络。GangZhou提出来的MMSN协议,针对仅配备有一个射频收发模块的传感器网络,实现综合TDMA/FDMA调度,充分利用多信道资源,达到高网络吞吐量。MMSN提出了4个信道分配算法,针对不同情况,在两跳内的节点间均匀地分配多信道资源。第一种“独占信道资源分配”算法保证两跳内的节点都被分配到不同的信道,但是此算法基于“可用信道数大于两跳内的节点数”的前提。第二种“隐性共识”算法也要求充足的可用信道,而实际无线传感器网络的无线信道资源有限,如IEEE802.15.4将2.4G-2.48GHz的无线信道资源划分为16个信道,所以难以满足该算法的前提要求。第三种“均匀选择”和第四种“偷听”算法,适用于可用信道数小于两跳内节点数的情况,在两跳内节点间尽可能均匀地分配有限的多信道资源,但是都不保证无冲突通信。MMSN通过四种信道分配算法和基于TDMA的时隙分配,充分利用多信道资源,提高网络吞吐量。但是MMSN将信道分配和时隙分配完全独立开来,并没有利用网络拓扑结构表征的节点间关系,将信道分配和时隙分配结合起来,从而可以为两跳内节点分配相同的时隙和信道,同时保证数据的无冲突传输,进一步增强并行传输,真正做到最大化信道资源的利用率。3基于综合tdma/fda接入方式针对上文分析的已有MAC协议的优缺点,和智能交通传感网高吞吐量、低时延的应用需求,本文基于MMSN协议,提出了改进的FT-Sch调度算法。FT-Sch基于综合TDMA/FDMA接入方式。与MMSN不同,FT-Sch利用网络拓扑结构表征的节点关系对时隙和信道同时进行调度,指出只要满足下文提出的2条调度准则,便能够保证节点无冲突地使用信道,而不需要给两跳内节点都分配不同的时频二维资源单元(t,f)。其中t表示节点被分配到的时隙号,f表示节点被分配到的信道号。FT-Sch通过最大化并行传输,支持更大节点密度下的无冲突传输。同MMSN和单信道TDMA相比,FT-Sch能提高网络吞吐量、并且降低时延。3.1基于数据采集树的分布式网络拓扑智能交通传感网的图像传感器节点分布在持续变化的交通环境中,所以FT-Sch的设计基于自组织更新的网络拓扑结构。在智能交通传感网中,安置大量互连的微型传感器节点,自组树形多跳网,对交通信息进行不间断的高速率数据采集。利用传感器网络来进行实时监控的ITS,也是数据采集类的无线传感器网络应用;这类应用都基于数据采集树的通信模型,即:传感器节点自组树形网;多个终端源节点向一个SINK节点传输数据。如图2所示,FT-Sch算法基于数据采集树的拓扑结构。各图像传感器源节点独立地完成数据采集,选择距汇聚节点(SINK)最近的邻居节点作为父节点,通过多跳中继的方式将数据传送至SINK节点,形成一个树状拓扑结构。拓扑初始化是分布式的拓扑学习过程。依照广度优先的遍历方式,从SINK开始,节点被依次触发,广播包含网络拓扑深度参数的HELLO数据包,并且根据收到的HELLO数据包建立一个邻居节点列表,同时选择最靠近SINK的邻居节点为父节点。拓扑的更新维护通过节点持续周期性地广播HELLO数据包实现。网络拓扑结构在以下两种情况下更新:①新节点加入网络;②原节点退出网络。对于第一种情况,新加入的节点监听一段时间网络,收集邻居节点发出的HELLO数据包,选择网络拓扑深度最小的邻居节点为父节点,由父节点按照下文提出的调度算法分配无线信道资源。对于第二种情况,设定退出网络为父节点在一定时间内没有收到来自此节点的HELLO数据包。父节点释放其资源空间,其子节点选择新的父节点,重新被分配无线信道资源。3.2ft-sch调度算法网络拓扑初始化完成之后,进行无线信道资源的时隙和信道二维调度。本文提出一个分布式的时频二维资源调度算法FT-Sch。依照广度优先的遍历顺序,从SINK开始,利用网络拓扑结构表征的节点间关系,父节点为子节点分配无冲突的时隙和信道组合(t,f)。节点在被分配的时隙t醒来,跳转到被分配的信道f,发送数据包。本文提出两条调度准则。遵照这两条准则进行资源调度,可以真正做到充分利用多信道资源,最大化并行传输,并且用最少的时隙数来保证多信道的无冲突通信。调度准则如下:1)节点不能与父节点和兄弟节点被分配到同一个时隙t里。因为节点只有一个射频芯片,无法同时进行数据的收和发。2)节点不能与父节点的邻居节点被分配到同一个时频二维资源单元(t,f)里。否则若节点和父节点的邻居节点同时发送数据,将在父节点处产生碰撞,父节点将无法正确解析来自子节点的数据包。图3举例说明FT-Sch调度算法,图中的数据采集树表征一个由7个节点组成的树状传感网。SINK节点一跳可达节点A,B和C;节点A为D与E的父节点;F为B的子节点。按照提出的FT-Sch调度算法,节点按照广度优先的顺序,同时进行信道和时隙资源的调度。D不是B的邻居节点,根据上文提出的两条调度准则,D和F都可以被分配(1,2)这个时隙信道二维单元,而不引发任何冲突。而MMSN协议将信道分配与TDMA完全分开,尽可能为两跳内节点分配不同的信道,然后再基于TDMA为节点进行时隙分配,以做到利用多信道进行数据传输。所以,按照MMSN,节点D和节点F均为E的邻居节点,D和F应该被分配不同的信道f,然后再基于TDMA进行时隙分配,进行多信道传输。同MMSN相比,FT-Sch在低能耗的基础上,结合实时更新的网络拓扑结构进行多信道资源调度;利用了某些邻居节点发送数据的不同时性,使得两跳之内某些节点可以共享同一个时频单元,从而减少了所需的时频单元数目,增加并行发送数据包的节点数目,最大化多信道资源的利用率,通过增强并行传输,因而提高了吞吐量,更适用于要求实时传输大量图像数据的智能交通传感网。3.3基于ft-sch算法的时隙单元调度算法的具体实现步骤如图4所示。父节点为子节点进行时频二维资源调度时,首先为子节点分配时隙单元,然后为子节点分配信道。与MMSN将信道分配与TDMA完全分开不同,本算法利用拓扑结构表征的节点间关系,基于TDMA的时隙分配进行信道分配。定义一帧为各源节点采集的一组数据全部传输至SINK所需的时间。一个时隙为最大比特数的数据包完成一跳传输所需的时间。每帧包含的时隙数根据网络节点分布密度、可用信道数的不同是可调的。而可用信道数是有上限的,IEEE802.15.4协议将2.4G-2.48GHz的无线信道资源划分为16个信道。因此在FT-Sch算法中引入表征最大可用信道数的参数chan_num,并且设定chan_num最大不超过16。按照提出的两条调度准则,分配的时隙单元不能和父节点与兄弟节点相同;如果冲突,本算法采用时隙号自加1的方法来更改;更改时隙单元之后再判断是否冲突。节点被分配到的时频二维资源单元(t,f)如果和父节点的邻居节点冲突,信道号自加1,判断新的(t,f)单元是否冲突。如果信道自加到超过chan_num,将信道f重置为1,已安排的时隙号自加1,重新判别是否冲突。每个节点维护一个邻居节点列表和一个兄弟节点列表,列表包含节点的时隙号t和信道号f的信息。在资源调度过程中,节点通过遍历邻居节点列表和兄弟节点列表来排除会引发冲突的时隙、信道。节点被调度完成之后,广播包含其(t,f)信息的HELLO数据包,邻居节点更新相应信息。节点依照广度优先的顺序依次被触发,完成时频二维信道资源的调度。4节点密度对网络时延的影响为了验证FT-Sch算法对网络吞吐量以及时延的改进效果,在MATLAB下实现了FT-Sch、MMSN以及单信道TDMA协议,并且用MATLAB模拟了智能交通传感网环境,对FT-Sch、MMSN和单信道TDMA协议的网络吞吐量和传输时延等参数进行统计和比较。模拟的智能交通传感网感知区内随机地分布着一定数量的图像传感器节点,整个模拟传感网设有1个汇聚节点,随机地设定网络中30%的节点为采集交通信息数据的源节点。评价FT-Sch算法的性能指标为网络吞吐量和传输时延。吞吐量指网络单位时间内成功传输的有效数据量,本研究中采用每timeslot内传输的采样数据包个数为吞吐量的统计单位。传输时延指各源节点采集的一组数据包全部传输至SINK的耗时,本研究中采用bittime为时延单位,即节点传输每bit数据所需时间。此外定义网络节点密度为每平方米范围内分布的传感器节点数目。在不同的智能交通传感网规模下,对不同可用信道数的FT-Sch、MMSN、以及单信道TDMA进行了吞吐量、传输时延等参数统计,并对三种调度方法进行了性能比较。2FT-Sch、4FT-Sch、8FT-Sch、16FT-Sch分别表示有2个可用信道、4个可用信道、8个可用信道和16个可用信道的FT-Sch调度算法。图5对比了采用不同可用信道数的FT-Sch算法时,智能交通传感网一帧所包含的时隙数随网络节点密度的变化。可用信道数越多,FT-Sch一帧所需的时隙数越小。证实多信道传输可以降低传输时延。同时可以看到,当可用信道数由8增加到16时,一帧包含的时隙数基本没有变化,说明FT-Sch算法引入的时频二维资源调度算法,在节点密度小于等于80000个/平方千米时,最多能用到8个信道。三种协议的时延和吞吐量统计量对比分别如图6和图7所示。仿真统计结果表明,采用单信道TDMA协议的智能交通传感网的传输