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

馬繼紅，楊文濤,白躍彬

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

?

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

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

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

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

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

0　引言

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

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

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

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

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

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

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

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

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

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

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

表2　符號定義表

預(yù)測兩個節(jié)點是否會在未來的某段時間Tf內(nèi)相遇，其實就是預(yù)測目前兩節(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ù)對相遇概率進(jìn)行預(yù)測。

3　實驗結(jié)果

3.1方法有效性驗證

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

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

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

Recall Ratio =A1/(A1+A2)

Accuracy = A1/(A1+A3)

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

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

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

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

圖2　PROPHET概率預(yù)測方法閾值選取對查全和檢準(zhǔn)率的影響

圖3　貝葉斯概率預(yù)測方法閾值選取對查全率和檢準(zhǔn)率的影響

3.2方法普適性驗證

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

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

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

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

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

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

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

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

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

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

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

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

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

表5　3種算法準(zhǔn)確率對比　%

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

表6　貝葉斯方法準(zhǔn)確率提升百分比　%

3.3實驗結(jié)果分析

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

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

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

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

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

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

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

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

4　結(jié)論

PROPHET路由方法主要關(guān)注相遇概率相對大小，并不關(guān)注相遇概率的絕對值，因此即使在預(yù)測準(zhǔn)確率偏低的情況下路由方法仍然有較好的表現(xiàn)?；谥笖?shù)分布的預(yù)測方法目前多限于數(shù)據(jù)研究，并未作為路由的主要依據(jù)。兩種預(yù)測方法的準(zhǔn)確率都偏低，無法作為分簇的條件。貝葉斯概率預(yù)測方法預(yù)測相遇概率的準(zhǔn)確性較高，已經(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。

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

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

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