延遲容忍網絡中能量有效的接觸探測研究

周 歡 任 東 徐守志蔣廷耀 黃志勇

(三峽大學湖北省水電工程智能視覺監測重點實驗室 宜昌 443002)

(三峽大學計算機與信息學院 宜昌 443002)

延遲容忍網絡中能量有效的接觸探測研究

周 歡 任 東 徐守志*蔣廷耀 黃志勇

(三峽大學湖北省水電工程智能視覺監測重點實驗室 宜昌 443002)

(三峽大學計算機與信息學院 宜昌 443002)

在延遲容忍網絡中，為了發現在其通信范圍內的鄰居節點，網絡中的節點必須不斷地探測周圍的環境。這個接觸探測過程極其耗費能量。如果網絡中的節點探測太過頻繁，會耗費很多能量，且使得網絡能量的使用效率降低。另一方面，稀疏的探測可能導致節點失去和其它節點的接觸，從而錯失交換數據的機會。因此，在延遲容忍網絡中能量效率和接觸機會之間存在著一種折中的關系。為了研究這種折中關系，該文首先對基于隨機路點模型(Random Way-Point model, RWP)的接觸探測過程進行建模，得到恒定探測間隔下接觸探測概率的表達式，并且證明在所有平均探測間隔相同的策略中，以恒定間隔探測的策略是最優的。其次，基于提出的理論模型，分析不同情況下能量效率和接觸探測概率之間的折中。最后，通過仿真實驗驗證該理論模型的正確性。

延遲容忍網絡；能量效率；接觸探測；隨機路點模型

1 引言

近年來，隨著裝備有Wi-Fi 接口或者藍牙接口的無線便攜設備(如：Ipad, PDAs，智能手機等)的普及和流行，基于延遲容忍網絡(Delay Tolerant Networks, DTNs)方面的應用得到了蓬勃的發展[1]。延遲容忍網絡又稱為間歇性連通網(Intermittently Connected Networks, ICNs)，稀疏網絡(SparseNetworks)，或機會移動網絡(Opportunistic Mobile Networks, OppNets)，是無線網絡中一個新興的研究熱點[2?5]。延遲容忍網絡目前還沒有統一的定義，泛指由于節點的稀疏分布、快速移動和無線通信技術的限制等原因造成的源節點和目的節點之間不存在完整的端到端連接的一類特殊的移動自組織網。

在延遲容忍網絡中，為了實現節點之間的數據傳輸，網絡中的節點必須不斷地探測周圍的環境，從而發現在其通信范圍內的鄰居節點。顯而易見，這個接觸探測過程會消耗大量能量。一些研究者在諾基亞6600手機上做了一個實驗檢測接觸探測過程中消耗的能量，結果表明手機做一次接觸探測所需要的能量和打一次電話所需要的能量幾乎相等[6]。再者，延遲容忍網絡是一個接觸很稀疏的網絡，節點的接觸時間間隔遠遠大于節點的接觸時長；這就意味著如果網絡中的節點探測周圍的環境太頻繁，會浪費很多的能量。因此，研究如何提高接觸探測過程中能量的使用效率是一個很緊迫的問題。

目前，已經有很多研究者對接觸探測過程中的能量有效問題進行了研究[6?12]。文獻[6]給出了兩種新穎的自適應工作機制來動態地為接觸探測過程選擇合適的參數。網絡中的節點在兩個無線電之間進行切換：一種是低功率無線電，它采用一種慢發現模式去發現接觸和傳輸數據；另一種是高功率無線電，它根據節點的移動情況采用一種快的發現模式發現接觸和傳輸數據。實驗結果表明文中提出的自適應算法要比靜態的能量保持算法消耗的能量減少50%，但是相應的網絡性能卻能提高8%。文獻[7, 8]研究了延遲容忍網絡中探測間隔對于錯失一次接觸的概率的影響，并且研究了接觸錯失概率和能量消耗之間的折中。再者，通過分析真實移動數據集中節點間的接觸規律，文中提出一種自適應的接觸探測機制。基于真實移動數據集的實驗結果表明文中提出的自適應的接觸探測機制要比采用恒定的接觸探測間隔的策略消耗的能量少3倍。文獻[9]提出一種理論模型研究接觸探測對于鏈路時長的影響，以及能量消耗和吞吐量之間的折中。除此之外，該文也提供一個用于在能量有限情況下計算最優接觸探測頻率的框架，其中每個節點都根據節點相遇率去自適應地調整接觸探測頻率。針對延遲容忍移動傳感器網絡(Delay Tolerant Mobility Sensor Network, DTMSN)節點間連接探測開銷大、錯失率高的問題，文獻[11]提出一種高效的DTMSN異步探測機制。文獻[12]提出一種簡單的自適應的接觸探測機制去節省探測過程中消耗的能量，和文獻[7,8]不同，該機制需要通過GPS設備獲取節點的移動速度，并且只允許節點在靜止或者低速移動過程中發送探測包。

和現有工作不同，本文的工作側重于對基于隨機路點模型的接觸探測過程進行研究，并且提出一種理論模型去研究接觸探測過程中的能量有效問題。本文工作的創新點和主要貢獻為：(1)基于隨機路點模型，提出一種研究延遲網絡中接觸探測過程的理論模型。給出隨機路點模型中接觸時長分布的情況下，從理論上得到接觸探測概率的表達式，并且證明在所有平均探測間隔相同的策略中，以恒定間隔探測的策略是最優的。(2)基于該理論模型，得到接觸探測概率和能量消耗之間的關系，并分析不同場景下的能量效率和接觸探測概率之間的折中。(3)通過仿真實驗驗證提出的理論模型的正確性。結果表明，不同場景下的仿真實驗結果和理論結果都很接近，從而證明提出的理論模型的正確性。

2 網絡模型

這一節介紹延遲容忍網絡中和接觸探測過程相關的網絡模型。延遲容忍網絡中有多種移動模型，包括隨機路點模型[13]、隨機漫步模型(Random walk model)[14]和真實的移動軌跡(Realistic mobility trace)[15]。本文集中對基于隨機路點模型的接觸探測過程進行研究。在隨機路點模型中，考慮一種2維的正方形場景，面積為S，長和寬都為s。在移動模型中，每個節點會以相同的概率從Vmin, Vmax中選擇一個移動速度V，然后以速度V向一個選定的目標位置移動。一旦到達目標位置，節點會暫停一段時間，然后再選擇另外一個速度向另一個目標位置移動。以這種方式一直重復以上的過程。為了方便建模，假設網絡中總共有N個節點，節點的移動速度V，節點的暫停時間相同并且為0。

在延遲容忍網絡中，節點之間處于接觸狀態當且僅當它們在彼此的通信范圍內。節點之間不間斷地接觸的時間長度定義為接觸時長，同時連續的接觸之間的間隔時間被定義為接觸時間間隔。假設接觸時長Td是獨立同分布的隨機變量，其累計分布函數為FTd(t)。圖1給出了一個關于兩個節點之間的接觸時長Td和接觸時間間隔Tc的例子。為了方便分析，同時假設每次探測需要的能量是相同的，這樣節點的能量消耗率就可以轉化為平均的接觸探測頻率。

為了實現上面的數據交換過程，網絡中的節點必須不斷地探測周圍的環境去發現在其附近的其它節點。假設網絡中總共有 N 個節點。這些節點由一些具有藍牙接口的便攜設備組成，且有相同的通信距離 r。因為便攜設備中藍牙的通信距離一般小于10 m，所以本文也假設通信距離r≤10m。延遲容忍網絡中兩個節點是接觸的當且僅當兩個節點在彼此的通信范圍內。但是，如果兩個節點在接觸過程中都沒有探測的話，也會錯失彼此之間的接觸。因此，下面會對延遲容忍網絡中的接觸探測過程進行建模。

圖1 恒定探測間隔T下兩個節點之間的接觸探測過程示例

3 接觸檢測過程建模

這一節首先從理論上得到當節點的探測間隔為恒定值時的接觸探測概率的表達式，然后從理論上證明在所有平均接觸探測間隔相同并且節點的接觸過程未知的策略中，采用恒定探測間隔的策略是最優的。

3.1 接觸探測概率

這里定義接觸探測概率 Pd為兩個節點之間的接觸被其中某一個節點探測到的概率。為了方便下面的分析，假設對于節點A，一個和節點B之間的接觸能夠被探測到(也就是有效的接觸)，當且僅當和節點B之間的接觸被節點A探測到，否則這次接觸就被錯失。如圖1所示，設定節點A以恒定的間隔T探測，那么對于節點A來說，接觸2和接觸3是有效的接觸，而接觸1則為錯失的接觸。首先考慮網絡中的節點以恒定的間隔T探測(如圖1所示)，下面的部分會分析平均探測間隔相同的接觸探測策略。為了計算接觸探測概率 Pd，需要考慮多個參數，包括探測的間隔T和接觸時長 Td等。值得注意的是，當Td≥T的時候，兩個節點之間的接觸都能被探測到。因此，有如下的定理：

定理1 對于以恒定的間隔T探測的節點A來說，接觸探測概率可以表示為

證明 假設節點A在時間點{T, 2T,…}探測其周圍的環境。為了方便建模，這里先考慮在時間范圍[0,T]內去計算接觸探測概率。用隨機變量t代表在時間范圍[0,T]內和節點A的某一次接觸發生的時間。文獻[5]聲明“延遲容忍網絡是一種很稀疏的網絡，因而節點間的接觸時間間隔要遠大于探測間隔T”。基于這個聲明，可以得出t是均勻地分布在[0,T]的范圍內，那么這一次接觸能夠被節點A檢測到，如果(1)與節點A的接觸時間t剛好發生在節點A在時間T要探測周圍的環境時；(2)與節點A的接觸時間t發生在[0,T)的時間范圍內，但是它們的接觸時長足夠長，可以保證節點A在時間T要探測周圍的環境時，它們仍然處于接觸的狀態。因此，接觸探測概率是上面兩個部分之和，也可以表示為式(1)。因為在時間范圍(T,2T],(2T,3T],…內的接觸探測過程和[0,T]范圍內的接觸探測過程類似，所以接觸探測概率可以表示為式(1)。 證畢

如果節點之間的接觸時長Td服從一個給定的分布，就可以從理論上得到能量消耗和Pd(T)之間關系。文獻[16, 17]顯示隨機路點模型中的Td是獨立同分布的變量，其累計分布函數FTd(t)可以表示為

其中r是節點的通信范圍，V是節點的移動速度。根據式(2)可以看出，FTd(t)不能積分。為了方便下面的建模，考慮將式(2)進行簡化。如果t≤r/V，可以得到

如果t＞r/V，根據式(3)，可以得到

因此，式(2)的近似值可以表示為

圖2給出了在不同場景下FTd(t)的近似值(App)和精確值(Pre)的比較。從圖中可以看出，隨著接觸時長Td的增加，FTd(t)的近似值和精確值很接近，特別是當r = 6 m, V = 6 m/s時。因此，在下面的建模中，本文直接用FTd(t)的近似表達式來代替FTd(t)的精確表達式去計算接觸探測概率。

將式(5)代入式(1)中，可以得到接觸探測概率Pd(T)的表達式為

3.2 最優接觸探測策略

上面僅僅給出了當節點的探測間隔為恒定值時的接觸探測概率。事實上，在隨機路點模型中，在所有平均接觸探測間隔相同并且節點的接觸過程未知的策略中，采用恒定探測間隔的策略是最優的。

定理 2 考慮一個總共有 N 個節點在網絡中的環境，并且節點的接觸時長是獨立同分布的。再者，網絡中的節點對有相同的接觸時間間隔分布，且平均接觸時間間隔為1/λ。那么，在所有平均接觸探測間隔相同并且節點的接觸過程未知的策略中，采用恒定探測間隔的策略是最優的。

證明 不失一般性，考慮網絡中的節點要在一段很長的時間 L 內探測周圍的環境，并且采用不同策略的節點在這段時間內總共探測 n 次。根據前面的介紹，對于采用恒定的探測間隔T=L/n的策略，在時間L 內的接觸探測概率為Pd(T)=1F(t)dt。假設某一個特定的策略在時間點Tdt1,t2,…,tn探測總共 n 次，并且t1＜t2＜…＜tn, tn?t1≤L。設定t0=0，然后就可以得到 n 個接觸探測間隔：I1=t1?t0,I2=t2?t1,…,In=tn?tn?1。因為節點是隨機地選擇時間點tk探測，并且網絡中的節點對有相同的接觸時間間隔分布，其平均接觸時間間隔為1/λ，因此，在第 k 個時間間隔Ik=tk?tk?1內被某個節點探測到的有效接觸的期望數可以表示為：λ(N?1)(Ik?FTd(t)dt )，這里 N 是網絡中節點的總數。然后，在時間 L 內的期望接觸探測概率可以表示為

當Ik≥T時，可以得到

當Ik＜T時，可以得到

將式(8)和式(9)代入式(7)中，可以得到

隨機路點模型中接觸時長的分布是獨立同分布的，并且節點對有相同的接觸時間間隔分布，其分布可以近似為具有相同的接觸率的指數分布[18?19]。因此，可以得出在隨機路點模型中，在所有平均接觸探測間隔相同并且節點接觸過程無法預知的策略中，采用恒定探測間隔的策略是最優的。 證畢

3.3 能量效率和接觸探測概率之間的折中

基于前面得到的接觸探測概率的表達式，這一節介紹能量效率和接觸探測概率之間的折中。本文只考慮在接觸探測過程中消耗的能量，并未考慮數據傳輸過程中消耗的能量。因此，這里定義能量消耗為E=1/T，也就是網絡中節點的探測率。如果網絡中節點的探測率越大，那么節點在接觸探測過程中消耗的能量就越多。因此，式(6)可以變化為

根據式(11)，當能量消耗 E 趨近于無窮大時，可以得到接觸探測概率Pd(E)=1，也就是Pd(E)的最大值。當能量消耗E=0時，可以得到接觸探測概率Pd(E)=0，也就是Pd(E)的最小值。

圖3給出了不同場景下能量效率和接觸探測概率之間的折中。圖3(a)給出了當網絡中節點的移動速度 V 變化時，能量效率和接觸探測概率之間的折中，而圖3(b)則給出了當網絡中節點的通信范圍r 變化時，能量效率和接觸探測概率之間的折中。從圖中可以看出，接觸探測概率隨著能量消耗的增加而增加。這個結果是合理的，因為更多的能量消耗意味著更加頻繁的接觸探測，從而導致接觸探測概率的增加。但是，當能量消耗增加到一定值的時候，接觸探測概率的增加率會大大地減小。例如，當r=6 m,V=2 m/s時，接觸探測概率在能量消耗為 0.8時就將近達到最大值；當r=6 m,V=6 m/s，接觸探測概率在能量消耗為2.5時將近達到最大值。因此，這些點就是接觸探測過程中能量效率和接觸探測概率之間的“好的折中點”。

圖2 不同場景下FTd(t)的近似值和精確值的比較

圖3 不同場景下能量效率和接觸探測概率之間的折中

4 模型驗證

本文利用 MATLAB 作為仿真工具來驗證提出的理論模型的正確性。實驗采用一個有10個節點分布在面積為1000×1000 m2的場景。場景中的節點根據隨機路點模型移動，并且有相同的通信范圍r。根據上面的假設，考慮網絡中所有的節點都有相同的移動速度V，并且移動過程中的暫停時間為0。

圖4給出了不同場景下FTd(t)的仿真結果(Sim)和FTd(t)的近似值(App)以及精確值(Pre)的比較。從圖中可以看出，隨著探測間隔T的增加，相比FTd(t)的精確值，不同場景下FTd(t)的仿真結果更加接近于FTd(t)的近似值，特別是當r=6 m, V=6 m/s 以及V=3 m/s。基于以上的結果，可以看出相比FTd(t)的精確值，本文給出的近似值更加接近FTd(t)的實際值。因此，本文可以用式(5)代替式(2)，來直接計算接觸探測概率。

圖5給出了不同場景下接觸探測概率Pd(T)的仿真結果(Sim)和理論結果(Theo)的比較。圖5(a)顯示了當節點的移動速度變化時，Pd(T)的仿真結果和理論結果的比較，圖5(b)顯示了當節點的通信范圍變化時，Pd(T)的仿真結果和理論結果的比較。從圖中可以看出，隨著探測間隔T的增加，不僅當節點的移動速度變化時，而且當節點的通信范圍變化時，接觸探測概率Pd(T)的仿真結果和理論結果都非常接近。

綜上所述，通過不同場景下的仿真實驗可以看出，相比FTd(t)的精確值，FTd(t)的仿真結果更加接近于FTd(t)的近似值；接觸探測概率Pd(T)的仿真結果也非常接近于其理論結果，從而證明了本文提出的理論模型的正確性。

5 結束語

圖4 FTd(t)的理論結果和相應的仿真結果的比較

圖5 不同場景下Pd(T)的理論結果和相應的仿真結果的比較

本文研究了延遲容忍網絡中基于隨機路點模型的接觸探測過程的能量有效問題。在給定隨機路點模型中接觸時長分布的情況下，從理論上分別得到了接觸探測概率的表達式，并且也證明了在所有平均探測間隔相同并且不能提前知道節點的接觸過程的策略中，采用恒定探測間隔的策略是最優的。其次，基于提出的理論模型，分析了不同情況下能量效率和接觸探測概率之間的折中。最后，通過仿真實驗驗證所提出的模型的正確性。實驗結果表明在不同場景下接觸探測概率的仿真結果和理論結果都非常接近，從而證明了提出模型的正確性。

[1] Wei Kai-min, Liang Xiao, and Xu Ke. A survey of social-aware routing protocols in delay tolerant networks: applications, taxonomy and design-related issues[J]. IEEE Communications Surveys and Tutorials, 2014, 16(1): 556-578.

[2] 吳亞輝, 鄧蘇, 黃宏斌. 延遲容忍網絡狀態感知的路由策略研究[J]. 電子與信息學報, 2011, 33(3): 575-579.

Wu Ya-hui, Deng Su, and Huang Hong-bin. Research of situation-aware routing method in delay tolerant network [J]. Journal of Electronics & Information Technology, 2011, 33(3): 575-579.

[3] Zhou Huan, Chen Ji-ming, Fan Jia-lu, et al.. Consub: incentive-based content subscribing in selfish opportunistic mobile networks[J]. IEEE Journal on Selected Areas in Communications, 2013, 31(9): 669-679.

[4] 張振京, 金志剛, 舒炎泰. 基于節點運動預測的社會性DTN高效路由[J]. 計算機學報, 2013, 36(3): 626-635.

Zhang Zhen-jing, Jin Zhi-gang, and Shu Yan-tai. Efficient routing in social DTN based on nodes,movement prediction [J]. Journal of Computers, 2013, 36(3): 626-635.

[5] Zhou Huan, Chen Ji-ming, Zhao Hong-yang, et al.. On exploiting contact patterns for data forwarding in duty-cycle opportunistic mobile networks[J]. IEEE Transactions on Vehicular Technology, 2013, 62(9): 4629-4642.

[6] Drula C, Amza C, Rousseau F, et al.. Adaptive energy conserving algorithms for neighbor discovery in opportunistic bluetooth networks[J]. IEEE Journal on Selected Areas in Communications, 2007, 25(1): 96-107.

[7] Wang, Wei, Srinivasan V, and Motani M. Adaptive contact probing mechanisms for delay tolerant applications[C]. Proceedings of the ACM MobiCom, Montreal, Canada, 2007: 230-241.

[8] Wang Wei, Srinivasan V, and Motani M. Opportunistic energy-efficient contact probing in delay-tolerant applications [J]. IEEE/ACM Transactions on Networking, 2009, 17(5): 1592-1605.

[9] Qin Shuang, Feng Gang, and Zhang Yi-de. How the contact-probing mechanism affects the transmission capacity of delay-tolerant networks[J]. IEEE Transactions on Vehicular Technology, 2011, 60(4): 1825-1834.

[10] Zhou Huan, Zheng Huan-yang, Wu Jie, et al.. Energyefficient contact probing in opportunistic mobile networks[C]. Proceedings of the IEEE ICCCN, Nassau, Bahamas, 2013: 1-7.

[11] 李文霽, 鄭康鋒, 張冬梅, 等. 一種高效的延遲容忍移動傳感器網絡異步探測機制[J]. 電子與信息學報, 2012, 34(12): 2891-2897.

Li Wen-ji, Zheng Kang-feng, Zhang Dong-mei, et al.. An efficient asynchronous probing scheme for delay-tolerant mobility sensor network[J]. Journal of Electronics & Information Technology, 2012, 34(12): 2891-2897.

[12] Hess A, Hyyti? E, and Ott J. Efficient neighbor discovery in mobile opportunistic networking using mobility awareness[C]. Proceedings of COMSNETS, Bangalore, India, 2014: 1-8.

[13] Broch J, Maltz D, Johnson D, et al.. A performance comparison of multi-hop wireless ad hoc network routing protocols[C]. Proceedings of the ACM Mobicom, Dallas, USA, 1998: 85-97.

[14] McDonald B and Znati T. A path availability model for wireless Ad-hoc networks[C]. Proceedings of the IEEE WCNC, New Orleans, USA, 1999: 35-40.

[15] Eagle N, Pentland A, and Lazer D. Inferring social network structure using mobile phone data[J]. Proceedings of National Academy of Sciences, 2009, 106(36): 15274-15278.

[16] Tsao Cheng-lin, Liao Wan-jiun, and Kuo Jia-chun. Link duration of the random way point model in mobile Ad hoc networks[C]. Proceedings of the IEEE WCNC, Las Vegas, USA, 2006: 367-371.

[17] Wu Yueh-ting, Liao Wan-jiun, Tsao Cheng-lin, et al.. Impact of node mobility on link duration in multihop mobile networks[J]. IEEE Transactions on Vehicular Technology, 2009, 58(5): 2435-2442.

[18] Abdulla M and Simon R. The impact of intercontact time within opportunistic networks: protocol implications and mobility models[R]. TechRepublic White Paper, 2009.

[19] Spyropoulos T, Psounis K, and Raghavendra C. Performance analysis of mobility-assisted routing[C]. Proceedings of the ACM Mobihoc, Los Angeles, USA, 2006: 49-60.

周 歡： 男，1986年生，博士，講師，研究方向為延遲容忍網絡、移動社交網絡和物聯網技術.

任 東： 男，1976年生，博士，副教授，研究方向為模式識別、圖像處理和物聯網技術.

徐守志： 男，1969年生，博士，教授，研究方向為無線傳感器網絡和車輛自組網.

Research on Energy-efficient Contact Probing in Delay Tolerant Networks

Zhou Huan Ren Dong Xu Shou-zhi Jiang Ting-yao Huang Zhi-yong
(Hubei Key Laboratory of Intelligent Vision Based Monitoring for Hydroelectric Engineering, Yichang 443002, China)
(College of Computer and Information Technology, China Three Gorges University, Yichang 443002, China)

In the Delay Tolerant Networks (DTNs), in order to discover the neighbors, the nodes in the network have to probe the surrounding environment continually. This can be an extremely energy-consuming process. If the nodes probe very frequently, they consume a lot of energy, and may be energy inefficient. On the other hand, infrequent contact probing might cause loss of many contacts, and thus missing the opportunities to exchange data. Therefore, there exists a trade-off between the energy efficiency and contact opportunities in the DTNs. In order to investigate this trade-off, this study first proposes a model to quantify the contact detecting probability when the contact probing interval is constant based on the Random Way-Point (RWP) model. Moreover, this study also demonstrates that the strategy which probes at a constant interval performs the best performance, among all contact probing strategies with the same average contact probing interval. Then, based on the proposed model, this study analyzes the trade-off between the energy efficiency and contact detecting probability under different situations. Finally, extensive simulations are conducted to validate the correctness of the proposed model.

Delay Tolerant Networks (DTNs); Energy efficiency; Contact probing; Random Way-Point (RWP) model

TP393.04

： A

：1009-5896(2015)06-1285-06

10.11999/JEIT140995

2014-07-25收到，2014-12-11改回

國家自然科學基金(61174177, 41172298)，國家863計劃項目(2013AA10230207)，湖北省自然科學基金(2014CFB145)，湖北省水電工程智能視覺監測重點實驗室開放基金(2014KLA07)和三峽大學人才科研啟動基金(KJ2014B056, KJ2014B060)資助課題

*通信作者：徐守志 xsz@ctgu.edu.cn