車輛無線傳感器網絡廣播協議的研究*

梁 偉，陳燕飛，李 娜

（常熟理工學院計算機科學與工程學院 常熟215500）

1 引言

隨著我國城市汽車保有量的不斷攀升，城市交通問題日益突出。例如城市“停車難、亂停車”現象非常普遍，既影響城市功能的發揮，也給居民汽車消費造成障礙。而目前我國大型停車場仍不具備智能車位管理系統。對于用戶而言，置身于大型停車場中，快速到達有效停車位仍相對困難，這樣便造成停車場整體運行效率低，甚至會因為停車不方便造成管理混亂。因此，本文提出了停車場車位自動化檢測的研究方案。該研究方案將運用到無線傳感器的網絡設計中，并利用無線傳感器網絡日益成熟的技術解決停車場自動化管理的難題。利用該方案能及時統計空閑車位，分配用戶指定車位，加快用戶的泊車速度，提高停車場的運行效率，并節約成本。

近年來，車輛傳感器網絡獲得了研究界極大的研究興趣。2010年，加拿大Ottawa大學PARADISE研究實驗室在車輛傳感器網絡定位服務發現協議和輔助定位的網關廣播發現協議中獲得了多項研究成果；2011年，美國加州大學在車輛傳感器網絡信息傳播合作的主動安全控制應用方面，也同樣進行了相關的研究。國內方面，如上海交通大學在車輛傳感器網絡及新一代智能交通信息服務的研究中也頗有成果。

2 停車場傳感器網絡系統總體概述

大量的傳感器節點被隨機散布在目標監測區域；對網絡進行網絡拓撲規劃；在數據收集過程中，需要每個傳感器采集到的有效數據及時、準確地傳回節點和基站；傳感器節點采集大量的實時數據進行壓縮處理。系統提供了停車場中總車位占用數以及更為具體的區域信息。在每個入口、出口和區域過渡處安放了傳感器。入口和出口處的傳感器，以無線方式將入口和出口的車輛數據傳輸到出口崗亭的中心基站，監測區域過渡點的傳感器檢測車流和方向，并確定車輛是否在區域間移動。傳感器將數據發送到中心基站，基站將對所有的數據進行分析，實時提供停車場總共可用的停車位數量和每個區域的停車位數量。車位檢測系統由4部分構成：

·安裝在停車場車位上的車位檢測器和安裝于天花板的路由節點構成的自組織無線傳感器網絡；

·由無線射頻模塊和監控機組成的停車場網關服務器；

·由PC機組成的停車場管理終端，用于管理停車場的車位使用情況和監控設備運行狀態；

·安裝在停車場天花板下的LED顯示屏，用于顯示停車場剩余車位的顯示情況，數據傳輸采用主動方式，傳感網采集車位占用與否，數據無線發送給停車場網關服務器。

其中，車位檢測器由微處理器、無線通信模塊、電源模塊、傳感器模塊構成。微處理器定時查詢傳感器模塊狀態。電源模塊負責提供一個穩定的電壓給微處理器，在適當的時候關閉一些模塊，使整個系統進入低功耗狀態。

處理器模塊：采用低功耗單片機，因為采用電池供電，要求系統的平均電流要低，才能延長產品的使用壽命。

無線通信模塊：射頻芯片是標準的低成本、低功耗、單片、高集成度的解決方案，工作在免費頻帶上，主要特點為具有接擴頻序列基帶調制解調和有效數據傳輸速率；適合簡化功能裝置和全功能裝置操作；電池電量可監控，適合各種惡劣的環境。

電源模塊：實現節點設計的微型化，電池每月自放電率小于10%，在以網絡形式工作狀態下通過合理的配置節點發射極的接收、發射以及待機狀態，可有效地延長節點的運用壽命。針對節點供電單元不便于更換的無線傳感器網絡，新的能源處理要領研究及網絡系統的低功耗設計也是當前值得關注的課題。

傳感器模塊：射頻芯片能對光、麥克風、震動做出傳感，無線傳感器網絡節點的數據采集部分可以根據不同的應用采用不同的傳感器，比如溫度、濕度、光、壓力、煙霧等。

3 通信與時間復雜度

車位檢測的網關協議基本上分為3類：

·主動方式，網關在整個網絡中廣播自己；

·被動方式，請求車輛遍布于整個網絡廣播區域；

·混合方式，網關以固定的周期廣播自己，請求車輛在廣播區域內發送它們的請求消息。

主動方式具有很好的連通性，但是如果在網關數目很多的情況下，成本也會相應提高。被動方式對于小型的網絡成本比較低，但可拓展性很差。混合方式相對于主動和被動方式有效得多，然而最重要的是怎樣確定廣播區域的半徑。在本文中，筆者提出了一種新的混合自適應性的輔助定位網關廣播和發現協議。這種機制不僅是混合式的，而且也是自適應性的，因為它可以根據變化的網關客戶端數量和已經存在的網關數量來確定網關廣播區域半徑，以網關的分布方式和動態方式確定主動的廣播區域。筆者對主動和被動網關發現進行比較，避開了混合協議的缺陷，并且調整了網關廣播的半徑。

3.1 主動廣播區域

首先考慮網關G想發送廣播消息給它的源車輛。網關G為網關廣播確定了一個主動的廣播區域，當一輛車V在主動廣播區域中接收到了一個網關廣播消息時，為了確認網關廣播消息已經到達了源車輛，主動廣播區域應該具有一個和其他區域一樣的預期區域。為了保證V和G屬于同一個主動廣播區域，其他區域可以被添加進去(如圖1所示)。這種算法提出了一個錐形的主動廣播區域。如果考慮到預期區域是一個以(t1-t0)×v為半徑的圓，那么提出的錐形的主動廣播區域是能夠獲得的最小的區域。

然而，錐形的主動廣播區域不是最佳的主動廣播區域。如果所有從G到V的路徑存在錐形的主動廣播區域外的車輛，就不能夠保證在錐形的主動廣播區域中找到一條V和G的路徑。因此，需要對廣播區域拓展，可以采用一個矩形的主動廣播區域(如圖2所示)或者一個半圓形的主動廣播區域(如圖3所示)。如果請求車輛的搜索區域里存在網關，那么利用定位輔助廣播和發現協議可以在有限的時間內找到請求車輛所請求的網關；如果一個請求車輛的周圍有很多的網關，那么在一個有限的時間內請求者會收到所有網關的回復。

3.2 通信與時間復雜度的計算

在這一部分中，先確定主動廣播區域，再計算通信和時間復雜度。

（1）計算錐形的主動廣播區域面積

H0(x0,y0)是車輛V在t0時刻以速度v行駛的位置，G(xg,yg)是網關G的固定位置，t1是下一周期廣播的起始時間。

圖1顯示了錐形的主動廣播區域Rt△ADG的近似面積。如果確定了A、G和D的坐標，就可以確定△AGD的面積。G的固定坐標是xg和yg，A(xa,ya)和B(xb,yb)取決于A的預期區域。用以H0為圓心、以最大距離為半徑的圓表示V的預期區域，這樣就可以被車輛V在t1時刻以速度v穿過。因此，圓C可以用C(H0，(t1-t0))來表示。D在x軸上的投影可以確定D的橫坐標為xd=x0+(t1-t0)×v，D在y軸上投影顯示了yd和yg是相等的。所以D的坐標是(x0+(t1-t0)×v,yg)。A在x軸上投影顯示了xa和xd是相等的。因此,xa=x0+(t1-t0)×v。A的縱坐標需要更多的計算。實際上，從圖1注意到ya=y0(t1-t0)×v+d。可以使用三角函數計算出d的距離。在此之前，△BCG和△AEB是相似的。實際上，△BCG和△AEB分別是直角三角形。此外，∠GAD和∠BAE是相等的。因此，由于△AGD和△ABE相似，所以它們至少有兩個角相等，所以，第三個角∠AGD和∠ABE也是相等的。另外，由于△BCG和△ADG有一個角相等并且是直角三角形，所以它們也是相似的。因此，可以得出△BGC和△ABE也是相似的。

現在應用直角三角形的三角函數：

最后，已知了△ADG所有頂點的坐標，可以很容易地知道△ADG的面積：

所以，錐形主動廣播區域的面積為：

（2）計算矩形的主動廣播區域的面積

H0(x0,y0)是車輛V在t0時刻以速度v行駛的位置，G(xg,yg)是網關G的固定位置，t1是下一周期廣播的起始時間。

圖2中顯示了矩形的主動廣播區域的矩形ABGD的面積。如果確定了A、B、G和D的坐標，就可以確定矩形ABGD的面積。G(xg,yg)的坐標是固定的。A(xa,ya)、B(xb,yb)和D(xd,yd)的坐標取決于車輛V的預期區域。用以H0為圓心、以最大距離為半徑的圓表示V的預期區域，這樣就可以被車輛V在時刻t1以速度v穿過。因此，圓C可以用C(H0，(t1-t0)×v)來表示。A、B和D在x軸和y軸上的投影可分別確定A、B和D的橫坐標和縱坐標，分別為：A(x0+(t1-t0)×v,yg)、B(x0+(t1-t0)×v,y0+(t1-t0)×v)、D(xg,y0+(t1-t0)×v)。

在確定了矩形ABGD所有點的坐標后，可以簡單地確定ABGD的面積：

所以，矩形主動廣播區域的面積為：

（3）計算半圓的主動廣播區域的面積

H0(x0,y0)是車輛V在t0時刻以速度v行駛的位置，G(xg,yg)是網關G的固定位置，t1是下一周期廣播的起始時間。

圖3顯示了半圓的主動廣播區域的面積是以G(xg,yg)為圓心、半徑為R=GP的半圓。如果確定了G和P的坐標，就可以確定半圓SC的面積。G(xg,yg)的坐標是固定的。P(xp,yp)的坐標取決于車輛V的預期區域。如前文所述，用以H0為圓心、以最大距離為半徑的圓表示V的預期區域，這樣就可以被車輛V在t1時刻以速度v穿過。因此，圓C表示為C(H0，(t1-t0)×v)。P在x軸和y軸上的投影可確定P的橫坐標和縱坐標，為P(x0+(t1-t0)×v,yg)。

現在，可以簡單地確定半圓SC的面積：

所以半圓形主動廣播區域的面積為：

（4）計算網關廣播消息的數量

G(xg,yg)是網關G的坐標。H0(x0,y0)是車輛V在t0時刻以速度v行駛的位置，t1是下一周期廣播的起始時間，ρ是車載網絡的密度，nd是網關廣播的頻率。

在該網關發現協議中，網關廣播消息的數量主要取決于主動廣播區域。主動廣播區域是可變的，它主要取決于車輛的預期區域和通過網關的請求區域。錐形的主動廣播區域相對于矩形和半圓形的主動廣播區域有更多的局限性。在另一方面，半圓的主動廣播區域比錐形和矩形的主動廣播區域面積要大。假設密度為ρ，在已知主動廣播區域的密度后就可以確定主動廣播區域中車輛的數量。

S1、S2、S3的計算分別得出了錐形、矩形和半圓形的主動廣播區域的面積。在計算了主動廣播區域的面積后，假設密度為ρ，就可以簡單地確定主動廣播區域中車輛的數量N：

為了避免消息的冗余，網關廣播消息的傳播在主動廣播區域中是受控制的。因此，每一輛在主動廣播區域中的車輛只轉發第一次收到的廣播消息，已經轉發過的廣播消息會被忽略。由此，在主動廣播區域中的同一個消息只會被傳播一次。所以：

其中，Na為廣播消息的數量。

由于網關是定期傳播廣播消息的，把時間等分成每一小段△t，并且假設在考察的時間段內廣播的數量為n，因此可以得到在一個周期內廣播的數量np：

因此，在最壞的情況下，網關廣播消息的數量取決于主動廣播區域和廣播的頻率。相應的等式為：

其中，n1、n2、n3分別為錐形、矩形和半圓形主動廣播區域的廣播消息。

（5）計算請求消息的數量

V的坐標為(xv,yv)，網關G的坐標為(xg,yg)，車載網絡的密度為ρ。

圖4說明了一個服務請求者車輛的請求區域在主動區域之外的情況。在最壞的情況下，如果一輛車輛不在網關的主動廣播區域中，想要找到一個網關，那么其請求消息將會一直被傳播下去，直到有一個屬于主動廣播區域的網關接收到。假設消息的傳播和車輛行駛的方向一致，則可以確定請求消息所在的區域。在本文的協議中，為了避免傳播冗余的消息，請求消息的傳播是受控的。也就是說，同一個消息只被車輛轉發一次。所以，在請求消息傳播的區域中，請求消息的數量和車輛的數量是相同的。

設車輛V的請求消息的數量為nq，則：

（6）計算回復消息的數量

在最壞的情況下，主動廣播區域中的所有車輛排在一條線上，那么回復消息將會被主動廣播區域中的所有車輛轉發。

在這種情況下，一個網關的回復消息的數量為：

其中，S是相應的主動廣播區域的面積，ρ是車載網絡的密度。

結論1消息的復雜度是由網關的數量和請求車輛的數量決定的。網關的主動廣播區域面積不是固定的，而是動態和自適應變化的。消息的復雜度取決于請求車輛的位置和運動狀態，所有消息的復雜度是在考察的時間段內每一輛請求車輛的廣播消息的數量、請求消息的數量和相應的回復消息的數量的總和。

被交換的消息的總數為：

結論2時間的復雜度是在考察的時間段內服務請求車輛收到第一個服務回復的平均時間。ns是請求車輛發起網關發現的數目。在最壞的情況下，網關請求車輛發出的網關請求消息會一直被傳播，直到找到一個網關接收。然后網關必須生成一個回復消息并且回復給請求者車輛。因此，假設請求者發給網關的請求消息的數量為nq，網關回復給請求者的消息的數量nr，λt是消息在車輛傳感器網絡中傳播所需的時間。因此請求車輛收到它的第一個回復消息的時間為：

因此，一個網關請求車輛收到第一個網關回復的平均時間為：

4 結束語

本文討論了車載網絡輔助定位在車位檢測技術中的理論研究，并給出了停車場無線傳感器網絡設計的總體設計方案。在本文中，提出了一種新的混合自適應性的輔助定位網關廣播和發現協議。這種機制不僅是混合式的，而且也是自適應性的，因為它可以根據變化的網關客戶端數量和已經存在的網關數量確定網關廣播區域半徑。以網關的分布方式和動態方式確定主動的廣播區域。對主動和被動網關發現進行比較，避開了混合協議的缺陷，并且調整了網關廣播的半徑。詳細地給出了計算車輛傳感器網絡廣播協議的消息交換的復雜度和消息傳輸總時間復雜度的公式。該設計方案在提高整個控制系統效率方面具有重要的作用，在未來的工作中，需要對該設計方案的性能進行評估，并且和已經存在的用于大型停車場的無線傳感器網絡設計方案進行比較，并將該方案運用于不同的設計模型中。

1 馮馳,劉希勝.基于ZigBee的無線環境監測網絡設計.應用科技,2009,36(5):39～42,60

2 孟振飛,趙亞靈,侯貽帥.基于ZigBee技術的無線數傳模塊設計.電子元器件應用，2010,12(4):37～39,43

3 Boukerche A,Abrougui K,Pazzi R W.Context-aware and location-based service discovery protocol for vehicular networks.Proceedings of the 6th ACM Symposium on Performance Evaluation of Wireless Ad Hoc,Sensor,and Ubiquitous Networks,Spain,2009:93～100

4 昌學年,姚毅,閆玲.位移傳感器的發展及研究.計量與測試技術,2009,36(9):42～44

5 Morgan Y L.Notes on DSRC&WAVE standards suite:its architecture,design,and characteristics.IEEE Communications Surveys & Tutorials,2010,12(4):504～518

6 郭穩濤,何怡剛.基于RFID的智能停車場管理系統的研究與設計.自動化技術與應用,2010,29(6):61～64

7 Zhao Jijun,Li Hua,Zhao Xin.The comparative research on the location technology of wireless sensor networks.Communications and Network,2009,1(2):114～120

8 魯資,林水生,周亮.基于無線傳感器網絡的溫度場繪制.傳感器與微系統,2011(30):17～19

9 Mak T K,Laberteaux K P,Sengupta R,et al.Multichannel medium access control for dedicated short-range communications.IEEE Transactions on Vehicular Technology,2009,58(1):349～366

10 Huang C L,Guan X,Fallah Y P,et al.Robustness evaluation of decentralized self-information dissemination control algorithms for VANET tracking applications.Proceedings of IEEE 70th Vehicular Technology Conference，VTC2009-fall,Alaska,USA,2009

11 Jiao J B,Ye Q X,Huang Q M.A configurable method for multi-style license plate recognition.Pattern Recognition,2009,42(3):358～369

12 Kavitha T,Sridharan D.Security vulnerabilities in wireless sensor networks:a survey.Journal of Information Assurance and Security,2010(5):31～44

13 Padmavathi G,Shanmugapriya D.A survey of attacks,security mechanisms and challenges in wireless sensor networks.International Journal of Computer Science and Information Security,2009,4(1&2)

14 Bi Yuanguo,Liu Kuanghao,Cai L X,et al.A multi-channel token ring protocol for QoS provisioning in inter-vehicle communications.IEEE Transactions on Wireless Communications,2009,8(11):5 621～5 631

15 IEEE 802.11p-2010.IEEE Standard for Information Technology-Telecommunications and Information Exchange Between Systems-Local and Metropolitan Area Networks-Specific Requirements-PartⅡ:Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications Amendment 6:Wireless Access in Vehicular Environments,2010