車聯社交網絡：機遇、挑戰和應用

何宗鍵+曹建農+鄭俊浩

中圖分類號：TP391 文獻標志碼：A 文章編號：1009-6868 （2014） 01-0031-004

Vehicular Social Networks： Opportunities， Challenges and Applications

摘要：對車聯社交網絡根據研究側重點做了分類，并對車聯社交網絡中的一些機遇和挑戰進行了探討；提出了一種利用社交網絡分享的實時交通信息為車聯網進行最短路徑規劃導航的解決方案。實驗數據表明該方案在導航效率上超越了現有的靜態路徑規劃方案。

關鍵詞： 車聯網；社交網絡；群智計算；無意識協作

Abstract： In this paper， we survey and classify existing works on vehicular social networks. Then， some challenging issues are discussed. Finally， we propose an application that uses socially shared real-time traffic information to find the quickest route to a destination. Our evaluations show that the proposed solution outperforms existing static route-planning solutions.

Key words： vehicular networks； social networks； collective computing； opportunistic sensing

隨著通信技術、移動計算技術以及嵌入式技術的發展，傳統線上社交網絡在不斷地向移動化、普適化方面發展。使得用戶可以更自由、更方便隨時隨地通過社交網絡分享信息與交流合作。收集并對社交網絡中的信息進行提取、分析、挖掘并加以利用已經成為了社交網絡研究領域的重要研究課題。目前，經過十多年的發展，智能手機已經相對成熟，能夠提供聯網能力、移動能力、感知能力和計算能力，從而成為移動社交網絡的主要平臺載體。如果我們要問，下一個移動社交網絡的載體會是什么？下一輪移動社交網絡的增長點在哪里？不難預見，智能汽車將有極大的潛力成為未來移動社交網絡的另外一個重要載體。

智能汽車是具有網絡連接能力、感知能力和計算能力的新型車輛。未來有潛力改變人們的出行和生活方式。之所以預見智能汽車可以成為移動社交網絡的新載體，主要原因是它可以滿足移動社交網絡所要求的多種相關能力。鑒于移動能力是車輛的天性，在此不再贅述。下文著重闡述智能汽車的聯網能力、感知能力和計算能力：

（1）聯網能力

行駛在路上的車輛將不再是孤立的個體。通過無線網絡技術實現車車、車路、車云互聯已經成為未來智能汽車發展的必然趨勢[1]。當前，部分汽車已經通過3G/LTE技術實現了車云互聯。同時，IEEE已經于2010年頒布了車用短距離通信協議IEEE 802.11p，為將來的車車、車路互聯提供了底層技術支撐。在企業界，傳統汽車廠商（寶馬、福特等）和新興的信息技術公司（谷歌、蘋果、特斯拉等）同時都積極展開車聯網相關的研發工作。

（2）感知能力

目前的車輛上已經擁有了超過100多種傳感器，可以感知車輛速度、油量、引擎轉速、外圍溫度、汽車排放等一系列數據。這些傳感器數據可以通過標準車載診斷接口（OBD）[2-3]獲取。

（3）計算能力

目前的許多汽車上都已經配備了32位的CPU，與此同時，遍布車身還有超過50個MCU，與處理器通過車身控制器局域網（CAN）總線[4]相連，共同構成了強大的計算系統。更為重要的是，通過智能汽車進行復雜計算能耗將不再是關鍵問題，因為車身蓄電池可以為計算系統提供持久的電力供應。這與智能手機平臺相比是一個巨大的優勢。

鑒于以上理由，如果智能汽車與社交網絡二者可以有機融合，將會進一步推動推動車聯網、移動計算以及群智計算等相關研究領域在廣度和深度上的進一步發展。本文將其結合成的系統命名為車聯社交網絡。

然而，智能汽車與社交網絡的結合并不是一蹴而就的。其結合充滿著挑戰，并且需要解決若干關鍵科學問題。

1 車聯社交網絡研究的

相關工作

現階段，車聯社交網絡的研究主要集中在兩個方面：一方面從社交網絡出發，嘗試引入車聯網的一些特性，來強化社交網絡本身；另一方面從車聯網絡入手，嘗試把社交網絡中的一些概念等結合進來，其目的是強化車聯網絡。除此之外，車聯網與社交網的結合也產生了一些傳統方式難以實現或實現成本過高的應用。本節將依次按照這3類文獻介紹相關工作。圖1是本節的文獻分類圖。

車輛輔助的社交網絡主要圍繞車聯網絡的構建、駕車信息分享等熱點展開。美國麻省理工學院在2006年首次提出了車輛中的社交網絡的概念[5]，與此同時，他們在車輛中開發了一套名為Flosser的系統，主要用于駕車好友之間信息分享。此后，各大汽車公司紛紛把社交分享功能融入到自家的車載信息系統中，其中比較知名的有通用公司的OnStar和寶馬公司的iDrive[6]。然而，如何在車聯網環境下自動構建社交網絡依然是一個問題，Drive and Share[7]提出了一套基于IP多媒體和機器到機器通信的社交網絡構建方法。文獻[8]進一步探討了如何在車聯網環境下解決社交網絡的信任問題。

社交輔助的車聯網絡則主要關注在如何利用社交網絡的社交關系來提供可信網絡傳輸；或者把社交網絡中的一些理論，如小世界理論，集中性分析等引入車聯網來提高時延容忍網絡的路由精確度。文獻[9]提出了一個車輛之間協作的框架，其目的是通過車輛間的協作，提供更好的多跳消息傳遞。文獻[10]把社交網絡中的信任引入了車聯網，試圖解決車聯網中的信任問題。文獻[11]把社交網絡中的Socially Selfish理論引入車聯網，以此提高車聯網在時延容忍條件下的路由效率。

除了上文提到的社交信息分享以外，車聯社交網絡的新應用還主要包含如下內容：（1）即時通信。RoadSpeak[12]是一個車車之間的即時聊天工具。文獻[13]更進一步把它擴展為多方實時語音通信，可替代現有的基于無線電的出租車呼叫中心等應用。（2）路徑規劃。文獻[10]、文獻[14]提出了一種基于車聯社交網絡的路徑規劃方法，用來通過用戶分享的簡單信息，如交通擁堵，來實現更加實時的車輛導航。（3）實時預警。文獻[15]提出了一種通過社交網絡對駕駛員進行實時預警的應用，例如前方路段危險等。以供駕駛員更方便的駕駛。

2 車聯社交網絡面臨的

問題及挑戰

車聯社交網絡的發展面臨若干關鍵科學問題及挑戰。本節將著重介紹這些問題。

2.1 車聯社交網絡的構造、維護與

傳遞

由于車輛的高移動性特點，車車、車路通信的網絡呈現出拓撲頻繁變化、經常斷開等特征。在拓撲高速變化的網絡上如何構造與維護社交網絡是一個極大的挑戰。這其中的研究問題包括：（1）共同興趣結點的發現，即如何查找、發掘與發現有共同興趣，或者有關系的結點。（2）結點的加入和離開。在高速變化的網絡中，如何低成本的維護一個社交網絡的結構，即結點的加入和離開也是一個具有挑戰的問題。（3）車聯社交網絡的信息傳遞。如何高效、開支更少的通過車聯社交網絡傳遞信息，這其中包括了信息的單播，多播和社交群內的廣播等研究內容。

2.2 信息感知與獲取

與傳統社交網絡不同，傳統社交網絡中的信息更多的是用戶有意識地產生的（如發照片、發狀態等）。而在車載環境下，由于安全原因，駕駛員不方便有意識地共享一些信息。因此，更多的信息需要在用戶無意識的情況下去感知和獲取。這其中的研究問題包括：（1）機會感知。由于缺少用戶主觀采集數據，系統需要根據上下文信息，自主地采集數據。（2）數據的預處理。從車輛傳感器獲取的原始數據往往不包含語義信息（如加速度），需要借助車輛計算平臺進行預處理，以獲得更加有實際意義的信息（如急剎車）。（3）無意識協作機制。單個用戶無意識貢獻的數據往往是稀疏的、殘缺的，甚至是不準確的。需要借助社交網絡，把多個用戶的數據整合起來，以推斷出實際的情況。

2.3 社交隱私保護

隱私是車聯社交網的重要研究內容，主要的挑戰來自兩個方面：其一，車聯社交網絡中產生的很多數據都是高度敏感的隱私數據，例如用戶的行車軌跡、停車位置、同行人員等；其二，由于車聯網的拓撲結構的變化性，數據緩存、多跳等是必然的數據傳遞手段。而在緩存、多跳的過程中，容易產生數據泄露風險。因此，如何保證用戶社交信息安全的前提下進行數據采集、分享和使用是重要研究課題。

2.4 深度整合的應用

現有的車聯社交網絡研究還停留在用車聯網來增強社交網中的原有應用，或反過來用社交網增強車聯網的原有應用階段。缺乏深度整合的、新產生的應用。因此，如何發掘、發現新的車聯社交網的應用也是一個亟待解決的挑戰。例如，是否可以把社交網絡游戲中的好友競爭機制引入到車聯網中。激勵好友共同節省排放、遵守交規等。

3 基于社交網分享信息的

實時路徑規劃

基于實時交通信息的路徑規劃相比基于地圖的靜態路徑規劃有極大的優勢。但是如何獲取實時交通信息是一大難題。傳統采用感應線圈或監控探頭的方案由于依賴基礎設施[16]，造成成本高昂。借助車聯社交網絡，在臨近的好友之間通過無線網絡共享交通信息，可以做到低成本的數據收集。

3.1 問題描述

在源車輛準備開始導航前，通過車聯網向周圍相鄰路段上的車輛發送數據收集請求。周圍的車輛收到數據請求后，會繼續把請求轉發給相鄰車輛。同時會把自己的周圍的交通狀態反饋給源車輛。然而，這種方式采集數據帶來的最大問題是會造成廣播風暴，浪費大量的網絡帶寬。因此，必須采取措施，限制數據采集的規模。當然，理論上如果要想找到最優導航路徑，必須要獲得全局交通信息，但是這在現實中是不可能的。我們只能退而求其次，求解相對可以接受的次優方案。該問題等同于在一個初始邊權重未知，但可以逐漸探索可知的圖中尋找最短路徑。該問題在圖論及運籌學中被以有源隨機最短路徑問題（SSPPR）提出。并且已經證明了該問題屬于非多項式-完全（NP-Complete）問題[17]。因此，該問題沒有多項式時間內的最優解，除非P等同NP。

3.2 解決方案

為了解決這個問題，我們提出了一種啟發式搜索算法。該算法基于如下兩個觀察：經過的道路越長，通常消耗的時間也越長；如果最短路徑的擁堵程度可以接受，沒必要另辟蹊徑。因此，我們在搜索的過程中，設置了兩個閾值，一個是最長的路徑閾值a，表示當前規劃路徑為最短路徑的倍數。另外一個是擁堵閾值b，表示擁堵程度。搜索的路徑長度不得超過閾值a，同時，在當前道路的擁堵程度小于閾值b時，搜索會沿著最短路徑前進。如果超過了閾值b，則會搜索當前路段的所有相鄰路段。我們把該算法稱為Backoff-and-Fork，簡稱BnF。

圖2是該算法的一個實際例子。假設S和E分別為起點和終點。首先算法會把最短路徑S-c-h-E設為備選路段，然后搜素沿著備選路段進行。對S-c進行交通狀況收集，假設S-c的路況良好。之后，算法對c-h進行交通狀況收集，發現該段路況擁堵。這時，算法會回退到結點c，把c的所有相鄰路段（即c-d與c-f）設為備選路段。并計算d-E和f-E的最短路徑，并把最短路徑c-d-g-E和c-f-h-E也設為備選路段。接下來繼續沿著備選路段開展搜索，直至抵達終點E。

4 實驗與結果分析

為了測試方案的有效性，我們基于香港理工大學自行開發的智能交通平臺iTransNet[18]進行了測試。該測試平臺的拓撲信息如圖3所示。該平臺上有一些可編程控制的車輛，并且車輛之間通過ZigBee進行數據通信。因此，我們可以通過ZigBee來獲取周圍路段的交通信息，并實時控制車輛的行進方向。我們把我們的方案與傳統的靜態圖中尋找最短路徑的Dijkstra算法進行對比。

圖4、圖5是實驗結果圖。圖4的3張是在密集交通的情況下獲得，圖5的3張圖是在稀疏的交通情況下獲得。通過實驗，我們可以看到，在稀疏的情況下，我們的算法與最短路徑算法對比優勢不是很明顯，因為此時時間最省的路徑通常就是最短路徑，繞路是不劃算的。但是在密集交通下，我們算法的優勢相當明顯。與最短路徑相比，繞開擁堵路段最多可以節省大約60%的時間。當然，在節省時間的同時，繞路是有成本的，那就是行駛的距離變長了。從最右側的兩幅子圖中可看出，算法會導致行駛總路徑變長，是方案的額外開銷。

5 結束語

本文首先對車聯社交網絡的研究現狀做了歸類和綜述。在此基礎上，對車聯社交網絡中的一些機遇和挑戰進行了探討。然后，提出了一種利用社交網絡分享的實時交通信息為車聯網進行最短路徑規劃導航的解決方案。在iTransNet上的實驗數據表明該方案在導航效率等方面超越了現有的靜態路徑規劃方案。

參考文獻

[1] HARTENSTEIN H， LABERTEAUX K P. A tutorial survey on vehicular ad hoc networks [J]. Communications Magazine， IEEE， 2008，46（6）： 164-171. doi： 10.1109/MCOM.2008.4539481.

[2] ELLISON N B. Social network sites： Definition， history， and scholarship [J]. Journal of Computer - Mediated Communication， 2007，13 （1）： 210-230. doi： 10.1111/j.1083-6101.2007.00393.x.

[3] OBD II Technology. [EB/OL]. （2013-10-20）. http：//www.obdii.com/.

[4] ISO 15765-4：2011. Road vehicles -- Diagnostic communication over Controller Area Network （DoCAN） [S]. 2011.

[5] LIANG P A. Social networking in vehicles [R]. Massachusetts Institute of Technology， 2006.

[6] TSCHELIGI M， MESCHTSCHERJAKOV A， WILFINGER D. Interactive Computing on Wheels [J]. Computer， 2011， 44（8）： 100-102. doi： 10.1109/MC.2011.246.

[7] LEQUERICA I， GARCIAlLONGARON M， RUIZ P M. Drive and share： efficient provisioning of social networks in vehicular scenarios [J]. Communications Magazine， IEEE， 2010，48（11）： 90-97. doi： 10.1109/MCOM.2010.5621973.

[8] ABBANI N， JOMAA M， TARHINI T， et al. Managing Social Networks in vehicular networks using trust rules [C] //Proceedings of Wireless Technology and Applications （ISWTA）， 2011 IEEE Symposium on， 25-28， Sept. 2011， Langkawi， 2011：168-173. doi： 10.1109/ISWTA.2011.6089402.

[9] MOUSANNIF H， KHALIL I， OLARIU S. Cooperation as a service in VANET： implementation and simulation results [J]. Mobile Information Systems， 2012，8（2）： 153-172. doi： 10.3233/MIS-2012-0136.

[10] HUANG D J； HONG X Y， GERLA M. Situation-aware trust architecture for vehicular networks [J]. Communications Magazine， IEEE， 2010，48（11）：128-135. doi： 10.1109/MCOM.2010.5621979.

[11] LI Q H， ZHU S C， CAO G H. Routing in Socially Selfish Delay Tolerant Networks [C] //Proceedings of the INFOCOM， 2010 IEEE， 14-19 March 2010， San Diego， CA， 2010：1-9. doi： 10.1109/INFCOM.2010.5462138.

[12] SMALDONE S， HAN L， SHANKAR P， et al. RoadSpeak： enabling voice chat on roadways using vehicular social networks [C] //Proceedings of the 1st Workshop on Social Network Systems， 2008， New York， NY， USA： ACM， 2008：43-48. doi： 10.1145/1435497.1435505.

[13] HAN L， SMALDONE S， SHANKAR P， et al. Ad-hoc voice-based group communication [C] // Proceedings of the Pervasive Computing and Communications （PerCom）， 2010 IEEE International Conference， March 29 2010-April 2 2010， Mannheim， 2010：190-198. doi： 10.1109/PERCOM.2010.5466977.

[14] SHA W， KWAK D， NATH B， et al. 2013. Social vehicle navigation： integrating shared driving experience into vehicle navigation [C] //Proceedings of the 14th Workshop on Mobile Computing Systems and Applications （HotMobile'13）， April 2013， ACM， New York， NY， USA： ACM， 2013，17（2）：16. doi： 10.1145/2444776.2444798.

[15] HE Z， CAO J， LI T. Mice： A real-time traffic estimation based vehicular path planning solution using vanets [C] //Proceedings of the Connected Vehicles and Expo （ICCVE）， 2012 International Conference， 12-16 Dec. 2012， Beijing， China， 2012：172-178.

[16] SINGH K， LI B. Estimation of traffic densities for multi-lane roadways using a markov model approach [J]. Industrial Electronics， IEEE Transactions， 2011，（99）：1.

[17] ANDREATTA G， ROMEO L. Stochastic shortest paths with recourse [J]. Networks， 1988，18（3）. 193-204.

[18] ZHOU B， CAO J， ZENG X， et al. Adaptive traffic light control in wireless sensor network-based intelligent transportation system [C] //Proceedings of the Vehicular Technology Conference Fall （VTC 2010-Fall）， 2010 IEEE 72nd， 6-9 sept. 2010， Ottawa， 2010：1-5. doi： 10.1109/VETECF.2010.5594435.

作者簡介

何宗鍵，同濟大學軟件工程本科和計算機科學與技術碩士畢業；香港理工大學計算學系在讀博士研究生；主要研究領域為車聯網、無線傳感器網絡與移動計算；已發表論文20余篇，其中被SCI/EI檢索10余篇。

曹建農，南京大學計算機科學系本科畢業、美國華盛頓州立大學計算機碩士和博士畢業；香港理工大學計算學系教授、博士生導師、系主任，網絡和移動通信實驗室主任；主要研究領域為計算機網絡、移動和普適計算、并行和分布式計算、容錯和中間件等；承擔并完成20余項科研項目；已發表論文300余篇，其中SCI收錄85篇，EI收錄232篇。

鄭俊浩，杭州電子科技大學計算機科學與技術專業本科畢業；香港理工大學計算學系在讀碩士研究生；主要研究方向是車聯網，特別是基于車聯社交網絡的應用。

[13] HAN L， SMALDONE S， SHANKAR P， et al. Ad-hoc voice-based group communication [C] // Proceedings of the Pervasive Computing and Communications （PerCom）， 2010 IEEE International Conference， March 29 2010-April 2 2010， Mannheim， 2010：190-198. doi： 10.1109/PERCOM.2010.5466977.

[14] SHA W， KWAK D， NATH B， et al. 2013. Social vehicle navigation： integrating shared driving experience into vehicle navigation [C] //Proceedings of the 14th Workshop on Mobile Computing Systems and Applications （HotMobile'13）， April 2013， ACM， New York， NY， USA： ACM， 2013，17（2）：16. doi： 10.1145/2444776.2444798.

[15] HE Z， CAO J， LI T. Mice： A real-time traffic estimation based vehicular path planning solution using vanets [C] //Proceedings of the Connected Vehicles and Expo （ICCVE）， 2012 International Conference， 12-16 Dec. 2012， Beijing， China， 2012：172-178.

[16] SINGH K， LI B. Estimation of traffic densities for multi-lane roadways using a markov model approach [J]. Industrial Electronics， IEEE Transactions， 2011，（99）：1.

[17] ANDREATTA G， ROMEO L. Stochastic shortest paths with recourse [J]. Networks， 1988，18（3）. 193-204.

[18] ZHOU B， CAO J， ZENG X， et al. Adaptive traffic light control in wireless sensor network-based intelligent transportation system [C] //Proceedings of the Vehicular Technology Conference Fall （VTC 2010-Fall）， 2010 IEEE 72nd， 6-9 sept. 2010， Ottawa， 2010：1-5. doi： 10.1109/VETECF.2010.5594435.

作者簡介

何宗鍵，同濟大學軟件工程本科和計算機科學與技術碩士畢業；香港理工大學計算學系在讀博士研究生；主要研究領域為車聯網、無線傳感器網絡與移動計算；已發表論文20余篇，其中被SCI/EI檢索10余篇。

曹建農，南京大學計算機科學系本科畢業、美國華盛頓州立大學計算機碩士和博士畢業；香港理工大學計算學系教授、博士生導師、系主任，網絡和移動通信實驗室主任；主要研究領域為計算機網絡、移動和普適計算、并行和分布式計算、容錯和中間件等；承擔并完成20余項科研項目；已發表論文300余篇，其中SCI收錄85篇，EI收錄232篇。

鄭俊浩，杭州電子科技大學計算機科學與技術專業本科畢業；香港理工大學計算學系在讀碩士研究生；主要研究方向是車聯網，特別是基于車聯社交網絡的應用。

[13] HAN L， SMALDONE S， SHANKAR P， et al. Ad-hoc voice-based group communication [C] // Proceedings of the Pervasive Computing and Communications （PerCom）， 2010 IEEE International Conference， March 29 2010-April 2 2010， Mannheim， 2010：190-198. doi： 10.1109/PERCOM.2010.5466977.

[14] SHA W， KWAK D， NATH B， et al. 2013. Social vehicle navigation： integrating shared driving experience into vehicle navigation [C] //Proceedings of the 14th Workshop on Mobile Computing Systems and Applications （HotMobile'13）， April 2013， ACM， New York， NY， USA： ACM， 2013，17（2）：16. doi： 10.1145/2444776.2444798.

[15] HE Z， CAO J， LI T. Mice： A real-time traffic estimation based vehicular path planning solution using vanets [C] //Proceedings of the Connected Vehicles and Expo （ICCVE）， 2012 International Conference， 12-16 Dec. 2012， Beijing， China， 2012：172-178.

[16] SINGH K， LI B. Estimation of traffic densities for multi-lane roadways using a markov model approach [J]. Industrial Electronics， IEEE Transactions， 2011，（99）：1.

[17] ANDREATTA G， ROMEO L. Stochastic shortest paths with recourse [J]. Networks， 1988，18（3）. 193-204.

[18] ZHOU B， CAO J， ZENG X， et al. Adaptive traffic light control in wireless sensor network-based intelligent transportation system [C] //Proceedings of the Vehicular Technology Conference Fall （VTC 2010-Fall）， 2010 IEEE 72nd， 6-9 sept. 2010， Ottawa， 2010：1-5. doi： 10.1109/VETECF.2010.5594435.

作者簡介

何宗鍵，同濟大學軟件工程本科和計算機科學與技術碩士畢業；香港理工大學計算學系在讀博士研究生；主要研究領域為車聯網、無線傳感器網絡與移動計算；已發表論文20余篇，其中被SCI/EI檢索10余篇。

曹建農，南京大學計算機科學系本科畢業、美國華盛頓州立大學計算機碩士和博士畢業；香港理工大學計算學系教授、博士生導師、系主任，網絡和移動通信實驗室主任；主要研究領域為計算機網絡、移動和普適計算、并行和分布式計算、容錯和中間件等；承擔并完成20余項科研項目；已發表論文300余篇，其中SCI收錄85篇，EI收錄232篇。

鄭俊浩，杭州電子科技大學計算機科學與技術專業本科畢業；香港理工大學計算學系在讀碩士研究生；主要研究方向是車聯網，特別是基于車聯社交網絡的應用。