馬繼紅，楊文濤,白躍彬

(1.邯鄲職業(yè)技術學院 機電工程系，河北 邯鄲　056001；2.北京航空航天大學 計算機學院，北京　100191)

?

DTN中基于貝葉斯的節(jié)點相遇概率預測方法

馬繼紅1，楊文濤2,白躍彬2

(1.邯鄲職業(yè)技術學院 機電工程系，河北 邯鄲056001；2.北京航空航天大學 計算機學院，北京100191)

DTN網(wǎng)絡由于頻繁的網(wǎng)絡斷開、高延遲和異構(gòu)性等原因，導致網(wǎng)絡可用性較低；為了提高DTN網(wǎng)絡可用性，一方面要提高數(shù)據(jù)包送達目的節(jié)點的比例，另一方面也要注意控制網(wǎng)絡中的副本數(shù)量；著重研究在便攜設備交換網(wǎng)(PSN)和移動規(guī)律性較弱的車載網(wǎng)絡(VAN)等網(wǎng)絡中對節(jié)點相遇概率直接預測的方法；提出了一種利用貝葉斯概率的方法進行相遇概率預測，這種方法基于數(shù)據(jù)集的歷史數(shù)據(jù)，不依賴于具體的數(shù)據(jù)集，具有較好的適應性和準確性。

DTN網(wǎng)絡；貝葉斯網(wǎng)絡；節(jié)點；相遇概率

0　引言

容遲容斷網(wǎng)絡DTN 是主要針對端到端連接和節(jié)點資源都有限時的一種網(wǎng)絡解決方案，用以滿足隨意的異步消息的可靠傳遞。PROPHET路由協(xié)議借助歷史數(shù)據(jù)對相遇概率進行估算，根據(jù)和目的節(jié)點的相遇概率進行轉(zhuǎn)發(fā)，取得了較好的效果。兩個節(jié)點的相遇概率預測是DTN預測的核心問題。對于星際網(wǎng)絡(IPN)和規(guī)律性較強的車載網(wǎng)絡(VAN)[1]等移動規(guī)律較為固定和已知的網(wǎng)絡形態(tài)中，節(jié)點相遇的時間可以通過對節(jié)點的運動建模計算得到較為精確的時間，因此，在這種網(wǎng)絡形態(tài)下不需要進行相遇概率的預測。而對于便攜設備交換網(wǎng)(PSN)和移動規(guī)律性較弱的車載網(wǎng)絡(VAN)等網(wǎng)絡，由于無法對節(jié)點的移動規(guī)律進行建模，所以目前此類網(wǎng)絡中的路由主要通過劃分社區(qū)或直接計算等多種方式對節(jié)點間相遇概率進行預測，并利用預測結(jié)果作為路由選擇的依據(jù)。本文將著重研究在后一種情況下對節(jié)點相遇概率直接預測的方法。

目前還不存在一種可以對相遇概率進行直接預測且預測準確率較高的算法，同時上述預測方法考慮因素較為單一，在不同數(shù)據(jù)集中表現(xiàn)具有較大區(qū)別，在具體不同的網(wǎng)絡環(huán)境下通用性較差。本文提出了一種利用貝葉斯概率的方法進行相遇概率預測，這種方法基于數(shù)據(jù)集的歷史數(shù)據(jù)，不依賴于具體的數(shù)據(jù)集，具有較好的適應性和準確性。

1　基于貝葉斯網(wǎng)絡的DTN節(jié)點相遇知識學習方法

1.1節(jié)點相遇知識挖掘

節(jié)點相遇知識是指DTN中任意兩節(jié)點間存在的兩節(jié)點在過去一段時間內(nèi)的相遇情況的特征，包括節(jié)點接觸頻率、平均接觸時長、平均接觸時間間隔等。這些參數(shù)中有些參數(shù)屬于受節(jié)點影響的主要原因，有些則受其它因素影響。為了得到影響節(jié)點相遇的主要因素，通過構(gòu)建貝葉斯網(wǎng)絡對節(jié)點間相遇情況的特征進行學習。

表1　節(jié)點相遇知識特征參數(shù)

1.2構(gòu)建貝葉斯網(wǎng)絡模型

通過結(jié)構(gòu)學習和參數(shù)學習過程，可以構(gòu)建出一個基于網(wǎng)絡性能參數(shù)變量的貝葉斯網(wǎng)絡結(jié)構(gòu)模型，如圖1所示。從圖中可以看出主要因素有接觸頻率、平均接觸時長、被影響因素為節(jié)點流行度和節(jié)點相似度。貝葉斯網(wǎng)絡模型表示出了各個網(wǎng)絡參數(shù)之間的依賴關系，同時可以得出它們具體參數(shù)值之間的概率關系。

圖1　貝葉斯網(wǎng)絡結(jié)構(gòu)圖

2　基于貝葉斯概率的DTN節(jié)點相遇概率預測方法

對相對概率的預測，是指在兩個節(jié)點處在沒有接觸的情況下，根據(jù)節(jié)點的歷史數(shù)據(jù)信息及所處網(wǎng)絡環(huán)境對兩節(jié)點在未來一段時間內(nèi)相遇的概率進行預測。將用到表2中的符號。

表2　符號定義表

預測兩個節(jié)點是否會在未來的某段時間Tf內(nèi)相遇，其實就是預測目前兩節(jié)點在最近接觸后Tl時間時，再等待Tf時間內(nèi)兩節(jié)點是否會有新的接觸，即二者所處接觸間隔的長度Ic是否短于Tf+Tl。

P(節(jié)點在Tf內(nèi)相遇)=P(Ic

Tf和Tl都是已知量，故整個問題轉(zhuǎn)化為對間隔長度Ic的估計。由于目前已經(jīng)等待了Tl的時間，故Ic>Tl。所以：

P(節(jié)點在Tf內(nèi)相遇)=P(IcTl)

由條件概率公式可得：

P(IcTl)=P(IcTl)/P(Ic>Tl)

綜合以上公式可得：

P(節(jié)點在Tf內(nèi)相遇)=f(Tl

上式中的f(a)為發(fā)生a事件的頻率。在這個場景中，頻率可通過統(tǒng)計歷史數(shù)據(jù)獲得。綜上，可利用歷史數(shù)據(jù)對相遇概率進行預測。

3　實驗結(jié)果

3.1方法有效性驗證

對于實驗可能會出現(xiàn)的結(jié)果可以分為4種情況，如表3所示。

表3　實驗結(jié)果類型

對于預測準確性的度量可以參考信息檢索中的查全率(Recall Ratio)和檢準率(Accuracy)。二者的定義如下所示：

Recall Ratio =A1/(A1+A2)

Accuracy = A1/(A1+A3)

公式中所用符號均如表3所示。對于路由過程存在多個消息副本的DTN路由協(xié)議來說，查全率較為重要；對于單個消息副本的DTN路由協(xié)議來說，檢準率更為重要。在實際應用中可以根據(jù)需求靈活選擇參數(shù)，獲得較好的路由效果。

實驗均采用Haggle-6數(shù)據(jù)集，為防止異常數(shù)據(jù)的影響只對接觸時間超過一個數(shù)據(jù)采集周期(120 s)的接觸進行分析。預測的目標都是在未來1小時內(nèi)是否會有新的接觸發(fā)生。由于未限定求相遇概率的原因，因此實驗并未根據(jù)實際需求取閾值，而是將所有閾值(每隔0.1%進行取樣)下的查全率和檢準率進行對比，以圖的形式展示。其中查全率用虛線表示，檢準率用實線表示。

圖2為PROPHET路由算法中提供的相遇概率預測方法所得到的查全率和檢準率的對比。其中橫坐標為根據(jù)算法的預測概率區(qū)分是否會相遇的閾值，縱坐標為在該閾值下的查全率(虛線)和檢準率(實線)。其中，這里PROPHET預測路由算法中的參數(shù)采用ONE仿真軟件中的默認設置。從結(jié)果可知，隨著閾值的提高，所預測的檢準率會逐漸提升，但查全率始終維持在0.5左右的水平。

圖3 為本文算法所預測的相遇概率預測。從圖中可以看出在默認取0.5做分割閾值時，無論是查全率還是檢準率都明顯高于PROPHET算法。而且查全率和檢準率有較為明顯的負相關，可以通過選擇不同閾值滿足不同路由協(xié)議的需求。

圖2　PROPHET概率預測方法閾值選取對查全和檢準率的影響

圖3　貝葉斯概率預測方法閾值選取對查全率和檢準率的影響

3.2方法普適性驗證

上面的方法驗證了貝葉斯方法的有效性，為了驗證說明方法的普適性，在另外4種不同類型的數(shù)據(jù)集中將貝葉斯方法同另外兩種方法分別進行對比驗證。4種數(shù)據(jù)集主要參數(shù)如表4所示。

表4　數(shù)據(jù)集及相關參數(shù)

Haggle數(shù)據(jù)集[2]是劍橋大學通過將自制的藍牙設備(iMotes)部署到人身上進行數(shù)據(jù)采集得到的。

NUS數(shù)據(jù)集[3]是新加坡國立大學通過手機采集的的數(shù)據(jù)。

Reality數(shù)據(jù)集[4]是麻省理工學院利用一百部諾基亞6600手機收集的數(shù)據(jù)。

Sassy數(shù)據(jù)集[5]是圣安德魯斯大學利用自制的IEEE802.15設備(T-mote)進行的數(shù)據(jù)采集，

對于每組實驗主要有3個參數(shù)：數(shù)據(jù)集、預測方法及預測時間。根據(jù)上表的參數(shù)可以看出，我們一共進行了84組實驗。每組實驗進行100000次抽樣，保證平均每個閾值樣本所代表的參數(shù)為100個。

為了綜合考慮查全率和檢準率，在這里定義綜合準確率為查全率和檢準率的幾何平均值，這個值在二者差距較大的情況下較客觀的反應了預測質(zhì)量。取每次實驗各閾值對應的綜合準確率中的最大值作為這次實驗預測質(zhì)量的代表。各組實驗結(jié)果如圖4～圖7所示。其中黑色實線代表貝葉斯方法在不同預測時長的綜合準確率，虛線和灰色十字分別代表PROPHET路由中的預測方法和基于指數(shù)分布的預測方法在不同預測時長的綜合準確率。

圖4　Haggle3數(shù)據(jù)集3種方法對比

圖5　NUS數(shù)據(jù)集3種方法對比

圖6　Sassy數(shù)據(jù)集3種方法對比

圖7　Reality數(shù)據(jù)集3種方法對比

從圖中可以看出，基于貝葉斯概率的節(jié)點相遇概率計算方法在各不同種類的數(shù)據(jù)集中的預測中的各種預測時長準確性均優(yōu)于其他兩種預測方法。

表5　3種算法準確率對比　%

表5為3種方法在4個數(shù)據(jù)集中的平均準確率，可以看出貝葉斯方法在各個數(shù)據(jù)集中預測準確性最高。表6表明新的貝葉斯方法對PROPHET方法和指數(shù)分布這兩種相遇概率預測方法的準確度分別提升了39.62%和75.73%。

表6　貝葉斯方法準確率提升百分比　%

3.3實驗結(jié)果分析

通過統(tǒng)計數(shù)據(jù)集中接觸間隔，可以對基于貝葉斯的相遇概率預測方法預測概率提升的原因進行解釋。

PROPHET路由協(xié)議中的相遇概率預測方法在節(jié)點沒有接觸時，預測的兩節(jié)點的相遇概率會隨時間逐漸縮??；基于指數(shù)分布的相遇概率預測方法假設接觸間隔服從指數(shù)分布，所預測的相遇概率也是隨時間逐漸縮小。

Haggle數(shù)據(jù)集里接觸間隔和頻率的關系如圖 8所示。其中橫軸為接觸間隔，單位為小時；縱軸為接觸間隔的頻數(shù)。從圖中可以看出，在開始時，隨著接觸間隔的增長，接觸間隔的頻率即節(jié)點再次接觸的概率逐漸減小，這一點上之前的兩種路由算法是較為符合實際情況的。但是隨著時間的增長，當接觸間隔超過十個小時后，接觸間隔的頻率隨間隔增長會逐漸增加，并在18～24個小時左右達到峰值。結(jié)合數(shù)據(jù)集采集的場景，在第一天會議結(jié)束后到第二天會議開始，之間的時間間隔大約就是18～24個小時。在這個階段，PROPHET路由協(xié)議中的相遇概率預測方法和基于指數(shù)分布的相遇概率預測方法均無法給出相應的預測。

圖8　Haggle數(shù)據(jù)集接觸間隔長度和頻率的關系圖

圖9　Reality數(shù)據(jù)集接觸間隔長度和頻率的關系圖

基于貝葉斯的相遇概率預測方法通過對歷史數(shù)據(jù)的統(tǒng)計，可以有效擬合實際中的接觸間隔變化規(guī)律。如當距離上次接觸距離為五小時時，可以從圖中的歷史數(shù)據(jù)觀察到未來五小時內(nèi)會有新的接觸發(fā)生的頻率占接觸間隔五小時以上的頻率較小，因此發(fā)生接觸的可能性也較??；當距離上次接觸發(fā)生時間距離15小時時，雖然未發(fā)生接觸時間間隔更長，但根據(jù)歷史數(shù)據(jù)可知這時未來五小時內(nèi)可能發(fā)生新接觸的概率反而會增大，因此所得到的相遇概率的預測值也會相應變大。

不同于Haggle數(shù)據(jù)集僅收集幾天的數(shù)據(jù)，Reality數(shù)據(jù)集連續(xù)收集了節(jié)點九個月的移動和接觸數(shù)據(jù)，更便于觀察節(jié)點接觸的長期規(guī)律性。Reality數(shù)據(jù)集接觸間隔長度和頻率的關系如圖9所示，其中橫軸單位為天。從圖中可以看出，雖然節(jié)點接觸時間總體來看具有長期規(guī)律性，即接觸概率隨接觸間隔的增長而降低，但圖中仍然可以看出間隔時間的分布并非平滑的曲線，而是存在眾多明顯的峰值，而且峰值的排列具有一定的規(guī)律性：大約每七天左右就會出現(xiàn)一個峰值。結(jié)合數(shù)據(jù)集采集的場景來看，在校園活動中存在較強的以星期為周期的規(guī)律性：課程、例會、周末社交活動，很多人會間隔七天左右再次見面。Reality數(shù)據(jù)集的分析結(jié)果體現(xiàn)了這種規(guī)律性。

結(jié)合之前的分析可知，PROPHET路由協(xié)議中的概率預測方法和基于指數(shù)分布的預測方法均無法預測這種間隔七天的規(guī)律性，而貝葉斯方法可以通過歷史數(shù)據(jù)的統(tǒng)計獲得這種規(guī)律性，得到更為準確的預測值。同時，貝葉斯方法對這種規(guī)律性的預測完全基于歷史數(shù)據(jù)而不需基于任何先驗知識，是的基于貝葉斯的相遇概率預測方法具有普適性。

4　結(jié)論

PROPHET路由方法主要關注相遇概率相對大小，并不關注相遇概率的絕對值，因此即使在預測準確率偏低的情況下路由方法仍然有較好的表現(xiàn)?；谥笖?shù)分布的預測方法目前多限于數(shù)據(jù)研究，并未作為路由的主要依據(jù)。兩種預測方法的準確率都偏低，無法作為分簇的條件。貝葉斯概率預測方法預測相遇概率的準確性較高，已經(jīng)可以作為DTN節(jié)點分簇的依據(jù)。

[1] Hull B,Bychkovsky V,Zhang Y,et al. CarTel: a distributed mobile sensor computing system[A]. Proceedings of the 4th international conference on Embedded networked sensor systems (SenSys’06)[C].2006.

[2] Pan H,Chaintreau A, Scott J,et al. Pocket switched networks and human mobility in conference environments [A]. Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking (WDTN’05)[C].2005.

[3] Natarajan A,Motani M,Srinivasan V. Understanding urban interactions from bluetooth phone contact traces [A].PAM 2007,8th Passive and Active Measurement Conference[C].2007.

[4] Nathan E,Pentland A. Reality mining: sensing complex social systems[J]. Journal of Personal and Ubiquitous Computing,2006.

[5] Bigwood G,Rehunathan D,Bateman M,et al. Exploiting self-reported social networks for routing in ubiquitous computing environments [A].Proceedings of IEEE International Conference on Wireless and Mobile Computing,Networking and Communication (WiMob '08)[C].2008.

A Prediction Method of Node Encounter Probability Using Bayesian in DTN

Ma Jihong1,Yang Wentao2,Bai Yuebin2

(1.Department of Mechanical and Electrical Engineering,Handan Polytechnic College,Handan056001,China 2.School of Computer Science and Engineering,Beihang University,Beijing100191,China)

Due to the frequent network disconnection,high latency and heterogeneity,DTN network has resulted in low network availability. In order to improve the availability of DTN network,it should increase the proportion of the data packets to the destination node. On the other hand,it also should control the number of copies in the network. The method of direct prediction of node encounter probability in the network,such as PSN,and weak regularity VAN,is studied. It presents a prediction method of Bayesian probability of encounter probability. This method is based on the historical data of data sets,which is not dependent on specific data sets,with better flexibility and accuracy.

DTN; Bayesian network; node; encounter probability

1671-4598(2016)04-0185-04DOI：10.16526/j.cnki.11-4762/tp.2016.04.054

TP393

A

2015-10-17；

2015-10-30。

國家自然科學基金項目(61073076)；河北省科技計劃支撐項目(13200326D)。

馬繼紅(1977-)，女，河北定州人，在讀碩士，副教授，主要從事計算機控制方向的研究。

白躍彬(1962-)，男，河北石家莊人，教授，博士生導師，主要從事計算機網(wǎng)絡及分布式系統(tǒng)方向的研究。