任 智,黃希凱,譚永銀
(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)
機(jī)會(huì)社會(huì)網(wǎng)絡(luò)中一種基于社區(qū)的高效路由算法
任 智,黃希凱,譚永銀
(重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)
針對(duì)機(jī)會(huì)社會(huì)網(wǎng)絡(luò)中RADR(機(jī)會(huì)社會(huì)網(wǎng)絡(luò)消息傳送算法)存在消息傳輸時(shí)延偏大和消息傳輸成功率偏低的問(wèn)題,提出一種ECRA(基于社區(qū)的高效的機(jī)會(huì)社會(huì)網(wǎng)絡(luò)路由算法)。ECRA只選取與消息目的節(jié)點(diǎn)在同一個(gè)社區(qū)的鄰居節(jié)點(diǎn)來(lái)計(jì)算重要度,并且利用連通拓?fù)鋫陕?tīng)相遇節(jié)點(diǎn),檢測(cè)相遇節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中是否存在更高重要度的節(jié)點(diǎn),若存在,則利用相遇節(jié)點(diǎn)將消息傳遞給具有更高重要度的鄰居節(jié)點(diǎn)。理論分析和仿真結(jié)果表明,ECRA與RADR及相關(guān)對(duì)比算法比較,在消息傳輸成功率、平均端到端時(shí)延等方面的性能均得到了提升。
機(jī)會(huì)社會(huì)網(wǎng)絡(luò);路由算法;社區(qū);重要度;偵聽(tīng)機(jī)制
機(jī)會(huì)網(wǎng)絡(luò)是一種特殊的移動(dòng)自組織網(wǎng)絡(luò),它能夠在網(wǎng)絡(luò)鏈路處于間歇性連接的狀態(tài)下,提供端到端的通信服務(wù)[1]。隨著移動(dòng)終端設(shè)備的高速發(fā)展,利用移動(dòng)設(shè)備進(jìn)行消息傳輸也越來(lái)越普遍,將社會(huì)關(guān)系引用到機(jī)會(huì)網(wǎng)絡(luò)當(dāng)中,能更好地優(yōu)化機(jī)會(huì)網(wǎng)絡(luò)的消息傳輸機(jī)制[2]。
目前,研究人員已提出一些有效的機(jī)會(huì)社會(huì)網(wǎng)絡(luò)路由算法:SGBR(基于社會(huì)群組的路由算法)[3]利用節(jié)點(diǎn)間相遇的頻繁程度計(jì)算出連通度值,通過(guò)設(shè)定連通度閾值劃分社區(qū),向與目的節(jié)點(diǎn)連通度值大的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息,該算法的缺點(diǎn)是無(wú)序發(fā)送消息時(shí)可能導(dǎo)致生存期剩余時(shí)間小的消息到期被刪除,降低了傳輸成功率。CHMTS(社區(qū)分層消息傳輸)算法[4]利用EO(外部?jī)?yōu)化)算法劃分社區(qū),并使用改進(jìn)的Prophet算法進(jìn)行消息傳輸,該算法的缺點(diǎn)是消息轉(zhuǎn)發(fā)時(shí)沒(méi)有考慮整個(gè)傳輸鏈路的高效性。文獻(xiàn)[5]提出了一種RADR(機(jī)會(huì)社會(huì)網(wǎng)絡(luò)消息傳輸算法),該算法使用k-Clique算法[6]進(jìn)行社區(qū)檢測(cè),在消息傳輸階段根據(jù)節(jié)點(diǎn)重要度進(jìn)行路由選擇,但是該算法存在節(jié)點(diǎn)重要度計(jì)算不準(zhǔn)確以及路由選擇單一的問(wèn)題。針對(duì)RADR出現(xiàn)的問(wèn)題,本文提出一種ECRA(基于社區(qū)的高效的機(jī)會(huì)社會(huì)網(wǎng)絡(luò)路由算法)。
1.1社區(qū)劃分
ECRA采用k-Clique算法進(jìn)行社區(qū)劃分,k-Clique算法中熟悉集Fi為節(jié)點(diǎn)vi的相遇節(jié)點(diǎn)中持續(xù)相遇時(shí)間超過(guò)閾值的節(jié)點(diǎn)集合,vj是vi熟悉集內(nèi)的節(jié)點(diǎn),不完全熟悉集為FCj,即vi得到的vj的熟悉集。Co為局部社區(qū)。當(dāng)節(jié)點(diǎn)vo與節(jié)點(diǎn)vi相遇,算法執(zhí)行步驟如下:
步驟1:節(jié)點(diǎn)初始化,Co={vo},F(xiàn)o=?,F(xiàn)Cj=?。
步驟2:當(dāng)節(jié)點(diǎn)vo與節(jié)點(diǎn)vi相遇時(shí),交換彼此局部社區(qū)Ci、熟悉集Fi和不完全熟悉集FCj的信息。步驟3:若vi不在vo的熟悉集Fo中,則vo更新與節(jié)點(diǎn)vi的持續(xù)時(shí)間,然后執(zhí)行步驟4;如果持續(xù)時(shí)間超過(guò)閾值,則將vi加入vo的熟悉集Fo和局部社區(qū)Cv中。
步驟4:若熟悉集Fi至少包括Co中的k-1個(gè)節(jié)點(diǎn),則也將節(jié)點(diǎn)vi加入到Co中。
步驟5:若vi已是Co中節(jié)點(diǎn),且vi熟悉集中的節(jié)點(diǎn)vj滿足|FCj∩Co|≥k-1,則將vj加入到Co中。
1.2問(wèn)題描述
RADR存在以下問(wèn)題:
(1)原算法考慮節(jié)點(diǎn)的重要度是為了將消息盡快轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)所在社區(qū),而在計(jì)算節(jié)點(diǎn)重要度時(shí),將節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)的社會(huì)強(qiáng)度加權(quán)計(jì)算進(jìn)去,沒(méi)有考慮鄰居節(jié)點(diǎn)中存在非消息目的節(jié)點(diǎn)所在社區(qū)的節(jié)點(diǎn),會(huì)對(duì)節(jié)點(diǎn)重要度的計(jì)算造成干擾,影響傳輸效率。
(2)原算法認(rèn)為節(jié)點(diǎn)重要度高的節(jié)點(diǎn)遇見(jiàn)目的節(jié)點(diǎn)的概率更高,并且將消息轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)社區(qū)的概率更高,沒(méi)有考慮到利用連通拓?fù)浣Y(jié)構(gòu)偵聽(tīng)機(jī)制來(lái)轉(zhuǎn)發(fā)消息,降低了傳輸成功率和消息轉(zhuǎn)發(fā)效率,并增加了傳輸時(shí)延。
本文提出的ECRA旨在解決RADR存在的兩個(gè)問(wèn)題,新算法中為節(jié)點(diǎn)重要度計(jì)算和消息轉(zhuǎn)發(fā)設(shè)計(jì)了兩種新機(jī)制,從而達(dá)到降低消息傳輸時(shí)延、提高傳輸成功率和轉(zhuǎn)發(fā)效率的目的。
2.1社會(huì)權(quán)重和重要度計(jì)算
RADR使用社會(huì)權(quán)重和重要度來(lái)衡量節(jié)點(diǎn)的社會(huì)性。
(1)社會(huì)權(quán)重的計(jì)算
在第i個(gè)時(shí)間片段ΔTi內(nèi),節(jié)點(diǎn)x與節(jié)點(diǎn)y有n次接觸,第k次接觸為CD(x,y)k,則在這個(gè)時(shí)間片段內(nèi)的接觸時(shí)間TCT(x,y)i的計(jì)算公式為
在第j天的第i個(gè)時(shí)間片段ΔTi,節(jié)點(diǎn)x與y的平均累積接觸持續(xù)時(shí)間為AD(x,y)ji,計(jì)算公式為
節(jié)點(diǎn)x與節(jié)點(diǎn)y的社會(huì)權(quán)重由下式計(jì)算得到:
式中,t為一天劃分的時(shí)間片段數(shù)。
(2)節(jié)點(diǎn)重要度的計(jì)算
節(jié)點(diǎn)的重要度與節(jié)點(diǎn)的社會(huì)權(quán)重有關(guān),其計(jì)算公式為
式中,N(x)為節(jié)點(diǎn)x的所有鄰居節(jié)點(diǎn)集合,d為隨機(jī)因子。
2.2ECRA包含的新機(jī)制
2.2.1節(jié)點(diǎn)重要度的計(jì)算更新
由2.1節(jié)可知,RADR計(jì)算節(jié)點(diǎn)的重要度時(shí),N(x)是節(jié)點(diǎn)x的所有鄰居節(jié)點(diǎn)集合,如圖1所示,圖中Ui表示節(jié)點(diǎn)所在社區(qū)。式(4)將節(jié)點(diǎn)A的所有鄰居節(jié)點(diǎn)的社會(huì)權(quán)重加權(quán)代入公式計(jì)算,這樣計(jì)算出來(lái)的結(jié)果不能準(zhǔn)確地反應(yīng)出是節(jié)點(diǎn)到目標(biāo)社區(qū)的重要度大,因?yàn)楣?jié)點(diǎn)到其他社區(qū)的加權(quán)可能會(huì)導(dǎo)致總的節(jié)點(diǎn)重要度大。因此,為了準(zhǔn)確衡量節(jié)點(diǎn)到目的節(jié)點(diǎn)社區(qū)的重要度,ECRA在運(yùn)用式(4)計(jì)算時(shí),N(x)只包含與目的節(jié)點(diǎn)同一個(gè)社區(qū)的節(jié)點(diǎn),這樣更能體現(xiàn)到達(dá)目的節(jié)點(diǎn)社區(qū)的概率,消息能更快地傳遞到目的節(jié)點(diǎn)所在社區(qū)。
圖1 節(jié)點(diǎn)重要度計(jì)算示意圖
2.2.2利用連通拓?fù)鋱D偵聽(tīng)相遇節(jié)點(diǎn)
ECRA利用連通拓?fù)涞挠欣麠l件提出了節(jié)點(diǎn)偵聽(tīng)的思路,利用中間節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)給重要度更高的節(jié)點(diǎn),可以提高傳輸可靠性和傳輸效率,降低端到端時(shí)延。圖2所示為通信重疊區(qū)域內(nèi)消息傳輸示意圖。由圖可知,消息攜帶節(jié)點(diǎn)S向其周?chē)墓?jié)點(diǎn)廣播Hello消息,確定通信范圍內(nèi)周?chē)泥従庸?jié)點(diǎn)。鄰居關(guān)系確定后,節(jié)點(diǎn)S利用MAC(媒體訪問(wèn)控制)層偵聽(tīng)它的鄰居節(jié)點(diǎn)B發(fā)出的裝載數(shù)據(jù)和控制信息的消息,判斷消息類(lèi)型并提取頭部的MAC地址。獲得幀中MAC地址后,MAC層通過(guò)跨層信息共享的方式將其送往網(wǎng)絡(luò)層;網(wǎng)絡(luò)層收到該MAC地址后做一次反向ARP(地址解析協(xié)議)處理,獲知鄰居節(jié)點(diǎn)與哪些節(jié)點(diǎn)進(jìn)行通信。如果節(jié)點(diǎn)S的網(wǎng)絡(luò)層發(fā)現(xiàn)節(jié)點(diǎn)A是B的鄰居,即使B的重要度相對(duì)更低,也將消息m發(fā)送給B,以便使消息通過(guò)B傳遞到A,利用節(jié)點(diǎn)A讓消息盡快到達(dá)與目的節(jié)點(diǎn)相遇概率更高的節(jié)點(diǎn),從而提高傳輸成功率。
圖2 通信重疊區(qū)域內(nèi)消息傳輸示意圖
2.3算法操作步驟
根據(jù)相遇節(jié)點(diǎn)與消息目的節(jié)點(diǎn)是否同屬于一個(gè)社區(qū),ECRA分為兩種傳輸方式:
(1)相遇節(jié)點(diǎn)與消息目的節(jié)點(diǎn)同屬于一個(gè)社區(qū)
步驟1:節(jié)點(diǎn)i、j在網(wǎng)絡(luò)中移動(dòng),攜帶消息m的節(jié)點(diǎn)i與節(jié)點(diǎn)j相遇,節(jié)點(diǎn)i判斷節(jié)點(diǎn)j是否是消息m的目的節(jié)點(diǎn);
步驟2:如果鄰居節(jié)點(diǎn)j是消息的目的節(jié)點(diǎn),則i直接將消息m發(fā)送給目的節(jié)點(diǎn)j,完成消息傳遞,否則進(jìn)行下一步;
步驟3:節(jié)點(diǎn)i和j相互交換雙方的存儲(chǔ)矢量表,若節(jié)點(diǎn)j中存在消息m,則雙方不做操作,繼續(xù)移動(dòng),否則轉(zhuǎn)向下一步;
步驟4:節(jié)點(diǎn)i與節(jié)點(diǎn)j交換雙方的社會(huì)信息表,如果節(jié)點(diǎn)j到消息m的目的節(jié)點(diǎn)D的社會(huì)權(quán)重大于節(jié)點(diǎn)i到節(jié)點(diǎn)D的社會(huì)權(quán)重,則節(jié)點(diǎn)i將消息m拷貝一份,傳遞給節(jié)點(diǎn)j,否則轉(zhuǎn)向下一步;
步驟5:如果節(jié)點(diǎn)j到目的節(jié)點(diǎn)D的社會(huì)權(quán)重小于節(jié)點(diǎn)i到節(jié)點(diǎn)D的社會(huì)權(quán)重,則由當(dāng)前節(jié)點(diǎn)i繼續(xù)攜帶消息在網(wǎng)絡(luò)中移動(dòng)。
(2)相遇節(jié)點(diǎn)與消息目的節(jié)點(diǎn)不屬于同一個(gè)社區(qū)
步驟1:節(jié)點(diǎn)i、j在網(wǎng)絡(luò)中移動(dòng),攜帶消息m的節(jié)點(diǎn)i與節(jié)點(diǎn)j相遇,節(jié)點(diǎn)i判斷節(jié)點(diǎn)j是否是消息m的目的節(jié)點(diǎn);
步驟2:如果鄰居節(jié)點(diǎn)j是消息的目的節(jié)點(diǎn),則i直接將消息m發(fā)送給目的節(jié)點(diǎn)j,完成消息傳遞,否則轉(zhuǎn)向下一步;
步驟3:節(jié)點(diǎn)i和j相互交換雙方的存儲(chǔ)矢量表,若節(jié)點(diǎn)j中存在消息m,則雙方不做操作,繼續(xù)移動(dòng),否則轉(zhuǎn)向下一步;
步驟4:節(jié)點(diǎn)i與節(jié)點(diǎn)j交換雙方的社會(huì)信息表,如果節(jié)點(diǎn)j到消息m的目的節(jié)點(diǎn)D的重要度大于節(jié)點(diǎn)i到節(jié)點(diǎn)D的重要度,則節(jié)點(diǎn)i將消息m拷貝一份,傳遞給節(jié)點(diǎn)j;否則轉(zhuǎn)向下一步;
步驟5:利用連通拓?fù)鋱D跨層偵聽(tīng)輔助傳輸機(jī)制,節(jié)點(diǎn)i偵聽(tīng)相遇節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)信息,判斷節(jié)點(diǎn)j的鄰居中有沒(méi)有重要度大于節(jié)點(diǎn)i的鄰居節(jié)點(diǎn),若有,則將消息m拷貝一份,轉(zhuǎn)發(fā)給節(jié)點(diǎn)j,否則轉(zhuǎn)向下一步;
步驟6:當(dāng)前節(jié)點(diǎn)i繼續(xù)攜帶消息在網(wǎng)絡(luò)中移動(dòng)。
本文使用ONE[7]作為仿真平臺(tái),仿真場(chǎng)景參數(shù)設(shè)定如表1所示。
表1 仿真場(chǎng)景參數(shù)設(shè)定
本節(jié)通過(guò)改變節(jié)點(diǎn)緩存的大小,分析比較ECRA、RADR和CHMTS算法在消息傳輸成功率、平均端到端時(shí)延、轉(zhuǎn)發(fā)效率和消息平均存儲(chǔ)時(shí)間4個(gè)方面的性能。
(1)消息傳輸成功率
圖3 節(jié)點(diǎn)緩存對(duì)消息傳輸成功率的影響
圖3所示為節(jié)點(diǎn)緩存對(duì)消息傳輸成功率的影響。由圖可知,當(dāng)節(jié)點(diǎn)緩存不斷變大時(shí),消息成功傳輸?shù)母怕示兴岣?。ECRA消息成功傳輸?shù)母怕室獌?yōu)于另外兩種算法,這是因?yàn)镋CRA利用有效連通拓?fù)鋫陕?tīng)鄰居節(jié)點(diǎn),將消息轉(zhuǎn)發(fā)給更有利于數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)的節(jié)點(diǎn),使轉(zhuǎn)發(fā)更具有效性,同時(shí)在計(jì)算節(jié)點(diǎn)重要度時(shí),只計(jì)算與目的節(jié)點(diǎn)同一個(gè)社區(qū)的鄰居節(jié)點(diǎn),使節(jié)點(diǎn)重要度的計(jì)算更準(zhǔn)確,更有利于消息的傳遞,從而有效地提高了算法的消息傳輸成功率。
(2)平均端到端時(shí)延
圖4所示為節(jié)點(diǎn)緩存對(duì)平均端到端時(shí)延的影響。由圖可知,隨著節(jié)點(diǎn)緩存不斷增加,3種算法的平均端到端時(shí)延也在變大,而ECRA的平均端到端時(shí)延要優(yōu)于其他兩種算法。這是因?yàn)镋CRA通過(guò)偵聽(tīng)判斷通信范圍重疊區(qū)域內(nèi)節(jié)點(diǎn)發(fā)送的矢量信息,獲知被偵聽(tīng)節(jié)點(diǎn)中是否存在節(jié)點(diǎn)重要度更高的鄰居節(jié)點(diǎn),若有,則將消息發(fā)送給被偵聽(tīng)的節(jié)點(diǎn),由該節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)給其節(jié)點(diǎn)重要度更高的鄰居節(jié)點(diǎn),使消息更快地到達(dá)與目的節(jié)點(diǎn)相遇概率更高的節(jié)點(diǎn),從而降低了消息傳輸所消耗的時(shí)間,相比其他兩種算法表現(xiàn)出了更低的時(shí)延特性。
圖4 節(jié)點(diǎn)緩存對(duì)平均端到端時(shí)延的影響
(3)消息轉(zhuǎn)發(fā)效率
圖5所示為節(jié)點(diǎn)緩存對(duì)消息轉(zhuǎn)發(fā)效率的影響。由圖可知,ECRA的消息轉(zhuǎn)發(fā)效率優(yōu)于其他兩種算法,這是因?yàn)镋CRA改進(jìn)了節(jié)點(diǎn)重要度的計(jì)算,避免了將消息轉(zhuǎn)發(fā)給其他不必要的節(jié)點(diǎn),降低了消息副本數(shù),使消息轉(zhuǎn)發(fā)更加有效,改善了網(wǎng)絡(luò)的擁塞情況,進(jìn)而提高了轉(zhuǎn)發(fā)效率。而其他兩種算法在限制消息副本數(shù)和減少不必要消息轉(zhuǎn)發(fā)上均存在不足,所以在消息轉(zhuǎn)發(fā)效率這個(gè)性能指標(biāo)上要低于ECRA。
圖5 節(jié)點(diǎn)緩存對(duì)消息轉(zhuǎn)發(fā)效率的影響
(4)消息平均存儲(chǔ)時(shí)間
圖6所示為節(jié)點(diǎn)緩存對(duì)消息平均存儲(chǔ)時(shí)間的影響。由圖可知,ECRA的消息平均存儲(chǔ)時(shí)間在3種算法中是最小的,這是因?yàn)镋CRA對(duì)RADR做了改進(jìn),在消息傳遞時(shí)充分利用到目的節(jié)點(diǎn)重要度較高的節(jié)點(diǎn)轉(zhuǎn)發(fā)消息,在相對(duì)短的時(shí)間內(nèi)把消息投遞給了目的節(jié)點(diǎn),縮短了消息的存儲(chǔ)時(shí)間。
圖6 節(jié)點(diǎn)緩存對(duì)消息平均存儲(chǔ)時(shí)間的影響
本文針對(duì)RADR存在的問(wèn)題,提出了一種ECRA,該算法提出連通拓?fù)鋱D節(jié)點(diǎn)偵聽(tīng)機(jī)制,并改進(jìn)節(jié)點(diǎn)重要度計(jì)算公式。仿真結(jié)果表明,ECRA較RADR及其他對(duì)比算法表現(xiàn)出了更好的消息傳輸成功率、轉(zhuǎn)發(fā)效率和更低的傳輸時(shí)延、平均存儲(chǔ)時(shí)間。
[1]熊永平,孫利民,牛建偉,等.機(jī)會(huì)網(wǎng)絡(luò)[J].軟件學(xué)報(bào),2009,20(1):124-137.
[2]Wu J,Wang Y.Opportunistic Mobile Social Networks [M].Boca Raton:CRC Press,2014:256-266.
[3]Abdelkader T,Naik K,Nayak A,et al.SGBR:A Routing Protocol for Delay Tolerant Networks Using Social Grouping[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(12):2472-2481.
[4]Wang L,Geng X.A community-driven hierarchical message transmission scheme in opportunistic networks[J].Smart Computing Review,2011,1(1):85-94.
[5]Moreira W,Mendes P,Sargento S.Opportunistic Routing Based on Daily Routines[C]//Proc of the IEEE International Symposium on Wireless,Mobile and Multimedia Networks 2012.San Francisco,US:IEEE,2012:1-6.
[6]Hui P,Yoneki E,Chan S Y,et al.Distributed Community Detection in Delay Tolerant Networks[C]// Proc of ACM/IEEE international workshop on Mobility in the evolving internet architecture 2007.New York,US:ACM Press,2007:716-722.
[7]Keranen A,Ott J,Karkkainen T.The ONE simulator for DTN protocol evaluation[C]//Proc of the International Conference on Simulation Tools and Techniques 2009.Brussels,Belgium:IEEE,2009:55-59.
An Efficient Community-based Routing Algorithm in Opportunistic Social Networks
REN Zhi,HUANG Xi-kai,TAN Yong-yin
(Chongqing Key Laboratory of Mobile Communication Technology,Chongqing University of Posts and Telecommunications,Chongqing 400065,China)
To solve the problems of high transmission delay and low forwarding efficiency in the Routing Algorithm based on Daily Routines(RADR)in opportunistic social networks,an Efficient Community-based Routing Algorithm is proposed (ECRA).The algorithm only selects the neighbor nodes which are in the same community with message destination node to calculate the node’s important degree.The algorithm uses topological connections to intercept the encounter node.If there exists node which has higher node’s importance than the encounter nodes neighbor,the message is transmitted to the encounter node neighbor nodes by the encounter node.Theoretical analysis and simulation results show that ECRA outperforms existing RADR and the correlation algorithms in terms of delivery ratio,average end-end delivery delay,relay ratio and average storage time.
opportunistic social networks;routing algorithms;communities;important degree;interceptionmechanism
TP393
A
1005-8788(2016)02-0063-04
10.13756/j.gtxyj.2016.02.020
2015-12-07
國(guó)家自然科學(xué)基金資助項(xiàng)目(61379159);重慶市自然科學(xué)基金資助項(xiàng)目(cstc2012jjaA40051)
任智(1971-),男,四川內(nèi)江人。教授,博士,主要研究方向?yàn)閷拵o(wú)線移動(dòng)通信網(wǎng)絡(luò)及網(wǎng)絡(luò)仿真技術(shù)。
黃希凱,碩士研究生。E-mail:413575446@qq.com