面向城市道路交通的传感器组网优化

李海舰 ，董宏辉 ，徐东伟 ，贾利民

(1.北京交通大学 轨道交通控制与安全国家重点实验室，北京，100044；2.北京交通大学 交通运输学院，北京，100044)

交通传感器以数据流的形式进行交通数据的传输，即传感器能够持续检测交通流信息，得到连续的检测数据，并按规定的时间间隔上传数据。传感器数据中包含的信息很可能蕴含着当时的交通流特性、事故信息、交通流状态、道路拥堵程度等，要求能够被及时处理和响应。姜桂艳等[1]研究的城市主干路路段行程时间估计和戢晓峰等[2]研究的区域路网交通信息提取方法都是以利用交通传感器采集的交通流数据为基础的。Li等[3]、Hu等[4]和Zhou等[5]分别研究了交通传感器优化布局技术，提出了面向不同应用的交通传感器在实际路网中的布设方法。需要进一步研究的是在物理层交通传感器布设之后，为获取路网中的不同范围和不同形式的交通信息，交通传感器的逻辑层组网优化技术。近年来，随着嵌入式系统、网络技术、微电子技术的发展，传感器网络得到重视和发展。传感器网络由大量具有通信和计算能力的传感器节点构成，是可根据环境自主完成任务的智能自组织分布式网络系统。其研究起步于20世纪80年代，2000年以来，随着微电子技术、计算技术和无线通信等技术的进步，制造廉价、微型、低功耗、多功能的传感器节点成为可能。由大量集成信息采集、数据处理和通信等功能的传感节点组成的传感器网络具有高可靠、易部署和可扩展等特点，正逐渐受到人们的重视，并获得迅速发展[6−7]。在国内，传感器网络系统方面的研究起步较晚，近几年发展迅速。传感器网络在智能交通方面应用也得到广泛关注，主要集中在道路信息采集[8−9]、交通安全[10−12]和交通控制[13]等方面。传感器组网的研究对道路信息的有效采集、信息传输和处理，以至交通事故判别与检测[14]、交通优化控制、交通安全提升等都有重要的现实意义。通过传感器的组网，可以实现路口、路段和区域交通信息的综合获取和交通状态判别，能够及时发现影响交通安全和导致拥堵的交通事件。综合国内外文献，面向城市道路交通的传感器组网优化的研究较少，本文作者主要面向城市道路交通，初步探讨基于交通事件的传感器组网优化方法。

1 传感器反映的交通信息

1.1 基于信息度的宏观交通状态描述

从传感器交通信息反映的宏观交通状态入手，对传感器通过采集的交通信息数据反映宏观交通状态的方式进行了描述和表示，并在此基础上定义了传感器所反映出的宏观交通信息度。

宏观交通状态可由速度、流量、占有率等宏观参数表示，所以宏观交通状态主要表现在速度、流量、占有率等宏观参量上。对于路段上布设的一个交通传感器，由于其能够检测一定的宏观交通参数，则它能够完全反映(暂不考虑传感器的准确率)出传感器点处相应参数的交通信息。另外在离传感器一定距离处，由于交通参数变化的连续性和数据量的相关性，则彼处的交通信息(即宏观交通状态)可以在一定的概率下由此传感器信息代替或反映。所以交通传感器可以以一定的概率反映出一定距离内的交通状态信息。某传感器能够准确反映传感器处交通状态的概率为 1，则准确代表距此传感器x距离单位处的交通状态的概率为p=p(x)。这样在整个定义域内(－∞＜x＜＋∞)，p(x)可看作某传感器能够代表距此传感器x距离单位处交通状态的概率。

1.2 传感器的空间信息度函数

根据上节的分析，在一个路段上，交通传感器反映空间交通信息可以用概率进行表示，这里定义一个传感器的信息度函数，定义：

式中：x为距此传感器的距离；p(x)为此传感器能够准确代表距离其x处的交通状态的概率；g(x)为此传感器的信息度函数。

路段上某传感器的信息度函数g(x)可以进行如下描述：

(1)g(x)是对传感器检测的某种交通状态参数而言，不同的交通状态参数有不同的信息度函数。其物理意义为距交通传感器一定距离处的交通信息，能被传感器检测到的交通信息所代表的概率或程度；也可理解为某传感器能够代表的空间单位距离上交通信息的程度。

(2)g(x)是关于定义域(一般为研究路段或研究区域)上的连续函数，且g(0)=1。

(3)根据不同的路面特征、道路环境及道路等级等道路条件，g(x)可有不同的曲线特征，如正态曲线、指数曲线、三角形(斜坡)(图1)或其他曲线特征。实际情况中，大多为非对称的，因为路段上游和路段下游的交通特性是不同的。

图1 信息度函数的分布特征Fig.1 Distribution of information function

1.3 传感器的信息价值

路段及路网的交通状态对管理者和出行者来说都是很重要的，这也是ITS系统的数据来源之一，所以，由这些状态参数所形成的交通信息对管理者和出行者的决策、城市交通规划部门的参考等等都有很大的指导意义。这些信息的准确性、完整性对管理者和规划者正确决策和合理规划起着关键作用，所以，某传感器检测到的交通信息蕴含着一定的社会价值。

这里的社会价值指在此路段上布设传感器后，在整个传感器寿命周期内，与没有布设传感器相比所增加的价值，可以根据社会价值不同的外在表现划分为3个部分(拥挤成本、额外成本、蕴含价值)，用下式表示：

式中：VCC(Congestion costs)为由于放置该传感器，路段减少的拥挤成本；VEC(External costs)为由于本路段信息量的增加，得到的额外价值，或减少的额外成本，主要包括车辆减少的油耗成本以及污染、噪声等外部成本；VIV(Intrinsic Value)为交通信息蕴含的固有价值。

对于VCC的标定，利用下式：

式中：NU为传感器使用年限，a；NY为1 a的天数，d/a；CV为每辆车每小时的平均拥挤成本，与当地平均劳动工资有关，元/(辆·h)；T为研究路段每天的拥挤小时数，h/d；QC为由于此路段缺少传感器信息增加的拥挤车辆数，辆[15]。

对于VEC的标定，利用下式：

式中：EV为每辆车每小时的平均额外价值，与道路水平有关，元/(辆·h)。

对于VIV，可根据交通数据拥有者的评估进行标定。

2 动态组网方法

2.1 模型建立

在物理层传感器都已经部署的基础上，如何针对典型交通事件(如事故判别、交通疏导、信号控制、路段信息收集等)，如何选取适当数量和适当位置的传感器，使这些传感器得到尽可能大的综合信息价值量是本节建模所要解决的问题。其建模目标是使传感器信息的社会价值与处理传感器数据的成本之差最大化，即综合信息价值最大化。给定路段k上的典型事件A，建立基于传感器单位小时综合价值最大的动态组网模型如下：

式中：W为组网后的传感器每小时综合价值；i为传感器编号；ji为传感器i所在路段编号；k为事件A所在路段编号；gi(x)为传感器i的信息度函数；w为传感器编号解集；w0为事件A附近可利用的物理传感器编号集合；qi为物理层第i个传感器能够提供给此事件的每小时平均信息价值；vi为物理层第i个传感器所具有的每小时平均信息价值；ci为处理或利用传感器i的信息产生的每小时固定成本；点xi-、点xi+由gi-(x)，gi+(x)与gi(x)函数的叠加点决定(前后两传感器信息度函数叠加时取最大者)；gi-(x)和gi+(x)为解集中同一路段上传感器i前后两传感器的信息度函数。

其中：rjk=rkj，0≤rjk≤1。

rjk可以通过分析j和k路段上传感器采集的交通信息的相关性得到。

对于qi，若点p1和p2在同一路段，则传感器i从p1到p2处的每小时信息价值为：

若点p1和p2不在同一路段，p1点在路段j上，p2在路段k上，且路段j和路段k的交点为pjk，则传感器i从点p1到点p2处的每小时信息价值为：

2.2 算法描述

模型求解是一个动态规划问题，当传感器个数较多时，求得最优解比较困难。由于解集元素是一个个加入的，可以利用贪心算法求得满意解。贪心算法操作简单，求解思路清晰，易于编程实现，通过设置一定的约束条件来控制求解过程，能够得到次优解或最优解。求解思路如下：

Step 1：确定各参数。

Step 2：确定研究的事件A，并根据事件A确定相关的物理层传感器，从而确定路段k和初始传感器集合w0。

Step 3：对于事件A，利用贪心选择规则确定第一个初始解，并计算W的值。

Step 4：在剩余的传感器中按照贪心选择规则依次增加解集元素，得到新的W。

Step 5：判断W变化情况，若不满足事先给出的约束条件，则重复步骤 4；否则停止计算，返回最大值Wm和对应解集w。

贪心选择规则可以选择与事件A点处相关性最大的或信息价值最高的传感器，或根据相关系数、信息价值和成本3个因素的融合值由大到小选取。约束条件可设定为求解精度或算法的迭代次数。

3 实例分析

3.1 路网选取

图2 事件A相关的传感器分布图Fig.2 Distribution of sensor related to an event

选取北京市西三环和西四环处的一个路网区域，假设典型事件A发生在图示(见图2圆圈处)的位置(4号传感器处，由4号传感器到3号传感器的车流方向)，为了尽快得到事件A点处周围的交通信息，利用本模型选取合适的传感器进行动态组网。这里以路网中实际部署的传感器(微波传感器)为研究对象。传感器i的信息度函数、单位小时固定成本、单位小时信息价值分别记作gi(x)，ci和vi，为简化起见，各传感器信息度函数、单位小时固定成本、单位小时信息价值分别取相同值，记为G(x)，C0和V0，即：

3.2 求解步骤

(1)确定参数C0和V0

C0表示处理一个传感器信息的每小时固定费用，与传感器信息处理系统和人员利用情况有关。若系统的费用为 30元/h，信息处理人员一名(以北京市平均工资10元/h计)，则C0取40元/h[16]；V0可以由V算出。通过对北京市快速路交通检测器拥挤成本、额外成本、蕴含价值的标定，利用1.3节中的模型得到一个传感器信息价值为V=14 034 000元[16]，则传感器信息价值为V0=V/(6×365×24)=267 元/h。

(2)确定传感器信息度函数和贪心选择规则

通过2008年4月10日北京市二环路部署的微波传感器得到的交通状态参数数据[16]，得到北京市快速路传感器的信息度函数为g(x)=e−0.1592x，将其用于本实例快速路，可取G(x)=g(x)=e−0.1592x。

贪心选择规则可设定为每次选择与事件A点处相关性最大的传感器，可得各传感器信息与事件A的相关系数见表1。

表1 各传感器与事件A相关系数表Table 1 Correlation coefficient between sensor and an event

(3)确定各路段信息相关系数矩阵

通过2008年4月10日各传感器(图2)测得的路段速度数据，得到5个主要路段的交通信息相关系数矩阵见表2。

表2 路段信息相关系数矩阵Table 2 Correlation coefficient matrix of road information

(4)贪心算法求解过程

利用上述的贪心选择规则，逐个加入新的传感器到解集中，得算法的计算过程和综合价值的计算结果(见表3)。

表3 求解计算过程Table 3 Course of calculation

(5)动态组网优化结果

从表3可知：当选择12个传感器时，可得W值达到最大，此时的解集w为4，3，5，12，2，13，6，11，1，7，14和8，得到的W为553.442元/h。计算完毕，最终解集见图3(W整体上升过程中有个别点下降(如第6步、第8步)，说明贪心算法的每一步选择不一定是最优的，但此方法能找到满意解或最优解，本例为最优解)。

图3 算法最终结果Fig.3 Last result of algorithm

4 结论

(1)通过研究由传感器获得交通信息的空间特性，定义了传感器的空间信息度函数，并分析和标定了传感器的信息价值。在此基础上建立的基于每小时信息价值最大的动态组网模型，实现了物理层传感器基于特定交通事件的逻辑层动态组网。通过给出的求解算法，实现了动态组网模型的求解计算过程，并为实例给出了合理的组网结果，也为传感器的信息度函数和信息价值理论提够了应用支持。

(2)通过对传感器信息的进一步挖掘，可以提高各传感器信息的利用效率。对不同类型的交通事件，文中模型和算法都可以通过标定相应的模型参数得到相应事件的组网结果，并获得合理的交通信息，为交通管理提供依据。

[1]姜桂艳,李继伟,张春勤.城市主干路路段行程时间估计的BPR修正模型[J].西南交通大学学报,2010,45(1): 124−129.JIANG Gui-yan,LI Ji-wei,ZHANG Chun-qin.Modified BPR functions for travel time estimation of urban arterial road segment[J].Journal of Southwest Jiaotong University,2010,45(1): 124−129.

[2]戢晓峰,刘澜,吴其刚.区域路网交通信息提取方法[J].西南交通大学学报,2008,43(3): 422−426.JI Xiao-feng,LIU Lan,WU Qi-gang.Extraction method for traffic information of regional road network[J].Journal of Southwest Jiaotong University,2008,43(3): 422−426.

[3]LI Xiao-peng,Ouyang Y F.Reliable sensor deployment for network traffic surveillance[J].Transportation Research Part B:Methodological,2010,45(1): 218−231.

[4]HU Jian-ming,SONG Jing-yan,ZHANG Ming-chen,et al.Topology optimization for urban traffic sensor network[J].Tsinghua Science and Technology,2008,18(2): 229−236.

[5]Zhou X S,George F L.An information-theoretic sensor location model for traffic origin-destination demand estimation applications[J].Transportation Science,2010,44(2): 254−273.

[6]杨少军.无线传感器网络若干关键技术研究[D].西安: 西北工业大学电子信息学院,2006: 9−24.YANG Shao-jun.Research on key techniques of wireless sensor networks[D].Xi’an: Northwestern Polyteehnieal University.School of Electronics and Information,2006: 9−24.

[7]Hsieh T T.Using sensor networks for highway and traffic applications[J].IEEE Potentials,2004,23(2): 13−16.

[8]Knaian A N.A wireless sensor network for smart roadbeds and intelligent transportation systems[D].Massaehusetts:Massaehusetts Institute of Technology.Department of Electrical Engineering,2000: 4−35.

[9]岳文剑.基于传感器网络的交通数据采集平台研究[D].大连:大连理工大学建设工程学部,2005: 9−35.YUE Wen-jian.Study of traffic data collection platform based on sensor-networks[D].Dalian: Dalian University of Technology.Faculty of Infrastructure Engineering,2005: 9−35.

[10]CHEN Wei-jie,GAO Li-qiang,CHEN Zhi-lei,et al.An intelligent guiding and controlling system for transportation network based on wireless sensor network technology[C]// The Fifth International Conference on Computer and Information Technology (CIT’05).Shanghai,China,2005: 810−814.

[11]CHEN Wei-jie,GHEN Li-feng,CHEN Zhang-long,et al.A real time dynamic traffic control system based on wireless sensor network[C]//Proceedings of International Conference on Parallel Processing Workshops.Shanghai,China,2005: 258−264.

[12]袁凌云,朱云龙,瞿立成.分布式无线交通监控系统的研究与实现[J].计算机工程,2006,32(8): 249−251.YUAN Ling-yun,ZHU Yun-long,QU Li-cheng.Research and implementation of transportation monitoring system based on distributed wireless sensor network[J].Computer Engineering,2006,32(8): 249−251.

[13]TAN Guo-zhen,XIONG Cai-gang,ZHAO Dian-kui,et al.The application of wireless sensor network in the vehiele safety[C]//Proceedings of WCICA.Dalian,China,2006: 8727−8731.

[14]赵殿奎.用无线传感器网络检测公路交通突发事件[D].大连:大连理工大学电子信息与电气工程学部,2007: 5−47.ZHAO Dian-kun.Highway traffic emergency auto-detection using wireless[D].Dalian: Dalian University of Technology.Faculty of Electronic Information and Electric Engineering,2007:5−47.

[15]Leow W L,Ni D H,Hossein P N,et al.A sampling theorem approach to traffic sensor optimization[J].IEEE Transactions on Intelligent Transportation Systems,2008,6(9): 369−374.

[16]贾利民,董宏辉,秦勇,等.交通状态获取的新型传感器、传感器网络优化与融合[R].北京: 北京交通大学轨道交通控制与安全国家重点实验室,2009: 102−124.JIA Li-min,DONG Hong-hui,QIN Yong,et al.The new traffic sensors,sensor networking optimization and data fusion of traffic state[R].Beijing: Beijing Jiaotong University.State Key Laboratory of Rail Traffic Control and Safety,2009: 102−124.