機會群智感知網絡關鍵技術

熊永平　劉偉　劉卓華

摘要：認為機會群智感知網絡能夠充分利用移動終端在城市中分布密度高、相遇頻繁以及作為移動終端攜帶者的人具有社會屬性等特點，并利用移動終端之間的協作機會，從而實現了數據感知應用。提出了基于機會通信的機會群智感知網絡的概念，并提出了機會群智感知網絡的主要關鍵技術：大范圍數據收集的機會傳輸技術、特定時空區(qū)域的數據分發(fā)技術、異步通信機會發(fā)現和人群真實移動行為建模等。同時，針對各關鍵技術提出了解決思路和技術路線。

關鍵詞： 群智感知；機會網絡；機會傳輸

群智感知[1-2]就是在移動感知設備普遍存在的背景下提出的物聯網新型感知模式。與傳統有意識部署的固定無線傳感網不同，它是將眾包的思想與移動感知相結合，將普通用戶的移動設備作為基本感知單元，并通過網絡進行有意識或無意識的協作，形成群智感知網絡，實現感知任務分發(fā)與感知數據收集，從而完成大規(guī)模的、復雜的社會感知任務。而這些任務僅依靠個體很難實現，例如，在交通擁堵狀況和城市空氣質量監(jiān)測應用中，只有當大量的個體提供行駛速度或空氣質量信息才有應用價值。

近年來，其他一些國家已經涌現出大量群智感知技術的應用和研究，包括收集交通路況的CarTel，收集空氣質量和污染物的CommonSense，收集城市噪聲信息的NoiseSPY，收集騎車人的運動軌跡和身體狀況的BikeNet等。然而當前的群智感知研究主要針對基于基礎設施網絡的集中式感知系統[3]。該系統中的移動設備一般預設通過蜂窩網絡與互聯網連接，并將當前設備采集的感知數據傳輸到數據中心。城市感知應用往往都需要持續(xù)收集大量的數據，甚至可能是大規(guī)模多媒體數據。這一方面將耗費用戶較多的網絡流量和電量，導致收集成本高，降低用戶參與熱情影響系統可用性；另一方面也給蜂窩網絡帶來較大的負載壓力。

考慮到移動終端在城市中分布密度高，相遇頻繁，以及作為移動終端攜帶者的人具有社會屬性等特點，集中式的群智感知網絡結構并未充分利用移動終端之間的協作機會。當前的移動終端基本都具備了短距離無線通信技術如BlueTooth或Wi-Fi，當設備進入彼此通信范圍時，可以利用短距離無線技術交換數據，即支持機會計算模式[4]。如圖1所示，隨著設備的持續(xù)移動，數據在多個移動設備之間中繼傳輸，直到將數據傳輸到具有意愿上傳的用戶，例如電池容量高且具備低成本互聯網鏈路（例如包月流量很大或Wi-Fi接入）的設備，進而上報到后端數據中心。

機會群智感知網絡是由人攜帶的移動設備協作形成的移動機會網絡[5]，移動設備的持有者隨機地到達各個地方，隨時隨地進行感知，所產生的數據利用人移動所帶來的通信機會多次轉發(fā)后實現感知數據的傳輸，以完成感知任務。由于人群移動的自主性和隨機性，很難存在端到端連通路徑，機會群智感知網絡采用“存儲-攜帶-轉發(fā)”工作模式，當節(jié)點收到來自上一跳節(jié)點轉發(fā)的數據后，攜帶該數據并等待下一跳轉發(fā)機會的到來。利用這種模式，用戶可以以很低的成本傳輸感知數據并參與感知任務，有利于推進群智感知應用的實用化。

機會網絡領域作為近年來學術界關注的熱點，已經產生了大量的研究成果。面向群智感知的機會網絡和一般移動機會網絡有著一些共同的問題，但也面臨著不同的挑戰(zhàn)。例如當前研究的機會路由要求每個節(jié)點具有全局統一標識，側重研究從數據源節(jié)點如何路由數據到目的節(jié)點；而在機會群智感知網絡中，源感知設備需要將數據通過機會轉發(fā)到具有合適互聯網鏈路的設備，進而上報到后端應用，可能并不知道目標設備的節(jié)點標識。又如群智感知系統采集實時擁堵信息，是一類具有時空特性的數據應用，這類數據生命周期短，且只對擁堵點周圍區(qū)域的設備有效，與大范圍長期收集的公共數據不同。因此并不需要傳輸到數據中心，只需要將數據持續(xù)分發(fā)給一個目標區(qū)域內的用戶。因此我們提出了機會群智感知網絡的幾項關鍵技術。

1 面向大范圍感知數據收集

的機會傳輸

群智感知最主流的應用是低成本、大范圍、持續(xù)收集感知數據，感知數據以機會轉發(fā)的方式通過節(jié)點間協作在多個移動節(jié)點之間逐跳傳輸，直到到達具有互聯網鏈路的節(jié)點，進而將數據傳輸到后臺的數據中心。這與普通移動機會網絡的機會路由不同，感知節(jié)點并不知道感知數據消息的目標節(jié)點，機會傳輸的目的可以是任意一個或多個Sink節(jié)點。一方面根據不同的應用，感知數據收集需要滿足采樣頻率、覆蓋范圍和收集延遲等指標要求；另一方面數據在移動節(jié)點之間協作傳輸需要耗費節(jié)點的能量和計算能力，在Sink節(jié)點則需要耗費運營商提供的付費網絡帶寬。大多數群智感知任務都是公共服務，參與任務對用戶的直接激勵收益不明顯，較高的傳輸代價將影響參與感知任務的用戶積極性，進而降低感知網絡的覆蓋范圍和可用性。

機會網絡中的數據路由傳輸在機會網絡研究中已經出現了豐富的成果[5]，機會路由機制涉及兩個方面：（1）消息的復制份數。由于網絡拓撲動態(tài)變化帶來的傳輸不可靠，采用多拷貝能夠增加傳輸成功率。機會路由的兩個極端方法分別是單拷貝直接傳輸和每個相遇節(jié)點一份拷貝的流行性路由機制，過多的冗余拷貝會降低網絡資源利用率，需要消除；（2）下一跳選擇策略，即判斷相遇節(jié)點是否為下一跳轉發(fā)節(jié)點。獲取網絡狀態(tài)信息越多，就越有利于選擇策略的優(yōu)化。

機會群智感知網絡中的機會傳輸機制則需要考慮感知數據機會傳輸過程的相關性能指標，包括互聯網鏈路傳輸成本、傳輸延時和能耗、傳輸成功率、數據量等。大部分移動終端都有成本不等的互聯網鏈路，相當于Sink節(jié)點。在感知數據收集應用的機會網絡中，感知數據只要傳輸到有意愿提供互聯網鏈路的任意一個移動節(jié)點Sink，就可以將數據上傳到數據中心。因此如果將所有可能的Sink節(jié)點看成一個組，該過程則可以建成一個Anycast模型。

由于機會網絡的間歇性連通和節(jié)點移動帶來的拓撲結構動態(tài)變化，節(jié)點無法及時獲取網絡拓撲來計算到Anycast組節(jié)點的跳數距離。可以采用與每個組成員節(jié)點的相遇概率來表示節(jié)點與該組節(jié)點的距離，該概率可通過綜合考慮節(jié)點與組成員節(jié)點的相遇頻率、相遇持續(xù)時間以及節(jié)點間的相遇傳遞性來計算。此外，由于網絡中有多個消息需要傳輸，為了降低網絡的開銷，消息以固定K個拷貝方式轉發(fā)。在大規(guī)模的機會網絡中，可能無法知道所有Anycast組節(jié)點的相關信息，僅考慮相遇概率最大的N個節(jié)點。

我們提出以下幾種Anycast傳輸方法：

（1）基本方法。這種方法是以節(jié)點最大的相遇概率為判別標準，通過記錄節(jié)點到每一個組成員節(jié)點的相遇概率，同時記錄相遇概率最大的組成員個數來決定將消息轉發(fā)給哪個相遇節(jié)點。攜帶消息的節(jié)點如果遇到判別標準比它大的節(jié)點，就選擇該節(jié)點為下一跳轉發(fā)節(jié)點。這種方法符合Anycast組傳輸的基本思路，發(fā)送消息給最近的組成員節(jié)點。

（2）考慮組節(jié)點分布的方法。這種方法需要綜合考慮與所有組成員節(jié)點的相遇概率，判別標準為相遇概率平均值。當與各個組節(jié)點的相遇概率相差不大時，該方法將消息轉發(fā)到與更多成員節(jié)點相遇的節(jié)點。

（3）自適應的Anycast方法。這種方法采用類似勢場的概念，把每個組成員看成一個場源電荷，每個節(jié)點的電勢值與到該組節(jié)點的距離成反比。模擬電場如圖2所示，假設組成員節(jié)點i在網絡中形成一個勢場，該勢場在節(jié)點[a]上的勢值計算公式為：[Ca（i）-λ（λ>0）]，其中[Ca（i）]是上一小節(jié)中定義的節(jié)點間的相對距離，而[λ]是勢值下降速度。圖2展示了6個成員節(jié)點的Anycast組在網絡中形成的勢場圖，X和Y軸是地理位置坐標，Z軸是勢值，可以看出：[λ]越大，節(jié)點到組成員節(jié)點的距離對電勢值影響越大，單個組成員節(jié)點形成的勢場下降越快；隨著[λ]值的減小，距離對勢值的影響越來越小，而組成員密度對勢值影響越來越大，即組成員節(jié)點越密集的區(qū)域勢值越大。

2 面向時空局部有效感知

數據的機會分發(fā)

機會群智感知網絡的另一類重要應用是面向時空局部有效數據。例如，在某一地理區(qū)域內的道路擁堵或交通事故信息、銀行等公共服務點排隊信息、商場的臨時促銷信息等，這類信息具有時空局部有效性，傳播的距離越遠，經過的時間越長，這類信息的有效性就越低。同時，用戶需求也具有這種時空特性，用戶移動到某個區(qū)域，更為關注當前區(qū)域附近的信息，對以前的信息和更遠區(qū)域的信息可能不感興趣。網絡中的節(jié)點在感知到當前區(qū)域中的信息后，利用機會相遇將數據擴散到周邊節(jié)點上，并在信息有效空間區(qū)域內的節(jié)點間進行協作擴散，以分發(fā)給目標區(qū)域上感興趣的移動節(jié)點。

機會群智感知網絡技術中最關鍵的是感知數據機會傳播模型。時空局部有效的感知數據應該在一個相對受限的空間范圍內傳播。由于移動感知設備的自主隨機移動，很難建立感知數據在多次轉發(fā)后的傳播模型。該傳播模型主要和感知數據的動態(tài)擴散算法有關，感知數據限制在有效區(qū)域內擴散，因此人們需要研究根據給定的感知數據的傳播延時、應用特性、區(qū)域節(jié)點密度以及網絡負載等多種因素，以動態(tài)調整目標數據消息的轉發(fā)策略和拷貝份數。

設計一個高效的數據分發(fā)機制，首先需要確定消息分發(fā)需求，并從典型應用出發(fā)，歸納具有時空特性消息的分發(fā)需求，包括消息的空間范圍、分布密度和延遲以及各種消息的優(yōu)先級等；其次需要詳細分析影響消息分發(fā)機制性能的諸多因素及其之間的關系，如進入空間區(qū)域內移動節(jié)點數目、分布和移動模型，移動節(jié)點的緩存和通信帶寬等網絡資源以及消息的個數、類型、優(yōu)先級和消息源的分布等；最后確定通信方式，針對單個節(jié)點移動軌跡的覆蓋范圍有限和機會網絡間歇性連通的特點，可以在所遇到的節(jié)點中選擇部分節(jié)點擴散消息，實現在非連通區(qū)域消息分發(fā)，維護消息在分發(fā)區(qū)域的密度。

假定在每個攜帶節(jié)點上維護一個節(jié)點狀態(tài)值，則需要記錄當前節(jié)點連續(xù)相遇的、沒有攜帶感知數據的節(jié)點個數。當該節(jié)點連續(xù)遇到M個未攜帶數據消息的節(jié)點，將生成一個感知數據的拷貝并傳輸給第M個相遇的節(jié)點，并使之成為一個新的攜帶節(jié)點，然后將該狀態(tài)值重置為0。此外，當攜帶節(jié)點遇到任一個攜帶感知數據的節(jié)點都將狀態(tài)值重置為0。每個節(jié)點的狀態(tài)變化可以用一個Markov過程來刻畫，節(jié)點遇到一個攜帶數據的節(jié)點是概率ρ，遇到未攜帶數據的節(jié)點概率是1-ρ，則變化過程可用如圖3所示。

該Markov過程對應的轉移概率矩陣表示如式（1）所示：

該過程可以計算出節(jié)點處于M-1狀態(tài)的概率，還可以估算出攜帶消息的節(jié)點出現的速率。由于攜帶節(jié)點自主移動會不斷離開目標區(qū)域，離開速率需要根據節(jié)點移動速度、區(qū)域面積和移動模型等參數計算。當攜帶節(jié)點生成速率等于其離開速率時，可以計算出當前的算法參數值M，所有節(jié)點也可以根據當前觀察到的節(jié)點移動速率和個數動態(tài)計算M值，從而實現感知數據攜帶節(jié)點密度的穩(wěn)態(tài)分布。

3 異步通信機會發(fā)現

機會群智感知網絡節(jié)點采用短距離通信技術交換數據。探測發(fā)現通信范圍內的鄰居節(jié)點是實現感知數據機會傳輸的前提條件，對數據傳輸性能有非常重要的影響。在網絡運行過程中，感知節(jié)點之間沒有全局同步時鐘，只能異步進行鄰居探測。由于節(jié)點的隨機移動性以及區(qū)域稀疏性，節(jié)點通常無法獲知其他節(jié)點的運動狀況，并且節(jié)點之間實際相遇維持時間往往較短，所以感知節(jié)點不僅需要在沒有任何其他節(jié)點的預先信息的條件下異步實現鄰居節(jié)點間的彼此探測，還需要滿足探測及時和足夠低的機會丟失率等性能要求。同時，由于移動節(jié)點能量有限，異步探測需要考慮能耗這一重要因素。為了減少節(jié)點探測機制產生的能耗，節(jié)點不可能頻繁地發(fā)出探測信息，也不能容忍長期處于監(jiān)聽狀態(tài)。

針對移動節(jié)點之間的通信機會發(fā)現，我們主要采用自適應的休眠調度方法，確保節(jié)點以高占空比降低功耗同時實現高效能。例如可以將兩個鄰居節(jié)點A和B的占空比DA和DB分別選擇為DA≈1/PA1+1/PA2和DB≈1/PB1+1/PB2（其中PA和PB分別是兩個節(jié)點的休眠周期，且滿足兩兩互素）。根據中國余數定理，必然存在周期P滿足在一個周期內節(jié)點A與節(jié)點B能夠同時喚醒。但該算法對于給定的占空比，可以選擇合適的素數對，并能夠確定能發(fā)現周圍出現的移動設備。

4 人群移動行為建模

真實人群移動特性和移動模型是機會群智感知網絡性能分析和傳輸機制設計的工作基礎。真實移動環(huán)境中的移動模型，需要綜合考慮人的物理特性和社會特性，其中物理特性是指人移動的物理規(guī)律，例如速度和方向的平滑變化等；而社會特性是指人的社會關系、行為偏好等。如何借鑒現有的移動模型方面的研究成果，并建立真實環(huán)境中的移動模型進而得到相遇機會的分布相當具有挑戰(zhàn)性。

針對城市環(huán)境中真實人群移動行為，我們提出了一個移動模型。在該模型中，在不同的時間或空間下，人的移動模型是不同的：從空間的維度來看，人在不同場景下的移動模式是不同的；從時間的維度來看，人的日常社會活動具有一定的規(guī)律性。該模型構建如下：

（1）真實移動場景建模。分析真實環(huán)境中不同類型的移動場景，例如道路、廣場和辦公室等。借鑒已有的移動模型，考慮節(jié)點的物理特性、社會關系和場景特征。可結合可用的真實trace數據，對每種特定移動場景進行建模。

（2）移動模型的構造。分析人日常社會活動的移動規(guī)律，將人在城市環(huán)境下的日常活動表示成不同場景間轉移的過程，不同場景采用相應的移動模型來描述。根據統計概率可以生成以場景為狀態(tài)的Markov過程；基于人社會活動的規(guī)律性，可以確定不同狀態(tài)間的時變轉移概率。如圖4描述了在4個場景間社會特性確定的時變轉移概率的實例。

（3）移動模型的分析。分析模型的收斂性，以及與機會群智感知網絡緊密相關的連接特性，包括節(jié)點相遇間隔、相遇持續(xù)時間等。

（4）移動模型的驗證。擬從3個方面綜合評價移動模型：對比真實trace數據，評估該移動模型是否能真實描述節(jié)點的移動性；評價模型的易用性，以及是否具有完整的數學形態(tài)表達；評價移動模型參數的可控性和適用度，是否可通過調整參數準確描述不同的移動場景。

5 結束語

智能終端正在快速普及和發(fā)展，由于終端的隨身攜帶性，利用移動終端間的協作機會實現數據感知應用在大范圍社會數據采集領域具有重要的應用潛力。文章提出了機會群智感知網絡的概念和主要關鍵技術，并提出了一些技術解決思路，具有重要的參考價值。

參考文獻

[1] 劉云浩. 群智感知計算[J].中國計算機學會通訊， 2012， 8 （10）： 38-41

[2] GANTI R K，YE F，and LEI H. Mobile Crowdsensing：Current State and Future Challenges [J].IEEE Communications Magazine， 2011， 49（11）： 32-39

[3] MA H， ZHAO D， and YUAN P. Opportunities in Mobile Crowd Sensing [J]. Communications Magazine， IEEE， 2014， 52（8）： 29-35

[4] CONTI M and KUMAR M. Opportunities in Opportunistic Computing [J]. Computer， 2010， 43 （1）： 42-50

[5] 熊永平， 孫利民， 牛建偉， 劉燕. 機會網絡[J]. 軟件學報， 2009， 20 （1）： 124-137