面向城市道路交通的傳感器組網優(yōu)化

李海艦 ，董宏輝 ，徐東偉 ，賈利民

(1.北京交通大學 軌道交通控制與安全國家重點實驗室，北京，100044；2.北京交通大學 交通運輸學院，北京，100044)

交通傳感器以數(shù)據(jù)流的形式進行交通數(shù)據(jù)的傳輸，即傳感器能夠持續(xù)檢測交通流信息，得到連續(xù)的檢測數(shù)據(jù)，并按規(guī)定的時間間隔上傳數(shù)據(jù)。傳感器數(shù)據(jù)中包含的信息很可能蘊含著當時的交通流特性、事故信息、交通流狀態(tài)、道路擁堵程度等，要求能夠被及時處理和響應。姜桂艷等[1]研究的城市主干路路段行程時間估計和戢曉峰等[2]研究的區(qū)域路網交通信息提取方法都是以利用交通傳感器采集的交通流數(shù)據(jù)為基礎的。Li等[3]、Hu等[4]和Zhou等[5]分別研究了交通傳感器優(yōu)化布局技術，提出了面向不同應用的交通傳感器在實際路網中的布設方法。需要進一步研究的是在物理層交通傳感器布設之后，為獲取路網中的不同范圍和不同形式的交通信息，交通傳感器的邏輯層組網優(yōu)化技術。近年來，隨著嵌入式系統(tǒng)、網絡技術、微電子技術的發(fā)展，傳感器網絡得到重視和發(fā)展。傳感器網絡由大量具有通信和計算能力的傳感器節(jié)點構成，是可根據(jù)環(huán)境自主完成任務的智能自組織分布式網絡系統(tǒng)。其研究起步于20世紀80年代，2000年以來，隨著微電子技術、計算技術和無線通信等技術的進步，制造廉價、微型、低功耗、多功能的傳感器節(jié)點成為可能。由大量集成信息采集、數(shù)據(jù)處理和通信等功能的傳感節(jié)點組成的傳感器網絡具有高可靠、易部署和可擴展等特點，正逐漸受到人們的重視，并獲得迅速發(fā)展[6?7]。在國內，傳感器網絡系統(tǒng)方面的研究起步較晚，近幾年發(fā)展迅速。傳感器網絡在智能交通方面應用也得到廣泛關注，主要集中在道路信息采集[8?9]、交通安全[10?12]和交通控制[13]等方面。傳感器組網的研究對道路信息的有效采集、信息傳輸和處理，以至交通事故判別與檢測[14]、交通優(yōu)化控制、交通安全提升等都有重要的現(xiàn)實意義。通過傳感器的組網，可以實現(xiàn)路口、路段和區(qū)域交通信息的綜合獲取和交通狀態(tài)判別，能夠及時發(fā)現(xiàn)影響交通安全和導致?lián)矶碌慕煌ㄊ录?。綜合國內外文獻，面向城市道路交通的傳感器組網優(yōu)化的研究較少，本文作者主要面向城市道路交通，初步探討基于交通事件的傳感器組網優(yōu)化方法。

1 傳感器反映的交通信息

1.1 基于信息度的宏觀交通狀態(tài)描述

從傳感器交通信息反映的宏觀交通狀態(tài)入手，對傳感器通過采集的交通信息數(shù)據(jù)反映宏觀交通狀態(tài)的方式進行了描述和表示，并在此基礎上定義了傳感器所反映出的宏觀交通信息度。

宏觀交通狀態(tài)可由速度、流量、占有率等宏觀參數(shù)表示，所以宏觀交通狀態(tài)主要表現(xiàn)在速度、流量、占有率等宏觀參量上。對于路段上布設的一個交通傳感器，由于其能夠檢測一定的宏觀交通參數(shù)，則它能夠完全反映(暫不考慮傳感器的準確率)出傳感器點處相應參數(shù)的交通信息。另外在離傳感器一定距離處，由于交通參數(shù)變化的連續(xù)性和數(shù)據(jù)量的相關性，則彼處的交通信息(即宏觀交通狀態(tài))可以在一定的概率下由此傳感器信息代替或反映。所以交通傳感器可以以一定的概率反映出一定距離內的交通狀態(tài)信息。某傳感器能夠準確反映傳感器處交通狀態(tài)的概率為 1，則準確代表距此傳感器x距離單位處的交通狀態(tài)的概率為p=p(x)。這樣在整個定義域內(－∞＜x＜＋∞)，p(x)可看作某傳感器能夠代表距此傳感器x距離單位處交通狀態(tài)的概率。

1.2 傳感器的空間信息度函數(shù)

根據(jù)上節(jié)的分析，在一個路段上，交通傳感器反映空間交通信息可以用概率進行表示，這里定義一個傳感器的信息度函數(shù)，定義：

式中：x為距此傳感器的距離；p(x)為此傳感器能夠準確代表距離其x處的交通狀態(tài)的概率；g(x)為此傳感器的信息度函數(shù)。

路段上某傳感器的信息度函數(shù)g(x)可以進行如下描述：

(1)g(x)是對傳感器檢測的某種交通狀態(tài)參數(shù)而言，不同的交通狀態(tài)參數(shù)有不同的信息度函數(shù)。其物理意義為距交通傳感器一定距離處的交通信息，能被傳感器檢測到的交通信息所代表的概率或程度；也可理解為某傳感器能夠代表的空間單位距離上交通信息的程度。

(2)g(x)是關于定義域(一般為研究路段或研究區(qū)域)上的連續(xù)函數(shù)，且g(0)=1。

(3)根據(jù)不同的路面特征、道路環(huán)境及道路等級等道路條件，g(x)可有不同的曲線特征，如正態(tài)曲線、指數(shù)曲線、三角形(斜坡)(圖1)或其他曲線特征。實際情況中，大多為非對稱的，因為路段上游和路段下游的交通特性是不同的。

圖1 信息度函數(shù)的分布特征Fig.1 Distribution of information function

1.3 傳感器的信息價值

路段及路網的交通狀態(tài)對管理者和出行者來說都是很重要的，這也是ITS系統(tǒng)的數(shù)據(jù)來源之一，所以，由這些狀態(tài)參數(shù)所形成的交通信息對管理者和出行者的決策、城市交通規(guī)劃部門的參考等等都有很大的指導意義。這些信息的準確性、完整性對管理者和規(guī)劃者正確決策和合理規(guī)劃起著關鍵作用，所以，某傳感器檢測到的交通信息蘊含著一定的社會價值。

這里的社會價值指在此路段上布設傳感器后，在整個傳感器壽命周期內，與沒有布設傳感器相比所增加的價值，可以根據(jù)社會價值不同的外在表現(xiàn)劃分為3個部分(擁擠成本、額外成本、蘊含價值)，用下式表示：

式中：VCC(Congestion costs)為由于放置該傳感器，路段減少的擁擠成本；VEC(External costs)為由于本路段信息量的增加，得到的額外價值，或減少的額外成本，主要包括車輛減少的油耗成本以及污染、噪聲等外部成本；VIV(Intrinsic Value)為交通信息蘊含的固有價值。

對于VCC的標定，利用下式：

式中：NU為傳感器使用年限，a；NY為1 a的天數(shù)，d/a；CV為每輛車每小時的平均擁擠成本，與當?shù)仄骄鶆趧庸べY有關，元/(輛·h)；T為研究路段每天的擁擠小時數(shù)，h/d；QC為由于此路段缺少傳感器信息增加的擁擠車輛數(shù)，輛[15]。

對于VEC的標定，利用下式：

式中：EV為每輛車每小時的平均額外價值，與道路水平有關，元/(輛·h)。

對于VIV，可根據(jù)交通數(shù)據(jù)擁有者的評估進行標定。

2 動態(tài)組網方法

2.1 模型建立

在物理層傳感器都已經部署的基礎上，如何針對典型交通事件(如事故判別、交通疏導、信號控制、路段信息收集等)，如何選取適當數(shù)量和適當位置的傳感器，使這些傳感器得到盡可能大的綜合信息價值量是本節(jié)建模所要解決的問題。其建模目標是使傳感器信息的社會價值與處理傳感器數(shù)據(jù)的成本之差最大化，即綜合信息價值最大化。給定路段k上的典型事件A，建立基于傳感器單位小時綜合價值最大的動態(tài)組網模型如下：

式中：W為組網后的傳感器每小時綜合價值；i為傳感器編號；ji為傳感器i所在路段編號；k為事件A所在路段編號；gi(x)為傳感器i的信息度函數(shù)；w為傳感器編號解集；w0為事件A附近可利用的物理傳感器編號集合；qi為物理層第i個傳感器能夠提供給此事件的每小時平均信息價值；vi為物理層第i個傳感器所具有的每小時平均信息價值；ci為處理或利用傳感器i的信息產生的每小時固定成本；點xi-、點xi+由gi-(x)，gi+(x)與gi(x)函數(shù)的疊加點決定(前后兩傳感器信息度函數(shù)疊加時取最大者)；gi-(x)和gi+(x)為解集中同一路段上傳感器i前后兩傳感器的信息度函數(shù)。

其中：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 算法描述

模型求解是一個動態(tài)規(guī)劃問題，當傳感器個數(shù)較多時，求得最優(yōu)解比較困難。由于解集元素是一個個加入的，可以利用貪心算法求得滿意解。貪心算法操作簡單，求解思路清晰，易于編程實現(xiàn)，通過設置一定的約束條件來控制求解過程，能夠得到次優(yōu)解或最優(yōu)解。求解思路如下：

Step 1：確定各參數(shù)。

Step 2：確定研究的事件A，并根據(jù)事件A確定相關的物理層傳感器，從而確定路段k和初始傳感器集合w0。

Step 3：對于事件A，利用貪心選擇規(guī)則確定第一個初始解，并計算W的值。

Step 4：在剩余的傳感器中按照貪心選擇規(guī)則依次增加解集元素，得到新的W。

Step 5：判斷W變化情況，若不滿足事先給出的約束條件，則重復步驟 4；否則停止計算，返回最大值Wm和對應解集w。

貪心選擇規(guī)則可以選擇與事件A點處相關性最大的或信息價值最高的傳感器，或根據(jù)相關系數(shù)、信息價值和成本3個因素的融合值由大到小選取。約束條件可設定為求解精度或算法的迭代次數(shù)。

3 實例分析

3.1 路網選取

圖2 事件A相關的傳感器分布圖Fig.2 Distribution of sensor related to an event

選取北京市西三環(huán)和西四環(huán)處的一個路網區(qū)域，假設典型事件A發(fā)生在圖示(見圖2圓圈處)的位置(4號傳感器處，由4號傳感器到3號傳感器的車流方向)，為了盡快得到事件A點處周圍的交通信息，利用本模型選取合適的傳感器進行動態(tài)組網。這里以路網中實際部署的傳感器(微波傳感器)為研究對象。傳感器i的信息度函數(shù)、單位小時固定成本、單位小時信息價值分別記作gi(x)，ci和vi，為簡化起見，各傳感器信息度函數(shù)、單位小時固定成本、單位小時信息價值分別取相同值，記為G(x)，C0和V0，即：

3.2 求解步驟

(1)確定參數(shù)C0和V0

C0表示處理一個傳感器信息的每小時固定費用，與傳感器信息處理系統(tǒng)和人員利用情況有關。若系統(tǒng)的費用為 30元/h，信息處理人員一名(以北京市平均工資10元/h計)，則C0取40元/h[16]；V0可以由V算出。通過對北京市快速路交通檢測器擁擠成本、額外成本、蘊含價值的標定，利用1.3節(jié)中的模型得到一個傳感器信息價值為V=14 034 000元[16]，則傳感器信息價值為V0=V/(6×365×24)=267 元/h。

(2)確定傳感器信息度函數(shù)和貪心選擇規(guī)則

通過2008年4月10日北京市二環(huán)路部署的微波傳感器得到的交通狀態(tài)參數(shù)數(shù)據(jù)[16]，得到北京市快速路傳感器的信息度函數(shù)為g(x)=e?0.1592x，將其用于本實例快速路，可取G(x)=g(x)=e?0.1592x。

貪心選擇規(guī)則可設定為每次選擇與事件A點處相關性最大的傳感器，可得各傳感器信息與事件A的相關系數(shù)見表1。

表1 各傳感器與事件A相關系數(shù)表Table 1 Correlation coefficient between sensor and an event

(3)確定各路段信息相關系數(shù)矩陣

通過2008年4月10日各傳感器(圖2)測得的路段速度數(shù)據(jù)，得到5個主要路段的交通信息相關系數(shù)矩陣見表2。

表2 路段信息相關系數(shù)矩陣Table 2 Correlation coefficient matrix of road information

(4)貪心算法求解過程

利用上述的貪心選擇規(guī)則，逐個加入新的傳感器到解集中，得算法的計算過程和綜合價值的計算結果(見表3)。

表3 求解計算過程Table 3 Course of calculation

(5)動態(tài)組網優(yōu)化結果

從表3可知：當選擇12個傳感器時，可得W值達到最大，此時的解集w為4，3，5，12，2，13，6，11，1，7，14和8，得到的W為553.442元/h。計算完畢，最終解集見圖3(W整體上升過程中有個別點下降(如第6步、第8步)，說明貪心算法的每一步選擇不一定是最優(yōu)的，但此方法能找到滿意解或最優(yōu)解，本例為最優(yōu)解)。

圖3 算法最終結果Fig.3 Last result of algorithm

4 結論

(1)通過研究由傳感器獲得交通信息的空間特性，定義了傳感器的空間信息度函數(shù)，并分析和標定了傳感器的信息價值。在此基礎上建立的基于每小時信息價值最大的動態(tài)組網模型，實現(xiàn)了物理層傳感器基于特定交通事件的邏輯層動態(tài)組網。通過給出的求解算法，實現(xiàn)了動態(tài)組網模型的求解計算過程，并為實例給出了合理的組網結果，也為傳感器的信息度函數(shù)和信息價值理論提夠了應用支持。

(2)通過對傳感器信息的進一步挖掘，可以提高各傳感器信息的利用效率。對不同類型的交通事件，文中模型和算法都可以通過標定相應的模型參數(shù)得到相應事件的組網結果，并獲得合理的交通信息，為交通管理提供依據(jù)。

[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]戢曉峰,劉瀾,吳其剛.區(qū)域路網交通信息提取方法[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].西安: 西北工業(yè)大學電子信息學院,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]岳文劍.基于傳感器網絡的交通數(shù)據(jù)采集平臺研究[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]袁凌云,朱云龍,瞿立成.分布式無線交通監(jiān)控系統(tǒng)的研究與實現(xiàn)[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]趙殿奎.用無線傳感器網絡檢測公路交通突發(fā)事件[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]賈利民,董宏輝,秦勇,等.交通狀態(tài)獲取的新型傳感器、傳感器網絡優(yōu)化與融合[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.