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

(1.北京交通大學(xué) 軌道交通控制與安全國家重點(diǎn)實(shí)驗(yàn)室，北京，100044；2.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京，100044)

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

1 傳感器反映的交通信息

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

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

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

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

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

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

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

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

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

(3)根據(jù)不同的路面特征、道路環(huán)境及道路等級等道路條件，g(x)可有不同的曲線特征，如正態(tài)曲線、指數(shù)曲線、三角形(斜坡)(圖1)或其他曲線特征。實(shí)際情況中，大多為非對稱的，因?yàn)槁范紊嫌魏吐范蜗掠蔚慕煌ㄌ匦允遣煌摹?/p>

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

1.3 傳感器的信息價(jià)值

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

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

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

對于VCC的標(biāo)定，利用下式：

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

對于VEC的標(biāo)定，利用下式：

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

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

2 動(dòng)態(tài)組網(wǎng)方法

2.1 模型建立

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

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

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

rjk可以通過分析j和k路段上傳感器采集的交通信息的相關(guān)性得到。

對于qi，若點(diǎn)p1和p2在同一路段，則傳感器i從p1到p2處的每小時(shí)信息價(jià)值為：

若點(diǎn)p1和p2不在同一路段，p1點(diǎn)在路段j上，p2在路段k上，且路段j和路段k的交點(diǎn)為pjk，則傳感器i從點(diǎn)p1到點(diǎn)p2處的每小時(shí)信息價(jià)值為：

2.2 算法描述

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

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

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

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

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

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

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

3 實(shí)例分析

3.1 路網(wǎng)選取

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

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

3.2 求解步驟

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

C0表示處理一個(gè)傳感器信息的每小時(shí)固定費(fèi)用，與傳感器信息處理系統(tǒng)和人員利用情況有關(guān)。若系統(tǒng)的費(fèi)用為 30元/h，信息處理人員一名(以北京市平均工資10元/h計(jì))，則C0取40元/h[16]；V0可以由V算出。通過對北京市快速路交通檢測器擁擠成本、額外成本、蘊(yùn)含價(jià)值的標(biāo)定，利用1.3節(jié)中的模型得到一個(gè)傳感器信息價(jià)值為V=14 034 000元[16]，則傳感器信息價(jià)值為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，將其用于本實(shí)例快速路，可取G(x)=g(x)=e?0.1592x。

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

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

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

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

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

(4)貪心算法求解過程

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

表3 求解計(jì)算過程Table 3 Course of calculation

(5)動(dòng)態(tài)組網(wǎng)優(yōu)化結(jié)果

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

圖3 算法最終結(jié)果Fig.3 Last result of algorithm

4 結(jié)論

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

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

[1]姜桂艷,李繼偉,張春勤.城市主干路路段行程時(shí)間估計(jì)的BPR修正模型[J].西南交通大學(xué)學(xué)報(bào),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ū)域路網(wǎng)交通信息提取方法[J].西南交通大學(xué)學(xué)報(bào),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]楊少軍.無線傳感器網(wǎng)絡(luò)若干關(guān)鍵技術(shù)研究[D].西安: 西北工業(yè)大學(xué)電子信息學(xué)院,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]岳文劍.基于傳感器網(wǎng)絡(luò)的交通數(shù)據(jù)采集平臺研究[D].大連:大連理工大學(xué)建設(shè)工程學(xué)部,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)的研究與實(shí)現(xiàn)[J].計(jì)算機(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]趙殿奎.用無線傳感器網(wǎng)絡(luò)檢測公路交通突發(fā)事件[D].大連:大連理工大學(xué)電子信息與電氣工程學(xué)部,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)獲取的新型傳感器、傳感器網(wǎng)絡(luò)優(yōu)化與融合[R].北京: 北京交通大學(xué)軌道交通控制與安全國家重點(diǎn)實(shí)驗(yàn)室,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.