基于社區(qū)等量交換的移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)路由算法

劉麗 張?jiān)? 黃衛(wèi)東 錢斌 劉蘭風(fēng)

摘要：針對(duì)移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)效率低下的問題，提出了一種基于社區(qū)等量交換的路由算法。首先衡量節(jié)點(diǎn)對(duì)社區(qū)的貢獻(xiàn)和從該社區(qū)獲得的收益，采用等量交換的原則來決定節(jié)點(diǎn)的合作策略，然后采用資源分配策略對(duì)節(jié)點(diǎn)為社區(qū)分配的數(shù)據(jù)轉(zhuǎn)發(fā)資源進(jìn)行優(yōu)化分配，接著進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)的選擇，最后對(duì)節(jié)點(diǎn)的貢獻(xiàn)和收益進(jìn)行更新。所提算法充分利用社區(qū)內(nèi)外的節(jié)點(diǎn)，合理分配轉(zhuǎn)發(fā)資源，從而達(dá)到提高數(shù)據(jù)轉(zhuǎn)發(fā)性能的目的。仿真結(jié)果表明，與其他經(jīng)典算法Direct，LABEL和ProPHET相比，該算法能夠顯著優(yōu)化數(shù)據(jù)轉(zhuǎn)發(fā)資源，提高數(shù)據(jù)轉(zhuǎn)發(fā)效率，獲得了更高的數(shù)據(jù)傳遞率、更低的轉(zhuǎn)發(fā)延遲和負(fù)載。

關(guān)鍵詞： 移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)；社區(qū)；路由轉(zhuǎn)發(fā)

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）10-0032-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1 引言

移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)（Mobile Opportunistic Network）利用移動(dòng)設(shè)備在移動(dòng)過程中偶然的相遇機(jī)會(huì)，采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的模式完成不依賴于基礎(chǔ)設(shè)施的數(shù)據(jù)傳輸[1]。普遍存在的移動(dòng)設(shè)備使得移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)成為未來社會(huì)生活中移動(dòng)應(yīng)用的重要通訊模式。

近年來，社交因素對(duì)移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)挠绊懼饾u被人們所關(guān)注，涌現(xiàn)了很多基于社交因素的路由算法。社區(qū)是指具有直接或間接社交聯(lián)系的人組成的關(guān)系緊密的群體。社區(qū)中的成員之間，與社區(qū)外的成員相比，具有更頻繁的接觸和相遇機(jī)會(huì)[2]。節(jié)點(diǎn)間的社區(qū)特性在移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)路由協(xié)議設(shè)計(jì)中具有積極的作用，能夠在一定程度上提高數(shù)據(jù)傳輸效率。然而，在眾多的移動(dòng)節(jié)點(diǎn)中，社區(qū)外的節(jié)點(diǎn)的數(shù)量遠(yuǎn)遠(yuǎn)多于同社區(qū)的節(jié)點(diǎn)數(shù)量。而社區(qū)外的弱聯(lián)系節(jié)點(diǎn)這一重大資源卻常常被忽略。

本文提出了一種基于社區(qū)等量交換的數(shù)據(jù)路由算法（Community based Equal Exchanged Routing Algorithm， 簡(jiǎn)稱CEERA），合理利用社區(qū)和弱聯(lián)系節(jié)點(diǎn)這兩種資源，考察節(jié)點(diǎn)與社區(qū)之間的貢獻(xiàn)和收益平衡，采取等量交換的原則，優(yōu)化轉(zhuǎn)發(fā)資源，從而達(dá)到提高數(shù)據(jù)轉(zhuǎn)發(fā)性能的目的。仿真結(jié)果表明，本文提出的算法能夠有效地提高數(shù)據(jù)轉(zhuǎn)發(fā)效率，降低網(wǎng)絡(luò)負(fù)載。

2 算法的提出

2.1 系統(tǒng)模型

假設(shè)系統(tǒng)中有N個(gè)節(jié)點(diǎn)，按照一定的社交聯(lián)系組成M個(gè)社區(qū)[C1，C2，...Ci，...CM]，其中i=1..M。同一社區(qū)中的節(jié)點(diǎn)具有較高的社交強(qiáng)度，從而具有更加頻繁的相遇概率，常被用來指導(dǎo)路由轉(zhuǎn)發(fā)。CEERA算法中，節(jié)點(diǎn)綜合考慮與所有社區(qū)的社交強(qiáng)度和關(guān)聯(lián)，從節(jié)點(diǎn)與社區(qū)之間的社交強(qiáng)度、未來相遇概率、節(jié)點(diǎn)對(duì)社區(qū)的貢獻(xiàn)，以及節(jié)點(diǎn)從該社區(qū)的收益四個(gè)方面衡量，以實(shí)現(xiàn)優(yōu)化分配數(shù)據(jù)轉(zhuǎn)發(fā)資源，提高數(shù)據(jù)轉(zhuǎn)發(fā)效率的目的。

2.2 衡量要素

節(jié)點(diǎn)與社區(qū)之間社交強(qiáng)度[ST（Ci）]。節(jié)點(diǎn)與社區(qū)之間的社交強(qiáng)度用來衡量節(jié)點(diǎn)與各個(gè)社區(qū)的接觸程度。某節(jié)點(diǎn)與社區(qū)[Ci]的社交強(qiáng)度[ST（Ci）]采用單位時(shí)間T內(nèi)遇到的該社區(qū)的節(jié)點(diǎn)數(shù)量來衡量，即公式（1）。

2.3 CEERA的工作流程

當(dāng)兩個(gè)節(jié)點(diǎn)如A和B進(jìn)入彼此的通信范圍，首先交換彼此的社區(qū)信息，更新相應(yīng)的社區(qū)社交強(qiáng)度信息。然后，根據(jù)節(jié)點(diǎn)的貢獻(xiàn)收益情況，采用等量交換的原則決定是否為對(duì)方節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)（合作策略）。接著，根據(jù)數(shù)據(jù)轉(zhuǎn)發(fā)策略決定轉(zhuǎn)發(fā)列表，進(jìn)行數(shù)據(jù)傳輸。如果決定不進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，轉(zhuǎn)發(fā)列表為空。最后，根據(jù)本次的轉(zhuǎn)發(fā)行為，更新各自的貢獻(xiàn)收益情況（更新策略）。

3 算法的實(shí)現(xiàn)

3.1 合作策略的實(shí)現(xiàn)

移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)幕A(chǔ)是節(jié)點(diǎn)之間的合作轉(zhuǎn)發(fā)，即節(jié)點(diǎn)愿意為相遇節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)。CEERA算法的合作策略采取基于社區(qū)等量交換的原則，依據(jù)節(jié)點(diǎn)對(duì)社區(qū)的貢獻(xiàn)和節(jié)點(diǎn)從社區(qū)獲得的收益兩個(gè)指標(biāo)來決定節(jié)點(diǎn)采取合作轉(zhuǎn)發(fā)行為還是拒絕轉(zhuǎn)發(fā)的行為。

節(jié)點(diǎn)一方面為各個(gè)社區(qū)轉(zhuǎn)發(fā)數(shù)據(jù)做出貢獻(xiàn)，另一方面也接受各個(gè)社區(qū)節(jié)點(diǎn)的轉(zhuǎn)發(fā)幫助獲得收益。對(duì)于節(jié)點(diǎn)來說，精簡(jiǎn)轉(zhuǎn)發(fā)操作減少頻繁替換的前提是自身得到最大的收益。假設(shè)單位時(shí)間T內(nèi)，節(jié)點(diǎn)為各個(gè)社區(qū)做的貢獻(xiàn)為[CON（Ci）]，則其在單位時(shí)間內(nèi)總的貢獻(xiàn)為[i=1MCON（Ci）]。假設(shè)節(jié)點(diǎn)從各個(gè)社區(qū)得到的收益為[BEN（Ci）]，則其在單位時(shí)間內(nèi)總的貢獻(xiàn)為[i=1MBEN（Ci）]。在節(jié)點(diǎn)有限的傳輸帶寬資源下，節(jié)點(diǎn)要得到最大收益需要滿足公式（3），即節(jié)點(diǎn)以最少的轉(zhuǎn)發(fā)貢獻(xiàn)獲得最大的轉(zhuǎn)發(fā)收益。這個(gè)問題可以轉(zhuǎn)換為0-1背包問題，從而得到公式（4）。

由于每個(gè)節(jié)點(diǎn)都想獲得最優(yōu)的收益，因此，當(dāng)[BEN（Ci）CON（Ci）]接近1時(shí)，可以得到接近于最優(yōu)的收益，即節(jié)點(diǎn)對(duì)社區(qū)[Ci]的轉(zhuǎn)發(fā)貢獻(xiàn)與其從該社區(qū)得到的收益基本持平。由此可知，節(jié)點(diǎn)對(duì)社區(qū)采取等量交換的原則，可以最大限度地利用其轉(zhuǎn)發(fā)資源，有效地減少替換操作，從而提高數(shù)據(jù)轉(zhuǎn)發(fā)效率。

由于節(jié)點(diǎn)的貢獻(xiàn)和收益不是同時(shí)發(fā)生的，兩者之間往往存在一定的時(shí)間差，因此設(shè)立一個(gè)閾值[minSize，maxSize]來進(jìn)行調(diào)節(jié)。從節(jié)點(diǎn)A的角度來說明具體的合作策略如下：

3.2 更新策略的實(shí)現(xiàn)

當(dāng)數(shù)據(jù)轉(zhuǎn)發(fā)成功后，要及時(shí)更新對(duì)應(yīng)節(jié)點(diǎn)的貢獻(xiàn)值和收益值。仍以節(jié)點(diǎn)A為例來說明更新策略。假設(shè)節(jié)點(diǎn)A為節(jié)點(diǎn)B轉(zhuǎn)發(fā)了若干數(shù)據(jù)。則對(duì)于每個(gè)轉(zhuǎn)發(fā)的數(shù)據(jù)，根據(jù)數(shù)據(jù)的源節(jié)點(diǎn)、目的節(jié)點(diǎn)與轉(zhuǎn)發(fā)節(jié)點(diǎn)三者之間的關(guān)系，更新策略可以分為下面四種情況進(jìn)行處理：

（1） A、B都是中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。這時(shí)節(jié)點(diǎn)A幫助節(jié)點(diǎn)B轉(zhuǎn)發(fā)了若干數(shù)據(jù)，節(jié)點(diǎn)B得到了節(jié)點(diǎn)A的轉(zhuǎn)發(fā)服務(wù)，則節(jié)點(diǎn)B從節(jié)點(diǎn)A所在社區(qū)[Ci]所得的收益值將會(huì)增加。

（2） 節(jié)點(diǎn)A是中間轉(zhuǎn)發(fā)節(jié)點(diǎn)，而節(jié)點(diǎn)B是源節(jié)點(diǎn)（產(chǎn)生數(shù)據(jù)的節(jié)點(diǎn)）。這種情況的處理與（1）類似，節(jié)點(diǎn)A對(duì)B所在社區(qū)[Cj]的貢獻(xiàn)將會(huì)增加，節(jié)點(diǎn)B從A所在社區(qū)[Ci]所得到的收益將會(huì)增加。

（3） 節(jié)點(diǎn)A是目的節(jié)點(diǎn)（數(shù)據(jù)的接收節(jié)點(diǎn)），而節(jié)點(diǎn)B是中間轉(zhuǎn)發(fā)節(jié)點(diǎn)。這種情況下，節(jié)點(diǎn)A接收了所需要的數(shù)據(jù)，從節(jié)點(diǎn)B所在社區(qū)[Cj]中獲益。因此，節(jié)點(diǎn)A從社區(qū)[Cj]得到的收益將會(huì)增加。而節(jié)點(diǎn)B因?yàn)閹椭斯?jié)點(diǎn)A，其對(duì)社區(qū)[Ci]的貢獻(xiàn)也將會(huì)相應(yīng)增加。

（4） 節(jié)點(diǎn)A是目的節(jié)點(diǎn)，節(jié)點(diǎn)B是源節(jié)點(diǎn)。這種情況下，節(jié)點(diǎn)A和節(jié)點(diǎn)B互相為對(duì)方社區(qū)做了貢獻(xiàn)，其貢獻(xiàn)和收益相抵。節(jié)點(diǎn)A、B的貢獻(xiàn)收益將保持不變，不做更新操作。

4 算法性能評(píng)價(jià)

4.1 仿真環(huán)境及設(shè)置

本文中使用仿真工具ONE Simulator[10]，實(shí)驗(yàn)數(shù)據(jù)采用INFOCOM2006實(shí)際數(shù)據(jù)集進(jìn)行仿真實(shí)驗(yàn)。實(shí)驗(yàn)中，將CEERA與經(jīng)典路由算法直接轉(zhuǎn)發(fā)路由算法（Direct）、基于社區(qū)的轉(zhuǎn)發(fā)路由算法LABEL以及ProPHET路由算法進(jìn)行性能對(duì)比和分析。

4.2 仿真結(jié)果及分析

通過以上仿真比較可知，CEERA具有最高的數(shù)據(jù)交付率，較低的網(wǎng)絡(luò)負(fù)載，最少的平均延遲，以及最多的平均跳數(shù)，獲得了最優(yōu)的數(shù)據(jù)轉(zhuǎn)發(fā)效率。從而證明CEERA使得移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)轉(zhuǎn)發(fā)性能得到明顯提升。

5 結(jié)語

本文中提出了基于社區(qū)等量交換的數(shù)據(jù)轉(zhuǎn)發(fā)路由算法CEERA，以節(jié)點(diǎn)與社區(qū)之間的貢獻(xiàn)和收益的等量交換為原則，優(yōu)化分配節(jié)點(diǎn)的轉(zhuǎn)發(fā)資源，合理分配節(jié)點(diǎn)的存儲(chǔ)空間，以實(shí)現(xiàn)優(yōu)化數(shù)據(jù)轉(zhuǎn)發(fā)性能的目的?；趯?shí)際數(shù)據(jù)集INFOCOM2006的仿真實(shí)驗(yàn)表明，與傳統(tǒng)經(jīng)典算法相比，CEERA可以有效地提高移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)中的數(shù)據(jù)轉(zhuǎn)發(fā)效率。

參考文獻(xiàn)：

[1] 馬東華， 袁培燕， 趙東. 移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)路由問題研究進(jìn)展[J]. 軟件學(xué)報(bào)， 2015， 26（3）：600-616.

[2] 姚玉坤， 楊及開， 劉文輝. 機(jī)會(huì)網(wǎng)絡(luò)中基于社區(qū)的高效消息傳輸算法[J]. 計(jì)算機(jī)應(yīng)用， 2015，35（9）：2447-2452.

[3] Lindgren A， Doria A， Schelén O. Probabilistic routing in intermittently connected networks[J].Service Assurance with Partial and Intermittent Resources， ser. Lecture Notes in Computer Science，2004，3126：239-254.

[4] Ker?nen A， K?rkk?inen T， Ott J. Simulating Mobility and DTNs with the ONE[J]. Journal of Communications，2010，5（2）：92-105.

【通聯(lián)編輯：王力】