基于機會網絡中移動人群感應的鄰居協作機制?

萬 辛

（天津市國瑞數碼安全系統股份有限公司 天津 100101）

基于機會網絡中移動人群感應的鄰居協作機制?

萬 辛

（天津市國瑞數碼安全系統股份有限公司 天津 100101）

數據采集是新興移動傳感系統的一個基本的構建塊，來自于許多的移動設備。在論文中，我們提出了通過機會網絡的一個有效的信息擴散協議傳感器數據采集。所提出的方法是檢測行人群，基于在所檢測到的組成員之間的節點和維護本地網絡（即一個集群）之間無線連接的歷史。通過協同執行集群成員的鄰居發現和鏈路管理，它提高了鄰居發現的能源效率，最大限度地減少了信息傳遞延遲。仿真結果表明，該方法可以提高信息傳遞性能將近16%～83%以及等效接觸探測間隔。

數據采集；機會網絡；檢測；信息傳遞；集群

1 引言

移動傳感技術使一些創新的應用和服務快速進步。通過在移動設備（例如，智能手機）從內置的傳感器收集測量數據，我們可以認識到在沒有密集部署傳感基礎設施的環境中目前的情況和群體行為［1～2］。我們需要一個可擴展的平臺，提供這樣的移動傳感應用，收集一些移動設備到網絡服務器的傳感器數據。大多數現有的移動傳感系統呈現每個節點的傳感器數據通過蜂窩網絡上傳。然而，除了他們移動設備的電池消耗，伴隨著數據上傳這種方法需要用戶支付的3G通信費用。再以物質刺激鼓勵人們加入服務，這會不會是許多參與感知場景的最佳解決方案。現在，公共信息科技與產業基礎設施，如免費的Wi-Fi熱點被廣泛提供在城市地區（例如，在火車站和購物中心），對于移動傳感系統的數據收集，機會網絡將提供一個替代的解決方案：每個節點暫時存儲傳感器數據在本地存儲器上，當周圍的Wi-Fi熱點出現的時候再上傳到服務器上。雖然這可能會產生數據收集的一些額外的延遲，但它會降低用戶的門檻及參與感知服務。

這種方法的一個潛在的問題是因為無線接入點，如Wi-Fi熱點通常部署稀疏，數據上傳的機會是有限的。為了有效地增加上傳的機會以及減輕數據收集延遲，傳感器數據也在移動設備之間共享。通過短程無線通信相鄰節點之間共享本地傳感器數據，然后伺機將收集到的數據通過3G和Wi-Fi網絡上傳到服務器，數據收集的效率將會大幅度提高（圖1）。為了在許多的移動設備中交換傳感器數據，我們需要解決以下的問題：第一個問題是移動設備的信息傳遞延遲和能量消耗之間的權衡。在人們頻繁移動的情況下，節點之間的接觸時間往往是短暫的，往往在幾十秒內。在每個節點應該頻繁進行鄰居發現，以檢測這樣的短暫接觸而減少數據收集延遲，它通常所帶來的是嚴重的能量消耗。第二個問題是對節點密度的魯棒性。在無線連接的協議如Wi-Fi的點對點（ad-hoc）模式，數據包的接收概率通常會由于信息包的頻繁碰撞并伴隨著節點密度的增加而下降。在這個意義上說，面向連接的協議，如藍牙將更適合我們的情況。另一方面，他們經常有一個節點可以保持的通信鏈路數量的限制。當相鄰節點的數量遠大于最大程度時，節點需要反復建立和斷開通信鏈路及時向鄰居交換傳感器數據。因此，鏈路建立的開銷將是不可忽略的，從而可能會降低帶寬利用率。大多數現有的路由協議的機會網絡通常假設理想的通信，并沒有考慮較低層的網絡問題。

圖1 系統結構

在本文中，在機會網絡下移動設備之間共享傳感器數據，我們提出了一個高效節能的信息擴散協議。在擁擠的情況下，像一個活動場所和購物中心，人們自然形成群體進行移動（例如，朋友，家庭或陌生人只是移動到同一目的地）。該方法檢測這樣的行人組基于無線連接節點和維護本地網絡（即集群）小組成員之間的歷史。通過協同進行集群成員的鄰居發現和鏈路管理，加強了鄰居發現與節點的約束處理的能源效率。通過仿真實驗使用一個模擬器［3］，我們比較所提出的方法與非協作的方法的性能，所有的節點隨機的時間間隔重復鄰居發現和發送連接請求到所有檢測到的鄰居。結果表明，該方法可以提高信息傳遞性能的16%-83%結果表明，該方法可以提高信息傳遞性能的16%-83%等效接觸探測間隔。

2 機會網中的集群

2.1 機會網絡中移動點對點網絡的動態集群

在一個斷斷續續連接的移動點對點網絡中或機會網絡進行高效的信息傳遞，以及對一些路由協議研究。最直接的方法是路由協議［4］，當節點在其通信范圍內其中一個節點在其本地存儲復制所有信息。雖然它可以實現最小的信息傳遞延遲，在沒有任何信息之前，它通常會產生過多的冗余信息交換。許多工廠已經擴展了路由協議以應對這個問題，通過預測每個鄰居在未來遇到指定節點的概率［5］。基于接觸概率，發送者為每個鄰居減少冗余信息傳輸做出復制的決定。由于數據包很少發生碰撞，上述路由協議基本呈現的是一個稀疏的網絡。另一方面，為了適用于這樣的路由機制為移動人群感應傳感器數據擴散，節點頻繁的通訊移動這將是必不可少的，以最小的能量開銷和實現更高的節點密度的魯棒性。該方法作為路由協議和藍牙的MAC/PHY層之間的中間件，彌合這些差距通過機會網絡移動實現了人群感應使得傳感器數據擴散更高效。

2.2 鄰居發現的高效節能及其接觸探測

鄰居發現（或接觸探測）一直被認為在機會網中是一個有效的信息傳遞的基本構建塊。制定接觸探測任務使用補充的理論，由于探測是在瞬間完成的，證明了不斷探測間隔提供一個最佳的鄰居發現可能性。發現通過基于檢測到的鄰居數量進而動態調整探測間隔以達到高效節能的鄰居發現［7］。這兩種方法都集中在優化探測間隔，以避免時間冗余，假設每個節點進行獨立的接觸探測。另一方面，該方法協同執行集群成員之間的接觸探測以減少空間冗余，在每一輪，只有少量的集群中的節點執行鄰居發現和檢測結果與其他成員分享。由于集群成員相互接近時，可以實現合理的鄰居檢測率與降低探測頻率。因此，所提出的協同接觸探測機制是現有的優化方法，使接觸探測的效率可以進一步提高，基于時間優化策略調整每個集群的探測間隔［6～7］。

在本文中，我們假設人們在一些公共空間（如一個購物中心）移動設備配備點對點通信能力（即移動節點或節點）。認識到群眾行為和周圍的情況下，傳感器數據在每個節點上不斷收集和共享其他節點，依賴于應用程序的預處理后的環境。無線訪問點（如，Wi-Fi熱點）在環境中稀疏部署以便收集傳感器數據，當移動節點到訪問點周圍數據則上傳到一個網絡服務器。如果用戶允許這樣做，節點也可以通過蜂窩網絡直接上傳數據到服務器。我們還假設信息的大小比無線網絡帶寬足夠小。每個節點有足夠大的緩沖區空間，因此緩沖區溢出從未發生。

該方法檢測行人組基于節點之間無線連接最近的歷史。然后在檢測組成員之間為本地合作形成一個集群。每個集群有一個特殊的節點稱為集群頭（CH），在集群內部通信它需要對集群維護和控制。這里我們考慮CH及其集群的情況。該方法假設所有集群成員滿足以下條件：

因此節點ui需要保持連通性，隨著CHu0超過T秒加入集群。T的臨界值應該大于預期接觸時間為獨立移動的節點，可以通過模擬估計或通過分析歷史軌跡數據。除非另外注明，在本文中我們假設T=60秒。注意，在我們的模擬中，在不同組之間節點接觸小于臨界值88%，最初，每個單個成員節點形成的集群本身需要CH。后來，CH定期執行接觸探測并更新成員組的集群，這樣所有的成員，滿足式（1）。

在集群內部網絡集群成員一直保持連接。所有傳感器數據收集的成員直接共享集群內部通信鏈接中集群的其他節點。當通過鄰居發現節點在不同的集群中檢測，在集群之間檢測到的節點建立臨時通信鏈路與鄰居交換信息（即傳感器數據）。而建立的鏈接通常是伴隨著幾秒鐘開銷，信息交換本身可以在很短的時間內完成，因為信息的大小遠小于通信帶寬。因此，在該方法中，集群成員協作管理集群內部鏈接，最多一個通信鏈路建立相鄰之間的集群。由于傳感器數據立即在集群成員之間共享，在集群中數據維護可以通過一個通信鏈路被轉移到鄰近的集群中的所有節點。因此該方法減輕了信息傳遞延遲造成的約束程度和鏈接的開銷建立通過聚集集群內部信息交換進入少量的通信鏈接中。

此外，集群成員在空間上是近距離的，因此他們的鄰居集將會彼此相似。基于這一特性，CH隨機選擇少量的集群成員（稱為發現者）在每一輪讓他們完成鄰居發現。這有效地降低接觸探測能源消耗的平均頻率，同時保持合理的接觸檢測能力。

因此該方法減輕了能源消耗和信息傳遞延遲造成的約束程度通過形成一個集群節點移動作為一個群體和協作執行接觸探測，鏈接管理和信息交換跟集群成員。

一個節點ui執行的鄰居發現，它迅速切無線電頻率和多次傳遞查詢信息。因此，ui很難響應來自相鄰節點的查詢在其鄰居發現的過程中。因此每個鄰居的探測概率uj取決于其處于非發現狀態和ui本身的發現過程的持續時間（即有效掃描時間）。鄰居探測概率隨Tc有效的掃描時間增加，并且當Tc=5.12s時其可達到99%［10］。盡管頻繁接觸探測需要檢測短接觸，同時也會使鄰居發現相鄰節點之間失去聯系。此外，大量的電池在發現過程中不斷消耗。上一節中提到的，該方法處理問題通過選擇少量的發現者和集群成員之間分享他們的檢測結果。發現從鄰近的集群可以有效地提高能源效率和響應能力。上面的概率可以被定義為

在這里，只有n為集群成員（即發現者）完成鄰居發現。假設未發現者ui和每個集群成員之間的距離是一個概率分布 f(r)，一個鄰居的ui的概率，假設u被發現是由一個發現者uj的集群得到的：

我 們 假 設 ri1≤ri2≤…≤rin顯 然 ，概 率P(Xi1Xi2… Xin)滿足以下條件：

既然u1在ui中是最近的發現者，設置F(r)=f(r) dr從ui到發現者的累積分布。累積分布函數的距離在ui和u1之間是由：

通過F1()

r，我們獲得ri1的概率密度函數：

基于（3）、（4）和（6），我們得到：

檢查接觸檢測率的發現者，我們通過式（7）推導出P(Xi1Xi2… Xin)的下限。為分析，我們假設集群成員之間的距離是（0，rmax）之間的均勻分布，在rmax是在5～20m之間的變化。基于藍牙的典型的通信范圍無線傳輸范圍R設置為10m。圖2顯示了一個鄰近的非發現者的概率下界是發現在集群中至少有一個發現者，發現者的數量是不同的。當集群成員之間的最大距離是5m，鄰近的非發現者可以被發現概率為84%，集群中只有一個成員那就是發現者。因此，通過限制集群中發現者的數量，我們可以有效地減少平均接觸探測頻率，同時保持合理的接觸檢測率。

圖2 鄰居探測概率

最初，每個節點形成一個尺寸為1的集群。然后每個集群獨立重復以下三個階段為了集群維護和信息交換。

1）集群維護：CH執行鄰居發現獲得當前的鄰居集（圖3（a））。與此同時，其他節點在未發現狀態應對CH的查詢，然后CH更新集群的成員基于收集到的連接信息。

2）聯系調查：CH從集群成員（CH本身除外）中隨機選擇（n-1）個發現者。然后選中的成員執行鄰居發現與鄰近的集群接觸檢測（圖3（b））。

3）信息交換：CH和發現者與鄰近的集群中的節點建立通信鏈接交換傳感器數據保持在每個集群（圖3（c））。從鄰近的集群接受連接請求，信息交換后立即斷開集群內部鏈接。最后，得到了傳感器數據通過集群內部通信鏈接共享到集群成員。

每一輪的總持續時間（三個階段組成）是隨機由CH決定的。注意，如果集群只有一個節點，階段2）和階段3）則省略。在這種情況下，CH在未發現的狀態，直到下一輪的開始。

圖3 協議設計

3 仿真實驗

評價該方法的性能，我們使用一個模擬器進行了仿真實驗［3］。我們假設100個移動節點繞著50米*50米的區域來回轉，形成10節點的組：我們形成10個參考點代表一組的平均行為。參考點遵循隨機路徑移動模型和獨立的移動領域。每一次移動，參考點隨機選擇一個目的地，路徑是以恒定速度從其領域到達目的地。移動速度也決定隨機區間0.5 m/s～1.5 m/s。到達路徑目的地后，參考點停止長達120s，然后朝著下一個目的地移動。參考點確定一個新的目的地時，相應的小組成員同時挑選自己的目的地，在3m內的參考點。因此我們模擬移動節點基于分組的移動性。

每10s，每個節點生成一個2kb的信息（即傳感器數據）和其朝著環境中所有節點的路由協議擴散。我們假設信息傳遞的最后期限是60s和定義的信息傳遞率是通過達到最后期限內的節點信息的百分比。假設藍牙v2.1+EDR，無線通信的范圍和速度分別設置為10m和2mbps。每個集群執行隨機接觸探測間隔Tinq±5.12s，和鄰居發現的持續時間是5.12s。Tinq是一個調整每個集群接觸探測的平均間隔參數。默認情況下，我們設置Tinq為15.36s。在仿真實驗中，我們確定鄰居探測概率基于［10］的理論模型和限制通信鏈路節點最大數量，每個節點一直到7。此外，我們假設一個2s的開銷為建立鏈接。仿真結果：

聯系檢測率：圖4顯示了接觸持續時間和接觸檢測率之間的關系。由于一個節點難探測到正在執行鄰居發現在同一時間的鄰居，即使隨著Naive所有節點經常重復鄰居發現，一些接觸還是被錯過。關于該方法，接觸探測的空間覆蓋將略低于Naive，因為它限制了發現者的數量減輕了能源消耗。另一方面，它也減少了同時存在鄰近的節的鄰居發現，從而發現可以探測其鄰居會有更高的概率。因此，該方法比Naive可以更有效地檢測短接觸。

圖4 接觸探測率

移動節點之間的信息擴散：我們還評估了信息擴散能力，不同的平均接觸探測間隔Tinq。圖5顯示了每個節點的平均設備發現間隔和信息傳遞率之間的關系。該方法實現了57%傳遞率，平均設備發現間隔為65秒。長的探測間隔導致錯過接觸，從而逐漸降低信息擴散能力，它仍然保持38%的傳遞率，平均探測間隔為308秒。總的來說，通過其協同接觸探測和基于集群的鏈接管理機制，該方法可以提高信息傳遞率16%～83%。

圖5 信息傳遞率

3）服務器的數據收集：最后，我們評估服務器的信息收集延遲，假設在每個集群成員上傳通過3 g網絡接收到的信息。圖6和圖7分別顯示延遲時間的概率分布和集群通過實驗的數量。最初，每個節點形成一個單節點集群，集群的數量是100。之后，集群逐漸增長通過合并相鄰的集群，并最終集群的數量聚集在10～20之間。由于每個節點傳感器收集的數據立即與其他集群成員共享，在5秒之內87%以上的信息達到服務器。考慮到集群的平均數量在整個模擬期間為14.3，與集中式蜂窩式架構相比，有效地減少了86%的通信鏈路的數量，同時保持一個合理的數據采集的性能。因此當地的移動節點之間的信息交換，有效地提高移動傳感系統的可伸縮性。

圖6 信息傳遞延遲

圖7 集群的數量

4 結語

在本文中，我們提出了一種高效信息擴散協議的移動人群的機會網絡傳感。該方法檢測行人組形成集群，在節點執行鏈接管理和接觸探測下的協作方式。仿真結果表明，該方法可以提高信息傳遞率16%～83%與等效的接觸探測間隔。

［1］J.Weppner，P.Lukowicz.Bluetooth based collaborative crowd density estimation with mobile phones［C］//in Proc.PerCom'13，2013：193-200.

［2］L.-Y.Wei，Y.Zheng，W.-C.Peng.Constructing popular routes from uncertain trajectories［C］//in Proc.KDD'12，2012：195-203.

［3］A.Ker¨anen，J.Ott，T.K¨arkk¨ainen.The ONE Simulator for DTN Protocol Evaluation［C］//in Proc.SIMUTools'09，2009.

［4］A.Vahdat，D.Becker.Epidemic routing for partially-connected ad hoc networks［C］//Tech.Rep.，2000.

［5］J.Burgess，B.Gallagher，D.Jensen，B.Levine.Max-Prop：Routing for vehicle-based disruption-tolerant net-works［C］//in Proc.INFOCOM'06，2006：1-11.

［6］W.Wang，V.Srinivasan，M.Motani.Adaptive contact probing mechanisms for delay tolerant applications［C］//in Proc.MobiCom'07，2007：230-241.

［7］B.Han，A.Srinivasan.eDiscovery：Energy eff i cient device discovery for mobile opportunistic communications［C］//in Proc.ICNP'12，2012：1-10.

［8］P.Basu，N.Khan，T.Little.A mobility based metric for clustering in mobile ad hoc networks［C］//in Proc.ICDCS Workshop，2001：413-418.

［9］C.Konstantopoulos，D.Gavalas，G.Pantziou.Clustering in mobile ad hoc networks through neighborhood stability-based mobility prediction［J］.Comput.Netw.，2008，52（9）：1797-1824.

［10］B.Peterson，R.Baldwin，J.Kharoufeh.Bluetooth inquiry time characterization and selection［J］.IEEE Transactions on Mobile Computing，2006，5（9）：1173-1187.

［11］G.Zaruba，S.Basagni，I.Chlamtac.Bluetrees-scatternet formation to enable bluetooth-based ad hoc networks［C］//in Proc.ICC'01，vol.1，2001：273-277.

A Neighbor Collaboration Mechanism for Mobile Crowd Sensing in Opportunistic Networks

WAN Xin
（Tianjin Guorui Digital Security System Co.，Ltd，Tianjin 100101）

Data collection from a crowd of mobile devices is anessential building block of emerging mobile sensing systems.In this paper，we propose an efficient information diffusion protocolfor sensor data collection via an opportunistic network.The proposed method detects groups of pedestrians based on the history of radio connectivity between the nodes and maintains a local network（i.e.，a cluster）among the detected group members.By collaboratively performing neighbor discovery and link management with the cluster members，it enhances energy-efficiency of the neighbor discovery and minimizes the information deliverydelay.Simulation results show that the proposed method canimprove the message delivery performance by 16%-83%with equivalent contact probing intervals.

data collection，opportunistic network，detects，information delivery，cluster

TP393

10.3969/j.issn.1672-9722.2017.10.023

Class Number TP393

2017年4月12日，

2017年5月19日

萬辛，男，博士研究生，工程師，研究方向：通信網絡及網絡安全。